Chapter 1.2 명제의 동치

복합명제(Compound Propositions)

• QUESTION
  • 주어진 복합 명제를 보다 간소화하거나 해결하기 쉬운 형태로 만들려면?
• ANSWER
  • 하나의 명제 표현을 동일한 진리 값을 갖는 다른 명제 표현으로 대체
• 복합명제(Compound Propositions)
  • p ∧ q 같이 명제변수로부터 논리 연산자들을 사용하여 만든 논리식
  • 가능한 참값에 따라 <항진명제, 모순명제,불확정명제> 3가지로 나뉜다.

- 항진(Tautology)과 모순(Contradiction)

• 정의 1: 항진명제(Tautology)
  • 복합명제를 구성하는 단위명제의 진리 값이 어떠한 값을 가진다 하여도 해당 복합명제가 항상 참인 경우
• 정의 1: 모순명제(Contradiction)
  • 복합명제를 구성하는 단위명제의 진리 값이 어떠한 값을 가진다 하여도 해당 복합명제가 항시 거짓인 경우

p	¬p	p∨¬p	p∧¬p
T	F	T	F
F	T	T	F

• 정의 1: 불확정명제(Contingency)
  • 항진도 모순도 아닌 경우

논리적 동치(Logical Equivalence)

• 정의 2:

  • 두 복합명제 p, q에 대하여, p↔q가 항진명제이면, p와 q는 논리적으로 동치임

    (표기법: p ≡ q or p⇔q)

"p↔q가 항진명제" 라는 말은 단위명제의 진리 값이 어떠한 값을 가져도 p와 q의 진리값이 같다는 말이다. 왜냐하면 ↔ 연산자 자체가 피연산자 두개가 서로 같을 때 참이기 때문이다.

참고로 p도 복합명제이고, q도 복합명제이고, p↔q도 복합명제이다. 헷갈리지 말자!

• Truth Table을 이용한 동치 판정 방법

  • 예제 1: Prove that ¬(p∨q) ⇔ ¬p∧¬q [De Morgan’s Law]

    p	q	p∨q	¬(p∨q)	¬p	¬q	¬p ∧ ¬q
    T	T	T	F	F	F	F
    T	F	T	F	F	T	F
    F	T	T	F	T	F	F
    F	F	F	T	T	T	T

    → 2개의 단위 명제로 구성된 경우, 4(=$2^2$)개의 행이 필요

  • 예제 2: Prove that p∨(q∧r) ⇔ (p∨q) ∧ (p∨r) [Distributive Law]

    p	q	r	q∧r	p∨(q∧r)	p∨q	p∨r	(p∨q) ∧ (p∨r)
    T	T	T	T	T	T	T	T
    T	T	F	F	T	T	T	T
    T	F	T	F	T	T	T	T
    T	F	F	F	T	T	T	T
    F	T	T	T	T	T	T	T
    F	T	F	F	F	T	F	F
    F	F	T	F	F	F	T	F
    F	F	F	F	F	F	F	F

    → 3개의 단위 명제로 구성된 경우, 8(=$2^3$ )개의 행이 필요

  • 복합명제가 n개의 단위명제로 구성되는 경우, 동치를 증명하기 위해 $2^n$개의 행이 필요

    → 🚫Too much space!, Too expensive! 💡 대안: 동치 법칙(Equivalence Laws)을 활용

동치 법칙(Equivalence Laws)

• 기본 법칙

  Equivalence(동치 종류)	Name(법칙 이름)
  p ∧ T ⇔ p p ∨ F ⇔ p	Identity laws (항등 법칙)
  p ∨ T ⇔ T p ∧ F ⇔ F	Domination laws (지배 법칙)
  p ∨ p ⇔ p p ∧ p ⇔ p	Idempotent laws (등멱 법칙)
  ¬(¬p) ⇔ p	Double negation law (이중 부정 법칙)
  p ∨ q ⇔ q ∨ p p ∧ q ⇔ q ∧ p	Commutative laws (교환 법칙)
  (p ∨ q) ∨ r ⇔ p ∨ (q ∨ r) (p ∧ q) ∧ r ⇔ p ∧ (q ∧ r)	Associative laws (결합 법칙)
  p ∨ (q ∧ r) ⇔ (p ∨ q) ∧ (p ∨ r) p ∧ (q ∨ r) ⇔ (p ∧ q) ∨ (p ∧ r)	Distributive laws (분배 법칙)
  ¬(p ∧ q) ⇔ ¬p ∨ ¬q ¬(p ∨ q) ⇔ ¬p ∧ ¬q	De Morgan’s laws (드 모르간 법칙)
  p ∨ (p ∧ q) ⇔ p p ∧ (p ∨ q) ⇔ p	Absorption laws (흡수 법칙) ※ 쉬운 이해 : 집합의 Venn Diagram 이용
  p ∨ ¬p ⇔ T p ∧ ¬p ⇔ F	Negation laws (부정 법칙)

• 조건문을 포함한 논리적 동치

  • p → q ⇔ ¬p ∨ q
  • p → q ⇔ ¬q → ¬p
  • p ∨ q ⇔ ¬p → q
  • p ∧ q ⇔ ¬(p → ¬q)
  • (p → q) ∧ (p → r) ⇔ p → (q ∧ r)
  • (p → r) ∧ (q → r) ⇔ (p ∨ q) → r
  • (p → q) ∨ (p → r) ⇔ p → (q ∨ r)
  • (p → r) ∨ (q → r) ⇔ (p ∧ q) → r

• 상호조건을 포함한 논리적 동치

  • p ↔ q ⇔ (p → q) ∧ (q → p)
  • p ↔ q ⇔ ¬p ↔ ¬q
  • p ↔ q ⇔ (p ∧ q) ∨ (¬p ∧ ¬q)
  • ¬(p ↔ q) ⇔ p ↔ ¬q

- 예제 문제

• ¬(p ∨ (¬p ∧ q)) ⇔ ¬p ∧ ¬q 임을 증명하라.

  ¬(p ∨ (¬p ∧ q)) ⇔ ¬p ∧ ¬(¬p ∧ q)) by first 드 모르간 법칙

  ⇔ ¬p ∧ (¬(¬p) ∨ ¬q) by second 드 모르간 법칙

  ⇔ ¬p ∧ (p ∨ ¬q) by 이중부정 법칙

  ⇔ (¬p ∧ p) ∨ (¬p ∧ ¬q) by second 분배 법칙

  ⇔ F ∨ (¬p ∧ ¬q) by 부정 법칙

  ⇔ (¬p ∧ ¬q) ∨ F by 교환 법칙

  ⇔ ¬p ∧ ¬q by 항등 법칙

부울대수에서의 분배법칙

• 부울대수에서의 분배법칙(제1법칙): A·(B+C) ⇔ A·B + A·C
• 부울대수에서의 분배법칙(제2법칙): A + B·C = (A+B)·(A+C)
  • 일반적인 대수식에서는 성립되지 않음
  • T/F 값만 취하는 Boolean Algebra에서 성립

여기서 A,B,C는 0 or 1이지만 모르므로 그냥 기호로 적어둔다..

(A+B)·(A+C) ⇔ A·A + A·C + A·B + B·C

​ ⇔ A + A·C + B·A + B·C ( A·A=A by 멱등법칙)

​ ⇔ A·(1 + C + B) + B·C

​ ⇔ A + B·C (1+C+B = 1)

부울대수의 표현 : AND연산 0 · 0 = 0, 0 · 1 = 0, 1 · 0 = 0, 1 · 1 = 1 이며, OR연산 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 1 으로 표현한다.