09. Propositional Logic

왜 명제 논리가 필요한가?

  일상 언어는 생각보다 많이 모호하다. 예를 들어 "or"라는 단어만 해도:

• "18세 이상이거나 애리조나 거주자면 공제 받을 수 있다" → 둘 다 해당돼도 OK (inclusive or)
• "일시불로 받거나 연금으로 받을 수 있다" → 둘 중 하나만 (exclusive or)
• "그걸 그만두거나 큰일 날 거야" → 사실상 조건문 (implication)

  같은 "or"인데 의미가 전부 다르다. 컴퓨터는 이런 모호함을 처리할 수 없다. 그래서 명제 논리로 의미를 정확하게 고정시키는 것이다.

---

Proposition이란?

  명제(proposition)는 참(True) 또는 거짓(False)으로 딱 떨어지는 선언적 문장이다.

• "2000년은 윤년이다" → True ✅
• "16은 소수다" → False ✅
• "2월은 28일이다" → 명제 아님 (2025년엔 맞고 2024년엔 틀림, 모호함)
• "무색의 초록 아이디어가 격렬하게 잠든다" → 명제 아님 (문법은 맞지만 의미가 없음)

명제는 반드시 참/거짓이 명확하게 결정돼야 한다.

---

Atomic vs. Compound Proposition

  명제는 두 종류가 있다.

Atomic proposition (원자 명제): 더 이상 쪼갤 수 없는 기본 명제. p, q, r 같은 기호로 나타낸다.

Compound proposition (복합 명제): 원자 명제들을 논리 연산자로 조합한 것.

기호	이름	의미
¬p	Negation	not p
p ∧ q	And	p이고 q
p ∨ q	Inclusive Or	p이거나 q (둘 다 가능)
p ⊕ q	Exclusive Or	p이거나 q (둘 중 하나만)
p ⇒ q	Implication	p이면 q
p ⇔ q	Equivalence	p이면 q이고, q이면 p

---

Truth Table

  진리표(truth table)는 복합 명제의 진리값이 각 구성 요소에 따라 어떻게 결정되는지를 보여준다. 대부분의 연산자는 직관적인데, implication(⇒) 이 좀 특이하다.

p	q	p ⇒ q
T	T	T
T	F	F
F	T	T
F	F	T

p ⇒ q가 False가 되는 경우는 딱 하나, p=T이고 q=F일 때뿐이다.

  왜 p가 False일 때 결과가 True냐고 하면, "약속을 어기는 건 약속을 했을 때만 가능하다"고 생각하면 된다. "1등 하면 치킨 사줄게"라는 약속은, 1등을 못 했을 때는 치킨을 사줘도 안 사줘도 약속을 어긴 게 아니다. 약속이 깨지는 건 1등 했는데 안 사줄 때뿐이다.

---

연산자 우선순위

논리 연산자도 사칙연산처럼 우선순위가 있다.

순서	연산자
1	¬ (NOT)
2	∧ (AND)
3	∨, ⊕ (OR, XOR)
4	⇒ (IMPLIES)
5	⇔ (IFF)

예를 들어 a ∨ b ∧ ¬c는 a ∨ (b ∧ (¬c))로 읽힌다. 헷갈리면 괄호를 쓰는 게 낫다.

---

논리적 동치 (≡) vs. ⇔

이 둘은 비슷해 보이지만 레벨이 다르다.

• ⇔ 는 논리식 안에서 쓰는 연산자다. p ⇔ q는 하나의 명제이고, p=T, q=F면 이 명제는 False가 된다.
• ≡ 는 논리식 밖에서 쓰는 기호다. "이 두 식은 진리표가 완전히 똑같다"는 메타 발언이다.

예를 들어 p ⇒ q ≡ ¬p ∨ q는 두 식의 진리표가 항상 동일하다는 뜻이다. 이건 Theorem 9.1로 증명된다.

---

Tautology, Contradiction, Satisfiability

이름	의미	예시
Tautology	항상 True	p ∨ ¬p
Contradiction	항상 False	p ∧ ¬p
Satisfiable	적어도 한 경우에 True	p ⇒ q

세 개의 관계:

• Tautology이면 반드시 satisfiable이다 (항상 True니까 당연히 True인 경우가 존재).
• Contradiction은 unsatisfiable이다.
• α가 tautology ⇔ ¬α가 unsatisfiable — α가 항상 True면, ¬α는 항상 False라서 단 한 번도 True가 안 된다.

---

Logical Laws

  논리 법칙들은 항상 성립하는 동치 관계다. 이걸 이용해서 복잡한 논리식을 단순화할 수 있다.

• Identity: p ∧ T ≡ p, p ∨ F ≡ p
• Domination: p ∨ T ≡ T, p ∧ F ≡ F
• Idempotent: p ∨ p ≡ p, p ∧ p ≡ p
• Double negation: ¬(¬p) ≡ p
• Commutative: p ∨ q ≡ q ∨ p
• Associative: (p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
• Distributive: p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
• De Morgan's Laws: ¬(p ∧ q) ≡ ¬p ∨ ¬q, ¬(p ∨ q) ≡ ¬p ∧ ¬q

De Morgan's Law는 NOT을 안으로 분배할 때 ∧ ↔ ∨ 기호가 뒤집힌다고 기억하면 된다.

---

Functional Completeness

Theorem 9.1(p ⇒ q ≡ ¬p ∨ q)과 Theorem 9.2(p ⊕ q ≡ (p ∧ ¬q) ∨ (¬p ∧ q))를 합치면 흥미로운 결론이 나온다.

⇒ 와 ⊕ 는 사실 없어도 된다. ∧, ∨, ¬ 세 개만으로 모든 논리식을 표현할 수 있기 때문이다. 이걸 functional completeness(함수 완전성)라고 한다.

더 나아가면 NAND 하나만으로도 완전하다. p NAND q = ¬(p ∧ q)인데, 이것만으로 ∧, ∨, ¬를 전부 표현할 수 있다. 실제로 디지털 회로 설계에서 NAND 게이트 하나로 모든 논리 회로를 구성하는 이유가 여기에 있다.

---

명제 공식의 귀납적 정의

  마지막으로, 명제 공식 자체도 귀납적으로 정의된다. 지난 시간에 배운 구조적 귀납법이 여기서도 등장한다.

• (Base case) 원자 명제 p, q, r은 공식이다.
• (Inductive step) α와 β가 공식이면 (α ∧ β), (α ∨ β), ¬α도 공식이다.

이 두 규칙만으로 무한히 많은 논리 공식을 전부 정의할 수 있다. 구조적 귀납법이랑 완전히 같은 패턴이다.

---

정리

• 명제는 참/거짓이 명확한 선언적 문장이다.
• 명제를 논리 연산자로 조합하면 복합 명제가 된다.
• 진리표로 복합 명제의 진리값을 체계적으로 계산할 수 있다.
• ≡ 는 두 식의 진리표가 동일하다는 메타 발언이고, ⇔ 는 논리식 안의 연산자다.
• Tautology는 항상 True, Contradiction은 항상 False, Satisfiable은 적어도 한 경우에 True.
• ∧, ∨, ¬ 세 개만으로 모든 논리식을 표현할 수 있다 (functional completeness).