10. Normal Forms

왜 Normal Form이 필요한가?

논리식은 같은 의미를 여러 방식으로 표현할 수 있다. 예를 들어 아래 두 식은 완전히 동일하다.

• p ⇒ q
• ¬p ∨ q

사람 눈에는 달라 보이지만 진리표가 동일하다. 근데 컴퓨터는 생긴 게 다르면 같은지 모른다. 그래서 모든 식을 표준화된 형태로 변환하면, 비교나 분석이 훨씬 쉬워진다.

Normal form의 규칙은 세 가지다.

• Operator Standardization: ∧, ∨, ¬ 만 허용 (⇒, ⇔, ⊕ 없음)
• Structural Standardization: AND-of-ORs 또는 OR-of-ANDs 구조만 허용
• Negation Standardization: ¬는 변수에만 붙일 수 있음 (¬(p ∨ q) 같은 형태 불가)

---

Literal이란?

Normal form을 이해하려면 먼저 literal 개념이 필요하다.

Literal은 변수 그 자체(p)이거나, 변수의 부정(¬p)이다. 더 이상 쪼갤 수 없는 가장 작은 단위다.

• Literal O: p, ¬p, q, ¬q
• Literal X: p ∧ q, ¬(p ∨ q)

p ∧ q는 두 literal의 조합이라서 literal이 아니고, ¬(p ∨ q)는 부정이 변수가 아닌 식에 붙어 있어서 literal이 아니다.

---

CNF vs DNF

Normal form에는 두 종류가 있다.

CNF (Conjunctive Normal Form): AND of ORs

• 바깥은 AND, 안은 OR
• 구조: (ℓ₁ ∨ ℓ₂ ∨ …) ∧ (ℓ₁ ∨ ℓ₂ ∨ …)
• 예시: (p ∨ ¬q ∨ r) ∧ (¬p ∨ s)
• CNF가 True가 되려면: 모든 clause에서 적어도 하나의 literal이 True여야 한다.

DNF (Disjunctive Normal Form): OR of ANDs

• 바깥은 OR, 안은 AND
• 구조: (ℓ₁ ∧ ℓ₂ ∧ …) ∨ (ℓ₁ ∧ ℓ₂ ∧ …)
• 예시: (p ∧ ¬q ∧ r) ∨ (¬p ∧ s)
• DNF가 True가 되려면: 적어도 하나의 clause에서 모든 literal이 True여야 한다.

---

변환 방법 1: 진리표에서 직접 변환

진리표에서 DNF를 바로 뽑아낼 수 있다.

알고리즘:

1. 진리표를 만든다.
2. 결과가 True인 행마다 AND 덩어리를 하나 만든다.
   • 그 행에서 변수가 T면 → p 그대로
   • 그 행에서 변수가 F면 → ¬p
3. 모든 AND 덩어리를 OR로 연결한다.

예를 들어 p ⇒ q의 진리표에서 True인 행이 세 개다.

p	q	p ⇒ q	AND 덩어리
T	T	T	p ∧ q
T	F	F	-
F	T	T	¬p ∧ q
F	F	T	¬p ∧ ¬q

결과: (p ∧ q) ∨ (¬p ∧ q) ∨ (¬p ∧ ¬q)

근데 이건 ¬p ∨ q로 훨씬 간단하게 쓸 수 있다. 진리표 방법은 직관적이지만, 변수가 n개면 행이 2ⁿ개라서 식이 엄청 길어질 수 있다는 게 단점이다.

---

변환 방법 2: 논리 법칙으로 변환

논리 법칙을 단계적으로 적용해서 직접 변환하는 방법이다. 세 단계로 이루어진다.

Step 1: ⇒, ⇔, ⊕ 제거

• α ⇒ β ≡ ¬α ∨ β
• α ⇔ β ≡ (α ∧ β) ∨ (¬α ∧ ¬β)
• α ⊕ β ≡ (p ∧ ¬q) ∨ (¬p ∧ q)

Step 2: De Morgan으로 ¬를 안으로 밀어 넣기

• ¬(α ∧ β) ≡ ¬α ∨ ¬β
• ¬(α ∨ β) ≡ ¬α ∧ ¬β
• ¬¬α ≡ α

Step 3: 분배 법칙으로 구조 만들기

• CNF를 원하면: ∨를 ∧ 안으로 분배
  • α ∨ (β ∧ γ) ≡ (α ∨ β) ∧ (α ∨ γ)
• DNF를 원하면: ∧를 ∨ 안으로 분배
  • α ∧ (β ∨ γ) ≡ (α ∧ β) ∨ (α ∧ γ)

---

예제: ¬(p ⇒ q) ∨ (p ⇒ r) → CNF

Step 1: ⇒ 제거

p ⇒ q ≡ ¬p ∨ q, p ⇒ r ≡ ¬p ∨ r 이므로:

¬(¬p ∨ q) ∨ (¬p ∨ r)

Step 2: De Morgan으로 ¬(¬p ∨ q) 처리

¬(¬p ∨ q) ≡ ¬(¬p) ∧ ¬q ≡ p ∧ ¬q

전체: (p ∧ ¬q) ∨ (¬p ∨ r)

Step 3: ∨를 ∧ 안으로 분배 (CNF 만들기)

(a ∧ b) ∨ c ≡ (a ∨ c) ∧ (b ∨ c) 이므로:

(p ∨ ¬p ∨ r) ∧ (¬q ∨ ¬p ∨ r)

p ∨ ¬p는 항상 True이므로 첫 번째 clause는 tautology. ∧ T는 사라지므로:

최종 결과: ¬q ∨ ¬p ∨ r

---

SAT 문제

Normal form은 CS에서 가장 유명한 문제 중 하나인 SAT(Satisfiability) 문제와 직결된다.

Q. 주어진 CNF 공식을 True로 만드는 변수 할당이 존재하는가?

이게 왜 중요하냐면, 스케줄링, 회로 설계, 계획 문제 등 현실의 수많은 어려운 문제들을 전부 CNF-SAT로 변환할 수 있기 때문이다. CNF-SAT를 효율적으로 풀 수 있으면 이 모든 문제가 한 번에 해결된다.

• DNF-SAT: P (빠르게 풀 수 있음). AND 덩어리 중 하나라도 전부 True이면 되니까 하나씩 확인하면 된다.
• CNF-SAT: NP-complete (아직 효율적인 풀이법 없음). 변수가 n개면 경우의 수가 2ⁿ개라 어떤 조합이 맞는지 찾는 게 엄청 어렵다.

CNF-SAT는 역사상 처음으로 NP-complete임이 증명된 문제다. NP 전체 클래스의 어떤 문제든 CNF-SAT로 변환할 수 있다는 뜻이다. 아직 아무도 효율적으로 풀지 못했고, 이게 P = NP 문제와 직결된다.

---

정리

• Literal: 변수 p 또는 그 부정 ¬p. Normal form의 최소 단위.
• CNF: AND of ORs. (∨들) ∧ (∨들). 모든 clause에서 하나 이상 True여야 전체 True.
• DNF: OR of ANDs. (∧들) ∨ (∧들). 하나의 clause에서 전부 True면 전체 True.
• 변환 방법 1: 진리표에서 True인 행마다 AND 덩어리를 만들어 OR로 연결 → DNF. 직관적이지만 길어질 수 있음.
• 변환 방법 2: 논리 법칙 3단계 (⇒ 제거 → De Morgan → 분배). 더 간결한 결과.
• SAT: CNF-SAT는 NP-complete. 현실의 수많은 어려운 문제들이 여기로 환원된다.