명제 논리
1. 개요
2. 명제 논리에서의 해석
3. 명제논리 연결사
3.1. 부정 (NOT; ¬, ~, -)
3.2. 선언 (OR; ∨)
3.2.1. 배타적 선언 (XOR; ⊕)
3.3. 연언 (AND; ∧, &)
3.4.1. 자연 언어 조건문과의 괴리
3.5. 쌍조건문(If and Only If; ↔, iff)
4. 추론과 명제논리 추론 규칙
4.1. 전건 긍정(Modus Ponens; →E)
4.2. 후건 부정(Modus Tollense)
4.3. 조건 도입(Conditional Proof; →I)
4.5. 선언 도입(∨I)
4.6. 연언 제거(∧E)
4.7. 연언 도입(∧I)
4.10. 폭발 원리(law of explosion; ⊥E)
5. 추론 전략
7. 관련 문서
1. 개요
'''명제논리(propositional logic)''' 혹은 '''문장논리(sentential logic)'''는 명제 혹은 문장들 간의 논리적 관계를 다룬다. 즉 예를 들어 <소크라테스는 사람이다>라는 명제를 기호화한다면, 이를 그냥 통째로 "P"로 표시할 뿐 더이상 쪼개 들어가질 않는다. 이런 명제들은 알파벳 대문자 (e.g. P, Q, R ...)로 기호화하는 것이 관례다. 명제 논리는 양화 논리의 특수한 경우로 생각할 수 있다.
$$ $$
명제논리는 결정가능(decidable)하다. 즉 임의의 명제 논리식이 타당한지 (혹은 두 명제 논리식 간에 논리적 도출 관계가 성립하는지) 여부는 기계적으로 판단할 수 있다. 아래에서 설명될 '''진리표(truth-table)'''를 사용하는 것이 그런 기계적 판단 방식의 대표적인 예시다. 논리식의 타당성을 기계적으로 판단할 수 있다는 것은, 명제 논리 체계에서는 동어반복적 문장이 곧 타당한 문장이며, 타당한 문장이 곧 동어반복적 문장이라는 것이다.
2. 명제 논리에서의 해석
명제 논리에서의 '''해석(interpretation)'''은 각 명제에 진리값을 할당하는 것이다. 예를 들어 (P & Q & R)이라는 문장이 있다고 생각해보자. 여기서 각 명제에 T를 할당하는 것은 한 가지 해석이다. 각각의 명제는 T이거나 F일 수 있으므로, n개의 명제가 있는 문장은 2^n개의 해석이 가능하다. 즉 이상의 예에서는 다음과 같은 여덟 가지의 해석이 가능하다는 것이다.
{T, T, T}
{T, T, F}
{T, F, T}
{T, F, F}
{F, T, T}
{F, T, F}
{F, F, T}
{F, F, F}
이러한 해석의 정의에 따라 명제 논리에서의 타당성, 귀결, 일관성이 다음과 같이 정의될 수 있다.
- 문장 ϕ가 모든 해석 하에서 참일 경우 문장 ϕ는 타당하다.
- 문장 ϕ와 문장집합 Γ에 대해, Γ의 모든 문장들을 참이게 하면서 ϕ를 거짓이게 하는 해석이 존재하지 않을 경우 ϕ는 Γ의 귀결이다.
- 문장집합 Γ에 대해, Γ의 모든 문장들을 참이게 하는 해석이 하나라도 존재할 경우 Γ는 일관적이다.
3. 명제논리 연결사
명제 논리에서 '''연결사(connective)'''는 한 개 이상의 명제 기호에 덧붙여짐으로써 해당 명제(들)에 새로운 의미를 더한다. 꼭 복수의 명제들을 '연결'할 필요없이 하나의 명제에만 붙는 연결사도 있음을 유의하라(예. ~).
연결사를 포함하지 않은 명제를 단순 명제라고 하며, 단순 명제와 하나 이상의 논리 연결사로 구성되는 명제를 복합 명제라고 한다[7]. 복잡한 구조를 가진 복합 명제들에서는 두 개 이상의 논리 연결사와 괄호들이 사용되기도 하는데, 이때 주요 부분을 연결해 주는 논리 연결사를 ‘주 논리 연결사’라고 한다.
아래에 언급된 명제 연결사들은 일반적으로 명제 논리에서 등장하는 연결사들이다.
이들의 의미는 '''진리표'''를 통해 엄밀하게 규정될 수 있다. 진리표는 피연산자의 진리치(참='''T''', 거짓='''F''')에 따라 연결사가 덧붙여진 새로운 명제의 진리치가 어떤 것이 되는지를 표시해준다.
예를 들어 임의의 2항 연결사인 ⊙가 어떻게 진리표를 통해 정의되는지 알아보기 위해 다음 예시를 참고하라:
해당 진리표는 ⊙의 진리표를 도식화시킨 것이다. 앞의 두 열은 피연산자인 명제 P와 Q가 갖는 진리치의 모든 가능한 배열을 망라한 것이다. 이때 가능한 배열의 경우의 수는 4이므로, 곧 행의 수가 넷이다. 마지막 세 번째 열은 이런 4가지 경우의 수 각각마다 ⊙가 붙었을 때의 연산 결과를 나타내며, 그 결과인 변수 α, β, γ, δ의 값 또한 각각 T 혹은 F다. 즉 이때 α, β, γ, δ이 어떤 값을 갖느냐에 따라 연결사 ⊙의 성격이 정의된다.
더불어 아래 명제 연결사만이 명제 논리의 확고부동한 연결사라고 생각할 필요는 없다. 예를 들어 $$\vee, \wedge$$가 $$\neg, \to$$에 의해 정의될 수 있음은 명백하며, 극단적으로는 하나의 연결사만으로도 모든 명제 논리를 포괄하는 것도 가능하다(예. Sheffer Stroke '|').
이하의 연결사 설명은 원칙적으로 메타 문장인 그리스어 문자로 기술되어야 하지만, 편의상 영문 알파벳 대문자로 기술한다.
3.1. 부정 (NOT; ¬, ~, -)
Negation ($$\sim$$ 혹은 $$\neg$$ 혹은 -)
한국어에선 "-가 아니다"에 대응한다. P가 참이면 ~P는 거짓, P가 거짓이면 ~P는 참이다.
예를 들어 "망치를 가져와라" 라고 했을 때, 망치가 아닌 무엇인가를 가지고 가는 경우에 해당한다.3.2. 선언 (OR; ∨)
選言 Disjunction 논리합 ($$\vee$$) [9]
P∨Q라고 하면 P, Q 중 적어도 하나는 성립한다는 것을 뜻한다. 둘 중 하나만 성립하는 것이 아니며, P와 Q 둘 모두 성립해도 된다. 이때 P와 Q를 "선언지(disjunct)"라고 부르기도 한다.
예를 들어 "망치 또는 빠루를 가져와라"라고 했을 때, 망치를 가져 와도 참이고, 빠루를 가져 와도 참이며, 망치와 빠루를 들고 와도 참이다.진리표는 다음과 같다.
"∨"는 한국어의 "혹은", 영어의 "or"에 대응하는 것 같지만, 일상 언어 표현들의 경우 두 선언지 가운데 하나를 선택해야만 하는 것 같은 직관이 있다. 예를 들어 "망치를 사용하시겠습니까, 혹은 빠루를 사용하시겠습니까?"라고 물어봤을 땐 망치와 빠루 중 하나만을 선택해야할 것 같다. 하지만 위에서 나타나다시피 "∨"를 쓴 문장인 "(망치를 쓴다) ∨ (빠루를 쓴다)"는 망치만 휘둘러도, 빠루를 휘둘러도, 망치와 빠루를 둘 다 사용해도 된다.
이러한 직관이 나타나는 이유는 우리말에서는 흔히 "그리고"와 "또는"을 다른 의미로 구분하기 때문이다.[10] 일상적으로 우리는 "또는"을 "그리고"와 다른 의미로 구별하기 때문에(즉, '또는'을 배타적 선언으로 인식하기 때문에) 망치 또는 빠루를 가져오라는 말을 들었을 때 "망치 그리고 빠루를 가져간다"는 선택지를 배제하게 되고, 마찬가지로 이를 요청한 쪽에서도 둘 다 시행하는 경우는 생각하지 않는다. 그렇지만 논리기술적으로는 P와 Q 둘 중의 하나 혹은(∨) P와 Q 둘 모두를 포함하는 기호를 만들어두는 것이 편리하기 때문에 해당 선택지도 포함하게 되므로 헷갈리지 말도록 하자.
영어에서는 양쪽 다 선택하는 or both와 같은 표현을 뒤에 붙이기도 한다.
3.2.1. 배타적 선언 (XOR; ⊕)
Exclusive OR 배타 논리합 ($$\oplus$$')
'둘 중 하나'만을 지시하는 선언문. 즉 "P⊕Q"가 참이면 P와 Q 둘 중 하나만 참이다. 이는 ∧와 ∨ 기호를 통해 정의될 수 있다. 즉 "P⊕Q"는 "(P∨Q)∧~(P∧Q)"와 동치다.
"망치와 빠루 중 하나를 가지고 와라" 라는 문장이 주어졌을 때, 망치나 빠루 둘 다 가지고 오지 않거나, 둘 다 들고 오면 참이 아니다.
P와 Q 모두 참일 때는 거짓임을 볼 수 있다. 또한 P∨Q는 ~(~P∧~Q)와 동치이므로, 선언문은 ∧와 ~만을 이용해 나타낼 수도 있다.수학II 에서 집합단원의 대칭차집합과 대응된다고 볼 수 있다.
3.3. 연언 (AND; ∧, &)
連言 Conjunction 논리곱 ($$\wedge$$ 혹은 $$\&$$) [11]
P ∧ Q는 P, Q 모두 참일 때에만 참이다. 이때 P와 Q를 "연언지(conjunct)"라고 부른다. 한국어에선 "-와/과 -", "-이고 -다", "-이며 -다" 등에 대응한다. 예를 들어 "망치와 빠루를 가져와라"라고 했을 때, 망치와 빠루 모두 들고 와야 참이 되는 것과 같다. ~와 ∨를 이용해 나타내면
~(~P∨~Q)이다.
~(~P∨~Q)이다.
3.4. 조건문(If ... Then ...; →, ⊃, Ɔ[12])
'''실질 조건문(material conditional)''' ($$\to$$, $$\supset$$, $$\text{Ɔ}$$)
P → Q는 P가 거짓이거나 Q가 참인 경우 오직 그 경우에 참이다. 즉 P가 참이고 Q가 거짓인 경우를 제외하면 모두 참이다. 이때 P를 "전건(antecedent)", Q를 "후건(consequent)"이라고 부른다.
동치 문서에도 나와 있듯이, 실질 조건 문장은 정의상 선언 문장과 논리적 동치다.
$$ \left( p \rightarrow q \right) \equiv \left( \neg p \vee q \right) $$
3.4.1. 자연 언어 조건문과의 괴리
조건문은 영어의 '''"If -면, ...다"''' 같은 표현에 대응한다. 하지만 실질 조건문은 이런 자연 언어의 쓰임새를 포착하는데 실패하고는 한다. 다음이 그 대표적인 예시다.
실질 조건문으로 분석할 경우 해당 문장은 참이다. 태양계 행성은 5개가 아니기 때문이다. 하지만 한국어 모국어 화자들은 대개 그러한 결과를 부조리하게 여긴다.'''"만약 태양계 행성이 5개라면, 라멘의 원조는 일본이 아니다."'''
관련된 쟁점에 대해서는 조건문 항목 참조.
3.5. 쌍조건문(If and Only If; ↔, iff)
'''쌍조건문(biconditional)'''
P ↔ Q는 '오직 P인 경우에만 Q이다'라는 의미이다. 'P와 Q가 동치이다', 'P이면 Q이고 Q이면 P이다'와 같이 표현하기도 한다. (P → Q) & (Q → P)와 동치이다. P와 Q의 진리값이 같을 때 T가 할당된다.
예를 들어서, '누군가 총각인 경우에 오직 그 경우에만 결혼하지 않은 남자다'라는 문장은 쌍조건문이다.3.6. 모순(Contradiction; ⊥, c)[13]
'Falsum' 혹은 'Bottom'이라고도 부른다. 무조건 거짓. 무조건 참은 "Top"이라고도 부르며 $$\top$$를 쓴다. 참은 True의 T or t모양을 따왔고, 거짓은 이 모양을 뒤집은 것이다. 표준적인 명제논리에서는 연결사가 아니다.
4. 추론과 명제논리 추론 규칙
귀결이 문장과 문장 사이의 의미론적 관계를 다룬다면, '''추론(inference)''' 혹은 '''도출(deriviation)'''은 오직 형식적인 관계만을 다루는 것이다. 다른 표현으로 하자면 귀결은 의미론적(semantic) 작업이고 추론은 통사론적(syntactic) 작업이다. 추론은 귀결과는 달리 문장의 진리값이나 해석에 의존하지 않는다. 오직 형식적인 규칙만을 따라 수행하는 작업일 뿐이다. 그리고 그러한 형식적 추론이 의미론적인 귀결 관계를 보장한다는 것은 건전성 정리에 의해 증명되어 있다.
공집합으로부터 추론가능한 문장을 논리학적 정리라고 하며, 논리학적 정리인 문장은 논리적으로 타당하다. 즉, 모든 해석 하에서 참이다.
이하 내용은 명제 논리의 추론/증명 체계 중 하나인 게르하르트 겐첸(Gerhard Gentzen)[14]의 '''자연 연역(Natural Deduction)''' 방식을 소개한 것이다. 자연연역과 동등하게 강력한 추론/증명 체계로 역시 겐첸이 고안한 귀결 연산(sequent calculus)이 있고, 이와 살짝 다른 방식으로는 힐베르트 체계(Hilbert system)가 있다.
아래 규칙에서 E는 제거(elemination), I는 도입(Introduction)을 뜻한다. $$P\Rightarrow Q$$는 명제 $$Q$$가 가정 $$P$$에 의존한다는 것을 뜻하는 반면, $$P_{1},\,P_{2}\vdash Q$$[15]는 $$P_{1}$$, $$P_{2}$$로부터 $$Q$$를 추론해낼 수 있다는 규칙을 나타낸다[16].
이하의 추론 규칙들은 원칙적으로 메타 문장인 그리스 문자로 기술해야 하지만, 편의상 영문 대문자로 대체한다.
4.1. 전건 긍정(Modus Ponens; →E)
- →E[17]: $$P,P\to Q\vdash Q$$
4.2. 후건 부정(Modus Tollense)
$$\neg Q,P\to Q\vdash \neg P$$
4.3. 조건 도입(Conditional Proof; →I)
- →I[18]: $$P\Rightarrow Q\vdash P\to Q$$
유사 사례: 어떤 문장이 앞서서 나타난다면, 그 문장을 후건으로 갖는 조건문을 쓸 수 있다. 이것은 1차 술어논리의 추론 규칙으로 활용된다.
4.4. 선언 제거(∨E)[19]
- ∨E: $$P \vee Q, P\Rightarrow R, Q\Rightarrow R\vdash R$$
유사 사례 1. (선언지 제거, 선언적 삼단논법disjunctive syllogism; DS라고도 한다.) : $$P \vee Q, \neg P \vdash Q$$[20]
유사 사례 2. (복합 양도 논법) : $$P \vee Q, P\Rightarrow R, Q\Rightarrow S\vdash R \vee S$$
4.5. 선언 도입(∨I)
- ∨I[22]: $$P\vdash P\vee Q$$: $$P\vdash Q\vee P$$
4.6. 연언 제거(∧E)
- ∧E[23]: $$P\wedge Q\vdash P$$: $$P\wedge Q\vdash Q$$
4.7. 연언 도입(∧I)
- ∧I[24]: $$P,\,Q\vdash P \wedge Q$$
4.8. 간접 귀류법(￢E)[25]
- ￢E: $$\neg P\Rightarrow \perp\vdash P$$
유사 사례 2. (간접 추리법[27]) : $$P\to \neg P\vdash \neg P$$
4.9. 직접 귀류법(￢I)[28]
- ￢I: $$P\Rightarrow \perp\vdash\neg P$$
4.10. 폭발 원리(law of explosion; ⊥E)
- ⊥E: $$\perp\vdash P$$
(1) P & ~P 전제
{1}(2) P 연언 제거
{2}(3) P ∨ Q 선언 도입
{1}(4) ~P 연언 제거
{3, 4}(5) Q 선언적 삼단논법
쉽게 풀어서 설명해보면,
(1) 서로 모순되는 두 명제를 만들고, 둘다 참이라고 가정한다. (예: 삼각형의 내각의 합은 180도다. 삼각형의 내각의 합은 180도가 아니다.)
(2) 다음으로 방금 만든 명제를 이용해 선언명제를 하나 만든다. (예: 삼각형의 내각의 합은 180도'''이거나''' 1=2이다.) 이 명제의 전건이 참이므로 후건의 내용과 상관없이 이 명제는 참이다.
(3) 그러나 처음에 '삼각형의 내각의 합이 180도가 아니다'라는 명제 역시 참이라고 했으므로 이 선언명제의 전건은 거짓이다.
(4) 방금 이 선언명제가 참이라는 것을 증명했으므로 전건이 거짓인데도 참이 되기 위해서는 후건(1=2이다) 역시 참이 되어야 한다.
(5) (2)~(4)를 통해 '1=2이다'는 참으로 증명됐다.
이는 중세 논리학에서 이미 발견되고 있는 증명으로, 중세 논리학 교과서에는 다음과 같은 증명이 실려 있다.
이처럼 모든 명제는 모순의 귀결이기 때문에, 표준적인 논리 체계 하에서 모순이 타당할 수 있다고 인정하게 되면 그 논리체계는 모든 문장이 참이 되는 공허한 체계가 된다. 대신 보조도출에서 모순을 참으로 가정하고 그로부터 결론을 이끌어내는 방식은 사용할 수 있다.
5. 추론 전략
모든 명제 논리의 증명을 기계적인 알고리즘을 통해 해결하는 방법은 존재하지 않는다. 그렇기 때문에 명제 논리의 증명에는 직관력이 필요할 수밖에 없다. 그러나 직관의 필요성을 인정한다고 할지라도, 효과적인 전략을 제시할 수 없는 것은 아니다. 이하의 전략은 많은 논리적 증명에서 유효하게 사용될 수 있다.
1. 선언문이 나오면 선언 제거를 활용하라.
2. 얻고자 하는 문장과 반대되는 가정을 한 다음 그로부터 가정의 부정을 도출하기 위해 귀류법을 활용하라.(예: 주어진 전제로부터 P를 얻고자 한다면 일단 ~P를 가정하고, ~P일 경우 모순이 발생함을 보여라.)
이상의 두 전략은 아주 유용하며, 예시로는 다음과 같은 선언적 삼단논법(disjunctive syllogism)의 증명을 들 수 있다.
(1) P ∨ Q 전제
(2) ~P 전제
(3) ~Q 가정/~E
(4) P 가정/∨E
(5) P {4} 반복
(6) Q 가정/∨E
(7) ~P 가정/~E
(8) Q {6} 반복
(9) ~Q {3} 반복
(10) P {7}~{9} ~E
(11) P {1}, {4}~{5}, {6}~{9} ∨E
(12) ~P {2} 반복
(13) Q {3}~{12} ~E
또한 다음과 같은 전략이 제시될 수 있다.
3. 얻고자 하는 결론이 조건문 형태라면 조건 도입과 조건문화를 응용하라.
4. 얻고자 하는 결론이 쌍조건문 형태라면, 조건문 각각을 증명하고 쌍조건화 규칙을 적용하라.(ex: P iff Q를 증명하기 위해 P를 가정하고 Q가 따라나오는 것와 Q를 가정하면 P가 따라나온다는 것을 각각 증명하라.)
6. 논리적 동치
표준 명제 논리에서 문장 $$\phi$$와 $$\psi$$가 논리적 동치인 것의 필요충분조건은 다음과 같다:
- 의미론/모형이론적 규정: $$\phi \leftrightarrow \psi$$이 타당함(i.e. 모든 모형에서 참임).
- 구문론/증명이론적 규정: $$\phi \vdash \psi,\, \psi \vdash \phi$$
7. 관련 문서
[1] 이때 '⊃'는 집합론에서의 진부분집합을 나타내는 기호와 생김새가 비슷하지만 완전히 다른 개체임에 유의할 것. 즉 변항이 명제라는게 확실한 경우 "φ⊃ψ"라는 표현을 볼 경우 이건 (수학처럼) "φ ← ψ"로 봐야 하는 게 아니라 정반대인 "φ → ψ"로 이해해야한다. 따라서 "P → Q"는 "P⊃Q"와 같은 의미지, 수학에서 흔히 알고 있는 "P⊂Q"가 아니다. "φ이면 ψ다"라는 조건문이 부분집합 관계와 같은 것으로 생각하기 쉽기에 "φ → ψ"를 "φ⊂ψ"라고 써야한다고 착각할 수 있다. 이 때문에 해외에서는 $$\text{Ɔ}$$로 구분해서 쓰는 경우도 있었다.[2] 모순은 하나의 명제로 도입될 수 있지만, 무조건 거짓을 뱉는 연산자로 볼 수도 있다.[3] 양도논법이라고도 한다.[4] 직관주의자들은 이 규칙을 거부한다. 거칠게 설명해, 명제 $$P$$의 부정에 대한 부정이 증명되더라도 명제 P가 증명가능한 것은 아니기 때문이다. 직관주의 논리에서 $$\neg P$$의 증명이 존재하기 위한 필요충분조건은 $$P\to \perp$$의 증명($$P$$의 증명이 input일 때 $$\perp$$의 증명을 output으로 내놓는 함수, 혹은 방법)이 존재하는 것이다. 따라서, $$\neg\neg P$$가 증명가능하다는 것은 $$\neg P\to \perp$$의 증명이 존재하는 경우이고, 이로부터 $$P$$에 대한 증명이 있으리라는 보장이 없기 때문에, 직관주의 논리에서 간접적 귀류법은 논리적 법칙이 될 수 없다. 직관주의 논리에서 참 개념이 증명가능 개념으로 대체된다는 것을 안다면 위 설명이 이해가 될 것이다.[5] 조건 도입규칙의 한 예로 볼 수 있다.[6] 엄밀히 말해서는 등호(=)는 성립하지 않으며, 그 대신 기호 'P'가 명제 <소크라테스는 사람이다>를 지시하는 이름인 것으로 규정되어야하나, 편의상 위와 같은 표기법을 사용한다[7] 논리 연결사로 구성된 복합 명제를 만들 때 부정의 기능을 하는 논리 연결사 ‘~’는 항상 그것이 부정하려는 명제 앞에 놓여야 한다. 예를 들면 “그들은 우리집에 왔다.(p)”는 문장을 부정한다고 해보자. 그러면 그 문장의 부정은 ‘~p’로 표현될 수 있다. 또한 괄호로 묶인 복합명제의 경우에는 괄호로 묶인 명제 전체를 부정한다. 예를 들면, “그들은 우리 집에 왔으며, 우리는 그들에게 접대를 했다.(p&q)”는 명제의 부정은 ‘~(p&q)’로 표현한다. 명제논리에서는 명제가 애매하지 않도록 괄호를 사용한다. 이는 수학에서 괄호를 쓰는 방식과 같다.[a] A B 한국논리학회, 국제논리학협회 표준[8] 더 줄여 iff로 쓰기도 한다[9] 1 + 1 = 1, 1 + 0 = 1, 0 + 1 = 1, 0 + 0 = 0[10] 학제적으로 전문성과 엄밀성이 필요한 분야일수록 이러한 경향성은 잘 나타나지 않는다. 대표적으로는 형법에서의 "m년 이하의 징역 또는 n원 이하의 벌금"이 있다.[11] 1 * 0 = 0, 0 * 1 = 0, 1 * 1 = 1, 0 * 0 = 0[12] 이때 '⊃'는 집합론에서의 진부분집합을 나타내는 기호와 생김새가 비슷하지만 '''완전히 다른 개체임에 유의할 것.''' 즉 변항이 명제라는게 확실한 경우 "φ⊃ψ"라는 표현을 볼 경우 이건 (수학처럼) "φ ← ψ"로 봐야 하는 게 아니라 '''정반대인''' "φ → ψ"로 이해해야한다. 따라서 "P → Q"는 "P⊃Q"와 같은 의미지, 수학에서 흔히 알고 있는 "P⊂Q"가 아니다. "φ이면 ψ다"라는 조건문이 부분집합 관계와 같은 것으로 생각하기 쉽기에 "φ → ψ"를 "φ⊂ψ"라고 써야한다고 착각할 수 있다. 이 때문에 해외에서는 $$\text{Ɔ}$$로 구분해서 쓰는 경우도 있었다.[13] 모순은 하나의 명제로 도입될 수 있지만, 무조건 거짓을 뱉는 연산자로 볼 수도 있다.[14] 1909년에 태어난 독일의 수학자이자 논리학자로 헤르만 바일, 폴 베르나이스, 힐베르트 같은 당대 최고 석학들의 가르침을 받았다. 스승인 힐베르트의 공리체계와는 다른 방식의 증명체계들을 제시한 것과 초한귀납법을 써서 산술의 일관성을 증명한 것(Consistency Proof)이 주요업적이다. 이렇듯 젊은 나이에 뛰어난 재능을 발휘한 천재였지만 나치당에 가입해 돌격대로 활동하였고 V-2 계획에도 참여한 흑역사가 있다. 1943년 독일이 점령한 체코의 프라하 대학교의 교수로 임용되어 프라하에서 생활하다가 전후 학교 직원들과 함께 체포된다. 이후 소련군에 넘겨졌다가 나치에 협력한 전력 때문에 수용소로 보내져 1945년 35세의 젊은 나이에 영양실조로 사망한다.[15] $$\vdash$$ 기호는 앞에서 소개한 명제논리의 연결사들이 아니라 명제논리에 속하는 명제들 사이의 추론관계를 나타내기 위해 사용된 메타언어의 기호라는 것에 유의할 것.[16] 소거 규칙은 한 명제를 그 명제를 구성하는 부분적인 명제들로, 도입 규칙은 여러 명제를 합해 하나의 복합적인 명제를 만든다고 볼 수 있다. 예를 들어 Modus Ponens 규칙은 한 조건문과 그 조건문의 전건을 (참이라고)가정했을 때, 전제된 조건문의 후건이 참임을 추론한다. 이러한 추론규칙의 적용을 통해 조건문이 더 간단한 명제로 분해되는 것이다. 또한 이러한 규칙들은 그 자체로 타당한 논증의 형식을 가진다. 따라서 주어진 전제에 아래의 규칙들을 올바르게 적용하여 어떤 명제를 도출할 수 있다면, 기존의 전제들과 이로부터 도출한 명제를 결과로 갖는 논증은 타당하다.[17] modus ponens, MP라고 불리기도 한다. 조건문이 참이고 그 전건이 참이라면, 후건은 참이다.[18] CP(Conditional Proof)라고도 한다. 주어진 전제로부터 어떤 명제를 도출할 수 있다면, 전제를 전건으로, 도출된 명제를 후건으로 갖는 조건문이 증명가능하다는 의미도 된다.[19] 양도논법이라고도 한다.[20] $$P \vee Q,P \vdash \neg Q$$는 논리적으로 맞지 않는 추론이다. 예를 들어, '모 위키러는 스 1 유저이거나 스 2 유저이다.'라는 문장에서, 그 위키러가 스 1 유저이면서 동시에 스 2 유저일 수 있으므로 '그 위키러는 스 1 유저이기 때문에 스 2 유저가 아니다'는 옳지 않은 추론이다. 하지만 '모 위키러는 중학생이거나 고등학생이다'라는 문장에서는, '중학생'과 '고등학생'이 상호 배타적이므로, 이때는 중학생을 긍정함으로써 그 위키러가 고등학생이 아니라는 것을 유도할 수 있다.[21] 위의 선언지제거법과 마찬가지로, 복합양도논법은 딜레마로 연결될 수 있는 위험을 항상 안고 있다. 예를 들어 '거짓말을 하면 신이 널 싫어하고, 참말을 하면 사람들이 널 싫어하므로 뭘 하든지 넌 미움받게 된다'는 잘못된 복합양도논법으로, 딜레마이다. 이 딜레마는 '참말을 하면 신이 사랑하고, 거짓말을 하면 사람들이 좋아하므로 언제나 난 이득이다'라는 식으로 바꿀 수 있다. 마찬가지로 위의 결혼/독신 문제도, '독신녀로 산다면 부모님께서 기뻐하고 결혼하면 남친이 기뻐하니 둘 다 이득이다.'라는 식으로 바꿀 수 있다.[22] Add(Addition)이라고도 한다. 한 명제가 참이라면, 이 명제를 부분으로 갖는 선언문은 참임을 의미한다.[23] Simp(Simplication)이라고도 한다. 한 연언문이 참이라면, 그 연언문을 구성하는 부분 명제들은 모두 참이다.[24] Conj(Conjunction)이라고도 한다. 참인 명제들로 구성되는 연언문은 참이다.[25] 직관주의자들은 이 규칙을 거부한다. 거칠게 설명해, 명제 $$P$$의 부정에 대한 부정이 증명되더라도 명제 P가 증명가능한 것은 아니기 때문이다. 직관주의 논리에서 $$\neg P$$의 증명이 존재하기 위한 필요충분조건은 $$P\to \perp$$의 증명($$P$$의 증명이 input일 때 $$\perp$$의 증명을 output으로 내놓는 함수, 혹은 방법)이 존재하는 것이다. 따라서, $$\neg\neg P$$가 증명가능하다는 것은 $$\neg P\to \perp$$의 증명이 존재하는 경우이고, 이로부터 $$P$$에 대한 증명이 있으리라는 보장이 없기 때문에, 직관주의 논리에서 간접적 귀류법은 논리적 법칙이 될 수 없다. 직관주의 논리에서 '''참 개념'''이 '''증명가능 개념'''으로 대체된다는 것을 안다면 위 설명이 이해가 될 것이다.[26] 엄밀히 말하자면 해당 추론은 조건화 증명을 한번 거친 것이다.[27] 유사 사례로 '클라비우스의 법칙'이 있다: $$(\neg P \to P) \vdash P$$[28] 조건 도입규칙의 한 예로 볼 수 있다.