[이산구조 개념-08] 한정자 추론 규칙 — UI·EI와 증명의 언어

1. 왜 한정자 추론 규칙이 필요한가

지금까지 다룬 추론 규칙들(Modus Ponens, Modus Tollens 등)은 모두 명제 변수 P, Q, R 단위에서 작동했다. 그런데 술어 논리에서는 변수와 한정자가 포함된 명제(∀x P(x), ∃x P(x))를 다뤄야 한다.

단계다루는 대상핵심 추론 규칙

명제 논리 (6~7강)	P, Q, R 같은 단순 명제	Modus Ponens, Resolution 등
술어 논리 (8강)	∀x P(x), ∃x P(x) 같은 한정자 명제	UI, EI 등

이를 가능하게 하는 것이 한정자 추론 규칙 — 특히 보편 예화(UI) 와 존재 예화(EI) 다.

---

2. 한정자(Quantifier) — 빠른 복습

4~5강에서 다뤘던 한정자의 핵심을 빠르게 복습한다.

한정자기호의미엄격도

보편 한정자	∀	모든 ~에 대해	엄격 (예외 0개)
존재 한정자	∃	어떤 ~가 적어도 하나 존재	유연 (1개라도 OK)

💡 한정자는 단순 명제를 넘어 데이터의 범위(Range) 를 다루는 도구다. "모든 학생", "어떤 학생"처럼 명제의 적용 범위를 명확히 한다.

---

3. 보편 예화 (Universal Instantiation, UI) ⭐ 핵심

정의

보편 예화(UI) 는 보편적으로 참인 명제 ∀x P(x)로부터, 도메인에 속하는 임의의 특정 요소 c에 대한 명제 P(c)가 참임을 추론하는 규칙이다.

형식

위치명제

전제	∀x P(x)
결론	∴ P(c) (단, c는 도메인의 임의 원소)

직관

"전체에게 참이라면, 개별에게도 참이다."

전체 집합에 대한 참인 진실을 개별 구성원 하나에게 적용하는 과정이다.

일상 예시

단계내용

보편 명제	"모든 포유류는 척추를 가지고 있다" → ∀x (Mammal(x) → HasSpine(x))
사실	"코끼리는 포유류다"
UI 적용	"코끼리는 척추를 가지고 있다" → Mammal(코끼리) → HasSpine(코끼리)

시험 빈출 활용

UI는 보통 Modus Ponens와 결합되어 출제된다.

 

 

[전제 1] ∀x (P(x) → Q(x))   ... "모든 x에 대해 P이면 Q"
[전제 2] P(c)               ... 특정 c에 대해 P(c) 참
[Step 1] P(c) → Q(c)        ... UI 적용
[Step 2] Q(c)               ... Modus Ponens 적용

💡 법률 적용 비유: "모든 사람은 법 앞에 평등하다"는 보편 원칙을 "김 씨도 법 앞에 평등하다"로 적용하는 것이 UI의 본질이다.

---

4. 존재 예화 (Existential Instantiation, EI) ⭐ 핵심

정의

존재 예화(EI) 는 존재적으로 참인 명제 ∃x P(x)로부터, 그 조건을 만족하는 특정 요소 c가 적어도 하나 존재함을 가정하고 c라는 이름을 부여하는 규칙이다.

형식

위치명제

전제	∃x P(x)
결론	∴ P(c) (단, c는 새로 도입한 특정 상수)

직관

"조건을 만족하는 누군가가 있다면, 그 누군가에게 임시로 이름을 붙여 추론을 시작하자."

일상 예시

단계내용

존재 명제	"어떤 새는 날 수 없다" → ∃x (Bird(x) ∧ ¬CanFly(x))
EI 적용	그 새를 c (예: 펭귄)라고 부르자 → Bird(c) ∧ ¬CanFly(c)
추가 추론	c를 가지고 다른 결론 도출 가능

UI vs EI 핵심 차이

구분UIEI

시작 명제	∀x P(x)	∃x P(x)
도입하는 c	임의의 어떤 원소든 OK	특정 조건 만족하는 c (이름 붙이기)
결과	P(c) (어떤 c라도 성립)	P(c) (이 특정 c에 대해 성립)
비유	"법률을 김씨에게 적용"	"범인이 있다면 그를 X라 부르자"

주의사항

EI에서 도입한 c는 "조건을 만족하는 어떤 하나"일 뿐, 그것이 유일하다는 의미는 아니다. 단지 추론 편의상 임시 이름을 붙인 것이다.

💡 시험 함정: EI로 도입한 c를 절대 이미 사용된 다른 변수와 동일시하면 안 된다. c는 새로 등장한 익명의 개체다.

---

5. UI·EI 응용 — 술어 논리 형식적 증명 예제

문제

다음 가정들로부터 결론을 도출하시오.

가정 1: ∀x (Student(x) → Studies(x)) ("모든 학생은 공부한다") 가정 2: Student(Ella) ("Ella는 학생이다") 결론: Studies(Ella) ("Ella는 공부한다")

풀이

단계도출적용 규칙

1	∀x (Student(x) → Studies(x))	가정 1
2	Student(Ella) → Studies(Ella)	UI (Step 1, x → Ella)
3	Student(Ella)	가정 2
4	Studies(Ella) ✅	Modus Ponens (Step 2, Step 3)

💡 핵심 흐름: 보편 명제 → UI로 특정화 → Modus Ponens로 결론 도출. 술어 논리 증명에서 가장 자주 등장하는 패턴이다.

---

6. 증명 세계의 어휘 사전 ⭐ 시험 단답형 빈출

본격적인 증명 전략(9~10강)에 들어가기 전, 증명 세계에서 사용되는 5가지 핵심 용어를 정확히 구분해야 한다.

용어영문정의증명 필요?

공리	Axiom / Postulate	증명 없이 참으로 받아들이는 근본 가정	❌ 불필요
가설	Conjecture	참일 것으로 믿어지지만 아직 증명되지 않은 명제	⏳ 증명 대상
정리	Theorem	엄밀한 증명을 거쳐 참으로 확정된 명제	✅ 증명 완료
보조정리	Lemma	더 큰 정리를 증명하기 위한 디딤돌 정리	✅ 증명 완료
따름정리	Corollary	정리로부터 자연스럽게 파생되는 부가 명제	✅ 증명 완료

---

7. 공리(Axiom) — 증명의 출발점

공리는 증명할 필요가 없이 참으로 받아들여지는 근본적인 가정이다.

건축 비유

건축수학

단단한 기초	공리
설계도	추론 규칙
완성된 건물	정리

모든 증명은 어떤 시작점에서 출발해야 하며, 그 시작점이 바로 공리다.

공리의 특징

특징설명

증명 불필요	스스로가 참이므로 추가 증명 없이 사용
근본 가정	시스템의 가장 기본적인 전제
구조 정의	다른 모든 명제가 공리를 기반으로 도출

공리 예시

분야공리

유클리드 기하학	"서로 다른 두 점을 지나는 유일한 직선이 존재한다"
정수론	"n이 짝수라면 n = 2k로 표현 가능하다 (k는 정수)" — 짝수의 정의
집합론	"동일한 원소를 갖는 두 집합은 같다"

💡 공리는 "왜 참인가?"를 묻지 않는다. 그것이 참이라는 약속에서 출발한다.

---

8. 정리(Theorem) — 증명된 진실

정리는 엄밀한 증명 과정을 거쳐 논리적 진실성이 최종 확인된 명제다.

정리의 3대 특징

특징설명

참으로 밝혀짐	증명을 통해 진리값이 참으로 확정
엄밀한 증명 과정	논리적으로 타당한 모든 단계를 거침
수학 연구의 목표	새 정리 발견이 수학 연구의 핵심

대표 정리 예시

정리내용

피타고라스 정리	직각삼각형에서 c² = a² + b²
페르마의 마지막 정리	n ≥ 3일 때 xⁿ + yⁿ = zⁿ을 만족하는 양의 정수 해 없음
"n이 홀수이면 n²도 홀수"	9강 직접 증명 예제

💡 한 번 증명된 정리는 다른 정리를 증명하는 새로운 도구가 된다. 이런 식으로 수학적 지식이 누적적으로 확장된다.

---

9. 보조정리(Lemma) — 디딤돌 정리

보조정리는 다른 주요 정리를 증명하기 위한 디딤돌 역할을 하는 작은 정리다.

비유

큰 산을 오를 때 중간에 놓는 베이스캠프 같은 존재. 그 자체로도 의미 있지만, 주된 목적은 더 큰 정리(정상 정복)를 위한 발판이다.

보조정리 사용 예시

 

 

[목표] 정리 A (예: 큰 분수 정리)
   ↓ 직접 증명이 너무 복잡함
[보조정리 1] 작은 사실 1 증명
[보조정리 2] 작은 사실 2 증명
   ↓ 이 두 보조정리를 결합
[정리 A 증명 완료]

💡 복잡한 정리를 증명할 때는 보조정리로 잘게 쪼개는 전략이 유효하다. 코드의 함수 분리와 비슷한 원리다.

---

10. 따름정리(Corollary) — 자연스러운 파생 결과

따름정리는 어떤 정리가 증명됨에 따라 자연스럽고 쉽게 파생되는 부가적인 정리다.

정리 vs 따름정리

구분정리따름정리

증명 난이도	핵심 노력 필요	정리가 증명되면 거의 자명
위상	주역	조연 (정리의 직접적 결과)
비유	새 빌딩 완공	빌딩에 딸린 부속 시설

따름정리 예시

정리따름정리

"n이 홀수이면 n²도 홀수"	"n²이 짝수이면 n도 짝수" (대우)
피타고라스 정리	직각삼각형 빗변 계산 공식 (단순 적용)

💡 따름정리는 정리를 증명한 노력의 부산물이라 볼 수 있다. 시험에서 "이것은 이전 정리의 따름정리다"라는 말이 나오면, 추가 증명 없이 적용 가능하다는 뜻.

---

11. 가설(Conjecture) — 아직 증명되지 않은 도전

가설은 참일 것으로 널리 믿어지지만 아직 증명되지 않은 명제다.

유명한 가설 예시

가설내용상태

골드바흐의 추측	2보다 큰 모든 짝수는 두 소수의 합	미해결 (1742~)
리만 가설	리만 제타 함수의 비자명한 영점은 모두 1/2 직선 위에 있음	미해결 (1859~)
페르마의 마지막 정리	(위와 동일)	1995년 증명되어 정리로 격상

💡 가설은 증명되면 정리로 격상된다. 페르마의 마지막 정리는 350년간 가설이었다가 1995년 앤드루 와일스에 의해 증명되어 진짜 '정리'가 되었다.

---

12. 추론 규칙(Rules of Inference) 종합 위치

지금까지 배운 모든 도구를 위치별로 정리하면 다음과 같다.

영역도구강의

출발점	공리, 정의	8강
목표	정리, 따름정리	8강
명제 추론 도구	Modus Ponens, Modus Tollens, 삼단논법, 분해규칙 등 8가지	6강
한정자 추론 도구	UI, EI	8강
명제 변형 도구	동치 법칙 12선 (드모르간, 분배 등)	3강
증명 전략	직접·대우·모순·경우별·존재·유일성	9~10강

💡 9~10강에서 다룰 4대 증명 전략은 위 도구들을 어떤 순서·어떤 방식으로 조합할 것인가의 큰 그림이다.

---

📌 한눈에 보는 핵심정리

개념핵심 내용

보편 예화 (UI)	∀x P(x) ⊢ P(c) — 전체에서 개별
존재 예화 (EI)	∃x P(x) ⊢ P(c) — 존재하는 c에 임시 이름 부여
UI 활용 패턴	보편 명제 → UI → Modus Ponens
EI 주의점	c는 익명 개체, 기존 변수와 동일시 금지
공리	증명 없이 참으로 받아들이는 근본 가정
가설	참일 것으로 믿어지나 미증명 (예: 리만 가설)
정리	증명된 참 명제 (예: 피타고라스 정리)
보조정리	큰 정리를 위한 디딤돌 정리
따름정리	정리에서 자연스럽게 파생된 결과

---

🧠 예상문제 2제

문제 1. 한정자 추론 규칙 식별

다음 증명 단계에서 Step 2에 적용된 추론 규칙으로 옳은 것은?

가정 1: ∀x (Bird(x) → HasFeathers(x)) 가정 2: Bird(Sparrow)

 

 

Step 1: ∀x (Bird(x) → HasFeathers(x))   (가정 1)
Step 2: Bird(Sparrow) → HasFeathers(Sparrow)   (?)
Step 3: HasFeathers(Sparrow)            (Modus Ponens, Step 2와 가정 2)

① 보편 예화 (Universal Instantiation, UI) ② 존재 예화 (Existential Instantiation, EI) ③ Modus Tollens ④ 단순화 (Simplification)

👉 정답: ①

Step 1의 보편 명제 ∀x (Bird(x) → HasFeathers(x))에서 변수 x를 특정 개체 Sparrow로 치환하여 Bird(Sparrow) → HasFeathers(Sparrow)를 도출한 것이다. 이는 보편 예화(UI) 의 정확한 적용이다.

💡 시험 핵심 패턴: ∀x → 특정 c 치환 = UI. 그 후 Modus Ponens로 결론 도출하는 흐름이 술어 논리 증명의 기본 공식이다.

---

문제 2. 증명 용어 구분

다음 중 공리(Axiom) 에 해당하는 것은?

① "n이 홀수이면 n²도 홀수이다" — 직접 증명을 통해 참임이 입증된 명제 ② "골드바흐의 추측" — 2보다 큰 모든 짝수는 두 소수의 합으로 표현 가능 ③ "서로 다른 두 점을 지나는 유일한 직선이 존재한다" — 유클리드 기하학의 기본 가정 ④ "n²이 짝수이면 n도 짝수이다" — 위 명제의 대우로부터 자연스럽게 도출

👉 정답: ③

각 선택지의 분류:

• ① 정리(Theorem) — 증명된 명제
• ② 가설(Conjecture) — 미증명 명제 (1742년부터 미해결)
• ③ 공리(Axiom) — 유클리드 기하학의 5대 공리 중 하나, 증명 없이 받아들이는 기본 가정 ✅
• ④ 따름정리(Corollary) — 다른 정리에서 자연스럽게 파생

⚠️ 시험 빈출 포인트: 공리·가설·정리·따름정리·보조정리의 구분은 단답형으로 매우 자주 출제된다. 각 용어의 핵심 차이를 한 줄로 외워두자. 공리 = 증명 불필요 / 가설 = 증명 미완료 / 정리 = 증명 완료 / 보조정리 = 정리 위한 디딤돌 / 따름정리 = 정리의 자연스러운 파생.