1. 명제의 세 가지 분류
복합 명제는 진리값의 패턴에 따라 정확히 세 가지로 나뉜다.
| 항진 | Tautology | 단위 명제의 진리값과 무관하게 항상 참 | 모든 행이 T |
| 부정(모순) | Contradiction | 단위 명제의 진리값과 무관하게 항상 거짓 | 모든 행이 F |
| 불확정 | Contingency | 항진도 아니고 부정도 아닌 명제 | T와 F가 섞여 있음 |
💡 시험 포인트: 어떤 복합 명제를 보면 가장 먼저 "이게 항진/부정/불확정 중 무엇인가?"를 진리표로 판별할 수 있어야 한다.
2. 항진(Tautology) — 무조건 참인 명제
항진은 구성하는 단위 명제가 어떤 진리값을 가지든 결과가 항상 참인 복합 명제다.
대표 예시: P ∨ ¬P
"비가 오거나, 비가 오지 않는다" — 이 세상 어떤 상황에서도 참이다.
| T | F | T |
| F | T | T |
P가 참이든 거짓이든, P와 ¬P 중 하나는 반드시 참이므로 둘의 OR는 항상 참이 된다.
일상 예시
- "모든 총각은 미혼 남성이다"
- "삼각형은 세 변을 가진다"
- "오늘은 월요일이거나 월요일이 아니다"
이런 문장들은 명제의 구조 자체가 참을 강제한다.
3. 부정/모순(Contradiction) — 무조건 거짓인 명제
부정은 항진의 정반대다. 단위 명제의 진리값과 무관하게 결과가 항상 거짓인 복합 명제다.
대표 예시: P ∧ ¬P
"나는 살아있고 동시에 죽어있다" — 어떤 경우에도 참이 될 수 없다.
| T | F | F |
| F | T | F |
P와 ¬P는 동시에 참이 될 수 없으므로 둘의 AND는 항상 거짓이다.
💡 용어 주의: 여기서 말하는 '부정(Contradiction)'은 NOT 연산자가 아니라 **'모순 명제'**를 뜻한다. 한국어 번역이 헷갈리니 영문 용어로 기억하는 게 안전하다.
4. 불확정 명제(Contingency) — 일반적인 명제
대부분의 명제가 여기에 속한다. 진리값이 상황에 따라 참이 되기도 하고 거짓이 되기도 하는 명제다.
대표 예시: P → Q
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
결과 열에 T와 F가 섞여 있으므로 불확정 명제다.
일상 예시
- "내일 비가 올 것이다" → 날씨에 따라 결정됨
- "P ∧ Q" → P와 Q가 모두 참일 때만 참
5. 명제 동치(Propositional Equivalence) — 다른 표현, 같은 의미
두 복합 명제가 본질적으로 완전히 동일한 의미를 가질 때, 이 둘을 **논리적으로 동치(Logically Equivalent)**라고 한다.
표기법
명제 p와 q가 논리적으로 동치일 때:
p ≡ q 또는 p ↔ q (항상 참)
핵심 정의
p ↔ q가 항진(Tautology) 일 때, p와 q는 논리적으로 동치다.
즉, 두 명제의 진리값이 모든 경우에 일치해야 한다.
6. 동치의 직관적 이해
언어로 풀어보면 다음과 같다.
| "비가 오지 않는다" | "비가 오는 것이 아니다" | ⭕ 동치 |
| "피자와 콜라를 둘 다 먹지 않았다" | "피자를 먹지 않았거나 콜라를 먹지 않았다" | ⭕ 동치 (드모르간) |
| "비가 온다" | "땅이 젖는다" | ❌ 동치 아님 |
💡 두 명제가 동치라면, 어디서든 서로 대체해서 사용할 수 있다. 이게 동치의 진짜 가치다. 복잡한 명제를 단순한 동치 명제로 바꿔서 문제를 풀 수 있게 된다.
7. 진리표를 이용한 동치 증명
두 명제가 동치임을 증명하는 가장 직관적인 방법은 진리표를 그려서 두 명제의 결과 열이 모든 행에서 일치함을 보이는 것이다.
예제: 드모르간의 법칙 증명
¬(P ∨ Q) ≡ ¬P ∧ ¬Q 을 진리표로 증명해보자.
| T | T | T | F | F | F | F |
| T | F | T | F | F | T | F |
| F | T | T | F | T | F | F |
| F | F | F | T | T | T | T |
좌변 ¬(P ∨ Q)의 결과 열과 우변 ¬P ∧ ¬Q의 결과 열이 모든 행에서 완벽히 일치한다. 따라서 두 명제는 논리적으로 동치다. ✅
8. 진리표 증명의 한계 — Too Expensive!
진리표는 직관적이지만 치명적인 단점이 있다.
행의 개수가 폭발적으로 증가
단위 명제가 n개일 때, 필요한 행의 수는 2ⁿ개다.
| 2개 | 4행 | 쉬움 |
| 3개 | 8행 | 쉬움 |
| 5개 | 32행 | 귀찮음 |
| 10개 | 1,024행 | 사실상 불가능 |
| 20개 | 1,048,576행 | 절대 불가능 |
💡 교수님 포인트로 추정: PDF에 "Too expensive!" 라고 강조 표시되어 있음. 진리표의 한계 때문에 **다음 강에서 배울 동치 법칙(Equivalence Laws)**이 필요하다.
이것이 3강에서 배울 동치 법칙을 이용한 증명 방식이 등장하는 이유다. 법칙을 이용하면 진리표 없이도 명제를 변형하며 동치를 증명할 수 있다.
📌 한눈에 보는 핵심정리
| 항진(Tautology) | 항상 참인 명제 | P ∨ ¬P |
| 부정/모순(Contradiction) | 항상 거짓인 명제 | P ∧ ¬P |
| 불확정(Contingency) | 상황에 따라 참/거짓 | P → Q, P ∧ Q |
| 논리적 동치 | 두 명제의 진리값이 항상 같음 | p ≡ q |
| 동치 표기 | 동치 기호 | ≡ 또는 ↔ (항진일 때) |
| 진리표 증명 | 모든 행의 결과가 일치 | 드모르간 법칙 검증 |
| 진리표의 한계 | n개 변수 → 2ⁿ행 필요 | 변수 많아지면 비효율 |
🧠 예상문제 2제
문제 1. 명제의 분류
다음 명제 (P → Q) ∨ (Q → P)의 분류로 옳은 것은?
① 항진(Tautology) ② 부정/모순(Contradiction) ③ 불확정(Contingency) ④ 판별 불가능
👉 정답: ①
진리표로 확인해보자.
| T | T | T | T | T |
| T | F | F | T | T |
| F | T | T | F | T |
| F | F | T | T | T |
결과 열이 모두 T이므로 **항진(Tautology)**이다.
핵심 원리: 두 함축 명제 중 적어도 하나는 항상 참이 된다. (P가 거짓이면 P→Q가 참, Q가 거짓이면 Q→P가 참)
문제 2. 동치 판별
다음 두 명제가 논리적으로 동치인지 판별하시오.
¬(P ∧ Q) 와 ¬P ∨ ¬Q
① 동치이다 (≡) ② 동치가 아니다 ③ P가 참일 때만 동치이다 ④ Q가 거짓일 때만 동치이다
👉 정답: ①
진리표로 검증:
| T | T | T | F | F | F | F |
| T | F | F | T | F | T | T |
| F | T | F | T | T | F | T |
| F | F | F | T | T | T | T |
¬(P ∧ Q) 열과 ¬P ∨ ¬Q 열이 모든 행에서 일치한다. 이것이 바로 드모르간의 법칙이며, 다음 강(3강)에서 자세히 다룰 동치 법칙 중 하나다.
'📌 SW전공-개념 > 이산구조' 카테고리의 다른 글
| [이산구조 개념-07] 형식적 증명 — 추론 규칙으로 결론 만들기 (1) | 2026.05.30 |
|---|---|
| [이산구조 개념-06] 추론 규칙 7선 — 논리적 추론의 도구함 (0) | 2026.05.29 |
| [이산구조 개념-05] 한정자의 순서·부정·동치 — 술어 논리 심화 (0) | 2026.05.28 |
| [이산구조 특별편 1] 드모르간과 AI — 19세기 논리가 21세기 인공지능이 되기까지 (1) | 2026.05.26 |
| [이산구조 개념-01] 부울 대수: 0과 1로 번역된 인간의 사고 (0) | 2026.05.23 |