논리

1. 명제(Proposition)

명제란 참(True) 또는 거짓(False)을 명확히 판별할 수 있는 문장을 의미한다.
예를 들어:

• "2는 짝수이다." → 참 (명제 O)
• "x는 짝수이다." → x가 특정되지 않으므로 명제가 아님 (명제 함수)

---

2. 합성 명제 (Compound Proposition)

하나 이상의 명제와 논리 연산자(AND, OR, NOT 등)로 이루어진 명제

논리 연산 (Truth Table 포함)

논리합(OR, ∨)

• p ∨ q: p 또는 q 중 하나라도 참이면 참

p  |  q  |  p ∨ q
-----------------
T  |  T  |   T
T  |  F  |   T
F  |  T  |   T
F  |  F  |   F

논리곱(AND, ∧)

• p ∧ q: p와 q 둘 다 참이어야 참

p  |  q  |  p ∧ q
-----------------
T  |  T  |   T
T  |  F  |   F
F  |  T  |   F
F  |  F  |   F

부정(NOT, ¬)

• ¬p: p가 참이면 거짓, 거짓이면 참

p  |  ¬p
---------
T  |  F
F  |  T

배타적 논리합(XOR, ⊕)

• p ⊕ q: p와 q가 다를 때 참

p  |  q  |  p ⊕ q
-----------------
T  |  T  |   F
T  |  F  |   T
F  |  T  |   T
F  |  F  |   F

조건 명제 (p → q)

• p → q: p가 참이면 q도 참이어야 함

p  |  q  |  p → q
-----------------
T  |  T  |   T
T  |  F  |   F
F  |  T  |   T
F  |  F  |   T

(거짓에서 참으로 가는 경우는 무조건 참으로 처리)

쌍조건 명제 (p ↔ q)

• p ↔ q: p와 q가 같을 때 참

p  |  q  |  p ↔ q
-----------------
T  |  T  |   T
T  |  F  |   F
F  |  T  |   F
F  |  F  |   T

---

3. 명제의 변형

조건 명제 p → q의 변형:

역 (Converse)	q → p	조건과 결론을 뒤바꿈
이 (Inverse)	¬p → ¬q	p와 q를 모두 부정
대우 (Contrapositive)	¬q → ¬p	역의 부정을 취한 것 (항상 원래 명제와 논리적으로 동치)

---

4. 논리적 동치 (Logical Equivalence)

두 명제가 항상 동일한 참/거짓 값을 가지면 논리적으로 동등함(≡).

논리적 동치 법칙

교환법칙 (Commutation Law)	p ∨ q ≡ q ∨ p	A 또는 B는 B 또는 A와 동일
결합법칙 (Associative Law)	(p ∨ q) ∨ r ≡ p ∨ (q ∨ r)	OR/AND 연산의 괄호 변경 가능
분배법칙 (Distributive Law)	p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)	AND가 OR 안으로 분배됨
항등법칙 (Identity Law)	p ∨ F ≡ p, p ∧ T ≡ p	OR의 항등원은 F, AND의 항등원은 T
지배법칙 (Domination Law)	p ∨ T ≡ T, p ∧ F ≡ F	OR의 지배원은 T, AND의 지배원은 F
부정법칙 (Negation Law)	p ∨ ¬p ≡ T, p ∧ ¬p ≡ F	어떤 명제든 참/거짓을 포함하면 항상 T/F
이중 부정 법칙 (Double Negation Law)	¬(¬p) ≡ p	두 번 부정하면 원래 값
멱등법칙 (Idempotent Law)	p ∨ p ≡ p, p ∧ p ≡ p	같은 명제를 OR/AND하면 변화 없음
드모르간 법칙 (De Morgan's Law)	¬(p ∧ q) ≡ ¬p ∨ ¬q, ¬(p ∨ q) ≡ ¬p ∧ ¬q	논리 연산의 부정 변환
흡수법칙 (Absorption Law)	p ∨ (p ∧ q) ≡ p	p가 이미 포함된 표현을 단순화
함축법칙 (Implication Law)	p → q ≡ ¬p ∨ q	조건 명제는 OR로 변환 가능
대우 법칙 (Contrapositive Law)	p → q ≡ ¬q → ¬p	대우 명제는 원래 명제와 동치

드모르간 법칙

NOT (A AND B) ≡ (NOT A) OR (NOT B)

예시:

"비가 안 오거나 길이 마르지 않았다." ≡ "비가 안 오지 않았다." AND "길이 마르지 않았다."

---

5. 항진 명제와 모순 명제

항진 명제(Tautology): 항상 참인 명제
모순 명제(Contradiction): 항상 거짓인 명제

p ∨ ¬p  ≡ 항상 참 (항진 명제)
p ∧ ¬p  ≡ 항상 거짓 (모순 명제)

---

6. 술어 논리 (Predicate Logic)

명제 논리(Propositional Logic): 명제 자체가 기본 단위
술어 논리(Predicate Logic): 명제 내부에 **변수(x)**가 들어가는 논리

P(x): "x는 짝수이다."

한정자 (Quantifiers)

• 전체 한정자 (∀, Universal Quantifier):
  • "모든 x에 대해 P(x)가 참이다."
  • 예: ∀x (x는 짝수이다)
• 존재 한정자 (∃, Existential Quantifier):
  • "어떤 x에 대해 P(x)가 참이다."
  • 예: ∃x (x는 짝수이다)

---

7. 추론 (Inference)

유효 추론 (Valid Inference): 전제가 참이면 결론도 참
추론 규칙

• 선언적 부가 (Addition): p → p ∨ q
• 단순화 (Simplification): p ∧ q → p
• 긍정 논법 (Modus Ponens): (p → q) ∧ p → q
• 부정 논법 (Modus Tollens): (p → q) ∧ ¬q → ¬p
• 삼단논법 (Syllogism): (p → q) ∧ (q → r) → (p → r)

긍정 논법

전제1: "비가 오면 길이 젖는다."
전제2: "비가 온다."
결론: "그러므로 길이 젖는다."