선행학습 · PREREQUISITE
기초 논리
Basic Logic
원문 : blog.naver.com/cki_math_lab/220730009313
序
논리 공부란 타당하지 않는 논증으로부터 타당한 논증을 구별하는 데 쓰이는 원리와 방법을 익히는 일이다.
이 예비 장에서의 논리 공부의 목적은 학생들로 하여금 논증의 증명의 각 단계에서 이용되고 있는 원리와 방법을
이해할 수 있도록 돕는데 있다.
명제 (命題, statement)
논리는 전문적으로 사용되고 있는 용어 "명제"로부터 시작한다. 명제는 참, 거짓 중 어느 한 경우이되 동시에
양쪽은 아닌 서술문(주장)을 뜻한다. 주어진 어느 명제가 참인지 거짓인지를 알려고 파고들 필요는 없겠지만
명제라면 참, 거짓 중 꼭 어느 한 쪽이어야 함을 분명히 가릴만한 조건이 갖추어져 있어야 한다.
단순명제 (單純命題, Simple statement)
'길동이는 학생이다.' 처럼 한 가지 사실을 주장하는 명제이다.
연결사(連結絲, Connectives)와 결합자(結合子, Connective)
연결사는 단순명제를 이어서 합성명제를 만들어 주는 기호로서 ∼, ∧, ∨, →, ↔ 등이 있다. 결합자란 명제와
명제를 연결하여 합성명제를 만드는 연결사를 말한다.
| ⅰ | 부정(否定, negation) 기호 | "아니다" | ∼ |
| ⅱ | 논리곱과 연언(連言, conjunction) 기호 | "이고" | ∧, & |
| ⅲ | 논리합과 선언(選言, disjunction) 기호 | "또는" | ∨ |
| ⅳ | 조건(條件, condition) 기호 | "⋯이면, ⋯" | → |
| ⅴ | 쌍조건(雙條件, bi-condition) 기호 | "⋯이면, 그리고 그 때에만" | ↔ |
합성명제 (Compound statement)
연결사를 사용해서 몇 개의 단순명제를 이어서 만든 명제이다. 단순명제일 경우 보통 p,q,r,⋯로,
합성명제일 경우 P,Q,R,⋯로 나타낸다. 복합명제, 겹명제라고도 한다.
명제함수 (命題函數, Propositional function)
"x−1>0"과 같이 변수 x에 어떤 값을 대입하면 명제가 되는 문장이나 식으로서, p(x)로 표시한다.
진리표 (眞理表, Truth table)
단일 명제의 진위(眞僞 : 참과 거짓)와 논리곱(연언)·논리합(선언) 따위에 의하여 합성된 합성 명제의
참 또는 거짓과의 대응 관계를 나타내는 표를 진리표라고 한다.
정의 1. (부정)
하나의 명제 p에 대하여 "p가 아니다." 또는 "p의 부정"으로 불리는 ∼p는 명제 p가 거짓일 때마다 참이고,
p가 참일 때마다 거짓인 명제이다.
| p | ∼p |
|---|---|
| T | F |
| F | T |
정의 2. (논리곱)
명제 p와 q의 논리곱은 p∧q로 나타내고, "p 그리고 q"(p and q)라 읽는다.
| p | q | p∧q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
정의 3. (논리합)
명제 p와 q의 논리합은 p∨q로 나타내고, "p 또는 q"(p or q)라 읽는다.
| p | q | p∨q |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
정의 4. (논리적 동치, Logically Equivalent)
두 명제 P와 Q가 모든 경우에 대해 진릿값이 같을 때 "P는 Q와 논리적 동치이다."라고 읽으며 P≡Q로 나타낸다.
예를 들면
이므로 p ≡ ∼(∼p)
| p | ∼p | ∼(∼p) |
|---|---|---|
| T | F | T |
| F | T | F |
정의 5. (조건문)
조건문은 p→q로 나타내고 "p이면 q이다."(if p then q)라고 읽으며 진릿값은 다음과 같다.
위 조건문에서 p 부분을 조건문의 전건부(前件部, antecedent) 또는 가정(假定, hypothesis) 또는 전제(前提, premise),
q 부분을 조건문의 후건부(後件部, consequent) 또는 결론(結論, conclusion)이라 한다.
| p | q | p→q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
연결사의 우선순위
괄호의 사용을 줄이기 위해 연결사의 결합에 아래와 같은 우선 순위를 부여한다. ∼이 가장 강하고 다음에 ∧, ∨,
그리고 다음에 →의 결합을 하기로 한다. 예를 들어, p→∼q∧∼r 은 p→[(∼q)∧(∼r)]과 같은 표현이다.
함축 (含蓄, Implication)
임의의 명제 p, q에 관해서 'p이면 q이다'라고 하는 것을 'p가 참이면 q가 거짓인 경우는 없다.'라고 단순화하여
기호 'p⊃q'로 표시하고, 이것을 'p는 q를 함축한다.'(imply)라고 한다.
조건문에 대한 이해
어떤 교수님이 어떤 학생에게 "만일 네가 학기말 고사에서 90점 이상을 받는다면, 너는 이 수학 과목에서 A학점을
받을 것이다."라고 말했다고 가정해 보자. 전건인 '너는 학기말 고사에서 90점 이상을 받는다.'를 'P', 후건인
'너는 이 수학 과목에서 A학점을 받는다.'를 'Q'라 하면 위 문장은 P→Q로 기호화된다. 네 가지 경우를 살펴보자.
| ❶ | P:T, Q:T | 학생이 실제로 90점 이상을 받았고, 교수님도 A학점을 준 경우. 거짓말을 하지 않았으므로 P→Q는 참. |
| ❷ | P:T, Q:F | 90점 이상을 받았지만 A학점을 주지 않은 경우. 거짓말을 한 셈이므로 P→Q는 거짓. |
| ❸ | P:F, Q:T | 90점 미만을 받았지만 A학점을 준 경우. 애초에 "90점 미만이면 어떻게 하겠다"는 약속을 하지 않았으므로 거짓말이라 할 수 없다. P→Q는 참. |
| ❹ | P:F, Q:F | 90점 미만을 받았고 A학점도 안 준 경우. 거짓말이라 할 수 없다. P→Q는 참. |
조건문은 전건이 참이고, 후건이 거짓인 경우에는 거짓이지만, 그 외의 경우들에서는 모두 참이다.
요컨대 "만일 x>3이면 x²>8이다."라는 주장의 핵심은 'x>3'이 참이면서 'x²>8'이 거짓인 x의 값이 존재하지 않는다는 주장이다. 다만 조건문의 정의가 "돌에 발부리를 차이면 아픔을 느낀다"처럼 인과관계까지 포착하지는 못한다 — 논리학의 목적(연역 논증의 타당성 평가)에 관련된 한(限)에서만 이 정의를 사용한다.
정리 6. (p→q ≡ ∼p∨q)
| p | q | p→q | ∼p | ∼p∨q |
|---|---|---|---|---|
| T | T | T | F | T |
| T | F | F | F | F |
| F | T | T | T | T |
| F | F | T | T | T |
정리 7. (p→q ≡ ∼(p∧∼q))
| p | q | p→q | ∼q | p∧∼q | ∼(p∧∼q) |
|---|---|---|---|---|---|
| T | T | T | F | F | T |
| T | F | F | T | T | F |
| F | T | T | F | F | T |
| F | F | T | T | F | T |
정의 8. (쌍조건문)
쌍조건문은 p↔q로 나타내고 "p이면 그리고 그 때에만 q이다."(p if and only if q)9)라고 읽는다.
| p | q | p↔q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
정리 9. (p↔q ≡ (p→q)∧(q→p))
| p | q | p↔q | p→q | q→p | (p→q)∧(q→p) |
|---|---|---|---|---|---|
| T | T | T | T | T | T |
| T | F | F | F | T | F |
| F | T | F | T | F | F |
| F | F | T | T | T | T |
정의 10. (항진명제와 모순명제, Tautology & Contradiction)
모든 경우에 대해 항상 참인 명제를 항진명제라 하고 "t"로, 모든 경우에 항상 거짓인 명제를 모순명제라 하고
"c"로 나타낸다. 예를 들어 p∨∼p ≡ t 이고 p∧∼p ≡ c 이다. 항진명제와 모순명제는 성분명제의 진릿값과 상관없이
명제 자체의 구조로 결정된다.
정의 11. (함의, Implication)
조건문 P→Q가 항진명제가 될 때 "P는 Q를 함의한다."라고 하고 P⇒Q로 나타낸다. 쌍조건문 P↔Q가 항진명제가 될 때
"P는 Q와 동치(同値, Equivalent)이다."라고 하고 P⇔Q로 나타낸다. 명제 P,Q에 대해 아래 네 가지 사실은 모두
같은 의미이다 : P⇒Q / P→Q가 항진명제이다 / ∼P∨Q가 항진명제이다 / P∧∼Q가 모순명제이다.
정의 12. (충분조건, 필요조건, 필요충분조건)
P⇒Q일 때 P를 Q가 되기 위한 충분조건이라 하고, Q를 P가 되기 위한 필요조건이라 한다. 필요조건과
충분조건이 동시에 될 때 필요충분조건이라 한다. 즉 P⇔Q일 때, P는 Q가 되기 위한 필요충분조건이다.
정리 13.
임의의 명제에 대해 아래 사실이 성립한다.
① 합의 법칙 (Law of addition) — P ⇒ P∨Q
② 단순화법칙 (Law of Simplification) — p∧q ⇒ p, p∧q ⇒ q
③ 추이법칙 (推移法則, Transitive Law) — (p→q)∧(q→r) ⇒ (p→r)
④ 선언지제거법 (Disjunctive Syllogism, 삼단논법) — (p∨q)∧∼p ⇒ q
⑤ 삼단긍정법 (Modus Ponens) — (p→q)∧p ⇒ q
⑥ 삼단부정법 (Modus Tollens) — (p→q)∧∼q ⇒ ∼p
② 단순화법칙 (Law of Simplification) — p∧q ⇒ p, p∧q ⇒ q
③ 추이법칙 (推移法則, Transitive Law) — (p→q)∧(q→r) ⇒ (p→r)
④ 선언지제거법 (Disjunctive Syllogism, 삼단논법) — (p∨q)∧∼p ⇒ q
⑤ 삼단긍정법 (Modus Ponens) — (p→q)∧p ⇒ q
⑥ 삼단부정법 (Modus Tollens) — (p→q)∧∼q ⇒ ∼p
각 법칙은 진리표를 작성해 조건문(⇒는 p→q가 항진명제임을 뜻함)이 항상 참임을 확인하면 증명된다.
정리 14.
임의의 명제에 대해 아래 사실이 성립한다.
① 이중부정법 (二重否定, Law of Double Negation) — ∼(∼p) ≡ p
② 멱등법칙 (冪等法則, Idempotent Law) — p∧p ≡ p, p∨p ≡ p
③ 대우법칙 (對偶法則, Contrapositive Law) — (p→q) ≡ (∼q→∼p)
④ 귀류법 (歸謬法, Reductio ad Absurdum) 또는 배리법 (背理法) — (p→q) ≡ ((p∧∼q)→c)
⑤ 교환법칙 (交換法則, Commutative Law) — p∧q ≡ q∧p, p∨q ≡ q∨p
⑥ 결합법칙 (結合法則, Associative Law) — (p∧q)∧r ≡ p∧(q∧r), (p∨q)∨r ≡ p∨(q∨r)
⑦ 분배법칙 (分配法則, Distributive Law) — p∧(q∨r) ≡ (p∧q)∨(p∧r), p∨(q∧r) ≡ (p∨q)∧(p∨r)
⑧ 드모르간의 법칙 (De Morgan's Law) — ∼(p∧q) ≡ ∼p∨∼q, ∼(p∨q) ≡ ∼p∧∼q
② 멱등법칙 (冪等法則, Idempotent Law) — p∧p ≡ p, p∨p ≡ p
③ 대우법칙 (對偶法則, Contrapositive Law) — (p→q) ≡ (∼q→∼p)
④ 귀류법 (歸謬法, Reductio ad Absurdum) 또는 배리법 (背理法) — (p→q) ≡ ((p∧∼q)→c)
⑤ 교환법칙 (交換法則, Commutative Law) — p∧q ≡ q∧p, p∨q ≡ q∨p
⑥ 결합법칙 (結合法則, Associative Law) — (p∧q)∧r ≡ p∧(q∧r), (p∨q)∨r ≡ p∨(q∨r)
⑦ 분배법칙 (分配法則, Distributive Law) — p∧(q∨r) ≡ (p∧q)∨(p∧r), p∨(q∧r) ≡ (p∨q)∧(p∨r)
⑧ 드모르간의 법칙 (De Morgan's Law) — ∼(p∧q) ≡ ∼p∨∼q, ∼(p∨q) ≡ ∼p∧∼q
위 정리의 대우법칙과 귀류법(배리법)은 증명에서 많이 사용하는 추론 방법이다. 조건문 형태의 명제 p→q를 직접 증명하기 어려울 경우 대우명제 ∼q→∼p를 증명하거나, p∧∼q를 가정하면 모순이 생긴다는 것14)을 보이면 된다.
정리 15.
명제 t를 항진명제, c를 모순명제, p를 임의의 명제라 할 때
① p∧t ⇔ p, p∨t ⇔ t
② p∨c ⇔ p, p∧c ⇔ c
③ c ⇒ p, p ⇒ t
① p∧t ⇔ p, p∨t ⇔ t
② p∨c ⇔ p, p∧c ⇔ c
③ c ⇒ p, p ⇒ t
정리 16. (흡수법칙, Absorption Law)
임의의 두 명제 p,q에 대하여
① p∧(p∨q) ≡ p
② p∨(p∧q) ≡ p
① p∧(p∨q) ≡ p
② p∨(p∧q) ≡ p
정의 17. (동시부정, Joint Denial)
연결사 p↓q (p nor q라 읽는다)는 p도 아니고 q도 아님을 뜻한다.
| p | q | p↓q |
|---|---|---|
| T | T | F |
| T | F | F |
| F | T | F |
| F | F | T |
연역적 추론 (演繹的 推論, Deductive Reasoning)
지금까지 배운 정리에서 다룬 법칙들을 추론 규칙이라 한다. 이 규칙들은 인용의 편리를 위해 선택한
것들로서 서로 독립성을 유지하는 것은 아니며, 다른 규칙을 가지고 증명이 가능한 경우도 있다. 예를 들어
대우명제의 법칙 (p→q)≡(∼q→∼p)을 추론 규칙만으로 증명하면:
이와 같이 진리표를 사용하지 않고 추론 규칙을 사용하여 추론하는 것을 연역적 추론이라 한다.
| p→q | ≡ ∼(p∧∼q) | ∵ 정리6 |
| ≡ ∼(∼q∧p) | ∵ 교환법칙 | |
| ≡ ∼(∼q∧∼(∼p)) | ∵ 이중부정 | |
| ≡ ∼q→∼p | ∵ 정리6 |
정리 18. (추출의 법칙 또는 이출법칙, Exportation Law)
(p∧q→r) ≡ [p→(q→r)]
| p∧q→r | ≡ p→∼(q∧∼r) | ∵ 정리6 |
| ≡ ∼[p∧(q∧∼r)] | ∵ 정리6, 이중부정 | |
| ≡ ∼[(p∧q)∧(∼r)] | ∵ 결합법칙 | |
| ≡ p∧q→r | ∵ 정리6 |
한정기호 (限定記號, Quantifier)
"모든 x에 대하여 p(x)."를 뜻하는 전칭기호(全稱記號, Universal Quantifier) ∀x와, "어떤 x가 존재해서 p(x)."를
뜻하는 존재기호(存在記號, Existential Quantifier) ∃x가 있다. 명제함수 p(x)에 한정기호를 붙이면
∀xp(x) 또는 ∃xp(x)와 같이 명제(진릿값을 갖는 문장)가 된다.
정의 19. (한정기호 부정법, Rule of Quantifier Negation)
p(x)가 명제함수라 할 때, ∼∀xp(x) ≡ ∃x∼p(x) ∼∃xp(x) ≡ ∀x∼p(x)
이 성립한다. 전체집합이 유한집합 {a₁,a₂,⋯,aₙ}일 경우를 생각하면, ∀xp(x) ≡ p(a₁)∧p(a₂)∧⋯∧p(aₙ)이고
∃xp(x) ≡ p(a₁)∨p(a₂)∨⋯∨p(aₙ)이므로, 한정기호의 부정규칙은 드모르간의 법칙을
일반화한 것임을 알 수 있다.
정리 20.
한정기호가 있는 명제함수에 대해 아래 사실이 성립한다.
① (∀x(p(x)))→q ≡ (∃x)(p(x)→q)
② (∃x(p(x)))→q ≡ (∀x)(p(x)→q)
③ p→(∀x q(x)) ≡ (∀x)(p→q(x))
④ p→(∃x q(x)) ≡ (∃x)(p→q(x))
② (∃x(p(x)))→q ≡ (∀x)(p(x)→q)
③ p→(∀x q(x)) ≡ (∀x)(p→q(x))
④ p→(∃x q(x)) ≡ (∃x)(p→q(x))
각 증명은 정리6(p→q≡∼p∨q), 한정기호 부정법(정의19), 논리합·논리곱과 한정기호의 이동 규칙, 그리고 다시 정리6을 순서대로 적용하는 4단계로 이루어진다.
한정기호 사용의 예
예: "모든 실수 x에 대해 x²+2x+1 ≥ 0이다."의 부정은
∼[∀x(x²+2x+1≥0)] ≡ ∃x(∼(x²+2x+1≥0)) ≡ ∃x(x²+2x+1<0)
즉 "어떤 실수 x에 대해 x²+2x+1<0"이 되며, 이는 거짓이다(∵ x²+2x+1=(x+1)²≥0 이므로).
- 1) 論理的 同値, Logically Equivalent
- 9) 줄여서 iff라고도 쓴다.
- 10) 恒眞命題, Tautology와 矛盾命題, Contradiction
- 11) 充分條件, Sufficient condition, 必要條件, Necessary condition, 必要充分條件, Necessary and Sufficient condition
- 13) 역으로 Q는 P가 되기 위한 필요충분조건이다.
- 14) p∧∼q → c
- 15) 吸收法則, Absorption Law
- 16) 同時否定, Joint Denial
- 17) 演繹的 推論, Deductive Reasoning
- 18) 推論 規則, Rules of Inference
- 19) 引用 : 남의 말이나 글 가운데서 필요한 부분을 끌어다 씀
- 20) 抽出의 法則 또는 移出法則, Exportation Law
- 21) 둘 이상의 단어가 모여 절(節)이나 문장의 일부분이 되는 말
- 22) "x에 관계없이", "임의의 x에 대해" 등의 표현도 사용된다.
- 23) Rule of Quantifier Negation