[이산구조 개념-07] 형식적 증명 — 추론 규칙으로 결론 만들기

1. 형식적 증명이란

형식적 증명(Formal Proof) 은 개별 추론 규칙(블록)들을 연결하여 거대한 결론(건축물)을 완성하는 과정이다.

레고 블록 비유

레고형식적 증명

개별 블록	추론 규칙 (Modus Ponens, Resolution 등)
설계도	증명 전략 (어떤 규칙을 어떤 순서로)
시작 부품	가정 (Premises)
완성 작품	결론 (Conclusion)
부실 블록 1개	전체 무너짐 ❌

💡 단 하나의 추론 규칙 적용이라도 잘못되면 전체 증명이 무효가 된다. 그래서 각 단계마다 어떤 규칙을 적용했는지 명시하는 것이 형식적 증명의 핵심 규칙이다.

---

2. 형식적 증명의 4대 특징

특징설명

체계적인 단계	각 단계는 명확한 추론 규칙에 따라 진행
가정에서 결론으로	참으로 주어진 전제에서 시작 → 목표 결론에 도달
추론 규칙의 활용	각 단계의 '연결재' 역할
오류 불허	단 하나의 논리적 오류도 증명 전체를 무효화

형식적 증명의 구조

 

 

[가정 1]    : 주어진 전제 1
[가정 2]    : 주어진 전제 2
   ⋮
[Step 1]    : (가정으로부터 도출) ... 적용한 규칙 명시
[Step 2]    : (Step 1로부터 도출) ... 적용한 규칙 명시
   ⋮
[결론]      : 목표 명제 도달

핵심은 시작점(가정) → 연결재(추론 규칙) → 도착점(결론) 의 3단 구조다.

---

3. 증명 작성의 5단계 전략 ⭐ 시험 핵심

형식적 증명 문제는 다음 5단계로 접근하면 거의 모든 문제를 풀 수 있다.

단계작업핵심 질문

1단계	일상 문장을 명제 변수로 치환	"어떤 명제를 P, Q, R로 둘까?"
2단계	모든 가정을 논리식으로 표현	"각 전제는 어떤 논리 구조인가?"
3단계	목표 결론 확인	"최종적으로 도달해야 할 명제는?"
4단계	추론 규칙으로 단계 연결	"어떤 규칙을 어떤 순서로?"
5단계	각 단계마다 적용 규칙 명시	"이 단계는 무슨 규칙으로 도출됐나?"

💡 시험 만점 비결: 4단계에서 막힐 때는 결론에서 거꾸로 역추적해보자. "결론을 얻으려면 직전 단계가 무엇이어야 하나?" 를 반복하면 길이 보인다.

---

4. 종합 예제 ⭐⭐⭐ — 일몰 전에 집에 도착하기

이번 강의 핵심 예제다. PDF에서 강조된 종합 증명 문제를 단계별로 풀어본다.

문제

다음 가정들로부터 "일몰 전에 집에 도착할 것이다" 라는 결론을 형식적으로 증명하시오.

가정 1: "오늘 오후는 맑지 않았고, 어제보다 추웠다." 가정 2: "수영을 갈 거라면, 오늘 오후가 맑아야 한다." 가정 3: "수영을 가지 않으면, 카누를 탈 것이다." 가정 4: "카누를 타면, 일몰 전에 집에 도착할 것이다."

목표 결론: "일몰 전에 집에 도착할 것이다."

---

Step 1 — 변수 치환

변수의미

p	오늘 오후가 맑다
q	어제보다 춥다
r	수영을 갈 것이다
s	카누를 탈 것이다
t	일몰 전에 집에 도착할 것이다

---

Step 2 — 가정을 논리식으로

가정일상 문장논리식

가정 1	오후가 맑지 않고, 어제보다 춥다	¬p ∧ q
가정 2	수영 가려면 맑아야 함	r → p
가정 3	수영 안 가면 카누 탐	¬r → s
가정 4	카누 타면 일몰 전 도착	s → t
목표	일몰 전 도착	t

---

Step 3 — 목표 확인

목표는 단일 명제 t 를 도출하는 것.

---

Step 4~5 — 단계별 증명

단계도출 명제적용 규칙사용한 전제

1	¬p ∧ q	가정 1	—
2	¬p	단순화 (Simplification)	Step 1
3	r → p	가정 2	—
4	¬r	부정법칙 (Modus Tollens)	Step 2, Step 3
5	¬r → s	가정 3	—
6	s	긍정법칙 (Modus Ponens)	Step 4, Step 5
7	s → t	가정 4	—
8	t ✅	긍정법칙 (Modus Ponens)	Step 6, Step 7

증명 완료 ✅

---

풀이 흐름 직관 정리

 

 

¬p ∧ q (가정1)
   ↓ 단순화
  ¬p
   ↓ + (r→p) (가정2) → 부정법칙
  ¬r
   ↓ + (¬r→s) (가정3) → 긍정법칙
   s
   ↓ + (s→t) (가정4) → 긍정법칙
   t  ← 목표 도달!

💡 핵심 풀이 패턴: 복합 가정(¬p ∧ q)을 단순화로 분해 → 분해된 명제로 Modus Ponens/Tollens 연쇄 적용 → 최종 결론 도달.

---

5. 증명 전략 — 어디서부터 시작할까?

처음 형식적 증명 문제를 보면 막막하다. 다음 4가지 전략을 순서대로 시도해보자.

전략 1 — 단순한 명제부터 확보

복합 가정(P∧Q)이 있다면 단순화 규칙으로 P와 Q를 각각 분리해두자. 이렇게 하면 사용 가능한 명제가 늘어난다.

전략 2 — 함축(→) 전제를 활용

P→Q 형태의 가정이 있다면:

• P를 가지고 있다면 → Modus Ponens로 Q 도출
• ¬Q를 가지고 있다면 → Modus Tollens로 ¬P 도출
• 다른 함축 Q→R이 있다면 → 삼단논법으로 P→R 도출

전략 3 — 선언(∨) 전제를 활용

P∨Q 형태의 가정이 있다면:

• ¬P를 가지고 있다면 → 선언적 삼단논법으로 Q 도출
• ¬P∨R 형태가 또 있다면 → 분해 규칙으로 Q∨R 도출

전략 4 — 결론에서 역추적(Backward Reasoning)

모든 시도가 막히면 결론에서 거꾸로 추적한다.

결론 형태역추적 질문

결론 Q	"P→Q와 P를 만들 수 있는가?"
결론 ¬P	"P→Q와 ¬Q를 만들 수 있는가?"
결론 P∧Q	"P와 Q를 각각 따로 만들 수 있는가?"
결론 P∨Q	"P 또는 Q 중 하나라도 만들 수 있는가?"

---

6. 자주 쓰이는 증명 패턴 5가지

시험에 자주 나오는 증명 패턴을 미리 익혀두면 풀이 속도가 크게 빨라진다.

패턴 ① 단순화 → Modus Ponens

 

 

[가정] P ∧ Q, P → R
[Step 1] P              (단순화)
[Step 2] R              (Modus Ponens)

패턴 ② 단순화 → Modus Tollens

 

 

[가정] ¬Q ∧ S, P → Q
[Step 1] ¬Q             (단순화)
[Step 2] ¬P             (Modus Tollens)

패턴 ③ 삼단논법 사슬

 

 

[가정] P → Q, Q → R, R → S
[Step 1] P → R          (삼단논법)
[Step 2] P → S          (삼단논법)

패턴 ④ 분해 규칙 연쇄

 

 

[가정] P ∨ Q, ¬P ∨ R, ¬R ∨ S
[Step 1] Q ∨ R          (분해, 전제 1·2)
[Step 2] Q ∨ S          (분해, Step 1과 전제 3)

패턴 ⑤ Modus Tollens → Modus Ponens

(예제 4에서 쓴 패턴) ¬결과 → ¬조건 도출 → 다른 함축의 시작점으로 활용

 

 

[가정] ¬p ∧ q, r → p, ¬r → s
[Step 1] ¬p             (단순화)
[Step 2] ¬r             (Modus Tollens)
[Step 3] s              (Modus Ponens)

💡 이 5가지 패턴이 형식적 증명 문제의 80% 이상을 커버한다. 시험 직전에 한 번씩 풀어보고 들어가자.

---

7. 증명 시 자주 하는 실수 5가지

실수 ① 적용 규칙 명시 누락

 

 

❌ 잘못된 예
Step 1: ¬p
Step 2: ¬r

⭕ 올바른 예
Step 1: ¬p     (단순화, 가정 1)
Step 2: ¬r     (Modus Tollens, Step 1과 가정 2)

실수 ② Modus Ponens와 Modus Tollens 혼동

올바른 적용잘못된 적용 (오류)

P→Q, P ⊢ Q (긍정법칙)	P→Q, Q ⊢ P (후건 긍정의 오류)
P→Q, ¬Q ⊢ ¬P (부정법칙)	P→Q, ¬P ⊢ ¬Q (전건 부정의 오류)

실수 ③ 함축의 방향 역행

P→Q는 P가 참이면 Q가 참을 의미한다. 절대 Q→P로 거꾸로 사용하면 안 된다 (이건 '역(Converse)' 으로, 동치가 아님).

실수 ④ 단순화 규칙의 오용

P∧Q에서는 P와 Q 각각 도출 가능하지만, P∨Q에서는 P나 Q를 단독으로 도출할 수 없다. (∨에서는 둘 중 하나만 참이어도 전체가 참이므로 어느 쪽이 참인지 모름)

실수 ⑤ 사용한 전제 표기 누락

각 단계에 어떤 가정/단계를 사용했는지 함께 적어야 채점에서 감점되지 않는다.

⚠️ 시험에서 답만 맞으면 되는 게 아니라, 증명 과정의 정당성이 평가 대상이다. 단계마다 근거를 명시하는 습관을 들이자.

---

8. 추가 연습 예제 — 셀프 풀이

다음 가정들로부터 q ∨ r 을 증명해보자. 직접 풀어본 후 정답과 비교해보자.

문제

가정 1: p ∨ q 가정 2: ¬p ∨ r 목표: q ∨ r

정답 풀이

단계도출규칙

1	p ∨ q	가정 1
2	¬p ∨ r	가정 2
3	q ∨ r ✅	분해 규칙 (Resolution)

분해 규칙 한 번으로 끝나는 가장 단순한 형태다.

💡 분해 규칙은 시험에서 단독으로 출제되기보다, 다른 규칙들과 결합해 출제된다. 패턴을 정확히 인식하는 연습이 필요하다.

---

📌 한눈에 보는 핵심정리

항목내용

형식적 증명	추론 규칙을 연결하여 결론 도출하는 체계적 과정
3대 구성	시작점(가정) + 연결재(추론규칙) + 도착점(결론)
5단계 풀이	변수 치환 → 논리식화 → 목표 확인 → 규칙 연결 → 규칙 명시
핵심 패턴 ①	단순화 → Modus Ponens
핵심 패턴 ②	단순화 → Modus Tollens
핵심 패턴 ③	삼단논법 사슬
핵심 패턴 ④	분해 규칙 연쇄
풀이 막힐 때	결론에서 거꾸로 역추적
자주 하는 실수	규칙 미명시, 함축 방향 역행, ∨를 ∧처럼 단순화
시험 만점 키	단계별 적용 규칙 + 사용 전제 명확히 표기

---

🧠 예상문제 2제

문제 1. 단계별 형식적 증명

다음 가정들로부터 결론 t 를 형식적 증명으로 도출할 때, Step 3에 들어갈 명제와 적용 규칙으로 옳은 것은?

가정 1: ¬p ∧ q 가정 2: r → p 가정 3: ¬r → s 가정 4: s → t

 

 

Step 1: ¬p           (단순화, 가정 1)
Step 2: ¬r           (Modus Tollens, Step 1과 가정 2)
Step 3: ?            (?)
Step 4: t            (Modus Ponens, Step 3과 가정 4)

① s, 긍정법칙(Modus Ponens, Step 2와 가정 3) ② ¬s, 부정법칙(Modus Tollens, Step 2와 가정 3) ③ s ∨ t, 가산 규칙(Addition, Step 2) ④ s ∧ t, 논리곱 규칙(Conjunction, Step 2와 가정 3)

👉 정답: ①

Step 3은 가정 3(¬r → s)에 Step 2의 ¬r을 적용한 결과다.

• ¬r → s 형태에서 전건 ¬r이 참이므로 → 후건 s가 참
• 이는 긍정법칙(Modus Ponens) 의 정확한 적용이다.

이후 Step 4에서 s → t와 s를 사용해 또 다시 긍정법칙으로 t를 도출하면 증명 완료.

💡 풀이 흐름 복습: ¬p ∧ q (가정1) → ¬p (단순화) → ¬r (Modus Tollens) → s (Modus Ponens) → t (Modus Ponens). 본문 4번 종합 예제와 동일한 구조다.

---

문제 2. 증명 전략 선택

다음 가정들로부터 r 을 증명하려고 한다. 첫 단계로 가장 적절한 추론 규칙은?

가정 1: p → q 가정 2: q → r 가정 3: p

① 단순화 규칙 (가정 1에 적용) ② 가산 규칙 (가정 3에 적용) ③ 삼단논법 (가정 1과 가정 2에 적용) ④ 부정법칙 (가정 2에 적용)

👉 정답: ③

가정 1(p→q)과 가정 2(q→r)를 삼단논법(Hypothetical Syllogism) 으로 결합하면 p→r이 도출된다. 그 후 가정 3(p)에 Modus Ponens를 적용하면 결론 r을 얻는다.

단계도출규칙

1	p → r	삼단논법 (가정 1, 가정 2)
2	r ✅	Modus Ponens (Step 1, 가정 3)

💡 다른 풀이도 가능: 가정 1과 가정 3에 먼저 Modus Ponens를 적용해 q를 얻고, 그 다음 가정 2와 Modus Ponens로 r을 얻어도 된다. 하지만 삼단논법으로 묶는 풀이가 한 단계 더 간결하다. 시험에서는 여러 풀이 경로가 존재하므로, 자신이 가장 자신 있는 패턴으로 풀어도 정답 처리된다.

⚠️ ① 단순화는 ∧ 명제에만 적용 가능 (가정 1은 → 명제이므로 불가). ② 가산은 결론과 무관한 명제 추가라 부적절. ④ 부정법칙은 ¬결과가 있어야 적용 가능한데 여기엔 없음.