| 논리학 Logics | |||
| {{{#!wiki style="margin: -0px -10px -5px; min-height: 28px" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -6px -1px -11px;" | <colbgcolor=#2ab5b5> 형식 논리 | 명제 논리(논리 연산 · 삼단논법(정언삼단논법) · 순환 논법) · 공리 · 진리치 · 술어 논리 · 논증(논증의 재구성) · 모순 · 역설 · 논리적 오류(논리적 오류/형식적 오류) | |
| <colcolor=#000,#fff> 비표준 논리 | 직관 논리 · 양상논리 · 초일관 논리 · 다치논리(퍼지논리) · 선형논리 · 비단조 논리 | ||
| 메타 논리 | 집합론 · 완전성 정리 · 불완전성 정리 | ||
| 비형식 논리 | 딜레마(흑백논리) | ||
| 비형식적 오류 | 귀납적 오류 · 심리적 오류 · 언어적 오류 · 자료적 오류 · 양비론 · 진영논리 · 편견 및 고정관념 · 궤변 · 거짓 등가성 | ||
| 분야 | 수리철학 · 수리논리학 | ||
| 철학 관련 정보 · 논리학 관련 정보 · 수학 관련 정보 · 수리논리학 둘러보기 | |||
| 수학기초론 Foundations of Mathematics | |||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | 다루는 대상과 주요 토픽 | ||
| 수리논리학 | 논리 · 논증{귀납논증 · 연역논증 · 귀추 · 유추} · 공리 및 공준 · 증명{증명보조기 · 자동정리증명 · 귀류법 · 수학적 귀납법 · 반증 · 더블 카운팅 · PWW} · 논리함수 · 논리 연산 · 잘 정의됨 · 조건문(조각적 정의) · 명제 논리(명제 · 아이버슨 괄호 · 역 · 이 · 대우) · 양상논리 · 술어 논리(존재성과 유일성) · 형식문법 · 유형 이론 · 모형 이론 | ||
| 집합론 | 집합(원소 · 공집합 · 집합족 · 곱집합 · 멱집합) · 관계(동치관계 · 순서 관계) · 순서쌍(튜플) · 서수(하세 다이어그램 · 큰 가산서수) · 수 체계 · ZFC(선택공리) · 기수(초한기수) · 절대적 무한 · 모임 | ||
| 범주론 | 범주 · 함자 · 수반 · 자연 변환 · 모나드 · 쌍대성 | ||
| 계산가능성 이론 | 계산 · 오토마타 · 튜링 기계 · 바쁜 비버 · 정지 문제 · 재귀함수 | ||
| 정리 | |||
| 드모르간 법칙 · 대각선 논법 · 러셀의 역설 · 거짓말쟁이의 역설 · 뢰벤하임-스콜렘 정리 · 슈뢰더-베른슈타인 정리 · 집합-부분합 정리 · 퍼스의 항진명제 · 굿스타인 정리 · 완전성 정리 · 불완전성 정리(괴델 부호화) · 힐베르트의 호텔 · 연속체 가설 · 퍼지 논리 | |||
| 기타 | |||
| 예비사항(약어 및 기호) · 추상화 · 벤 다이어그램 · 수학철학 | |||
| 틀:논리학 · 틀:이산수학 · 틀:이론 컴퓨터 과학 · 철학 관련 정보 · 논리학 관련 정보 · 수학 관련 정보 | }}}}}}}}} | ||
| 인공어 | ||
| {{{#!wiki style="margin:0 -10px -5px; min-height:calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin:-5px -1px -11px; letter-spacing: -0.5px; word-break: keep-all" | <colbgcolor=#f5f5f5,#2d2f34><colcolor=#212529,#e0e0e0> 공학 언어 | 수식 · 화학식 · 명제 논리 · 술어 논리 · 프로그래밍 언어 · 로지반 · 링코스 · 이쓰쿠일 · 도기 보나 · 보아보무 |
| 국제 보조어 | 솔레솔 · 볼라퓌크 · 에스페란토 · 이도 · 인테르링구에 · 베이식 잉글리시 · 인테르링구아 · 국제 수화 · 코타바 · 노시로어 · 링구아 프랑카 노바 |
| 예술어/가공의 언어 | 에녹어 · 앵글리시 · 퀘냐 · 신다린 · 암흑어 · 클링온어 · 발리리아어 · 아브어 · 칼라니어 · 상헬리어 · 나비어 · 킬리키어 | |
| 기타 | 모스 부호 | }}}}}}}}} |
1. 개요2. 명제 논리에서의 해석3. 명제논리 연결사
3.1. 부정 (NOT; ¬, ~, -)3.2. 선언 (OR; ∨)
4. 추론과 명제논리 추론 규칙3.2.1. 배타적 선언 (XOR; ⊕)
3.3. 연언 (AND; ∧, &)3.4. 조건문(If ... Then ...; →, ⊃, Ɔ)3.4.1. 자연 언어 조건문과의 괴리
3.5. 쌍조건문(If and Only If; ↔, iff)3.6. 모순(Contradiction; ⊥, c)4.1. 전건 긍정
5. 추론 전략6. 논리적 동치7. 관련 문서4.1.1. 가언 삼단논법
4.2. 후건 부정4.3. 조건 도입4.4. 선언 제거4.5. 선언 도입4.6. 연언 제거4.7. 연언 도입4.8. 간접 귀류법4.9. 직접 귀류법4.10. 폭발 원리1. 개요
명제논리(命題論理, propositional logic) 혹은 문장논리(文章論理, sentential logic)는 명제 혹은 문장들 간의 논리적 관계를 다룬다. 즉 예를 들어 <소크라테스는 사람이다>라는 명제를 기호화한다면, 이를 그냥 통째로 "P"로 표시할 뿐 더이상 쪼개 들어가질 않는다. 이런 명제들은 알파벳 대문자 (e.g. P, Q, R ...)로 기호화하는 것이 관례다. 명제 논리는 양화 논리의 특수한 경우로 생각할 수 있다.[math( )]
예시: ([math(P)] = "소크라테스는 사람이다", [math(Q)] = "지구는 행성이다")[1]:
|
명제논리는 결정가능(decidable)하다. 즉 임의의 명제 논리식이 타당한지 (혹은 두 명제 논리식 간에 논리적 도출 관계가 성립하는지) 여부는 기계적으로 판단할 수 있다. 아래에서 설명될 진리표(truth-table)를 사용하는 것이 그런 기계적 판단 방식의 대표적인 예시다. 논리식의 타당성을 기계적으로 판단할 수 있다는 것은, 명제 논리 체계에서는 동어반복적 문장이 곧 타당한 문장이며, 타당한 문장이 곧 동어반복적 문장이라는 것이다.
2. 명제 논리에서의 해석
명제 논리에서의 해석(interpretation)은 각 명제에 진리값을 할당하는 것이다. 예를 들어 [math((P\;\&\;Q\;\&\;R))]이라는 문장이 있다고 생각해보자. 여기서 각 명제에 [math(T)]를 할당하는 것은 한 가지 해석이다. 각각의 명제는 [math(T)]이거나 [math(F)]일 수 있으므로, [math(n)]개의 명제가 있는 문장은 [math(2^n)]개의 해석이 가능하다. 즉 이상의 예에서는 다음과 같은 여덟 가지의 해석이 가능하다는 것이다.- [math(\{T,\,T,\,T\})]
- [math(\{T,\,T,\,F\})]
- [math(\{T,\,F,\,T\})]
- [math(\{T,\,F,\,F\})]
- [math(\{F,\,T,\,T\})]
- [math(\{F,\,T,\,F\})]
- [math(\{F,\,F,\,T\})]
- [math(\{F,\,F,\,F\})]
이러한 해석의 정의에 따라 명제 논리에서의 타당성, 귀결, 일관성이 다음과 같이 정의될 수 있다.
- 문장 [math(\phi)]가 모든 해석 하에서 참일 경우 문장 [math(\phi)]는 타당하다.
- 문장 [math(\phi)]와 문장집합 [math(\Gamma)]에 대해, [math(\Gamma)]의 모든 문장들을 참이게 하면서 [math(\phi)]를 거짓이게 하는 해석이 존재하지 않을 경우 [math(\phi)]는 [math(\Gamma)]의 귀결이다.
- 문장집합 [math(\Gamma)]에 대해, [math(\Gamma)]의 모든 문장들을 참이게 하는 해석이 하나라도 존재할 경우 [math(\Gamma)]는 일관적이다.
3. 명제논리 연결사
명제 논리에서 연결사(connective)는 한 개 이상의 명제 기호에 덧붙여짐으로써 해당 명제(들)에 새로운 의미를 더한다. 꼭 복수의 명제들을 '연결'할 필요없이 하나의 명제에만 붙는 연결사도 있음을 유의하라(예. [math(\sim)]).연결사를 포함하지 않은 명제를 단순 명제라고 하며, 단순 명제와 하나 이상의 논리 연결사로 구성되는 명제를 복합 명제라고 한다[2]. 복잡한 구조를 가진 복합 명제들에서는 두 개 이상의 논리 연결사와 괄호들이 사용되기도 하는데, 이때 주요 부분을 연결해 주는 논리 연결사를 ‘주 논리 연결사’라고 한다.
아래에 언급된 명제 연결사들은 일반적으로 명제 논리에서 등장하는 연결사들이다.
| 논리 연결사 | 논리적 기능 | 종류 | 일상적 표현 |
| [math(\neg)][a] 또는 [math(\sim)] | 부정 | 부정문 | ~이 아니다(not ~). |
| [math(\wedge)][a] 또는 [math(\&)] | 연언 | 연언문 | 그리고, 그러나, 그럼에도 불구하고(and) |
| [math(\vee)] | 선언 | 선언문 | 또는(or) |
| [math(\to)] | 단순함축 | 조건문 | 만일~이라면, ~(if~, then~) |
| [math(\leftrightarrow)] | 단순동치 | 쌍조건문 | ~일 경우 그리고 그 경우에만 ~(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다. 즉 이때 α, β, γ, δ이 어떤 값을 갖느냐에 따라 연결사 ⊙의 성격이 정의된다.
더불어 아래 명제 연결사만이 명제 논리의 확고부동한 연결사라고 생각할 필요는 없다. 예를 들어 [math(\vee, \wedge)]가 [math(\neg, \to)]에 의해 정의될 수 있음은 명백하며, 극단적으로는 하나의 연결사만으로도 모든 명제 논리를 포괄하는 것도 가능하다(예. Sheffer Stroke '|').
이하의 연결사 설명은 원칙적으로 메타 문장인 그리스어 문자로 기술되어야 하지만, 편의상 영문 알파벳 대문자로 기술한다.
3.1. 부정 (NOT; ¬, ~, -)
Negation ([math(\sim)] 혹은 [math(\neg)] 혹은 -)한국어에선 "-가 아니다"에 대응한다. [math(P)]가 참이면 [math({\sim}P)]는 거짓, [math(P)]가 거짓이면 [math({\sim}P)]는 참이다.
예를 들어 "망치를 가져와라" 라고 했을 때, 망치가 아닌 무엇인가를 가지고 가는 경우에 해당한다.| P | ~P |
| T | F |
| F | T |
3.2. 선언 (OR; ∨)
선언은(는) 여기로 연결됩니다.
BEJ48의 노래에 대한 내용은 宣言 문서, 노래를 찾는 사람들의 노래에 대한 내용은 선언(노래) 문서
참고하십시오.選言 Disjunction 논리합 ([math(\vee)]) [6]
[math(P\vee Q)]라고 하면 [math(P)], [math(Q)] 중 적어도 하나는 성립한다는 것을 뜻한다. 둘 중 하나만 성립하는 것이 아니며, [math(P)]와 [math(Q)] 둘 모두 성립해도 된다. 이때 [math(P)]와 [math(Q)]를 "선언지(disjunct)"라고 부르기도 한다.
예를 들어 "망치 또는 빠루를 가져와라"라고 했을 때, 망치를 가져 와도 참이고, 빠루를 가져 와도 참이며, 망치와 빠루를 들고 와도 참이다.
진리표는 다음과 같다.
| P | Q | P ∨ Q |
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
"∨"는 한국어의 "혹은", 영어의 "or"에 대응하는 것 같지만, 일상 언어 표현들의 경우 두 선언지 가운데 하나를 선택해야만 하는 것 같은 직관이 있다. 예를 들어 "망치를 사용하시겠습니까, 혹은 빠루를 사용하시겠습니까?"라고 물어봤을 땐 망치와 빠루 중 하나만을 선택해야할 것 같다. 하지만 위에서 나타나다시피 "∨"를 쓴 문장인 "(망치를 쓴다) ∨ (빠루를 쓴다)"는 망치만 휘둘러도, 빠루를 휘둘러도, 망치와 빠루를 둘 다
이러한 직관이 나타나는 이유는 우리말에서는 흔히 "그리고"와 "또는"을 다른 의미로 구분하기 때문이다.[7] 일상적으로 우리는 "또는"을 "그리고"와 다른 의미로 구별하기 때문에(즉, '또는'을 배타적 선언으로 인식하기 때문에) 망치 또는 빠루를 가져오라는 말을 들었을 때 "망치 그리고 빠루를 가져간다"는 선택지를 배제하게 되고, 마찬가지로 이를 요청한 쪽에서도 둘 다 시행하는 경우는 생각하지 않는다. 그렇지만 논리기술적으로는 P와 Q 둘 중의 하나 혹은(∨) P와 Q 둘 모두를 포함하는 기호를 만들어두는 것이 편리하기 때문에 해당 선택지도 포함하게 되므로 헷갈리지 말도록 하자.
영어에서는 양쪽 다 선택하는 or both와 같은 표현을 뒤에 붙이기도 한다.
3.2.1. 배타적 선언 (XOR; ⊕)
Exclusive OR 배타 논리합 ([math(\oplus)]')'둘 중 하나'만을 지시하는 선언문. 즉 "[math(P\oplus Q)]"가 참이면 [math(P)]와 [math(Q)] 둘 중 하나만 참이다. 이는 [math(\wedge)]와 [math(\vee)] 기호를 통해 정의될 수 있다. 즉 "[math(P\oplus Q)]"는 "[math((P\vee Q)\wedge{\sim}(P\wedge Q))]"와 동치다.
"망치와 빠루 중 하나를 가지고 와라" 라는 문장이 주어졌을 때, 망치나 빠루 둘 다 가지고 오지 않거나, 둘 다 들고 오면 참이 아니다.
| P | Q | P ∨ Q | ~(P ∧ Q) | (P ∨ Q) ∧ ~(P ∧ Q) |
| T | T | T | F | F |
| T | F | T | T | T |
| F | T | T | T | T |
| F | F | F | T | F |
수학(하) 에서의 집합단원의 대칭차집합과 대응된다고 볼 수 있다.
3.3. 연언 (AND; ∧, &)
連言 Conjunction 논리곱 ([math(\wedge)] 혹은 [math(\&)]) [8][math(P\wedge Q)]는 [math(P)], [math(Q)] 모두 참일 때에만 참이다. 이때 [math(P)]와 [math(Q)]를 "연언지(conjunct)"라고 부른다. 한국어에선 "-와/과 -", "-이고 -다", "-이며 -다" 등에 대응한다. 예를 들어 "망치와 빠루를 가져와라"라고 했을 때, 망치와 빠루 모두 들고 와야 참이 되는 것과 같다. [math(\sim)]와 [math(\vee)]를 이용해 나타내면 [math({\sim}({\sim}P\vee{\sim}Q))]이다.
| P | Q | P ∧ Q |
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
3.4. 조건문(If ... Then ...; →, ⊃, Ɔ[9])
실질 조건문(material conditional) ([math(\to)], [math(\supset)], [math(\text{Ɔ})])[math(P\to Q)]는 [math(P)]가 거짓이거나 [math(Q)]가 참인 경우 오직 그 경우에 참이다. 즉 [math(P)]가 참이고 [math(Q)]가 거짓인 경우를 제외하면 모두 참이다. 이때 [math(P)]를 "전건(antecedent)", [math(Q)]를 "후건(consequent)"이라고 부른다.
| P | Q | P → Q |
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
동치 문서에도 나와 있듯이, 실질 조건 문장은 정의상 선언 문장과 논리적 동치다.
[math(\left(p\to q\right)\equiv\left(\neg p\vee q\right))]
3.4.1. 자연 언어 조건문과의 괴리
조건문은 영어의 "If --- then ..." 구문이나 한국어의 "만약 ---면, ...다" 같은 표현에 대응한다. 하지만 실질 조건문은 이런 자연 언어의 쓰임새를 포착하는데 실패하고는 한다. 다음이 그 대표적인 예시다."만약 태양계 행성이 5개라면, 라멘의 원조는 일본이 아니다."
실질 조건문으로 분석할 경우 해당 문장은 참이다(진리표의 5행에 해당;F, F, T). 태양계 행성은 5개가 아니기 때문이다. 하지만 사람들은 대개 그러한 결과를 부조리하게 여긴다.
3.5. 쌍조건문(If and Only If; ↔, iff)
쌍조건문(biconditional)[math(P\leftrightarrow Q)]는 '[math(P)]인 경우 그리고 그 경우에만 [math(Q)]이다'라는 의미이다. '[math(P)]와 [math(Q)]가 동치이다', '[math(P)]이면 [math(Q)]이고 [math(Q)]이면 [math(P)]이다'와 같이 표현하기도 한다. [math((P\to Q)\;\&\;(Q\to P))]와 동치이다. [math(P)]와 [math(Q)]의 진리값이 같을 때 T가 할당된다.
예를 들어서, '누군가 총각인 경우에 오직 그 경우에만 결혼하지 않은 남자다'라는 문장은 쌍조건문이다.
| P | Q | P ↔ Q |
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
3.6. 모순(Contradiction; ⊥, c)[10]
'Falsum' 혹은 'Bottom'이라고도 부른다. 무조건 거짓. 무조건 참은 "Top"이라고도 부르며 [math(\top)]를 쓴다. 참은 True의 T or t모양을 따왔고, 거짓은 이 모양을 뒤집은 것이다. 표준적인 명제논리에서는 연결사가 아니다.4. 추론과 명제논리 추론 규칙
귀결이 문장과 문장 사이의 의미론적 관계를 다룬다면, 추론(inference) 혹은 도출(deriviation)은 오직 형식적인 관계만을 다루는 것이다. 다른 표현으로 하자면 귀결은 의미론적(semantic) 작업이고 추론은 통사론적(syntactic) 작업이다. 추론은 귀결과는 달리 문장의 진리값이나 해석에 의존하지 않는다. 오직 형식적인 규칙만을 따라 수행하는 작업일 뿐이다. 그리고 그러한 형식적 추론이 의미론적인 귀결 관계를 보장한다는 것은 건전성 정리에 의해 증명되어 있다.공집합으로부터 추론가능한 문장을 논리학적 정리라고 하며, 논리학적 정리인 문장은 논리적으로 타당하다. 즉, 모든 해석 하에서 참이다.
이하 내용은 명제 논리의 추론/증명 체계 중 하나인 게르하르트 겐첸(Gerhard Gentzen)[11]의 자연 연역(Natural Deduction) 방식을 소개한 것이다. 자연연역과 동등하게 강력한 추론/증명 체계로 역시 겐첸이 고안한 귀결 연산(sequent calculus)이 있고, 이와 살짝 다른 방식으로는 힐베르트 체계(Hilbert system)가 있다.
아래 규칙에서 E는 제거(elemination), I는 도입(Introduction)을 뜻한다. [math(P\Rightarrow Q)]는 명제 [math(Q)]가 가정 [math(P)]에 의존한다는 것을 뜻하는 반면, [math(P_{1},\,P_{2}\vdash Q)][12]는 [math(P_{1})], [math(P_{2})]로부터 [math(Q)]를 추론해낼 수 있다는 규칙을 나타낸다[13].
이하의 추론 규칙들은 원칙적으로 메타 문장인 그리스 문자로 기술해야 하지만, 편의상 영문 대문자로 대체한다.
4.1. 전건 긍정
[math({\to}{\rm E}:P\to Q,\,P\vdash Q)]
Modus Ponens조건문이 참이고 그 전건이 참이라면, 후건은 참이다. [math({\rm MP})](modus ponens)라고 쓰기도 한다
| 한국어 추론 예시. 만일 눈이 온다면, 스키를 타러갈 수 있다. 눈이 온다. 스키를 타러갈 수 있다. |
4.1.1. 가언 삼단논법
[math({\rm HS}:P\to Q,\,Q\to R\vdash P\to R)]
Hypothetical syllogism| 한국어 추론 예시 만일 비가 온다면, 소풍을 가지 않는다. 만일 소풍을 가지 않는다면, 우리는 학교에 가야된다. 만일 비가 온다면, 우리는 학교에 가야된다. |
4.2. 후건 부정
[math({\rm MT}:P\to Q,\,\neg Q\vdash\neg P)]
Modus Tollens| 한국어 추론 예시. 만일 늦게 일어난다면, 너는 지각을 할 것이다. 너는 지각을 하지 않았다. 너는 늦게 일어나지 않았다. |
4.3. 조건 도입
[math({\to}{\rm I}:P\Rightarrow Q\vdash P\to Q)]
Conditional Proof[math({\rm CP})]라고도 한다. 주어진 전제로부터 어떤 명제를 도출할 수 있다면, 전제 [math(P)]를 전건(antecedent)으로, 도출된 명제 [math(Q)]를 후건(consequent)으로 갖는 조건문이 증명가능하다.
유사 사례: 어떤 문장이 앞서서 나타난다면, 그 문장을 후건으로 갖는 조건문을 쓸 수 있다. 이것은 1차 술어논리의 추론 규칙으로 활용된다.
4.4. 선언 제거
[math(\vee{\rm E}:P\vee Q,\,P\to R,\,Q\to R\vdash R)]
Disjunction elimination양도논법이라고도 한다.
| 한국어 추론 예시. 나는 혼자 여행을 가든지 도서관에 갈 것이다. 만일 내가 혼자 여행을 가면, 나는 외로울 것이다. 만일 내가 도서관에 가면, 나는 외로울 것이다. 나는 외로울 것이다. |
4.4.1. 선언적 삼단논법
[math({\rm DS}:P\vee Q,\,\neg P\vdash Q)][14]
Disjunctive syllogism선언지 제거라고도 한다.
| 한국어 추론 예시 내가 결혼을 하는 것은 꿈이든지 현실이다. 내가 결혼을 하는 것은 꿈이 아니다. 내가 결혼을 하는 것은 현실이다. |
4.4.2. 복합 양도 논법
[math({\rm CD}:P\to Q,\,R\to S,\,P\vee R\vdash Q\vee S)]
Constructive dilemma| 한국어 추론 예시 나는 결혼을 하든지 독신으로 살 것이다. 만일 내가 결혼을 한다면, 부모님께서 서운해 하실 것이다. 만일 내가 독신으로 산다면, 내 남자 친구가 서운해 할 것이다. 부모님께서 서운해 하시든지, 내 남자 친구가 서운해 할 것이다. |
4.5. 선언 도입
[math(\vee{\rm I}:P\vdash P\vee Q:P\vdash Q\vee P)]
Disjunction introduction[15]한 명제가 참이라면, 이 명제를 부분으로 갖는 선언문은 참임을 의미한다.
| 한국어 추론 예시. 바람이 분다. 바람이 불거나 비가 온다. |
4.6. 연언 제거
[math(\wedge{\rm E}:P\wedge Q\vdash P:P\wedge Q\vdash Q)]
Conjunction elimination[16]한 연언문이 참이라면, 그 연언문을 구성하는 부분 명제들은 모두 참이다.
| 한국어 추론 예시. 바람이 불고, 비가 온다. 바람이 분다. |
4.7. 연언 도입
[math(\wedge{\rm I}:P,\,Q\vdash P\wedge Q)]
Conjunction introduction[17]참인 명제들로 구성되는 연언문은 참이다.
| 한국어 추론 예시. 바람이 분다. 비가 온다. 바람이 불고, 비가 온다. |
4.8. 간접 귀류법
[math(\neg{\rm E}:\neg P\Rightarrow\bot\vdash P)]
직관주의자들은 이 규칙을 거부한다. 거칠게 설명해, 명제 [math(P)]의 부정에 대한 부정이 증명되더라도 명제 P가 증명가능한 것은 아니기 때문이다. 직관주의 논리에서 [math(\neg P)]의 증명이 존재하기 위한 필요충분조건은 [math(P\to\bot)]의 증명[18]이 존재하는 것이다. 따라서, [math(\neg\neg P)]가 증명가능하다는 것은 [math(\neg P\to\bot)]의 증명이 존재하는 경우이고, 이로부터 [math(P)]에 대한 증명이 있으리라는 보장이 없기 때문에, 직관주의 논리에서 간접적 귀류법은 논리적 법칙이 될 수 없다. 직관주의 논리에서 참 개념이 증명가능 개념으로 대체된다는 것을 안다면 위 설명이 이해가 될 것이다.
| 한국어 추론 예시. 만일 불치병의 환자가 웃으면, 그 주변사람들은 기쁘면서도 기쁘지 않았다. 불치병의 환자는 웃지 않았다.[19] |
4.8.1. 이중 부정 제거
[math(\neg\neg{\rm E}:\neg\neg P \vdash P)]
| 한국어 추론 예시 소크라테스가 죽지 않았다는 것은 거짓이다. 소크라테스는 죽었다. |
4.8.2. 간접 추리법
[math(P\to\neg P\vdash\neg P)]
유사 사례로 '클라비우스의 법칙'이 있다: [math((\neg P \to P) \vdash P)]
| 한국어 추론 예시 만일 이 결혼이 행복한 것이라면, 이 결혼은 행복한 것이 아니다. 이 결혼은 행복한 것이 아니다. |
4.9. 직접 귀류법
[math(\neg{\rm I}:P\Rightarrow\bot\vdash\neg P)]
조건 도입규칙의 한 예로 볼 수 있다.
4.10. 폭발 원리
[math(\bot{\rm E}:\bot\vdash P)]
Principle of explosion, Ex Falso Quodlibet[20]이것은 직관주의 논리학에서 받아들이는 원리로, 표준적인 자연연역 체계에서는 도출 규칙으로 다루지 않는다. 간단히 설명하면, 모순으로부터 모든 명제가 도출된다는 것이다. 직관주의 논리가 아닌 자연연역에서는 도출 규칙이 아닌 정리로, 다음과 같이 증명된다.
- [math(P\wedge\neg P)] (전제)
- [math(P\wedge\neg P\vdash P)] (연언 제거)
- [math(P\vdash P\vee Q)] (선언 도입)
- [math(P\wedge\neg P)](전제) [math(\vdash\neg P)] (연언 제거)
- [math(P\vee Q,\,\neg P\vdash Q)] (선언적 삼단논법)
- [math(\therefore P\wedge\neg P\vdash Q)]
쉽게 풀어서 설명해보면,
- 서로 모순되는 두 명제를 만들고, 둘다 참이라고 가정한다.
(예: 삼각형의 내각의 합은 180도다. 삼각형의 내각의 합은 180도가 아니다.) - 다음으로 방금 만든 명제를 이용해 선언명제를 하나 만든다.
(예: 삼각형의 내각의 합은 180도이거나 1=2이다.) 이 명제의 전건이 참이므로 후건의 내용과 상관없이 이 명제는 참이다. - 그러나 처음에 '삼각형의 내각의 합이 180도가 아니다'라는 명제 역시 참이라고 했으므로 이 선언명제의 전건은 거짓이다.
- 방금 이 선언명제가 참이라는 것을 증명했으므로 전건이 거짓인데도 참이 되기 위해서는 후건(1=2이다) 역시 참이 되어야 한다.
- (2)~(4)를 통해 명제 '1=2이다'는 참으로 증명되었다.
이는 중세 논리학에서 이미 발견되고 있는 증명으로, 중세 논리학 교과서에는 다음과 같은 증명이 실려 있다.
| 소크라테스는 죽었으며 죽지 않았다고 가정하자. 소크라테스는 죽었다. 소크라테스는 죽었거나 막대는 구석에 세워져 있다. 소크라테스는 죽지 않았다. 막대는 구석에 세워져 있다. |
이처럼 모든 명제는 모순의 귀결이기 때문에, 표준적인 논리 체계 하에서 모순이 타당할 수 있다고 인정하게 되면 그 논리체계는 모든 문장이 참이 되는 공허한 체계가 된다. 대신 보조도출에서 모순을 참으로 가정하고 그로부터 결론을 이끌어내는 방식은 사용할 수 있다.
5. 추론 전략
모든 명제 논리의 증명을 기계적인 알고리즘을 통해 해결하는 방법은 존재하지 않는다. 그렇기 때문에 명제 논리의 증명에는 직관력이 필요할 수밖에 없다. 그러나 직관의 필요성을 인정한다고 할지라도, 효과적인 전략을 제시할 수 없는 것은 아니다. 이하의 전략은 많은 논리적 증명에서 유효하게 사용될 수 있다.- 선언문이 나오면 선언 제거를 활용하라.
- 얻고자 하는 문장과 반대되는 가정을 한 다음 그로부터 가정의 부정을 도출하기 위해 귀류법을 활용하라.
(예: 주어진 전제로부터 [math(P)]를 얻고자 한다면 일단 [math(\neg P)]를 가정하고, [math(\neg 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. 논리적 동치
표준 명제 논리에서 문장 [math(\phi)]와 [math(\psi)]가 논리적 동치인 것의 필요충분조건은 다음과 같다:- 의미론/모형이론적 규정: [math(\phi \leftrightarrow \psi)]이 타당함(i.e. 모든 모형에서 참임).
- 구문론/증명이론적 규정: [math(\phi \vdash \psi,\, \psi \vdash \phi)]
명제 논리에서 도출되는 대표적인 논리적 동치 사례들을 참조하기 위해선 해당 링크 참조
7. 관련 문서
[1] 엄밀히 말해서는 등호(=)는 성립하지 않으며, 그 대신 기호 'P'가 명제 <소크라테스는 사람이다>를 지시하는 이름인 것으로 규정되어야하나, 편의상 위와 같은 표기법을 사용한다[2] 논리 연결사로 구성된 복합 명제를 만들 때 부정의 기능을 하는 논리 연결사 '[math(\sim)]'는 항상 그것이 부정하려는 명제 앞에 놓여야 한다. 예를 들면 “그들은 우리집에 왔다.([math(p)])”는 문장을 부정한다고 해보자. 그러면 그 문장의 부정은 '[math({\sim}p)]'로 표현될 수 있다. 또한 괄호로 묶인 복합명제의 경우에는 괄호로 묶인 명제 전체를 부정한다. 예를 들면, “그들은 우리 집에 왔으며, 우리는 그들에게 접대를 했다.([math(p\;\&\;q)])”는 명제의 부정은 [math({\sim}(p\;\&\;q))]로 표현한다. 명제논리에서는 명제가 애매하지 않도록 괄호를 사용한다. 이는 수학에서 괄호를 쓰는 방식과 같다.[a] 한국논리학회, 국제논리학협회 표준[a] [5] 더 줄여 iff로 쓰기도 한다[6] [math(\begin{aligned}1+1&=1\\1+0&=1\\0+1&=1\\0+0&=0\end{aligned})][7] 학제적으로 전문성과 엄밀성이 필요한 분야일수록 이러한 경향성은 잘 나타나지 않는다. 대표적으로는 형법에서의 "m년 이하의 징역 또는 n원 이하의 벌금"이 있다.[8] [math(\begin{aligned}1\times0&=0\\0\times1&=0\\1\times1&=1\\0\times0&=0\end{aligned})][9] 이때 '⊃'는 집합론에서의 진부분집합을 나타내는 기호와 생김새가 비슷하지만 완전히 다른 개체임에 유의할 것. 즉 변항이 명제라는게 확실한 경우 "[math(\phi)]⊃[math(\psi)]"라는 표현을 볼 경우 이건 (수학처럼) "[math(\phi\leftarrow\psi)]"로 봐야 하는 게 아니라 정반대인 "[math(\phi\to\psi)]"로 이해해야한다. 따라서 "[math(P\to Q)]"는 "[math(P)]⊃[math(Q)]"와 같은 의미지, 수학에서 흔히 알고 있는 "[math(P\subset Q)]"가 아니다. "[math(\phi)]이면 [math(\psi)]다"라는 조건문이 부분집합 관계와 같은 것으로 생각하기 쉽기에 "[math(\phi\to\psi)]"를 "[math(\phi\subset\psi)]"라고 써야한다고 착각할 수 있다. 이 때문에 해외에서는 [math(\text{Ɔ})]로 구분해서 쓰는 경우도 있었다.[10] 모순은 하나의 명제로 도입될 수 있지만, 무조건 거짓을 뱉는 연산자로 볼 수도 있다.[11] 1909년에 태어난 독일의 수학자이자 논리학자로 헤르만 바일, 폴 베르나이스, 힐베르트 같은 당대 최고 석학들의 가르침을 받았다. 스승인 힐베르트의 공리체계와는 다른 방식의 증명체계들을 제시한 것과 초한귀납법을 써서 산술의 일관성을 증명한 것(Consistency Proof)이 주요업적이다. 이렇듯 젊은 나이에 뛰어난 재능을 발휘한 천재였지만 나치당에 가입해 돌격대로 활동하였고 V-2 계획에도 참여한 흑역사가 있다. 1943년 독일이 점령한 체코의 프라하 대학교의 교수로 임용되어 프라하에서 생활하다가 전후 학교 직원들과 함께 체포된다. 이후 소련군에 넘겨졌다가 나치에 협력한 전력 때문에 수용소로 보내져 1945년 35세의 젊은 나이에 영양실조로 사망한다.[12] [math(\vdash)] 기호는 앞에서 소개한 명제논리의 연결사들이 아니라 명제논리에 속하는 명제들 사이의 추론관계를 나타내기 위해 사용된 메타언어의 기호라는 것에 유의할 것.[13] 소거 규칙은 한 명제를 그 명제를 구성하는 부분적인 명제들로, 도입 규칙은 여러 명제를 합해 하나의 복합적인 명제를 만든다고 볼 수 있다. 예를 들어 Modus Ponens 규칙은 한 조건문과 그 조건문의 전건을 (참이라고)가정했을 때, 전제된 조건문의 후건이 참임을 추론한다. 이러한 추론규칙의 적용을 통해 조건문이 더 간단한 명제로 분해되는 것이다. 또한 이러한 규칙들은 그 자체로 타당한 논증의 형식을 가진다. 따라서 주어진 전제에 아래의 규칙들을 올바르게 적용하여 어떤 명제를 도출할 수 있다면, 기존의 전제들과 이로부터 도출한 명제를 결과로 갖는 논증은 타당하다.[14] [math(P\vee Q,\,P\vdash\neg Q)]는 논리적으로 맞지 않는 추론이다. 예를 들어, '모 위키러는 스 1 유저이거나 스 2 유저이다.'라는 문장에서, 그 위키러가 스 1 유저이면서 동시에 스 2 유저일 수 있으므로 '그 위키러는 스 1 유저이기 때문에 스 2 유저가 아니다'는 옳지 않은 추론이다. 하지만 '모 위키러는 중학생이거나 고등학생이다'라는 문장에서는, '중학생'과 '고등학생'이 상호 배타적이므로, 이때는 중학생을 긍정함으로써 그 위키러가 고등학생이 아니라는 것을 유도할 수 있다.[15] Add(Addition)이라고도 한다.[16] Simp(Simplication)이라고도 한다.[17] 줄여서 Conj(Conjunction)이라고도 한다.[18] [math(P)]의 증명이 input일 때 [math(\bot)]의 증명을 output으로 내놓는 함수, 혹은 방법[19] 엄밀히 말하자면 해당 추론은 조건화 증명을 한번 거친 것이다.[20] 라틴어로, 거짓으로부터 좋을대로라는 의미다. 말 그대로의 의미.