최근 수정 시각 : 2019-06-10 09:17:07

명제 논리


1. 개요2. 명제 논리에서의 해석3. 명제논리 연결사
3.1. 부정 (NOT; ¬, ~, -)3.2. 선언 (OR; ∨)
3.2.1. 배타적 선언 (XOR; ⊕)
3.3. 연언 (AND; ∧, &)3.4. 조건문(If ... Then ...; →, ⊃, Ɔ)3.5. 쌍조건문(If and Only If; ↔, iff)3.6. 모순(Contradiction; ⊥, c)
4. 추론과 명제논리 추론 규칙
4.1. 전건 긍정(Modus Ponens; →E) 4.2. 후건 부정(Modus Tollense)4.3. 조건 도입(Conditional Proof; →I)4.4. 선언 제거(∨E)4.5. 선언 도입(∨I)4.6. 연언 제거(∧E)4.7. 연언 도입(∧I)4.8. 간접 귀류법(¬E)4.9. 직접 귀류법(¬I)4.10. 폭발 원리(Law of Explosion; ⊥E)
5. 추론 전략6. 논리적 동치

1. 개요

명제논리(propositional logic) 혹은 문장논리(sentential logic)명제 혹은 문장들 간의 논리적 관계를 다룬다. 즉 예를 들어 <소크라테스는 사람이다>라는 명제를 기호화한다면, 이를 그냥 통째로 "P"로 표시할 뿐 더이상 쪼개 들어가질 않는다. 이런 명제들은 알파벳 대문자 (e.g. P, Q, R ...)로 기호화하는 것이 관례다. 명제 논리는 양화 논리의 특수한 경우로 생각할 수 있다.
예시: (P</math> = "소크라테스는 사람이다", QQ= "지구는 행성이다")[1]:
  • "소크라테스는 사람이고, 지구는 행성이다" ⇒ "PQ P \wedge Q"
  • "소크라테스가 사람이 아니라면, 지구는 행성이거나 소크라테스는 사람이 아니다" ⇒ "¬P(Q¬P)\neg P \to (Q \vee \neg P)"

명제논리는 결정가능(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)는 한 개 이상의 명제 기호에 덧붙여짐으로써 해당 명제(들)에 새로운 의미를 더한다. 꼭 복수의 명제들을 '연결'할 필요없이 하나의 명제에만 붙는 연결사도 있음을 유의하라(예. ~).

연결사를 포함하지 않은 명제를 단순 명제라고 하며, 단순 명제와 하나 이상의 논리 연결사로 구성되는 명제를 복합 명제라고 한다[2]. 복잡한 구조를 가진 복합 명제들에서는 두 개 이상의 논리 연결사와 괄호들이 사용되기도 하는데, 이때 주요 부분을 연결해 주는 논리 연결사를 ‘주 논리 연결사’라고 한다.

아래에 언급된 명제 연결사들은 일반적으로 명제 논리에서 등장하는 연결사들이다.
논리 연결사논리적 기능종류일상적 표현
[a] 또는 ~부정부정문~이 아니다(not ~).
[a] 또는 &연언연언문그리고, 그러나, 그럼에도 불구하고(and)
선언선언문또는(or)
단순함축조건문만일~이라면, ~(if~, then~)
단순동치쌍조건문~일 경우 그리고 그 경우에만 ~(if and only if[5])

이들의 의미는 진리표를 통해 엄밀하게 규정될 수 있다. 진리표는 피연산자의 진리치(=T, 거짓=F)에 따라 연결사가 덧붙여진 새로운 명제의 진리치가 어떤 것이 되는지를 표시해준다.

예를 들어 임의의 2항 연결사인 ⊙가 어떻게 진리표를 통해 정의되는지 알아보기 위해 다음 예시를 참고하라:
P (피연산자1) Q (피연산자2) P ⊙ Q (연산 결과)
T T α
T F β
F T γ
F F δ

해당 진리표는 ⊙의 진리표를 도식화시킨 것이다. 앞의 두 은 피연산자인 명제 P와 Q가 갖는 진리치의 모든 가능한 배열을 망라한 것이다. 이때 가능한 배열의 경우의 수는 4이므로, 곧 의 수가 넷이다. 마지막 세 번째 열은 이런 4가지 경우의 수 각각마다 ⊙가 붙었을 때의 연산 결과를 나타내며, 그 결과인 변수 α, β, γ, δ의 값 또한 각각 T 혹은 F다. 즉 이때 α, β, γ, δ이 어떤 값을 갖느냐에 따라 연결사 ⊙의 성격이 정의된다.

더불어 아래 명제 연결사만이 명제 논리의 확고부동한 연결사라고 생각할 필요는 없다. 예를 들어 ,\vee, \wedge¬,\neg, \to에 의해 정의될 수 있음은 명백하며, 극단적으로는 하나의 연결사만으로도 모든 명제 논리를 포괄하는 것도 가능하다(예. Sheffer Stroke '|').

이하의 연결사 설명은 원칙적으로 메타 문장인 그리스어 문자로 기술되어야 하지만, 편의상 영문 알파벳 대문자로 기술한다.

3.1. 부정 (NOT; ¬, ~, -)

Negation (\sim 혹은 ¬\neg 혹은 -)
한국어에선 "-가 아니다"에 대응한다. P가 참이면 ~P는 거짓, P가 거짓이면 ~P는 참이다.
예를 들어 "망치를 가져와라" 라고 했을 때, 망치가 아닌 무엇인가를 가지고 가는 경우에 해당한다.
P ~P
T F
F T

3.2. 선언 (OR; ∨)

選言 Disjunction 논리합 (\vee) [6]
P∨Q라고 하면 P, Q 중 적어도 하나는 성립한다는 것을 뜻한다. 둘 중 하나만 성립하는 것이 아니며, P와 Q 둘 모두 성립해도 된다. 이때 P와 Q를 "선언지(disjunct)"라고 부르기도 한다.
예를 들어 "망치 또는 빠루를 가져와라"라고 했을 때, 망치를 가져 와도 참이고, 빠루를 가져 와도 참이며, 망치와 빠루를 들고 와도 참이다.
진리표는 다음과 같다.
P Q P ∨ Q
TT T
TF T
FT T
FF F

"∨"는 한국어의 "혹은", 영어의 "or"에 대응하는 것 같지만, 일상 언어 표현들의 경우 두 선언지 가운데 하나를 선택해야만 하는 것 같은 직관이 있다. 예를 들어 "망치를 사용하시겠습니까, 혹은 빠루를 사용하시겠습니까?"라고 물어봤을 땐 망치와 빠루 중 하나만을 선택해야할 것 같다. 하지만 위에서 나타나다시피 "∨"를 쓴 문장인 "(망치를 쓴다) ∨ (빠루를 쓴다)"는 망치만 휘둘러도, 빠루를 휘둘러도, 망치와 빠루를 둘 다 양손에 하나씩 들고 사용해도 된다.
이러한 직관이 나타나는 이유는 우리말에서는 흔히 "그리고"와 "또는"을 다른 의미로 구분하기 때문이다. [7] 실제로 우리는 "또는"을 "그리고"와 다른 의미로 구별하기 때문에 망치 또는 빠루를 가져오라는 말을 들었을 때 "망치 그리고 빠루를 가져간다"는 선택지를 배제하게 된다. 그렇지만 논리기술적으로는 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) (P ∨ Q) ∧ ~(P ∧ Q)
TT T F F
TF T T T
FT T T T
FF F T F
P와 Q 모두 참일 때는 거짓임을 볼 수 있다. 또한 P∨Q는 ~(~P∧~Q)와 동치이므로, 선언문은 ∧와 ~만을 이용해 나타낼 수도 있다.

수학II 에서 집합단원의 대칭차집합과 대응된다고 볼 수 있다.

3.3. 연언 (AND; ∧, &)

連言 Conjunction 논리곱 (\wedge 혹은 &\&) [8]
P ∧ Q는 P, Q 모두 참일 때에만 참이다. 이때 P와 Q를 "연언지(conjunct)"라고 부른다. 한국어에선 "-와/과 -", "-이고 -다", "-이며 -다" 등에 대응한다. 예를 들어 "망치와 빠루를 가져와라"라고 했을 때, 망치와 빠루 모두 들고 와야 참이 되는 것과 같다. ~와 ∨를 이용해 나타내면
~(~P∨~Q)이다.
P Q P ∧ Q
TT T
TF F
FT F
FF F

3.4. 조건문(If ... Then ...; →, ⊃, Ɔ[9])

실질 조건문(material conditional) (\to, \supset, \text{Ɔ})
P → Q는 P가 거짓이거나 Q가 참인 경우 오직 그 경우에 참이다. 즉 P가 참이고 Q가 거짓인 경우를 제외하면 모두 참이다. 이때 P를 "전건(antecedent)", Q를 "후건(consequent)"이라고 부른다. 조건문 "P → Q"는 "~P∨Q"와 동치다.
P Q P → Q
TT T
TF F
FT T
FF T

조건문은 영어의 "If ... then ..."이나 한국어의 "만약 -면, ...다" 같은 표현에 대응하지만, 일상언어에서의 직관적 쓰임새에 항상 부합하지는 않는다. 다음 두 예시를 참조하라:
  • 성공적인 예시: "만약 철희가 소년이라면, 철희는 남자다""(철희가 소년이다) → (철희는 남자다)"로 표현될 수 있을 법하며, 이는 적절해 보인다. 왜냐면 이 문장은 실제로 철희가 소년이고 남자일 때 명백히 참인 것으로 보이며, 동시에 철희가 소녀인 경우에도 해당 문장은 (전건이 애초에 만족되지 않으므로) 참으로 보는게 그럴 법하기 때문이다.
  • 실패하는 예시: 반면 "만약 태양계 행성이 5개면, 라멘은 맛있다"라는 문장을 생각해보자. 이 문장의 의미가 "(태양계 행성이 5개다) → (라멘은 맛있다)"와 같다고 한다면, "만약 태양계 행성이 5개면, 라멘은 맛있다"는 참된 문장이다. 왜냐면 태양계의 행성은 8개이기 때문이다. 하지만 이는 매우 부조리한 것 같다.

두 번째 사례의 경우 "만약 - 면, -다"라는 형식을 띠고 있음에도 불구하고 실질 조건문의 논리적 특성에 잘 부합하지 않음을 알 수 있다. 해당 사례를 설명하기 위해 언어철학자들은 양상논리를 도입한 엄밀 조건문(strict conditional) 개념을 적용시킨다. 또한 "직설법 조건문(indicative conditional)" 혹은 "가정법 조건문(subjunctive conditional)" 같은 유형들 또한 별도로 구분되어 이해되어야만 한다.

특히 진리표에서, (3)번째와 (4)번째가 참이되는 이유가 헷갈릴텐데.. 이렇게 생각하면 쉽다. 선생님이 학생에게 '체육대회에서 100m를 5초안에 뛸 수 있으면 아이스크림을 주겠다'라고 말했다고 해보자. 만일, 학생이 실제 체육대회에서 100m를 5초안에 못 뛰었다고 해서 선생님이 한 말이 거짓이 될 순 없다. 거짓이 되는 경우는 "단 한가지" 뿐이다. 즉, (2)학생이 100m를 5초 안에 들어왔는데 선생님이 아이스크림 안주는 경우만 거짓이다. (3)학생이 100m를 5초 안에 들어오지 못했지만 선생님이 안쓰러워 아이스크림을 사준 경우 역시 선생님이 했던 선생님은 약속을 어긴게 아니라 새로운 약속을 자기 맘속으로 추가한 것 뿐이다. 즉, 위 선생님의 약속(가언 명제) 자체는 이라는 이야기. 그리고 마찬가지로 (4)학생이 100m를 5초 안에 들어오지 못해서 선생님이 약속대로 아이스크림을 사주지 않는 경우 당연히 위 선생님의 약속(가언 명제)자체가 틀렸다고 할 수 없다. 즉, 으로 인정한다.

더 직관적으로 이해하고 싶다면 조건문을 의미하도록, 집합 P가 집합 Q의 부분집합이라는 명제를 벤다이어그램을 그려보자. 이때, 집합 내부에 x표시를 해보면 가능한 표시는 1) P, Q가 모두 참인 경우, 2) P가 거짓, Q가 참인 경우, 3) P,Q 모두 거짓인 경우 밖에 없다. 메타적으로 봤을 때, 'P가 Q의 부분집합이라는 명제'와 'P가 참일 때 Q가 거짓이라는 명제'는 모순이기 때문에 그려보는 것이 논리적으로 불가능하다.

동치 문서에도 나와 있듯이, 조건문은 아래와 같이 선언 명제 형식으로 바꾸는 게 가능하다. 일반적으로 교양 논리학 교과목에서 명제 논리를 다룰 때 일찍이 설명하는 편이다.
(pq)(¬pq) \left( p \rightarrow q \right) \equiv \left( \neg p \vee q \right)
이는 처음 배우는 학생들이 얼핏 직관적으로 이해하기 어려울 수 있는데, 영어로는 이해하기 쉽다.
  • Don't go there or you may be in trouble. = If you go there, then you may in trouble.
두 문장이 같은 뜻임을 알 수 있다. 명령문의 논리적 문법이 영어와 같지 않은 한국어로는 대신 다음과 같이 이해할 수는 있다.
  • 과자를 먹든지, 안 그러면 아이스크림을 먹든지.
위 문장에서 '안 그러면', '아니면' 등의 구가 선언(or) 역할을 한다는 점을 먼저 이해하면 아래의 예로 이해할 수 있다.
  • 거기 가지 마. 안 그러면 안 좋은 일이 생길 거야. = 네가 거기 가면 안 좋은 일이 생길 거야.

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가 할당된다.
예를 들어서, '누군가 총각인 경우에 오직 그 경우에만 결혼하지 않은 남자다'라는 문장은 쌍조건문이다.
P Q P ↔ Q
TT T
TF F
FT F
FF T

3.6. 모순(Contradiction; ⊥, c)[10]

'Falsum' 혹은 'Bottom'이라고도 부른다. 무조건 거짓. 무조건 참은 "Top"이라고도 부르며 \top를 쓴다. 참은 True의 T or t모양을 따왔고, 거짓은 이 모양을 뒤집은 것이다. 표준적인 명제논리에서는 연결사가 아니다.

4. 추론과 명제논리 추론 규칙

귀결이 문장과 문장 사이의 의미론적 관계를 다룬다면, 추론(inference) 혹은 도출(deriviation)은 오직 형식적인 관계만을 다루는 것이다. 다른 표현으로 하자면 귀결은 의미론적(semantic) 작업이고 추론은 통사론적(syntactic) 작업이다. 추론은 귀결과는 달리 문장의 진리값이나 해석에 의존하지 않는다. 오직 형식적인 규칙만을 따라 수행하는 작업일 뿐이다. 그리고 그러한 형식적 추론이 의미론적인 귀결 관계를 보장한다는 것은 건전성 정리에 의해 증명되어 있다.

공집합으로부터 추론가능한 문장을 논리학적 정리라고 하며, 논리학적 정리인 문장은 논리적으로 타당하다. 즉, 모든 해석 하에서 참이다.

이하 내용은 명제 논리의 추론/증명 체계 중 하나인 게르하르트 겐첸(Gerhard Gentzen)[11]자연 연역(Natural Deduction) 방식을 소개한 것이다. 자연연역과 동등하게 강력한 추론/증명 체계로 역시 겐첸이 고안한 귀결 연산(sequent calculus)이 있고, 이와 살짝 다른 방식으로는 힐베르트 체계(Hilbert system)가 있다.

아래 규칙에서 E는 제거(elemination), I는 도입(Introduction)을 뜻한다. PQP\Rightarrow Q는 명제 QQ가 가정 PP에 의존한다는 것을 뜻하는 반면, P1,P2QP_{1},\,P_{2}\vdash Q[12]P1P_{1}, P2P_{2}로부터 QQ를 추론해낼 수 있다는 규칙을 나타낸다[13].

이하의 추론 규칙들은 원칙적으로 메타 문장인 그리스 문자로 기술해야 하지만, 편의상 영문 대문자로 대체한다.

4.1. 전건 긍정(Modus Ponens; →E)

  • →E[14]: P,PQQP,P\to Q\vdash Q
한국어 추론 예시.
만일 눈이 온다면, 스키를 타러갈 수 있다.
눈이 온다.
스키를 타러갈 수 있다.
유사 사례 1. (가언 삼단논법) : PQ,QRPRP\to Q, Q\to R \vdash P\to R
한국어 추론 예시
만일 비가 온다면, 소풍을 가지 않는다.
만일 소풍을 가지 않는다면, 우리는 학교에 가야된다.
만일 비가 온다면, 우리는 학교에 가야된다.

4.2. 후건 부정(Modus Tollense)

¬Q,PQ¬P\neg Q,P\to Q\vdash \neg P
한국어 추론 예시.
만일 늦게 일어난다면, 너는 지각을 할 것이다.
너는 지각을 하지 않았다.
너는 늦게 일어나지 않았다.

4.3. 조건 도입(Conditional Proof; →I)

  • →I[15]: PQPQP\Rightarrow Q\vdash P\to Q

P를 가정해서 Q가 따라나올 때, 조건문을 쓸 수 있다.

유사 사례: 어떤 문장이 앞서서 나타난다면, 그 문장을 후건으로 갖는 조건문을 쓸 수 있다. 이것은 1차 술어논리의 추론 규칙으로 활용된다.

4.4. 선언 제거(∨E)[16]

  • ∨E: PQ,PR,QRRP \vee Q, P\Rightarrow R, Q\Rightarrow R\vdash R
한국어 추론 예시.
나는 혼자 여행을 가든지 도서관에 갈 것이다.
만일 내가 여행을 가면, 나는 외로울 것이다.
만일 내가 도서관에 가면, 나는 외로울 것이다.
나는 외로울 것이다.
유사 사례 1. (선언지 제거, 선언적 삼단논법disjunctive syllogism; DS라고도 한다.) : PQ,¬PQP \vee Q, \neg P \vdash Q[17]
한국어 추론 예시
내가 결혼을 하는 것은 꿈이든지 현실이다.
내가 결혼을 하는 것은 꿈이 아니다.
내가 결혼을 하는 것은 현실이다.
유사 사례 2. (복합 양도 논법) : PQ,PR,QSRSP \vee Q, P\Rightarrow R, Q\Rightarrow S\vdash R \vee S
한국어 추론 예시
나는 결혼을 하든지 독신녀로 살 것이다.
만일 내가 결혼을 한다면, 부모님께서 서운해 하실 것이다.
만일 내가 독신녀로 산다면, 내 남자 친구가 서운해 할 것이다.
부모님께서 서운해 하시든지, 내 남자 친구가 서운해 할 것이다[18].

4.5. 선언 도입(∨I)

  • ∨I[19]: PPQP\vdash P\vee Q: PQPP\vdash Q\vee P
한국어 추론 예시.
바람이 분다.
바람이 불거나 비가 온다.

4.6. 연언 제거(∧E)

  • ∧E[20]: PQPP\wedge Q\vdash P: PQQP\wedge Q\vdash Q
한국어 추론 예시.
바람이 불고, 비가 온다.
바람이 분다.

4.7. 연언 도입(∧I)

  • ∧I[21]: P,QPQP,\,Q\vdash P \wedge Q
한국어 추론 예시.
바람이 분다.
비가 온다.
바람이 불고, 비가 온다.

4.8. 간접 귀류법(¬E)[22]

  • ¬E: ¬PP\neg P\Rightarrow \perp\vdash P
한국어 추론 예시.
만일 불치병의 환자가 웃으면, 그 주변사람들은 기쁘면서도 기쁘지 않았다.
불치병의 환자는 웃지 않았다.[23]
유사 사례 1. 이중 부정 제거 : ¬¬PP\neg\neg P \vdash P
한국어 추론 예시
소크라테스가 죽지 않았다는 것은 거짓이다.
소크라테스는 죽었다.
유사 사례 2. (간접 추리법[24]) : P¬P¬PP\to \neg P\vdash \neg P
한국어 추론 예시
만일 이 결혼이 행복한 것이라면, 이 결혼은 행복한 것이 아니다.
이 결혼은 행복한 것이 아니다.

4.9. 직접 귀류법(¬I)[25]

  • ¬I: P¬PP\Rightarrow \perp\vdash\neg P

4.10. 폭발 원리(Law of Explosion; ⊥E)

  • ⊥E: P\perp\vdash P
이것은 직관주의 논리학에서 받아들이는 원리로, 표준적인 자연연역 체계에서는 도출 규칙으로 다루지 않는다. 간단히 설명하면, 모순으로부터 모든 명제가 도출된다는 것이다. 직관주의 논리가 아닌 자연연역에서는 도출 규칙이 아닌 정리로, 다음과 같이 증명된다.

(1) P & ~P 전제
{1}(2) P 연언 제거
{2}(3) P ∨ Q 선언 도입
{1}(4) ~P 연언 제거
{3, 4}(5) Q 선언적 삼단논법

이는 중세 논리학에서 이미 발견되고 있는 증명으로, 중세 논리학 교과서에는 다음과 같은 증명이 실려 있다.
소크라테스는 죽었으며 죽지 않았다고 가정하자.
소크라테스는 죽었다.
소크라테스는 죽었거나 막대는 구석에 세워져 있다.
소크라테스는 죽지 않았다.
막대는 구석에 세워져 있다.

이처럼 모든 명제는 모순의 귀결이기 때문에, 표준적인 논리 체계 하에서 모순이 타당할 수 있다고 인정하게 되면 그 논리체계는 모든 문장이 참이 되는 공허한 체계가 된다. 대신 보조도출에서 모순을 참으로 가정하고 그로부터 결론을 이끌어내는 방식은 사용할 수 있다.

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

명제 논리에서 도출되는 대표적인 논리적 동치 사례들을 참조하기 위해선 해당 링크 참조

파일:크리에이티브 커먼즈 라이선스__CC.png 이 문서의 내용 중 전체 또는 일부는 수리 논리학 문서의 r224 판, 3번 문단에서 가져왔습니다. 이전 역사 보러 가기




[1] 엄밀히 말해서는 등호(=)는 성립하지 않으며, 그 대신 기호 'P'가 명제 <소크라테스는 사람이다>를 지시하는 이름인 것으로 규정되어야하나, 편의상 위와 같은 표기법을 사용한다[2] 논리 연결사로 구성된 복합 명제를 만들 때 부정의 기능을 하는 논리 연결사 ‘~’는 항상 그것이 부정하려는 병제 앞에 놓여야 한다. 예를 들면 “그들은 우리집에 왔다.(p)”는 문장을 부정한다고 해보자. 그러면 그 문장의 부정은 ‘~p’로 표현될 수 있다. 또한 괄호로 묶인 복합명제의 경우에는 괄호로 묶인 명제 전체를 부정한다. 예를 들면, “그들은 우리 집에 왔으며, 우리는 그들에게 접대를 했다.(p&q)”는 명제의 부정은 ‘~(p&q)’로 표현한다. 명제논리에서는 명제가 애매하지 않도록 괄호를 사용한다. 이는 수학에서 괄호를 쓰는 방식과 같다.[a] 한국논리학회, 국제논리학협회 표준[a] [5] 더 줄여 iff로 쓰기도 한다[6] 1 + 1 = 1, 1 + 0 = 1, 0 + 1 = 1, 0 + 0 = 0[7] 사실 그렇지 않은 경우도 많다. 대표적으로는 형법에서의 "~년 이하의 징역 또는 ~~원 이하의 벌금"이 있다.[8] 1 * 0 = 0, 0 * 1 = 0, 1 * 1 = 1, 0 * 0 = 0[9] 이때 '⊃'는 집합론에서의 진부분집합을 나타내는 기호와 생김새가 비슷하지만 완전히 다른 개체임에 유의할 것.변항명제라는게 확실한 경우 "φ⊃ψ"라는 표현을 볼 경우 이건 (수학처럼) "φ ← ψ"로 봐야 하는 게 아니라 정반대인 "φ → ψ"로 이해해야한다. 따라서 "P → Q"는 "P⊃Q"와 같은 의미지, 수학에서 흔히 알고 있는 "P⊂Q"가 아니다. "φ이면 ψ다"라는 조건문이 부분집합 관계와 같은 것으로 생각하기 쉽기에 "φ → ψ"를 "φ⊂ψ"라고 써야한다고 착각할 수 있다. 이 때문에 해외에서는 \text{Ɔ}로 구분해서 쓰는 경우도 있었다.[10] 모순은 하나의 명제로 도입될 수 있지만, 무조건 거짓을 뱉는 연산자로 볼 수도 있다.[11] 1909년에 태어난 독일의 수학자이자 논리학자로 헤르만 바일, 폴 베르나이스, 힐베르트 같은 당대 최고 석학들의 가르침을 받았다. 스승인 힐베르트의 공리체계와는 다른 방식의 증명체계들을 제시한 것과 초한귀납법을 써서 산술의 일관성을 증명한 것(Consistency Proof)이 주요업적이다. 이렇듯 젊은 나이에 뛰어난 재능을 발휘한 천재였지만 나치당에 가입해 돌격대로 활동하였고 V-2 계획에도 참여한 흑역사가 있다. 1943년 독일이 점령한 체코의 프라하 대학교의 교수로 임용되어 프라하에서 생활하다가 전후 학교 직원들과 함께 체포된다. 이후 소련군에 넘겨졌다가 나치에 협력한 전력 때문에 수용소로 보내져 1945년 35세의 젊은 나이에 영양실조로 사망한다.[12] \vdash 기호는 앞에서 소개한 명제논리의 연결사들이 아니라 명제논리에 속하는 명제들 사이의 추론관계를 나타내기 위해 사용된 메타언어의 기호라는 것에 유의할 것.[13] 소거 규칙은 한 명제를 그 명제를 구성하는 부분적인 명제들로, 도입 규칙은 여러 명제를 합해 하나의 복합적인 명제를 만든다고 볼 수 있다. 예를 들어 Modus Ponens 규칙은 한 조건문과 그 조건문의 전건을 (참이라고)가정했을 때, 전제된 조건문의 후건이 참임을 추론한다. 이러한 추론규칙의 적용을 통해 조건문이 더 간단한 명제로 분해되는 것이다. 또한 이러한 규칙들은 그 자체로 타당한 논증의 형식을 가진다. 따라서 주어진 전제에 아래의 규칙들을 올바르게 적용하여 어떤 명제를 도출할 수 있다면, 기존의 전제들과 이로부터 도출한 명제를 결과로 갖는 논증은 타당하다.[14] modus ponens, MP라고 불리기도 한다. 조건문이 참이고 그 전건이 참이라면, 후건은 참이다.[15] CP(Conditional Proof)라고도 한다. 주어진 전제로부터 어떤 명제를 도출할 수 있다면, 전제를 전건으로, 도출된 명제를 후건으로 갖는 조건문이 증명가능하다는 의미도 된다.[16] 양도논법이라고도 한다.[17] PQ,P¬QP \vee Q,P \vdash \neg Q는 논리적으로 맞지 않는 추론이다. 예를 들어, '모 위키러는 스 1 유저이거나 스 2 유저이다.'라는 문장에서, 그 위키러가 스 1 유저이면서 동시에 스 2 유저일 수 있으므로 '그 위키러는 스 1 유저이기 때문에 스 2 유저가 아니다'는 옳지 않은 추론이다. 하지만 '모 위키러는 중학생이거나 고등학생이다'라는 문장에서는, '중학생'과 '고등학생'이 상호 배타적이므로, 이때는 중학생을 긍정함으로써 그 위키러가 고등학생이 아니라는 것을 유도할 수 있다.[18] 위의 선언지제거법과 마찬가지로, 복합양도논법은 딜레마로 연결될 수 있는 위험을 항상 안고 있다. 예를 들어 '거짓말을 하면 신이 널 싫어하고, 참말을 하면 사람들이 널 싫어하므로 뭘 하든지 넌 미움받게 된다'는 잘못된 복합양도논법으로, 딜레마이다. 이 딜레마는 '참말을 하면 신이 사랑하고, 거짓말을 하면 사람들이 좋아하므로 언제나 난 이득이다'라는 식으로 바꿀 수 있다. 마찬가지로 위의 결혼/독신 문제도, '독신녀로 산다면 부모님께서 기뻐하고 결혼하면 남친이 기뻐하니 둘 다 이득이다.'라는 식으로 바꿀 수 있다.[19] Add(Addition)이라고도 한다. 한 명제가 참이라면, 이 명제를 부분으로 갖는 선언문은 참임을 의미한다.[20] Simp(Simplication)이라고도 한다. 한 연언문이 참이라면, 그 연언문을 구성하는 부분 명제들은 모두 참이다.[21] Conj(Conjunction)이라고도 한다. 참인 명제들로 구성되는 연언문은 참이다.[22] 직관주의자들은 이 규칙을 거부한다. 거칠게 설명해, 명제 PP의 부정에 대한 부정이 증명되더라도 명제 P가 증명가능한 것은 아니기 때문이다. 직관주의 논리에서 ¬P\neg P의 증명이 존재하기 위한 필요충분조건은 PP\to \perp의 증명(PP의 증명이 input일 때 \perp의 증명을 output으로 내놓는 함수, 혹은 방법)이 존재하는 것이다. 따라서, ¬¬P\neg\neg P가 증명가능하다는 것은 ¬P\neg P\to \perp의 증명이 존재하는 경우이고, 이로부터 PP에 대한 증명이 있으리라는 보장이 없기 때문에, 직관주의 논리에서 간접적 귀류법은 논리적 법칙이 될 수 없다. 직관주의 논리에서 참 개념증명가능 개념으로 대체된다는 것을 안다면 위 설명이 이해가 될 것이다.[23] 엄밀히 말하자면 해당 추론은 조건화 증명을 한번 거친 것이다.[24] 유사 사례로 '클라비우스의 법칙'이 있다: (¬PP)P(\neg P \to P) \vdash P[25] 조건 도입규칙의 한 예로 볼 수 있다.