선행학습 · PREREQUISITE
기초 논리
Basic Logic
序
증명은 이미 참이라고 인정한 것에서 새로운 참을 이끌어 내는 일이다. 이 편에서는 그 과정에 필요한 최소한의 논리
도구 — 명제와 연결사, 진리표, 동치와 함의, 추론 규칙, 한정기호 — 를 정리한다. 여기서 만든 정의와 정리는
이후 모든 증명에서 근거로 인용된다.
명제 (命題, statement)
명제란 참인지 거짓인지가 분명하게 정해지는 문장이나 식을 말한다. 한 명제가 참이면서 동시에 거짓일 수는 없다.
그 진위를 지금 당장 알지 못해도 상관없다. 예를 들어 "4 이상의 모든 짝수는 두 소수의 합으로 나타낼 수 있다"(골드바흐의 추측)는
아직 참인지 거짓인지 밝혀지지 않았지만 둘 중 하나로 정해져 있으므로 명제이다. 반면 "이 문제는 어렵다"처럼 판단하는
사람에 따라 달라지는 문장은 명제가 아니다.
단순명제와 합성명제 (Simple & Compound statement)
"7은 소수이다."처럼 더 작은 명제로 나눌 수 없는 하나의 주장을 단순명제라 하고, "7은 소수이고 9는 소수가 아니다."처럼
단순명제 여러 개를 '그리고', '또는', '이면' 같은 말로 묶은 명제를 합성명제(복합명제)라 한다.
이 편에서는 단순명제를 소문자 p, q, r, ⋯로, 합성명제나 형태를 정하지 않은 임의의 명제를 대문자 P, Q, R, ⋯로 쓴다.
연결사 (連結詞, Connectives)
명제를 묶어 새 명제를 만드는 '그리고', '또는' 같은 말을 기호로 적은 것이 연결사이다. 이 편에서 쓰는 연결사는 다음 다섯 가지이다.
| ⅰ | 부정(否定, negation) | "아니다" | ∼ |
| ⅱ | 논리곱, 연언(連言, conjunction) | "그리고" | ∧, & |
| ⅲ | 논리합, 선언(選言, disjunction) | "또는" | ∨ |
| ⅳ | 조건(條件, conditional) | "⋯이면, ⋯" | → |
| ⅴ | 쌍조건(雙條件, biconditional) | "⋯일 때 그리고 그때에만" | ↔ |
연결사의 우선순위
괄호를 매번 쓰지 않도록, 기호가 묶는 힘의 순서를 정해 둔다. ∼가 가장 먼저 바로 뒤의 명제에 붙고, 그다음이 ∧와 ∨,
마지막이 →와 ↔이다. 그래서 ∼p∨q→r은 ((∼p)∨q)→r로 읽는다. ∧와 ∨가 함께 나와 순서가 헷갈릴 때는 괄호를 쓴다.
진리표 (眞理表, Truth table)
합성명제의 참·거짓은 그것을 이루는 성분명제의 참·거짓만으로 정해진다. 성분명제가 가질 수 있는 진릿값의 조합을 빠짐없이
나열하고, 각 조합에서 합성명제의 진릿값을 적은 표를 진리표라 한다. 참은 T, 거짓은 F로 쓰며, 성분명제가 n개이면
조합은 2n가지이다. 아래 정의 1~5는 각 연결사의 뜻을 진리표로 정한 것이다.
정의 1. (부정)
명제 p의 참·거짓을 뒤집은 명제를 p의 부정이라 하고 ∼p로 쓰며 "p가 아니다"(not p)로 읽는다.
예를 들어 p가 "7은 소수이다."이면 ∼p는 "7은 소수가 아니다."이다.
| p | ∼p |
|---|---|
| T | F |
| F | T |
정의 2. (논리곱)
두 명제를 '그리고'로 묶은 명제 p∧q를 p와 q의 논리곱이라 하고 "p 그리고 q"(p and q)로 읽는다.
p와 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 | p∨q |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
정의 4. (조건문)
"p이면 q이다"(if p, then q)라는 명제를 조건문이라 하고 p→q로 쓴다. p→q는 p가 참이고 q가 거짓일 때만
거짓이고, 나머지 세 경우에는 참이다.
앞쪽의 p를 가정(假定, hypothesis) 또는 전건(前件, antecedent), 뒤쪽의 q를 결론(結論, conclusion) 또는
후건(後件, consequent)이라 부른다.
| p | q | p→q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
조건문에 대한 이해
정의 4의 진리표에서 "p가 거짓이면 p→q는 무조건 참"이라는 부분이 어색하게 느껴질 수 있다. 조건문을 약속으로
읽으면 이해하기 쉽다. 동아리 회장이 "이번 토요일에 비가 오면 모임을 다음 주로 미룬다."라고 공지했다고 하자.
P: 토요일에 비가 온다, Q: 모임을 다음 주로 미룬다 라고 하면 이 공지는 P→Q이다. 공지가 지켜졌는지를 네 경우로 따져 보자.
| ❶ | P:T, Q:T | 비가 왔고 모임을 미뤘다. 공지대로 했으므로 P→Q는 참. |
| ❷ | P:T, Q:F | 비가 왔는데 모임을 미루지 않았다. 공지를 어겼으므로 P→Q는 거짓. |
| ❸ | P:F, Q:T | 비가 오지 않았는데 다른 사정으로 모임을 미뤘다. 공지는 비가 오는 날에 대해서만 말했으므로 어긴 것이 아니다. P→Q는 참. |
| ❹ | P:F, Q:F | 비가 오지 않았고 모임도 예정대로 열렸다. 역시 어긴 것이 아니다. P→Q는 참. |
약속이 깨지는 경우는 ❷ 하나뿐이다. 그래서 p→q는 p가 참이고 q가 거짓일 때만 거짓으로 정한다.
수학의 예로, 자연수 n에 대하여 "n이 4의 배수이면 n은 짝수이다."는 참인 조건문이다. n=6(전건 거짓, 후건 참)이나 n=5(둘 다 거짓)는 이 조건문을 깨뜨리지 않는다. 이 조건문이 실제로 주장하는 것은 "4의 배수이면서 홀수인 n은 없다"는 것뿐이다 (아래 정리 9). 한편 논리의 조건문은 p와 q 사이에 원인과 결과 같은 내용상의 연결을 요구하지 않는다. "2+2=4이면 1<2이다."도 진리표상 참이다. 증명에 필요한 것은 "전제가 참이면 결론도 참"이라는 진릿값의 관계뿐이므로 이 정의로 충분하다.
참고로, 오래된 논리학 책에서는 조건문 p→q를 말굽 기호를 써서 p⊃q로 적기도 한다. 이 편에서는 →만 쓴다.
정의 5. (쌍조건문)
"p이면 q이고, q이면 p이다"를 한꺼번에 주장하는 명제를 쌍조건문이라 하고 p↔q로 쓰며,
"p일 때 그리고 그때에만 q"(p if and only if q)1)로 읽는다. p와 q의 진릿값이 같으면 참, 다르면 거짓이다.
| p | q | p↔q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
정의 6. (항진명제와 모순명제, Tautology & Contradiction)
성분명제에 어떤 진릿값을 넣어도 늘 참인 명제를 항진명제, 늘 거짓인 명제를 모순명제라 한다.
진리표의 마지막 열이 모두 T이면 항진명제, 모두 F이면 모순명제이다. 이 편에서는 항진명제를 t, 모순명제를 c로 나타낸다.
예를 들어 p→(p∨q)는 항진명제이다(p가 참이면 p∨q도 참이므로 정의 4의 거짓인 경우가 생기지 않는다).
또 (p∧q)∧∼q는 모순명제이다(q와 ∼q가 동시에 참일 수 없다).
정의 7. (논리적 동치, Logically Equivalent)
두 명제 P, Q가 진리표의 모든 행에서 같은 진릿값을 가지면 P와 Q는 논리적으로 동치라 하고 P≡Q로 쓴다.
동치인 두 명제는 모양만 다를 뿐 같은 내용을 말하므로, 증명 중에 하나를 다른 하나로 바꿔 써도 된다.
예를 들어 조건문의 부정은 다음 표에서 ∼(p→q)와 p∧∼q의 열이 같으므로 ∼(p→q) ≡ p∧∼q이다.
곧 "p이면 q이다"를 부정하면 "p인데 q가 아니다"가 된다. "p가 아니면 q가 아니다"가 아니라는 점에 주의한다.
| p | q | p→q | ∼(p→q) | ∼q | p∧∼q |
|---|---|---|---|---|---|
| T | T | T | F | F | F |
| T | F | F | T | T | T |
| F | T | T | F | F | F |
| F | F | T | F | T | F |
정리 8. (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 |
정리 8부터는 법칙을 소문자 p, q, r로 적지만, 그 자리에 합성명제를 넣어도 그대로 성립한다. 진리표의 각 행에서 합성명제도 T나 F 가운데 하나의 값을 가질 뿐이기 때문이다. 정리 13·14의 "임의의 명제"도 이런 뜻이며, 아래 증명들은 이 사실을 쓴다.
정리 9. (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 |
정리 10. (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 |
정의 11. (함의, Implication)
조건문 P→Q가 항진명제일 때, 곧 진리표의 어느 행에서도 'P는 참, Q는 거짓'이 나오지 않을 때 "P는 Q를 함의한다"고 하고
P⇒Q로 쓴다. 마찬가지로 쌍조건문 P↔Q가 항진명제일 때 P⇔Q로 쓰며, 이는 정의 7의 P≡Q와 같은 뜻이다.
→와 ↔는 두 명제로 새 명제를 만드는 연결사이고, ⇒와 ⇔는 두 명제 사이에 그 관계가 언제나 성립한다는 주장이라는 점이 다르다.
정리 8·9에 따라 P⇒Q는 "∼P∨Q가 항진명제", "P∧∼Q가 모순명제"라고 말해도 같다.
정의 12. (충분조건, 필요조건, 필요충분조건)
P⇒Q일 때, P가 성립하기만 하면 Q가 따라 나오므로 P를 Q의 충분조건이라 하고, Q가 성립하지 않으면 P도 성립할 수 없으므로
Q를 P의 필요조건이라 한다. P⇒Q와 Q⇒P가 모두 성립할 때, 곧 P⇔Q일 때 P를 Q의 필요충분조건이라 한다.
예를 들어 자연수 n에 대하여 "n은 4의 배수"는 "n은 짝수"이기 위한 충분조건이고, "n은 짝수"는 "n은 4의 배수"이기 위한 필요조건이다.
"n은 짝수"와 "n²은 짝수"는 서로 필요충분조건이다.
정리 13. (자주 쓰는 함의)
임의의 명제 p, q, r에 대하여 다음이 성립한다.
① 삼단긍정법 (Modus Ponens) — (p→q)∧p ⇒ q
② 삼단부정법 (Modus Tollens) — (p→q)∧∼q ⇒ ∼p
③ 추이법칙 (推移法則, Transitive Law) — (p→q)∧(q→r) ⇒ (p→r)
④ 선언지제거법 (Disjunctive Syllogism) — (p∨q)∧∼p ⇒ q
⑤ 합의 법칙 (Law of Addition) — p ⇒ p∨q
⑥ 단순화법칙 (Law of Simplification) — p∧q ⇒ p, p∧q ⇒ q
② 삼단부정법 (Modus Tollens) — (p→q)∧∼q ⇒ ∼p
③ 추이법칙 (推移法則, Transitive Law) — (p→q)∧(q→r) ⇒ (p→r)
④ 선언지제거법 (Disjunctive Syllogism) — (p∨q)∧∼p ⇒ q
⑤ 합의 법칙 (Law of Addition) — p ⇒ p∨q
⑥ 단순화법칙 (Law of Simplification) — p∧q ⇒ p, p∧q ⇒ q
정의 11에 따라, 각각 ⇒ 왼쪽에서 오른쪽으로 가는 조건문의 진리표를 만들어 마지막 열이 모두 T임을 보이면 된다. ②의 진리표는 추론의 타당성 예 2에 있다.
정리 14. (자주 쓰는 동치)
임의의 명제 p, q, r에 대하여 다음이 성립한다.
① 교환법칙 (交換法則, 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
⑤ 이중부정법 (二重否定, 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)
② 결합법칙 (結合法則, 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
⑤ 이중부정법 (二重否定, 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)
각 식은 양변의 진리표를 만들어 모든 행에서 진릿값이 같음을 확인하면 된다(정의 7). ⑧은 아래 연역적 추론에서 정리 8·9·15로도 얻는다. ①~④는 수의 덧셈·곱셈 법칙과 닮았다(∧를 곱, ∨를 합으로 보면 된다. 다만 ③의 둘째 식처럼 ∨가 ∧ 위로 분배되는 것은 수에는 없는 성질이다). ⑦과 ⑧은 간접증명의 근거이다. p→q를 곧바로 보이기 어려우면 ⑦에 따라 ∼q→∼p를 대신 증명하거나, ⑧에 따라 p와 ∼q를 함께 가정한 뒤 모순2)을 이끌어 내면 된다(간접증명법).
정리 15. (t와 c의 성질)
항진명제 t와 모순명제 c는 수의 1과 0처럼 행동한다. 임의의 명제 p에 대하여
① p∧t ≡ p, p∨c ≡ p (1을 곱하거나 0을 더해도 그대로)
② p∨t ≡ t, p∧c ≡ c (무엇과 묶어도 t, c가 이긴다)
③ c ⇒ p, p ⇒ t (모순에서는 무엇이든 따라 나오고, 무엇에서든 항진명제는 따라 나온다)
t는 늘 T, c는 늘 F이므로(정의 6) p의 두 경우만 따지는 진리표로 바로 확인된다.
① p∧t ≡ p, p∨c ≡ p (1을 곱하거나 0을 더해도 그대로)
② p∨t ≡ t, p∧c ≡ c (무엇과 묶어도 t, c가 이긴다)
③ c ⇒ p, p ⇒ t (모순에서는 무엇이든 따라 나오고, 무엇에서든 항진명제는 따라 나온다)
t는 늘 T, c는 늘 F이므로(정의 6) p의 두 경우만 따지는 진리표로 바로 확인된다.
정리 16. (흡수법칙, Absorption Law)
임의의 두 명제 p,q에 대하여
① p∧(p∨q) ≡ p
② p∨(p∧q) ≡ p
①도 ∧와 ∨, t와 c를 서로 바꾸어 같은 방법으로 얻는다.
① p∧(p∨q) ≡ p
② p∨(p∧q) ≡ p
| p∨(p∧q) | ≡ (p∧t)∨(p∧q) | ∵ 정리15 ① |
| ≡ p∧(t∨q) | ∵ 분배법칙 | |
| ≡ p∧t | ∵ 교환법칙, 정리15 ② | |
| ≡ p | ∵ 정리15 ① |
정의 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)
두 명제가 동치인지(또는 한쪽이 다른 쪽을 함의하는지) 확인하는 길은 두 가지이다. 진리표로 모든 경우를 하나하나 따지거나,
정리 8~16처럼 이미 확인된 법칙을 근거로 식을 한 줄씩 바꾸어 가는 것이다. 뒤의 방법을 연역적 추론이라 하고,
그때 근거로 인용하는 법칙을 추론 규칙이라 한다. 각 줄의 오른쪽에 근거를 적어 두면 누구나 한 줄씩 검산할 수 있다.
정리 14의 ⑧(귀류법)을 이렇게 얻어 보자.
셋째 줄에서 보듯, "p이면서 q가 아니면 모순"이라는 말은 "p이면서 q가 아닌 경우는 없다"는 말과 같아서 결국 p→q와 같다.
추론의 각 단계를 이렇게 규칙으로 정당화하는 방식은 추론의 타당성 예 3의 형식적 증명에서 다시 쓴다.
| (p∧∼q)→c | ≡ ∼(p∧∼q)∨c | ∵ 정리8 |
| ≡ ∼(p∧∼q) | ∵ 정리15 ① | |
| ≡ p→q | ∵ 정리9 |
정리 18. (추출의 법칙 또는 이출법칙, Exportation Law)
임의의 명제 p, q, r에 대하여 p∧q→r ≡ p→(q→r)
가정 두 개를 한꺼번에 놓고 r을 보이는 것과, p를 먼저 가정한 뒤 "q이면 r"을 보이는 것이 같은 일이라는 뜻이다. 그래서 가정이 여러 개인 명제는 가정을 하나씩 차례로 들여오며 증명해도 된다.
가정 두 개를 한꺼번에 놓고 r을 보이는 것과, p를 먼저 가정한 뒤 "q이면 r"을 보이는 것이 같은 일이라는 뜻이다. 그래서 가정이 여러 개인 명제는 가정을 하나씩 차례로 들여오며 증명해도 된다.
| p∧q→r | ≡ ∼((p∧q)∧∼r) | ∵ 정리9 |
| ≡ ∼(p∧(q∧∼r)) | ∵ 결합법칙 | |
| ≡ ∼(p∧∼(q→r)) | ∵ 이중부정, 정리9 | |
| ≡ p→(q→r) | ∵ 정리9 |
명제함수 (命題函數, Propositional function)
"x²=4"는 x가 무엇인지 모르면 참·거짓을 말할 수 없지만, x=2를 넣으면 참인 명제, x=3을 넣으면 거짓인 명제가 된다.
이처럼 변수를 포함하고 있어서 변수에 값을 넣을 때마다 명제가 되는 식이나 문장을 명제함수(열린 문장)라 하고 p(x)처럼 쓴다.
한정기호 (限定記號, Quantifier)
명제함수 p(x)를 명제로 만드는 방법은 x에 값 하나를 넣는 것만이 아니다. x가 움직이는 범위(전체집합 U) 전체를 놓고
"몇 개의 x에서 참인가"를 말해도 참·거짓이 정해진다. 이때 붙이는 두 기호를 한정기호라 한다.
• ∀x p(x) — U의 원소 x가 무엇이든 p(x)가 참이다. ∀를 전칭기호(全稱記號, Universal Quantifier)라 한다(All의 A를 뒤집은 꼴).
• ∃x p(x) — p(x)를 참으로 만드는 x가 U 안에 적어도 하나 있다. ∃를 존재기호(存在記號, Existential Quantifier)라 한다(Exists의 E를 뒤집은 꼴).
예를 들어 U가 실수 전체일 때 ∀x(x²≥0)과 ∃x(x²=2)는 참이고, ∀x(x²>0)은 x=0 하나 때문에 거짓이다. 같은 식이라도 U가 바뀌면 진릿값이 바뀔 수 있다. U가 유리수 전체이면 ∃x(x²=2)는 거짓이다.
• ∀x p(x) — U의 원소 x가 무엇이든 p(x)가 참이다. ∀를 전칭기호(全稱記號, Universal Quantifier)라 한다(All의 A를 뒤집은 꼴).
• ∃x p(x) — p(x)를 참으로 만드는 x가 U 안에 적어도 하나 있다. ∃를 존재기호(存在記號, Existential Quantifier)라 한다(Exists의 E를 뒤집은 꼴).
예를 들어 U가 실수 전체일 때 ∀x(x²≥0)과 ∃x(x²=2)는 참이고, ∀x(x²>0)은 x=0 하나 때문에 거짓이다. 같은 식이라도 U가 바뀌면 진릿값이 바뀔 수 있다. U가 유리수 전체이면 ∃x(x²=2)는 거짓이다.
정리 19. (한정기호 부정법, Rule of Quantifier Negation)
명제함수 p(x)에 대하여 ∼∀x p(x) ≡ ∃x ∼p(x), ∼∃x p(x) ≡ ∀x ∼p(x)
증명. ∼∀x p(x)가 참이라는 것은 "모든 x에서 p(x)가 참"이 틀렸다는 뜻, 곧 p(x)가 거짓인 x가 하나라도 있다는 뜻이고,
이것이 바로 ∃x ∼p(x)가 참이라는 뜻이다. 둘째 식은 첫째 식의 p(x) 자리에 ∼p(x)를 넣고 양쪽을 부정한 뒤 이중부정을 쓰면 된다.
한마디로 "부정이 한정기호를 지나가면 ∀와 ∃가 서로 바뀐다." U의 원소가 몇 개뿐이면 ∀는 긴 논리곱, ∃는 긴 논리합이므로, 이 정리는 드모르간의 법칙(정리 14 ④)을 그대로 늘린 모습이다.
한마디로 "부정이 한정기호를 지나가면 ∀와 ∃가 서로 바뀐다." U의 원소가 몇 개뿐이면 ∀는 긴 논리곱, ∃는 긴 논리합이므로, 이 정리는 드모르간의 법칙(정리 14 ④)을 그대로 늘린 모습이다.
정리 20. (조건문과 한정기호)
q는 x를 포함하지 않는 명제, p(x)는 명제함수이고, 전체집합 U는 공집합이 아니라고 하자. 조건문의 한쪽에만 한정기호가 있으면 그 한정기호를 조건문 전체의 밖으로 꺼낼 수 있다. 결론 쪽에서 꺼내면 종류가 그대로이고, 가정 쪽에서 꺼내면 ∀와 ∃가 바뀐다.
① q→∀x p(x) ≡ ∀x (q→p(x))
② q→∃x p(x) ≡ ∃x (q→p(x))
③ (∃x p(x))→q ≡ ∀x (p(x)→q)
④ (∀x p(x))→q ≡ ∃x (p(x)→q)
② q→∃x p(x) ≡ ∃x (q→p(x))
③ (∃x p(x))→q ≡ ∀x (p(x)→q)
④ (∀x p(x))→q ≡ ∃x (p(x)→q)
③의 증명. 조건문은 "가정 참, 결론 거짓"일 때만 거짓이므로 양쪽이 거짓이 되는 경우를 비교한다. 왼쪽이 거짓 ⇔ 어떤 a에서 p(a)가 참이고 q는 거짓 ⇔ 어떤 a에서 p(a)→q가 거짓 ⇔ 오른쪽이 거짓. 거짓인 경우가 같으므로 두 명제는 동치이다. ①·②·④도 같은 방법으로 보인다. ②·④에서는 U가 공집합이 아니라는 조건이 필요하다 (U=∅이면 ∃x(⋯)는 언제나 거짓이므로, 예를 들어 ④의 왼쪽은 q가 참일 때 참이지만 오른쪽은 거짓이다). ④가 ∃로 바뀌는 이유: "모두가 p이면 q"가 성립하려면 p가 아닌 x가 하나 있거나 q가 참이면 충분하기 때문이다.
한정기호 사용의 예
예: 한정기호가 둘 이상이면 부정을 왼쪽부터 하나씩 안으로 밀어 넣는다. U를 실수 전체라 할 때
"어떤 실수 x를 골라도 그보다 큰 실수 y가 있다", 곧 ∀x ∃y (x<y)의 부정은
∼∀x ∃y (x<y) ≡ ∃x ∼∃y (x<y) ≡ ∃x ∀y ∼(x<y) ≡ ∃x ∀y (y≤x)
즉 "모든 실수 y 이상인 실수 x가 있다(가장 큰 실수가 있다)"이다. 이것은 거짓이므로(그런 x가 있어도 x+1이 더 크다) 원래 명제는 참이다.
한정기호의 순서를 바꾼 ∃y ∀x (x<y)는 "모든 실수보다 큰 실수 y가 있다"는 뜻이 되어 거짓이다(x=y를 넣어 보라).
이처럼 ∀와 ∃가 섞여 있으면 순서를 함부로 바꿀 수 없다.
- 1) 줄여서 iff라고도 쓴다.
- 2) (p∧∼q) → c