영어: mathematical logic
목차
1 개요
논리학을 수학의 기호 및 기법을 통하여 연구하는 논리학과 수학의 하위 학문 혹은 방법론. "기호 논리학"'와 같은 의미로 쓰이거나 그 일부로 여겨진다[1]
수학에선 집합론과 더불어 수학 기초론을 이루는 중요한 부분 중 하나. 컴퓨터과학과 철학에서도 핵심적인 소양 중 하나로 여겨진다.
일반적으로는 연역 논리에 한정되며[2], 본 문서에서도 연역 논리, 그중에서도 표준논리(standard logic)에 관한 내용만을 다룬다.
표준논리의 개념들은 대부분 일상 언어의 어휘들로부터 비롯된 것이다. 예를 들어 논리연산자 "∨"는 한국어 "혹은", 영어 "or"에서 비롯되었다. 그렇지만 논리학, 특히 표준 논리 개념들의 뜻은 그 본래 일상 언어 어휘의 쓰임새와 괴리가 있는 경우가 잦다. 아래에 설명된 선언문, 실질 조건문, 보편양화사의 존재함축 문제 참조. 그러므로 일상 언어 문장을 논리식으로 번역하거나, 혹은 반대로 논리식을 일상언어로 이해할 때에는 주의를 요한다.
2 역사
라이프니츠에 의해 기호를 통한 연역하는 체계에 대한 아이디어가 처음 개진되었다. 이후에 조지 불에 의해 논리를 대수처럼 계산하는 체계가 제시되었다. 이 때의 논리학은 명제의 내용 대신 진리치만 다룰 수 있는 정도였으나 프레게의 개념 표기, 그리고 찰스 샌더스 퍼스의 작업들에 의해 의해 독자적으로 양화논리가 개발되어 모든 수학적 명제의 내용도 기호로 나타내 형식적인 증명을 할 수 있게 되었다. 그 후 버틀란드 러셀과 알프레드 노스 화이트헤드의 명저 수학원리에서 모든 수학명제들을 논리학의 법칙들에서 연역하려는 시도가 큰 성과를 보임으로써 수학계와 철학계의 관심을 받게 되었다.
3 명제 논리
명제논리(propositional logic)는 명제 혹은 문장들 간의 논리적 관계를 다룬다. 즉 예를 들어 <소크라테스는 사람이다>라는 명제를 기호화한다면, 이를 그냥 통째로 "P"로 표시할 뿐 더이상 쪼개 들어가질 않는다. 이런 명제들은 알파벳 대문자 (e.g. P, Q, R ...)로 기호화하는 것이 관례다.
[math] [/math]
| 예시: ([math]P[/math] = "소크라테스는 사람이다", [math]Q[/math]= "지구는 행성이다")[4]: * "소크라테스는 사람이고, 지구는 행성이다" ⇒ "[math] P \wedge Q[/math]" * "소크라테스가 사람이 아니라면, 지구는 행성이거나 소크라테스는 사람이 아니다" ⇒ "[math]\neg P \to (Q \vee \neg P)[/math]" |
명제논리는 결정가능(decidable)하다. 즉 임의의 명제 논리식이 타당한지 (혹은 두 명제 논리식 간에 논리적 도출 관계가 성립하는지) 여부는 기계적으로 판단할 수 있다. 아래에서 설명될 진리표(truth-table)을 사용하는 것이 그런 기계적 판단 방식의 대표적인 예시다.
3.1 명제논리 연결사
명제 논리에서 연결사(connective)는 한 개 이상의 명제 기호에 덧붙여짐으로써 해당 명제(들)에 새로운 의미를 더한다. 꼭 복수의 명제들을 '연결'할 필요없이 하나의 명제에만 붙는 연결사도 있음을 유의하라(예. ~).
아래에 언급된 명제 연결사들은 일반적으로 명제 논리에서 등장하는 연결사들이며, 각 항목에서 진리표는 피연산자의 진리치(참=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]가 [math]\neg, \to[/math]에 의해 정의될 수 있음은 명백하며, 극단적으로는 하나의 연결사만으로도 모든 명제 논리를 포괄하는 것도 가능하다(예. Sheffer Stroke '|').
3.1.1 부정 (NOT; ¬, ~)
Negation ([math]\sim[/math] 혹은 [math]\neg[/math])
- 한국어에선 "-가 아니다"에 대응한다. P가 참이면 ~P는 거짓, P가 거짓이면 ~P는 참이다.
| P | ~P |
| T | F |
| F | T |
3.1.2 선언 (OR; ∨)
選言 Disjunction 논리합 ([math]\vee[/math])
- P∨Q라고 하면 P, Q 중 적어도 하나는 성립한다는 것을 뜻한다. 둘 중 하나만 성립하는 것이 아니며, P와 Q 둘 모두 성립해도 된다. 이때 P와 Q를 "선언지(conjunct)"라고 부르기도 한다. 진리표는 다음과 같다.
| P | Q | P ∨ Q |
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
"∨"는 한국어의 "혹은", 영어의 "or"에 대응하는 것 같지만, 일상 언어 표현들의 경우 두 선언지 가운데 하나를 선택해야만 하는 것 같은 직관이 있다. 예를 들어 "빵을 드시겠습니까, 혹은 밥을 드시겠습니까?"라고 물어봤을 땐 빵과 밥 중 하나만을 선택해야할 것 같다. 하지만 위에서 나타나다시피 "∨"를 쓴 문장인 "(빵을 먹는다) ∨ (밥을 먹는다)"는 빵만 먹어도, 밥만 먹어도, 빵과 밥을 둘 다 먹어도 참이다.
3.1.2.1 배타적 선언 (XOR; ⊕)
Exclusive OR 배타 논리합 ([math]\oplus[/math]')
- '둘 중 하나'만을 지시하는 선언문. 즉 "P⊕Q"가 참이면 P와 Q 둘 중 하나만 참이다. 이는 ∧와 ∨ 기호를 통해 정의될 수 있다. 즉 "P⊕Q"는 "(P∨Q)∧~(P∧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 |
P와 Q 모두 참일 때는 거짓임을 볼 수 있다. 또한 P∨Q는 ~(~P∧~Q)와 동치이므로, 선언문은 ∧와 ~만을 이용해 나타낼 수도 있다.
3.1.3 연언 (AND; ∧, &)
連言 Conjunction 논리곱 ([math]\wedge[/math] 혹은 [math]\&[/math])
- P ∧ Q는 P, Q 모두 참일 때에만 참이다. 이때 P와 Q를 "연언지(conjunct)"라고 부른다. 한국어에선 "-와/과 -", "-이고 -다", "-이며 -다" 등에 대응한다. 예를 들어 "망치와 빠루를 가져와라"라고 했을 때, 망치와 빠루 모두 들고 와야 참이 되는 것과 같다. ~와 ∨를 이용해 나타내면 ~(~P∨~Q)이다.
| P | Q | P ∧ Q |
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
3.1.4 조건문(If ... Then ...; →, ⊃)[5])
실질 조건문(material conditional) ([math]\to[/math] 혹은 [math]\subset[/math])
- P → Q는 P가 거짓이거나 Q가 참인 경우 오직 그 경우에 참이다. 즉 P가 참이고 Q가 거짓인 경우를 제외하면 모두 참이다. 이때 P를 "전건(antecedent)", Q를 "후건(consequent)"이라고 부른다. 조건문 "P → Q"는 "~P∨Q"와 동치다.
| P | Q | P → Q |
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
조건문은 영어의 "If ... then ..."이나 한국어의 "만약 -면, ...다" 같은 표현에 대응하지만, 그 일상 언어에서의 직관적 쓰임새에 항상 부합하지는 않는다. 다음 두 예시를 참조하라:
- 성공적인 예시: "만약 철희가 소년이라면, 철희는 남자다"는 "(철희가 소년이다) → (철희는 남자다)"로 표현될 수 있을 법하며, 이는 적절해 보인다. 왜냐면 이 문장은 실제로 철희가 소년이고 남자일 때 명백히 참인 것으로 보이며, 동시에 철희가 소녀인 경우에도 해당 문장은 (전건이 애초에 만족되지 않으므로) 참으로 보는게 그럴 법하기 때문이다.
- 실패하는 예시: 반면 "만약 태양계 행성이 5개면, 라멘은 맛있다"라는 문장을 생각해보자. 이 문장의 의미가 "(태양계 행성이 5개다) → (라멘은 맛있다)"와 같다고 한다면, "만약 태양계 행성이 5개면, 라멘은 맛있다"는 참된 문장이다. 왜냐면 태양계의 행성은 8개이기 때문이다. 하지만 이는 매우 부조리한 것 같다.
두 번째 사례의 경우 "만약 - 면, -다"라는 형식을 띠고 있음에도 불구하고 실질 조건문의 논리적 특성에 잘 부합하지 않음을 알 수 있다. 해당 사례를 설명하기 위해 언어철학자들은 양상논리를 도입한 엄밀 조건문(strict conditional) 개념을 적용시킨다. 또한 "직설법 조건문(indicative conditional)" 혹은 "가정법 조건문(subjunctive conditional)" 같은 유형들 또한 별도로 구분되어 이해되어야만 한다.
더 직관적으로 이해하고 싶다면 조건문을 의미하도록, 집합 P가 집합 Q의 부분집합이라는 명제를 벤다이어그램을 그려보자.
이때, 집합 내부에 x표시를 해보면 가능한 표시는 1) P, Q가 모두 참인 경우, 2) P가 거짓, Q가 참인 경우, 3) P,Q 모두 거짓인 경우 밖에 없다.
메타적으로 봤을 때, 'P가 Q의 부분집합이라는 명제'와 'P가 참일 때 Q가 거짓이라는 명제'는 모순이기 때문에 그려보는 것이 논리적으로 불가능하다.
3.1.5 모순(Contradiction; ⊥)[6]
"Bottom"이라고도 부른다. 무조건 거짓. 무조건 참은 "Top"이라고도 부르며 [math]\top[/math]를 쓴다. 참은 True의 T 모양을 따왔고, 거짓은 이 모양을 뒤집은 것이다.
3.2 명제논리의 추론 규칙
이하 내용은 명제 논리의 추론/증명 체계 중 하나인 게르하르트 겐첸(Gerhard Gentzen)의 귀결 연산(sequent calculus) 방식을 소개한 것이다. 귀결 연산과 동등하게 강력한 추론/증명 체계로 자연 연역(Natural Deduction)이 있고, 또한 살짝 다른 방식으로는 힐베르트의 공리적 체계 등이 있다.
귀결 연산 체계 규칙에서 E는 소거(elemination), I는 도입(Introduction)을 뜻한다. [math]P\Rightarrow Q[/math]는 명제 [math]Q[/math]가 가정 [math]P[/math]에 의존한다는 것을 뜻하는 하나의 행(sequent)에 해당하는 반면, [math]P_{1},\,P_{2}\vdash Q[/math]는 [math]P_{1}[/math], [math]P_{2}[/math]로부터 [math]Q[/math]를 추론해낼 수 있다는 규칙을 나타낸다[7].
- ∨E
[math]P \vee Q, P\Rightarrow R, Q\Rightarrow R\vdash R[/math]
- ∨I[8]
[math]P\vdash P\vee Q[/math]
[math]P\vdash Q\vee P[/math]
- ∧E[9]
[math]P\wedge Q\vdash P[/math]
[math]P\wedge Q\vdash Q[/math]
- ∧I[10]
[math]P,\,Q\vdash P \wedge Q[/math]
- →E[11]
[math]P,\,P\to Q\vdash Q[/math]
- →I[12]
[math]P\Rightarrow Q\vdash P\to Q[/math]
- ⊥E
[math]\vdash \perp\to P[/math]
- ⊥I
[math]P,\,\neg P\vdash \perp[/math]
- ￢E[13]
[math]\neg P\Rightarrow \perp\vdash P[/math]
- ￢I
[math]P\Rightarrow \perp\vdash\neg P[/math]
4 양화 논리 (혹은 '1차 술어 논리')
1차 술어 논리(first-order predicate logic) 혹은 양화 논리(quantificational logic)은 명제논리를 확장한 것이며, 명제를 쪼개서 대상과 술어 간의 관계까지 기호화하는 체계에 해당한다. 즉 예를 들어 <소크라테스는 사람이다>가 명제논리에서는 "P"로 표시된 반면, 양화 논리에서는 "Qs"라고 표현될 것이다. 양화 논리에서 술어(F, G, H ...)는 영문 대문자로, 특정 대상은 영문 소문자(a,b,c)로 표기하는 것이 관례다.
또한 명제논리와는 달리 술어논리에서는 대상들을 논항으로 갖는 변항(variable)이 등장한다. 예를 들어 "사람인 무언가"는 "Hx"라고 표기될 수 있다. 변항은 일반적으로 x, y, z 등으로 표기한다.
- 예시: (H = "사람이다", P = "행성이다", s = "소크라테스", e = "지구"):
- "소크라테스는 사람이고, 지구는 행성이다" ⇒ "Hs & Pe"
- "소크라테스가 사람이 아니라면, 지구는 행성이거나 소크라테스는 사람이 아니다" ⇒ "~Hs → (Pe ∨ ~Hs)"
- "소크라테스가 사람이면, 어떤 사람이 있다" ⇒ "Hs → ∃xHx"
- "모든 것이 행성이거나, 혹은 지구는 행성이 아니다." ⇒ "∀xPx ∨ ~Pe"
양화논리는 결정가능하지 않다. 따라서 양화논리의 경우 진리표 같은 기계적 방식을 통하여 타당성 혹은 논리적 귀결 관계를 판단할 수 없다.
4.1 양화논리 연결사
양화 논리의 대표적인 연결사로는 양화사(Quantifier)들이 있다. 양화사는 특정한 술어를 만족시키는 대상들이 주어진 논의영역(domain; universe of discourse)에 얼마나 있는지를 알려주는 의미를 갖는다.
- 존재양화사 [math]\exists[/math]
-한 것이 존재한다(exist). "Exist"의 E를 뒤집어서 따왔다.- 예. "파랑색이면서 둥그런 것이 존재한다" ⇒ "∃x(Bx & Cx)"
- 보편양화사 [math]\forall[/math]
모든 것이(all) -하다. "All"의 A를 뒤집어서 따왔다.- 예. "모든 것은 파랑색이면서 동그랗다" ⇒ "∀x(Bx & Cx)"
일반적으로 존재양화사(∃) 문장은 일상 언어에서의 "어떤 P는 Q다", "P인 것이 있다", 보편양화사(∀)는 "임의의 P는 Q다", "모든 것은 P다"에 대응하는 것으로 여겨진다. 하지만 임의의 술어 P에 대하여 일상언어 문장인 "만약 모든 P가 Q이면 어떤 P는 Q이다"라는 문장은 논리적으로 타당해보이지만, "∀x(Px → Px) → ∃x(Px & Qx)"는 논리적으로 타당하지 않다. 즉 양화사 또한 일상 언어에서의 직관과 괴리가 있다. 보다 자세한 사항은 존재함축 참조.
더불어 양화논리에서 추가적으로 도입되는 연결사로는 등호 "="가 있다. 등호는 대상을 가리키는 두 기호가 논의역 내의 동일한 대상을 가리키는 것을 나타내는데 쓰인다.
- 예시1. "관우는 미염공과 같다" ⇒ "g=m"
- 예시2. "관우는 존재한다" ⇒ "∃x(x=g)"
5 고차 논리
고차 논리(higher-order logic)에서는 술어를 양화할 수 있다. 즉 1차 술어 논리에서는 논의영역 내의 대상들을 두고 "모든 대상은 이러하다", "어떤 대상은 저러하다"라고 밖에 표현할 수 없는 반면, 2차 논리 이상의 고차 논리에서는 "모든 속성은 이러하다", "어떤 속성은 저러하다"라는 명제 또한 표현할 수 있다. 예컨대 고차 논리에서는 다음과 같은 명제를 서술할 수 있다:
- 라이프니츠 법칙(Leibniz's law): 모든 속성에서 일치하는 두 대상은 동일하다.
- 기호화: "∀F∀x∀y(((Fx → Fy) & (Fy → Fx)) → x = y)"
- 해석: 임의의 술어 F에 대해 임의의 대상 x와 y가 F를 만족시키는지 아닌지 여부에서 항상 일치하는 경우, x와 y는 같은 대상을 가리킨다.
6 교과 과목
수학과에서는 주로 집합론과 함께 전공과목으로 다루어지지만, 경우에 따라서는 학부에서는 다루지 않기도 한다. 철학과 학부에서도 깊이는 얕지만 전공과목으로 다루는 경우가 있다. 컴퓨터공학과에서는 학부의 경우 이산수학 수업에서 부분적으로 다룬다.
흔히 학부 과정에서 쓰는 교과서로는 수학과의 경우 Herbert Enderton의 A Mathematical Introduction to Logic, 철학과의 경우 Benson Mates의 Elementary Logic (한국어 번역서명 <기호논리학>, 김영정/선우환 역) 등이 있다.
7 참고 항목
보다 자세한 개념들에 관해서는 논리학 관련 정보 참조.
- ↑ 종종 수리 논리학은 철학적 논리학과 구별되어 쓰이고는 하는데, 현대의 철학적 논리학 또한 수학 기호를 적극적으로 받아들이므로 "기호논리학"과 "수리논리학"이 뜻이 아예 같다고 할 경우엔 자칫 오해가 빚어질 수 있다.
- ↑ 엄밀히 따지자면 현대의 공리적 확률론 혹은 비단조(non-monotonic) 논리 등이 그 반례가 될 수 있으나 넘어간다.
- ↑ 해당 문서의 내용과 많은 부분이 겹친다
- ↑ 엄밀히 말해서는 등호(=)는 성립하지 않으며, 그 대신 기호 'P'가 명제 <소크라테스는 사람이다>를 지시하는 이름인 것으로 규정되어야하나, 편의상 위와 같은 표기법을 사용한다
- ↑ 이때 '⊃'는 집합론에서의 진부분집합을 나타내는 기호와 생김새가 비슷하니 주의할 것!
- ↑ 모순은 하나의 명제로 보는 것이 마땅하나, 무조건 거짓을 뱉는 연산자로 볼 수도 있다.
- ↑ 소거 규칙은 한 명제를 그 명제를 구성하는 부분적인 명제들로, 도입 규칙은 여러 명제를 합해 하나의 복합적인 명제를 만든다고 볼 수 있다. 예를 들어 Modus Ponens 규칙은 한 조건문과 그 조건문의 전건을 (참이라고)가정했을 때, 전제된 조건문의 후건이 참임을 추론한다. 이러한 추론규칙의 적용을 통해 조건문이 더 간단한 명제로 분해되는 것이다. 또한 이러한 규칙들은 그 자체로 타당한 논증의 형식을 가진다. 따라서 주어진 전제에 아래의 규칙들을 올바르게 적용하여 어떤 명제를 도출할 수 있다면, 기존의 전제들과 이로부터 도출한 명제를 결과로 갖는 논증은 타당하다.
- ↑ Add(Addition)이라고도 한다. 한 명제가 참이라면, 이 명제를 부분으로 갖는 선언문은 참임을 의미한다.
- ↑ Simp(Simplication)이라고도 한다. 한 연언문이 참이라면, 그 연언문을 구성하는 부분 명제들은 모두 참이다.
- ↑ Conj(Conjunction)이라고도 한다. 참인 명제들로 구성되는 연언문은 참이다.
- ↑ modus ponens, MP라고 불리기도 한다. 조건문이 참이고 그 전건이 참이라면, 후건은 참이다.
- ↑ CP(Conditional Proof)라고도 한다. 주어진 전제로부터 어떤 명제를 도출할 수 있다면, 전제를 전건으로, 도출된 명제를 후건으로 갖는 조건문이 증명가능하다.
- ↑ 귀류법, 더 정확하게 말하자면 간접적 귀류법이다. 직관주의자들은 이 규칙을 거부한다. 거칠게 설명해, 명제 P의 부정에 대한 부정이 증명되더라도 명제 P가 증명가능한 것은 아니기 때문이다. [math]\neg P[/math]의 증명이 존재하기 위한 필요충분조건은 [math]P\to \perp[/math]의 증명(혹은 함수)이 존재하는 것이다. 따라서, [math]\neg\neg P[/math]가 증명가능하다는 것은 [math]\neg P\to \perp[/math]의 증명이 존재하는 경우이고, 이로부터 [math]P[/math]에 대한 증명이 있으리라는 보장이 없기 때문에, 직관주의 논리에서 간접적 귀류법은 논리적 법칙이 될 수 없다. 직관주의 논리에서 참 개념이 증명가능 개념으로 대체된다는 것을 안다면 위 설명이 이해가 될 것이다.