1. 수학적 증명이란 무엇인가
수학적 증명(Proof) 은 수학적 명제의 참을 확립하는 정당한 논증(Valid Argument) 과정이다.
증명은 마치 법정에서 변호사가 증거를 제시하여 판사를 설득하는 과정과 같다.
| 증거 (Evidence) | 전제 (Antecedent) |
| 변호 논리 | 추론 규칙 (Inference Rules) |
| 판결 | 결론 (Consequent) |
| 모든 증거가 타당하면 → 판결 인정 | 모든 단계가 정당하면 → 결론 참 |
| 전제 설정 | 참이라고 가정하는 시작점 | 건물의 기둥 |
| 추론 규칙 적용 | 전제로부터 새로운 참 명제 도출 | 벽돌 쌓기 |
| 결론 도출 | 최종 증명 명제 도달 | 완성된 지붕 |
💡 단 하나의 단계라도 논리적 오류가 있으면 전체 증명이 무너진다. 추론 규칙을 정확히 알아야 하는 이유다.
2. 논증(Argument) — 증명의 형식
논증은 결론으로 끝나는 일련의 명제 나열이다. 즉 "전제들 + 결론"의 구조다.
전제 1 (Premise 1)
전제 2 (Premise 2)
⋮
─────────────────
∴ 결론 (Conclusion)기호 ∴ 는 "그러므로(Therefore)"를 뜻한다.
| 정당성(Validity) | 전제가 참이면 결론도 반드시 참 | 논리 구조의 완벽함 |
| 건전성(Soundness) | 정당성 + 모든 전제가 실제로 참 | 구조 + 내용의 완벽함 |
"모든 새는 날 수 있다 (전제 1, 거짓). 참새는 새다 (전제 2, 참). 그러므로 참새는 날 수 있다 (결론, 참)."
이 논증은 정당하지만 건전하지 않다. 전제 1이 거짓이지만, 논리적 구조 자체는 타당하기 때문이다.
💡 시험에서 자주 묻는 함정: "전제가 참이 아니어도 정당한 논증일 수 있다." 정당성은 구조의 문제, 건전성은 사실의 문제다.
3. 추론 규칙(Inference Rules)이란
추론 규칙은 주어진 가정이 참일 때 결론이 참임을 보장하는 논리적 패턴이다.
[입력: 가정] → [처리: 추론 규칙] → [출력: 결론]
각 추론 규칙은 정해진 입력 패턴을 받아 정해진 결론을 출력하는 함수와 같다.
| 논리적 패턴 | 특정 전제 형태 → 특정 결론 형태 |
| 정당성 보장 | 규칙 자체가 항진 명제(Tautology)이므로 항상 참 |
| 기호화 | 논리 기호로 간결하게 표현 |
추론 규칙이 정당한 이유는 그 자체가 항상 참인 함축 명제(Tautology) 이기 때문이다.
예를 들어 가장 유명한 긍정법칙(Modus Ponens)은:
(P ∧ (P → Q)) → Q ← 이 식이 항상 참(Tautology)
이 항진성이 깨지지 않으면, 규칙을 적용한 결론은 무조건 참이다.
4. 추론 규칙 8선 — 한눈에 보기
이번 강에서 다룰 8가지 핵심 추론 규칙을 미리 표로 정리한다. (Rosen 교재 기준 7선 + Resolution 1개 = 8선)
| 1 | 긍정법칙 | Modus Ponens | P, P→Q ⊢ Q |
| 2 | 부정법칙 | Modus Tollens | ¬Q, P→Q ⊢ ¬P |
| 3 | 삼단논법 | Hypothetical Syllogism | P→Q, Q→R ⊢ P→R |
| 4 | 선언적 삼단논법 | Disjunctive Syllogism | P∨Q, ¬P ⊢ Q |
| 5 | 가산 규칙 | Addition | P ⊢ P∨Q |
| 6 | 단순화 규칙 | Simplification | P∧Q ⊢ P |
| 7 | 논리곱 규칙 | Conjunction | P, Q ⊢ P∧Q |
| 8 | 분해 규칙 ⭐ | Resolution | P∨Q, ¬P∨R ⊢ Q∨R |
💡 표기법 ⊢ 은 "전제로부터 결론을 도출한다"는 뜻으로, 일상적으로 ∴ 와 같은 의미로 쓰인다.
💡 왜 8선인가?: 전통적으로 7개 추론 규칙(MP, MT, HS, DS, Add, Simp, Conj)을 묶어 부르지만, 교수님 원래 교안에서는 Resolution(분해 규칙) 을 추가로 강조해 다루므로 사실상 8개를 학습한다. Resolution은 AI 자동 정리 증명의 핵심이라 시험에서도 자주 등장한다.
5. ① 긍정법칙(Modus Ponens) — 가장 기본 ⭐
P가 참이고 P→Q가 참이면, Q는 참.
| 전제 1 | P → Q |
| 전제 2 | P |
| 결론 | ∴ Q |
(P ∧ (P → Q)) → Q
전제 1: "전구에 불이 들어왔다면(P), 스위치가 켜져 있는 것이다(Q)." 전제 2: "전구에 불이 들어왔다(P)." 결론: "그러므로 스위치가 켜져 있다(Q)."
조건문 P→Q에서 P가 참일 때 Q를 '분리(Detach)' 해서 결론으로 가져올 수 있다는 의미.
💡 가장 직관적이고 가장 많이 쓰이는 규칙. 일상의 If-Then 추론은 거의 다 이 규칙이다.
6. ② 부정법칙(Modus Tollens) — 결론 부정으로 전제 부정 ⭐
P→Q가 참이고 Q가 거짓이면, P도 거짓.
| 전제 1 | P → Q |
| 전제 2 | ¬Q |
| 결론 | ∴ ¬P |
(¬Q ∧ (P → Q)) → ¬P
전제 1: "비가 오면(P), 땅이 젖는다(Q)." 전제 2: "땅이 젖지 않았다(¬Q)." 결론: "그러므로 비가 오지 않았다(¬P)."
P→Q는 "P가 참인데 Q가 거짓일 수는 없다"는 약속이다. 그러므로 Q가 거짓인 상황에서는 P도 반드시 거짓이어야 한다.
💡 시험 함정: 부정법칙은 P→Q에서 ¬Q를 얻어 ¬P를 도출한다. 절대 ¬P에서 ¬Q를 도출하면 안 된다 (이건 잘못된 추론, '전건 부정의 오류').
7. ③ 삼단논법(Hypothetical Syllogism) — 추이성
P→Q와 Q→R이 참이면, P→R도 참.
| 전제 1 | P → Q |
| 전제 2 | Q → R |
| 결론 | ∴ P → R |
((P → Q) ∧ (Q → R)) → (P → R)
전제 1: "오늘 비가 오면(P), 바비큐 파티를 하지 않는다(Q)." 전제 2: "바비큐 파티를 하지 않으면(Q), 내일 바비큐 파티를 한다(R)." 결론: "그러므로 오늘 비가 오면, 내일 바비큐 파티를 한다(P → R)."
수학에서 "a < b이고 b < c이면 a < c"와 같은 구조다. 중간 단계를 건너뛰어 직접 연결한다.
💡 여러 조건문이 사슬처럼 연결될 때 사용. 복잡한 증명에서 중간 단계를 압축하는 데 유용하다.
8. ④ 선언적 삼단논법(Disjunctive Syllogism) — 선택지 제거
P∨Q가 참이고 P가 거짓이면, Q는 참.
| 전제 1 | P ∨ Q |
| 전제 2 | ¬P |
| 결론 | ∴ Q |
((P ∨ Q) ∧ ¬P) → Q
전제 1: "내 차 키는 가방 안에 있거나(P), 책상 위에 있다(Q)." 전제 2: "가방 안에는 없다(¬P)." 결론: "그러므로 차 키는 책상 위에 있다(Q)."
"A 또는 B"라는 두 선택지에서 A가 제거되면, 남은 B가 정답이 될 수밖에 없다. 선택지 제거 논리다.
💡 추리 소설의 단골 추론 패턴. 셜록 홈즈가 "불가능한 것을 제거하면 남은 것이 진실"이라 말한 것이 바로 선언적 삼단논법.
9. ⑤ 가산 규칙(Addition) — 선언문 만들기
P가 참이면, P∨Q도 참.
| 전제 | P |
| 결론 | ∴ P ∨ Q |
P → (P ∨ Q)
전제: "오늘 시험이 있다(P)." 결론: "그러므로 오늘 시험이 있거나 오늘 날씨가 좋다(P ∨ Q)."
선언문 P∨Q는 둘 중 하나만 참이면 전체가 참이다. P가 이미 참이라면, Q가 무엇이든 P∨Q는 무조건 참이 된다.
💡 처음 보면 "왜 이게 필요하지?" 싶지만, 분해 규칙(Resolution) 같은 복잡한 추론에서 명제 형태를 맞추는 데 유용하게 쓰인다.
10. ⑥ 단순화 규칙(Simplification) — 연언문 분해
P∧Q가 참이면, P도 참(그리고 Q도 참).
| 전제 | P ∧ Q |
| 결론 | ∴ P (또는 ∴ Q) |
(P ∧ Q) → P
전제: "오늘 오후는 맑지 않고(¬P) 어제보다 추웠다(Q)." 결론: "그러므로 오늘 오후는 맑지 않았다(¬P)."
"A이고 B이다"가 참이려면 A와 B 모두 참이어야 한다. 따라서 둘 중 어느 하나만 떼어내도 그것은 참이다.
💡 형식적 증명에서 복합 전제를 분해해 개별 명제로 만들 때 가장 자주 쓰이는 규칙.
11. ⑦ 논리곱 규칙(Conjunction) — 명제 결합
P가 참이고 Q가 참이면, P∧Q도 참.
| 전제 1 | P |
| 전제 2 | Q |
| 결론 | ∴ P ∧ Q |
((P) ∧ (Q)) → (P ∧ Q)
전제 1: "나는 책을 읽는다(P)." 전제 2: "나는 음악을 듣는다(Q)." 결론: "그러므로 나는 책을 읽고 음악을 듣는다(P ∧ Q)."
| 단순화 (Simplification) | P ∧ Q → P (분해) |
| 논리곱 (Conjunction) | P, Q → P ∧ Q (결합) |
서로 정반대 방향의 규칙이다.
12. ⑧ 분해 규칙(Resolution) — 컴퓨터 정리 증명의 핵심 ⭐⭐⭐⭐
P∨Q와 ¬P∨R이 참이면, Q∨R도 참.
| 전제 1 | P ∨ Q |
| 전제 2 | ¬P ∨ R |
| 결론 | ∴ Q ∨ R |
((P ∨ Q) ∧ (¬P ∨ R)) → (Q ∨ R)
전제 1: "이번 주말에 비가 오거나(P), 공원에 놀러 갈 것이다(Q)." 전제 2: "이번 주말에 비가 오지 않거나(¬P), 집에서 넷플릭스를 볼 것이다(R)." 결론: "그러므로 공원에 놀러 가거나(Q), 집에서 넷플릭스를 볼 것이다(Q ∨ R)."
| P가 참 | 전제 2의 ¬P 거짓 → R 참이어야 함 | Q∨R 참 ✅ |
| P가 거짓 | 전제 1의 P 거짓 → Q 참이어야 함 | Q∨R 참 ✅ |
P가 참이든 거짓이든 Q∨R은 항상 참 → 항진 성립.
Resolution은 두 선언문(OR 명제)에서 서로 부정 관계인 항을 찾아 소거하고 남은 항들을 OR로 결합하는 규칙이다. 이 패턴은 절(clause) 단위 추론의 표준이다.
| 1 | 두 선언문에서 P와 ¬P 같은 상보 쌍 찾기 |
| 2 | 상보 쌍 소거 |
| 3 | 남은 항들을 ∨로 결합 |
| 자동 정리 증명 (Automated Theorem Proving) | 컴퓨터가 수학 정리를 자동으로 증명 |
| 논리 프로그래밍 (Prolog 등) | 질의응답 시스템의 추론 엔진 |
| SAT solver | 명제 논리식 만족 가능성 판별 |
| AI 지식 베이스 | 사실들로부터 새로운 사실 도출 |
💡 분해 규칙의 응용: AI의 자동 정리 증명, Prolog 같은 논리 프로그래밍 언어, SAT solver 등의 핵심 알고리즘이 바로 이 분해 규칙이다. 단순해 보이지만 컴퓨터가 논리를 다룰 때 가장 중요한 규칙이다.
⚠️ 시험 빈출: Resolution은 단답형으로 "두 전제로부터 결론을 도출하시오" 형태로 자주 출제된다. 상보 쌍(P와 ¬P)을 빠르게 찾아 소거하는 연습을 해두자.
13. 추론 규칙 8가지 비교 정리표
| Modus Ponens | P, P→Q | Q | "전건 긍정 → 후건 긍정" |
| Modus Tollens | ¬Q, P→Q | ¬P | "후건 부정 → 전건 부정" |
| Hypothetical Syll. | P→Q, Q→R | P→R | "조건문 사슬 연결" |
| Disjunctive Syll. | P∨Q, ¬P | Q | "선택지 제거" |
| Addition | P | P∨Q | "참 명제에 OR 추가 가능" |
| Simplification | P∧Q | P | "AND 명제 분해" |
| Conjunction | P, Q | P∧Q | "참 명제들 AND 결합" |
| Resolution ⭐ | P∨Q, ¬P∨R | Q∨R | "P 소거 후 결합" |
📌 한눈에 보는 핵심정리
| 증명(Proof) | 명제의 참을 확립하는 정당한 논증 |
| 논증(Argument) | 전제 + 결론의 구조 |
| 정당성(Validity) | 전제가 참이면 결론도 반드시 참 |
| 건전성(Soundness) | 정당성 + 모든 전제가 실제로 참 |
| 추론 규칙 | 전제→결론의 논리적 패턴, 본질은 항진 명제 |
| Modus Ponens | P, P→Q ⊢ Q (가장 기본) |
| Modus Tollens | ¬Q, P→Q ⊢ ¬P (대우 추론) |
| Hypothetical Syll. | P→Q, Q→R ⊢ P→R (조건문 추이) |
| Disjunctive Syll. | P∨Q, ¬P ⊢ Q (선택지 제거) |
| Resolution ⭐ | P∨Q, ¬P∨R ⊢ Q∨R (AI 정리증명 핵심) |
🧠 예상문제 2제
문제 1. 추론 규칙 식별
다음 논증에 적용된 추론 규칙으로 가장 적절한 것은?
전제 1: "만약 시험을 잘 보면, 장학금을 받는다." 전제 2: "장학금을 받지 못했다." 결론: "그러므로 시험을 잘 보지 못했다."
① 긍정법칙(Modus Ponens) ② 부정법칙(Modus Tollens) ③ 삼단논법(Hypothetical Syllogism) ④ 선언적 삼단논법(Disjunctive Syllogism)
👉 정답: ②
기호화하면:
| 전제 1 | P → Q (시험 잘 봄 → 장학금) |
| 전제 2 | ¬Q (장학금 못 받음) |
| 결론 | ¬P (시험 잘 못 봄) |
이는 부정법칙(Modus Tollens) 의 정확한 형태다: (¬Q ∧ (P → Q)) → ¬P
⚠️ 시험 함정: 만약 결론이 "그러므로 장학금을 받지 못했다"였다면 긍정법칙이지만, 결론에서 전제를 부정하고 있으므로 부정법칙이다. 화살표 방향(P→Q)에서 후건의 부정으로 전건의 부정을 끌어내는 추론이다.
문제 2. 분해 규칙(Resolution) 적용
다음 두 전제로부터 분해 규칙을 적용했을 때 도출되는 결론은?
전제 1: "회의는 화요일이거나(P), 줌으로 진행된다(Q)." 전제 2: "회의는 화요일이 아니거나(¬P), 자료가 사전 배포된다(R)."
① P ∨ R ② ¬P ∨ Q ③ Q ∨ R ④ ¬Q ∨ R
👉 정답: ③
분해 규칙 형식:
| 전제 1 | P ∨ Q |
| 전제 2 | ¬P ∨ R |
| 결론 | Q ∨ R |
P와 ¬P가 서로 소거되고, 남은 Q와 R이 ∨로 결합된다.
해석: "회의는 줌으로 진행되거나, 자료가 사전 배포된다."
💡 추가 학습: 분해 규칙은 두 선언문에서 서로 부정 관계인 항(P와 ¬P)을 찾아 소거하는 것이 핵심이다. AI 정리증명에서는 이 과정을 컴퓨터가 자동으로 반복 수행하여 결론을 도출한다.
'📌 SW전공-개념 > 이산구조' 카테고리의 다른 글
| [이산구조 개념-08] 한정자 추론 규칙 — UI·EI와 증명의 언어 (0) | 2026.05.31 |
|---|---|
| [이산구조 개념-07] 형식적 증명 — 추론 규칙으로 결론 만들기 (1) | 2026.05.30 |
| [이산구조 개념-05] 한정자의 순서·부정·동치 — 술어 논리 심화 (0) | 2026.05.28 |
| [이산구조 특별편 1] 드모르간과 AI — 19세기 논리가 21세기 인공지능이 되기까지 (1) | 2026.05.26 |
| [이산구조 개념-02] 항진·부정·동치 — 명제의 세 가지 운명 (0) | 2026.05.24 |