공제정리

수학 논리학에서, 공제 정리는 이것에 대한 명시적인 추론 규칙이 없는 시스템에서 조건부 증빙(의미 A → B)을 행하는 것을 정당화하는 메타토렘이다.추론 이론은 명제 논리학과 1차 논리 둘 다에 존재한다.^[1]추론 정리는 힐버트식 추론 시스템에서 중요한 도구로, 왜냐하면 그것은 그것이 없으면 가능했던 것보다 더 이해할 수 있고 보통 훨씬 더 짧은 증서를 쓸 수 있게 해주기 때문이다.어떤 다른 공식적인 증명 시스템에서는 명시적인 추론 규칙에 의해 동일한 편견이 제공된다. 예를 들어 자연 추론에서는 이를 암시적 도입이라고 부른다.

In more detail, the propositional logic deduction theorem states that if a formula ${\displaystyle B}$ is deducible from a set of assumptions ${\displaystyle \Delta \cup \{A\}}$ then the implication ${\displaystyle A\to B}$ is deducible from ${\displaystyle \Delta }$; in symbols, ${\dis$$playstyle \Delta \cup \{A\}\vdash B}$ implies ${\displaystyle \Delta \vdash A\to B}$. In the special case where ${\displaystyle \Delta }$ is the empty set, the deduction theorem claim can be more compactly written as: ${\displaystyle A\vdash B}$ implies ${\displaystyle \vdash A\to B}$.술어 논리에 대한 공제 정리는 비슷하지만, 몇 가지 추가적인 제약조건이 따른다($예{\displaystyle }$:$$A {\$displaystyle$ A$}$이(가) 폐쇄 공식일 경우 충족된다).일반적으로 공제 정리는 고려 중인 이론의 모든 논리적 세부사항을 고려할 필요가 있으므로, 비록 차이는 보통 미미하지만 각 논리 체계는 기술적으로 독자적인 공제 정리가 필요하다.

공제 정리는 1차 논리학의 일반적인^[2] 연역 체계를 가진 모든 1차 이론에 대해 보유한다.^[3]다만, 공제 정리가 실패하는 새로운 추론 규칙이 추가되는 1순위 제도가 있다.^[4]가장 주목할 만한 것은 힐버트 공간의 선형 하위공간이 비분산 격자를 형성하기 때문에, 비르코프-본 노이만 양자논리에서 공제 정리가 유지되지 않는다.

공제 예시

1. "프로브" 공리 1:

   • P 1. 가설
   • Q 2. 가설
     • P 3. 1의 반복
   • Q→P 4. 2-3에서 공제

   P→(Q→P) 5. 1 - 4 QED에서 공제

2. "프로브" 공리 2:

   • P→(Q→R) 1. 가설
     • P→Q 2. 가설
       • P 3. 가설
       • Q 4. 모드 폰 3,2
       • Q→R 5. 모드 폰 3,1
       • R 6. 모더스 폰 4,5
     • P→R 7. 3에서 6까지의 공제
   • (P→Q)→(P→R) 8. 2부터 7까지 공제

   (P→(Q→R)→(P→Q)→(P→R) 9. 1 - 8 QED에서 공제

3. 공리 1을 사용하여 ((P→(Q→P)→R)→R:

   • (P→(Q→P)→R 1. 가설
   • P→(Q→P) 2. 공리 1.
   • R 3. 모드스 폰스 2,1

   ((P→(Q→P)→R)→R 4. 1~3QED에서 공제

가상 추론 규칙

예를 들어, 당신은 우리가 우리의 일반적인 자명 논리에 가상(또는 추가적이고 임시적인) 추론 규칙을 세 가지 추가했다는 것을 알 수 있다.이것들은 "가설", "반복", "편법"이다.일반적인 추론 규칙(즉, "모듀스 폰"과 다양한 공리)은 여전히 이용할 수 있다.

1. 가설은 이미 이용할 수 있는 것에 추가 전제를 추가하는 단계다.따라서 이전 단계 S가 다음과 같이 추론된 경우:

${\displaystyle E_{1},E_{2},...,E_{n-1},E_{n}\vdash S,}$

그런 다음 다른 전제 H를 추가하고 다음을 얻는다.

${\displaystyle E_{1},E_{2},...,E_{n-1},E_{n},H\vdash H.}$

이것은 n번째의 들여쓰기 단계에서 n+1번째 단계로 넘어가고 말하는 것으로 상징된다.

• S 이전 단계
  • H 가설

2. 반복은 이전 단계를 다시 사용하는 단계다.실제로 이것은 가장 최근의 가설이 아닌 가설을 취하여 공제 단계 이전의 마지막 단계로 사용하고자 할 때만 필요하다.

3. 추리는 가장 최근의 가설(여전히 이용할 수 있음)을 제거하고 이전 단계에 접두사를 붙이는 단계다.이는 다음과 같이 한 수준을 표시 해제함으로써 나타난다.

• H 가설
• ......... (다른 단계)
• C(H에서 추출한 컨버전스)

• H→C공제

공제 메타이론을 이용한 증명에서 자명증명으로의 전환

명제 논리의 자명적 버전에서는 보통 공리 스키마(P, Q, R이 어떤 명제로 대체되는 경우) 중에서 하나를 가진다.

• Axiom 1은: P→(Q→P)
• Axiom 2는 (P→(Q→R)→(P→Q)→(P→R)이다.
• Modus ponens는: P와 P→Q에서 추론 Q.

이러한 공리 설계는 이들로부터 쉽게 공제 정리를 도출할 수 있도록 선택된다.그래서 우리가 그 질문을 구걸하는 것처럼 보일 수도 있다.그러나 진리표를 사용하여 tautography인지, 모듀스 폰이 진리를 보존하는지 확인함으로써 정당화될 수 있다.

이러한 공리 스키마로부터 아래에 사용되는 정리 스키마 P→P(의연성)를 재빨리 추론할 수 있다.

1. (P→(Q→P)→(P)→(P→Q→P)→(P→P)로 공리 스키마 2에서 P, (Q→P), P로 한다.
2. P가 있는 공리 스키마 1의 P→(Q→P)→P, (Q→P)
3. (P→(Q→P)→(P→P)→(P→P) 2단계와 1단계에 적용되는 모드 폰의 경우
4. P, Q와 함께 공리 스키마 1의 P→(Q→P)
5. 4단계와 3단계에 적용된 모드 폰의 P→P

우리가 γ과 H가 C를 증명한다고 가정하고, γ이 H→C를 증명한다고 가정하자.γ(반복 단계) 또는 공리의 전제인 추론에서 각 단계 S에 대해, 우리는 공리 1, S→(H→S)에 모드 폰(modus ponens)을 적용하여 H→S를 얻을 수 있다.단계가 H 그 자체(가설 단계)라면 정리 스키마를 적용하여 H→H를 얻는다.If the step is the result of applying modus ponens to A and A→S, we first make sure that these have been converted to H→A and H→(A→S) and then we take the axiom 2, (H→(A→S))→((H→A)→(H→S)), and apply modus ponens to get (H→A)→(H→S) and then again to get H→S.증거의 마지막에 우리는 필요에 따라 H→C를 가질 것이다. 단, 지금은 H가 아닌 γ에만 의존한다. 따라서 공제 단계는 사라지고, H에서 도출된 결론인 이전 단계로 통합된다.

결과 입증의 복잡성을 최소화하려면 변환 전에 일부 사전 처리를 수행해야 한다.실제로 H에 의존하지 않는 모든 단계(결론 제외)는 가설 단계 전에 위로 이동하여 한 수준을 나타내지 않아야 한다.그리고 결론이 아닌 반복과 같은 불필요한 단계(결론을 얻기 위해 사용되지 않거나 우회할 수 있는)는 제거되어야 한다.

전환 중에는 공제 개시(H→H 단계 직후)에 모듀스 폰의 모든 적용을 공리 1에 넣는 것이 유용할 수 있다.

모듀스를 변환할 때 A가 H의 범위를 벗어나면 공리 1, A→(H→A), 모듀스 폰 등을 적용해야 H→A를 얻을 수 있다.마찬가지로 A→S가 H의 범위를 벗어나면 공리 1, (A→S)→(H→(A→S)→(A→S)를 적용하여 H→(A→S)를 얻도록 한다.모드 폰스 단계가 결론인 경우가 아니라면, 두 모드 폰이 모두 범위 밖에 있다면 모드 폰은 H보다 위로 이동되어야 하므로 이 두 가지를 모두 수행할 필요가 없어야 한다.

Curry-Howard 통신에 따르면, 위의 공제 메타 테오렘 변환 과정은 람다 미적분학 용어에서 결합 논리 용어로 변환하는 과정과 유사하며, 여기서 공리 1은 K 결합기에 해당하고, 공리 2는 S 결합기에 해당한다.I 콤비네이터는 정리 스키마 P→P에 해당한다.

도움이 되는 정리

만약 어떤 사람이 공제 정리를 사용하는 복잡한 증거를 공제 정리를 사용하지 않는 직선적인 증거로 바꾸려고 한다면, 아마도 이러한 정리들을 처음부터 한 번 그리고 모두 입증한 다음 변환을 돕기 위해 그것들을 사용하는 것이 유용할 것이다.

$A\to A}$

가설 단계의 변환을 돕는다.

$[\displaystyle (B\to C)\to (A\to B)\to (A\to C)}}$

주요 전제가 가설에 의존하지 않을 때, 공리 1의 사용을 피하면서 공리 2를 대체하는 모듀스 폰의 변환을 돕는다.

$(A\to(B\to C)\to(A\to C))\to(A\to C)}$

작은 전제가 가설에 의존하지 않을 때 모듀스 폰의 변환을 돕고, 공리 1의 사용을 피하면서 공리 2를 대체한다.

이 두 가지 이론은 공리 2 대신 공동으로 사용할 수 있지만, 변환된 증명이 더 복잡할 것이다.

$(A\displaystyle (A\to B)\to (B\to C)\to (A\to C)}}$

$(A\to(A\to C)\to(A\to C)\to(A\to C)}$

페어스의 법칙은 공제 정리의 결과가 아니라, 공제 정리와 함께 사용하면 그렇지 않으면 증명할 수 없는 것들을 증명할 수 있다.

$[\displaystyle ((A\to B)\to A)\to A}$

그것은 또한 공리 2 대신에 사용할 수 있는 두 가지 이론들 중 두 번째 이론들을 얻는 데 사용될 수 있다.

공제정리증빙

우리는 명제 미적분학의 힐버트식 연역 체계에서 공제 정리를 증명한다.^[5]

Let ${\displaystyle \Delta }$ be a set of formulas and ${\displaystyle A}$ and ${\displaystyle B}$ formulas, such that ${\displaystyle \Delta \cup \{A\}\vdash B}$. We want to prove that ${\displaystyle \Delta \vdash A\to B}$.

Since ${\displaystyle \Delta \cup \{A\}\vdash B}$, there is a proof of ${\displaystyle B}$ from ${\displaystyle \Delta \cup \{A\}}$. We prove the theorem by induction on the proof length n; thus the induction hypothesis is that for any ${\displaystyle \Delta }$, ${\displaystyle A}$ and $$${\displaystyle B}$ ${\$$displaystyle$ $B}$의${\displaystyle }$Δ such$${$A{\displaystyle \mathrm{}\}}$ ${\displaystyle \Delta \cup \{A\}}$까지의 $길이$가 ${\displaystyle \Delta }$a${\displaystyle }$A → ${\displaystyle B}${\$dash A\to B}$인 증거가 있는 경우.

If n = 1 then ${\displaystyle B}$ is member of the set of formulas ${\displaystyle \Delta \cup \{A\}}$. Thus either ${\displaystyle B=A}$, in which case ${\displaystyle A\to B}$ is simply ${\displaystyle A\to A}$ which is derivable by substitution from p → p that is derivable from the axioms, hence also ${\displaystyle \Delta \vdash A\to B}$; or ${\displaystyle B}$ is in ${\displaystyle \Delta }$, in which case ${\displaystyle \Delta \vdash B}$; it follows from axiom p → (q → p) with substitution that ${\displaystyle \Delta \vdash B\to (A\to B)}$ and hence by modus$\Delta {\displaystyle \mathrm{}}$ ${\displaystyle ⊢}$ ${\displaystyle A}$→ ${\displaystyle B}$ ${\displaystyle \Delta \vdash A\to$ B$}$을(를) 고려하십시오$.$

이제 길이 n까지의 증거에 대한 유도 가설을 가정하고, $길이{\displaystyle }$ n+1의 증거와$$ 함께 B {\displaystyle $B}$을(를) $\Delta {\displaystyle \mathrm{}}$ ${\displaystyle \cup \{A\}}$ ${\displaystyle \Delta \cup \{A\}$로부터 증명할 수 있는 공식으로 합시다$$$.$그 다음 세 가지 가능성이 있다.

1. ${\displaystyle B}$ ${\displaystyle B}$은(는) $\Delta {\displaystyle \mathrm{}}$ ${\displaystyle \cup \{A\}}$ ${\displaystyle \Delta \cup \{A\}}$ 공식 집합의 멤버로$,$ 이 경우 n=0으로 진행한다.
2. ${\displaystyle B}$ ${\displaystyle B}$은(는) 공식 φ을 대체하여 도착했다.그러면 Δ $\Delta {\displaystyle \mathrm{}}$ ${\displaystyle \{\{A\}}$ ${\displaystyle \delta \cup \{A\}}$에서 φ은 최대 n개의 스텝으로$$ 증명되며, 따라서 유도 가설 $\Delta {\displaystyle \mathrm{}}$ ${\displaystyle \Delta \to }$ ${\displaystyle A}$ → $\$ {\$displaystyle \dash A\to \varphi$에 따라 A와 φ을 서로 다른 변수로 쓸 수 있다.$그러나{\displaystyle }$ 그 다음 우리는 ${\displaystyle \to }$에서 B$$ ${\displaystyle B}$을(를) 도출하는 데 사용되는 동일한 대체품을$$ $통해{\displaystyle }$ A → φ →${\displaystyle B}$ →$$$\varphi$$$$}$에 도착할 수 있다. 따라서 $\Delta {\displaystyle \mathrm{}}$ ${\displaystyle ⊢}$ ⊢ ${\displaystyle A}$→ B → B ${\displaysty \dash A\to B$
3. $[\displaystyle B}$는 모드스 포넨을 사용하여 도착한다$$.그 다음에는 $\Delta {\displaystyle \mathrm{}}$ ${\displaystyle \cup \{A\}}$ ${\displaystyle \Delta \cup \{A\}}}$이(가) $C{\displaystyle }${\$displaystyle$ C$}$와 C$$${\displaystyle }$→$$B {\$displaysty$ C\$to B}$을(가) 증명하는 공식 C가 있으며$,$ 이후 모드스폰이 $B{\displaystyle }$ ${\displaysty B}$에 사용된다$.$The proofs of ${\displaystyle C}$ and ${\displaystyle C\to B}$ are with at most n steps, and by the induction hypothesis we have ${\displaystyle \Delta \vdash A\to C}$ and ${\displaystyle \Delta \vdash A\to (C\to B)}$. By the axiom (p → (q → r)) → ((p → q) → (p → r)) with substitution itfollows that ${\displaystyle \Delta \vdash (A\to (C\to B))\to ((A\to C)\to (A\to B))}$, and by using modus ponens twice we have ${\displaystyle \Delta \vdash A\to B}$.

따라서 모든 경우에 정리도 n+1에 대해 유지되며, 유도에 의해 공제 정리가 증명된다.

술어 논리에서의 공제 정리

공제 정리는 다음과 같은 형태로 1차 논리에서도 유효하다.

• T가 이론이고 F, G가 F가 닫힌 공식이라면, 그리고 T${\displaystyle }$closed {F }${\displaystyle \mathrm{and}}$ G ${\displaystyle T\cup \{F\}\vdash G$ $T{\displaystyle }$ ${\displaystyle ⊢}$ ${\displaystyle F}$→ ${\displaystyle G}$ ${\displaystyle T\vdash F\rigrow G$

여기서 기호 $⊢{\displaystyle }$ ${\displaystyle \vdash }$은 "의 구문학적 결과"를 의미한다$$.우리는 명제 미적분학에서 이 공제 정리의 증명과 공제 정리의 증명과 어떻게 다른지 아래에 표시한다.

형식적 증명의 개념의 가장 일반적인 버전에는 명제 미적분학의 공리 체계(또는 명제 미적분의 모든 tautology를 그들 자신의 권리로 공리 체계로 삼아야 한다는 이해), 정량화 공리, 그리고 모듀스 폰 외에 다음과 같이 알려진 추론의 하나의 추가 규칙이 있다.일반화 규칙 : "K로부터, ∀vK를 유추한다."

G의 증명서를 T{{F}에서 F→G의 하나로 변환하기 위해서는 명제논리의 증명과 같은 방법으로 공리 또는 모듀스 폰의 적용에서 비롯되는 G의 증명 단계를 다룬다.일반화 규칙의 적용에 따른 단계는 다음과 같은 계량자 공리를 통해 처리된다(변수 v가 공식 H에서 자유롭지 않을 때마다 유효).

• (∀v(H→K)→(H→∀vK).

우리의 경우는 F가 닫힌 것으로 추정되기 때문에 H를 F로 가져갈 수 있다.이 공리는 F→K와 일반화에서 F→ fromvK를 추론할 수 있게 하는데, G의 증명에서 일반화의 규칙이 일부 K에 적용될 때마다 필요한 것이다.

In first-order logic, the restriction of that F be a closed formula can be relaxed given that the free variables in F has not been varied in the deduction of G from ${\displaystyle T\cup \{F\}}$. In the case that a free variable v in F has been varied in the deduction, we write ${\displaystyle T\cup \{F\}\vd$$^{v}G}($v가 변화했음을 나타내는 개찰구의 위첨자)이며, 해당 공제 정리의 형태는 $T{\displaystyle }$ ${\displaystyle ⊢}$ (${\displaystyle \mathrm{\forall }}$ ${\displaystyle v}$ ${\displaystyle F}$)${\displaystyle }$→ ${\displaystyle G}$ ${\displaystyle T\vdash (\forall vF)\rightarrow G}$이다$.$^[6]

변환 예제

자연 공제를 어떻게 하면 자명한 형태의 증명으로 전환할 수 있는지를 설명하기 위해 tautology Q→(Q→R)→R)에 적용한다.실제로, 우리가 이것을 할 수 있다는 것을 아는 것은 보통 충분하다.우리는 보통 훨씬 더 긴 자명한 증거 대신에 자연적인 유혹의 형태를 사용한다.

첫째로, 우리는 다음과 같은 자연적인 주입법을 사용하여 증명서를 작성한다.

• Q 1. 가설
  • Q→R 2. 가설
  • R 3. 모드스 폰 1,2
• (Q→R)→R 4. 2에서 3까지의 공제

• Q→(Q→R)→R) 5. 1에서 4 QED까지의 공제

둘째, 우리는 내부 추리를 자명적인 증거로 전환한다.

• (Q→R)→(Q→R) 1. 정리 스키마(A→A)
• ((Q→R)→(Q→R)→((Q→R)→Q)→(Q→R)→(Q→R) 2. 공리법 2.
• ((Q→R)→Q→(Q→R)→R) 3.모드 폰 1,2
• Q→(Q→R)→Q) 4.xiom 1.
  • Q 5. 가설
  • (Q→R)→Q 6. 모더스는 5,4
  • (Q→R)→R 7. 모듀스 폰 6,3
• Q→(Q→R)→R) 8. QED 5 ~ 7 QED에서 공제

셋째, 외부 공제를 다음과 같은 자명한 증명으로 변환한다.

• (Q→R)→(Q→R) 1. 정리 스키마(A→A)
• ((Q→R)→(Q→R)→((Q→R)→Q)→(Q→R)→(Q→R) 2. 공리법 2.
• ((Q→R)→Q→(Q→R)→R) 3.모드 폰 1,2
• Q→(Q→R)→Q) 4.xiom 1.
• [(Q→R)→Q→(Q→R)→R)]→[Q→(Q→R)→Q→(Q→R)] 5.xiom 1.
• Q→(((Q→R)→Q→(Q→R)→R) 6.모더스는 3,5
• [Q→(Q→R)→Q→(Q→R)→R)]→(Q→(Q→R)→Q]→[Q→(Q→R)→R)] 7.xiom 2.
• [Q→(Q→R)→Q]→[Q→(Q→R)→R)]8. modus ponnes 6,7
• Q→(Q→R)→R) 9.모드 폰 4.8 QED

이 세 단계는 Curry-Howard 서신을 사용하여 간결하게 진술할 수 있다.

• 첫째, 람다 미적분학에서 함수 f = λa. λb. b a는 타입 q → (q → r) → r을 갖는다.
• 둘째, b에서 람다 제거에 의해, f = λa. s i (k a)
• 셋째, a, f = s (k (s i) k에서 람다 제거에 의해

참고 항목

• 컷 엘리미네이션 정리
• 조건부 증명
• 커링
• 명제 미적분학
• 페어스의 법칙

메모들

참조

• Carl Hewitt (2008), "ORGs for Scalable, Robust, Privacy-Friendly Client Cloud Computing", IEEE Internet Computing, 12 (5): 96–99, doi:10.1109/MIC.2008.107. 2008년 9월/10월
• Kohlenbach, Ulrich (2008), Applied proof theory: proof interpretations and their use in mathematics, Springer Monographs in Mathematics, Berlin, New York: Springer-Verlag, ISBN 978-3-540-77532-4, MR 2445721
• Kleene, Stephen Cole (2002) [1967], Mathematical logic, New York: Dover Publications, ISBN 978-0-486-42533-7, MR 1950307
• Rautenberg, Wolfgang (2010), A Concise Introduction to Mathematical Logic (3rd ed.), New York: Springer Science+Business Media, doi:10.1007/978-1-4419-1221-3, ISBN 978-1-4419-1220-6.
• Shoenfield, Joseph R. (2001) [1967], Mathematical Logic (2nd ed.), A K Peters, ISBN 978-1-56881-135-2

외부 링크

• 빌니스 데트로브스와 칼리스 포딕스 포디넥스의 수학 논리 소개는 종합적인 자습서다.섹션 1.5를 참조하십시오.
• "복제 정리"