12. Quantificational Logic

왜 Quantificational Logic이 필요한가?

명제 논리(Propositional Logic)로는 "모든 학생은 똑똑하다" 같은 문장을 표현할 수 없다. 명제 논리는 p, q, r 같은 개별 명제만 다룰 수 있어서, "모든"이나 "어떤"처럼 집합 전체에 대한 말을 못 한다.

Quantificational Logic(양화 논리)은 명제 논리를 확장해서 이런 것들을 다룰 수 있게 해준다.

• Objects: 학생, 숫자, 컴퓨터 등
• Properties: "암탉이다", "소수다" 등
• Relations: "x는 y를 사랑한다", "x > y" 등

---

핵심 구성요소 1: Predicate (술어)

Predicate는 변수를 받아서 True/False를 돌려주는 함수 템플릿이다. 변수에 값을 넣으면 비로소 명제가 된다.

• H(x) = "x는 암탉이다" → H(Ginger) = "Ginger는 암탉이다" (True/False 확정)
• L(x,y) = "x는 y를 사랑한다"
• S(x,y,z) = "x + y = z" → S(1,2,3) = True, S(3,2,1) = False

---

핵심 구성요소 2: Universe (전체집합)

Universe of Discourse (U)는 변수가 가질 수 있는 값의 범위다. 같은 식이라도 Universe에 따라 True/False가 달라진다.

예를 들어 ∃x S(x,5,3) ("x + 5 = 3인 x가 존재하는가?"):

• U = {양의 정수}: False (음수가 없으니까)
• U = {정수}: True (x = -2가 존재)

---

핵심 구성요소 3: Quantifiers (한정자)

∀ (Universal Quantifier): "for all", "모든"

• ∀x H(x) = "모든 x는 암탉이다"
• Universe의 모든 x에 대해 True여야 전체가 True

∃ (Existential Quantifier): "there exists", "존재한다"

• ∃x H(x) = "암탉이 적어도 하나 존재한다"
• Universe에서 하나라도 True면 전체가 True

---

영어 번역 패턴 (중요!)

• "모든 P는 Q다" → ∀x(P(x) ⇒ Q(x))
• "어떤 P는 Q다" → ∃x(P(x) ∧ Q(x))

흔한 실수:

• ∀x(P(x) ∧ Q(x)) → "우주의 모든 것이 P이고 Q다" (Wrong!)
• ∃x(P(x) ⇒ Q(x)) → "P가 아닌 것이 하나라도 있으면 True" (Wrong!)

외우는 팁: ∀ 뒤에는 ⇒, ∃ 뒤에는 ∧

---

Quantifier 순서가 중요하다!

L(x,y) = "x는 y를 사랑한다"로 놓으면:

• ∀x∃y L(x,y): "모든 x는 어떤 y를 사랑한다" (각자 다른 y여도 됨)
• ∃y∀x L(x,y): "어떤 y를 모든 x가 사랑한다" (한 명이 고정돼 있음)

순서가 바뀌면 의미가 완전히 달라진다. ∀x∃y ≠ ∃y∀x

---

Free vs. Bound Variables

Bound variable: quantifier가 잡고 있는 변수.

• ∀x(P(x) ∧ Q(y))에서 x는 bound.

Free variable: 아무 quantifier도 없는 변수.

• ∀x(P(x) ∧ Q(y))에서 y는 free.

Closed formula: free variable이 없는 식.

왜 중요하냐면:

• Closed formula만 명확하게 True/False를 판단할 수 있다.
• Free variable이 있는 식은 거기에 뭘 넣느냐에 따라 결과가 달라져서 판단 불가.

---

Quantificational Logic 공식의 귀납적 정의

명제 논리 공식 정의랑 똑같고, constructor에 quantifier 두 개만 추가된 거다.

Base case:

• Case A (0-place): T, F, p, q, r 같은 상수와 명제 변수 (입력 없이 바로 True/False)
• Case B (n-place): H(x), L(x,y) 같이 변수를 받아야 True/False가 결정되는 predicate

Constructor:

• F∧G, F∨G, ¬F, F⇒G (명제 논리 그대로)
• ∀xF, ∃xF (quantifier 추가! 이게 전부 새로 추가된 것)

---

Interpretation & Model

Interpretation: 식에 의미를 부여하는 방법. 두 가지를 지정해야 한다.

1. Universe (U): 변수가 가질 수 있는 값의 범위
2. 각 Predicate가 어떤 관계인지

Model: 식을 True로 만드는 Interpretation. 명제 논리의 satisfying assignment와 같은 개념.

예를 들어 ∀x∃yP(x,y)에서:

• Interpretation 1: U={0,1}, P="x < y" → x=1일 때 False → Not a model
• Interpretation 2: U={0,1}, P="x ≠ y" → 모든 x에 True → Model!

기본적으로 양화 논리에서 U는 하나이고 모든 변수가 그 U에서 값을 가져온다. 변수마다 범위가 다르면 복잡해지니까 하나로 통일하는 것이다.

---

Satisfiability vs. Validity

명제 논리와 완전히 대응된다.

명제 논리	양화 논리	의미
Satisfiable	Satisfiable	적어도 하나의 model 존재
Contradiction	Unsatisfiable	어떤 interpretation에서도 False
Tautology	Valid	모든 interpretation에서 True

---

Key Equivalence Rules

Rule 1: Propositional substitutions

명제 논리의 모든 법칙이 양화 논리에서도 그대로 성립한다.

• ∀x¬¬P(x) ≡ ∀xP(x) (double negation)
• ∀x(P(x) ∧ (Q(x) ∨ R(x))) ≡ ∀x((P(x) ∧ Q(x)) ∨ (P(x) ∧ R(x))) (분배)

Rule 2: Change of variables (변수 이름 바꾸기)

bound variable의 이름을 바꿔도 의미가 같다. 단, 이미 다른 곳에서 쓰이는 이름으로 바꾸면 안 된다.

∃x(H(x) ∧ B(x)) ≡ ∃y(H(y) ∧ B(y))

Rule 3: Quantifier Negation (양화 논리판 De Morgan's Law)

• ¬(∀xF) ≡ ∃x(¬F) : "모두가 P다"의 부정 = "P가 아닌 게 하나 존재"
• ¬(∃xF) ≡ ∀x(¬F) : "P인 게 존재한다"의 부정 = "모두가 P가 아니다"

¬가 안으로 들어가면 ∀ ↔ ∃가 뒤집힌다. De Morgan에서 ∧ ↔ ∨ 뒤집히는 것과 같은 패턴.

Rule 4: Scope Change (범위 이동)

quantifier의 변수가 다른 부분에 등장하지 않으면, quantifier를 밖으로 꺼내거나 안으로 넣을 수 있다.

(∀x Outside(x) ⇒ Wet(x)) ∧ r ≡ ∀x((Outside(x) ⇒ Wet(x)) ∧ r)

r에 x가 없으니까 ∀x를 밖으로 꺼낼 수 있다.

---

Prenex Normal Form (PNF)

PNF는 모든 quantifier가 식의 맨 앞에 몰려있는 형태다. Prenex는 "앞에 붙인다"는 뜻.

형태: □₁x₁□₂x₂…□ₙxₙ (quantifier-free formula)

컴퓨터가 논리식을 처리할 때 quantifier가 앞에 다 모여있으면 훨씬 처리하기 쉽다.

변환 4단계:

1. 변수 이름 정리 (Rule 2): 겹치는 변수 이름 먼저 바꾸기
2. ⇒, ⇔ 제거 (Rule 1): p ⇒ q ≡ ¬p ∨ q, p ⇔ q ≡ (¬p ∨ q) ∧ (¬q ∨ p)
3. ¬를 안으로 밀기 (Rule 3): ¬∀, ¬∃ 처리
4. quantifier를 앞으로 끌어내기 (Rule 4): Scope Change로 전부 앞으로

예제: "개미가 있으면 그 중 하나가 여왕이다"

A(x) = "x는 개미", Q(x) = "x는 여왕"

Step 0 (형식화):
∃xA(x) ⇒ ∃y(A(y) ∧ Q(y) ∧ ∀z(Q(z) ⇒ z=y))

Step 1 (⇒ 제거):
¬(∃xA(x)) ∨ ∃y(A(y) ∧ Q(y) ∧ ∀z(Q(z) ⇒ z=y))

Step 2 (¬를 안으로, Rule 3):
(∀x¬A(x)) ∨ ∃y(A(y) ∧ Q(y) ∧ ∀z(Q(z) ⇒ z=y))

Step 3 (quantifier 앞으로, Rule 4):
∀x∃y∀z(¬A(x) ∨ (A(y) ∧ Q(y) ∧ (Q(z) ⇒ z=y)))

Done! PNF 완성.

---

정리

• Predicate: 변수를 받아 True/False를 돌려주는 함수 템플릿.
• Universe (U): 변수가 가질 수 있는 범위. 식의 True/False가 여기에 달려있음.
• ∀ (for all): 모든 x에 대해 True여야 함. 뒤에는 ⇒.
• ∃ (there exists): 하나라도 True면 됨. 뒤에는 ∧.
• Quantifier 순서: ∀x∃y ≠ ∃y∀x. 순서가 바뀌면 의미가 완전히 달라짐.
• Bound/Free variable: Closed formula(bound만 있는 것)만 True/False 판단 가능.
• Interpretation: Universe + 각 Predicate의 의미를 지정. Model은 식을 True로 만드는 Interpretation.
• Rule 3 (Quantifier Negation): ¬∀ ≡ ∃¬, ¬∃ ≡ ∀¬. 양화 논리판 De Morgan.
• PNF: 모든 quantifier를 맨 앞으로 모은 표준 형태. 4단계로 변환.