[이산 수학] 논리적 동치

논리적 동치

• 합성 명제는 하나 이상의 단순 명제를 논리 연산자로 결합한 형태이므로 복잡한 형태일 수도 있다.
• 합성 명제가 복잡하다는 것은 컴퓨터 시스템에서 표현하고 연산해야 하는 논리 연산의 수가 많음을 의미한다.
• 이렇게 많은 논리 연산으로 복잡하게 표현된 합성 명제를 진릿값이 같으면서 단순한 논리 연산으로 표현된 합성 명제로 대체한다면, 컴퓨터 시스템에서도 같은 결과를 내면서 간단하고 빠르게 표현하고 연산할 수 있을 것이다.

 

논리적 동치(Logically Equivalence : $P ≡ Q$)

두 합성 명제 `P` 와 `Q` 의 진릿값이 서로 같은 경우

• 두 합성 명제 `P, Q` 에 대하여 `P ≡ Q` 일 때 '합성 명제 `P` 와 `Q` 는 동치이다' 또는 '합성 명제 `P` 와 `Q` 는 같다' 라고 읽는다.
• 이렇게 두 합성 명제 `P, Q` 가 논리적 동치 관계이면 진릿값이 같음을 의미하므로, `P` 와 `Q` 는 서로를 대체해서 사용할 수 있다.
• 두 합성 명제가 동치인지 판별하는 방법에는 진리표를 이용하는 방법과 논리적 동치 법칙을 이용하는 방법이 있다.

 

진리표를 이용한 논리적 동치 판별

• 진리표는 두 합성 명제가 서로 동치 관게인지를 파악하는 가장 기본적인 도구로 사용된다.

 

$p \oplus q ≡ (\neg p \land q) \lor (p \land \neg q)$ 의 증명 진리표

`p`	`q`	$\neg p$	$\neg q$	$\neg p \land q$	$p \land \neg q$	$(\neg p \land q) \lor (p \land \neg q)$	$p \oplus q$
T	T	F	F	F	F	F	F
T	F	F	T	F	T	T	T
F	T	T	F	T	F	T	T
F	F	T	T	F	F	F	F

• 하나의 진릿값이라도 다르면 두 합성 명제는 동치가 아니다.

 

논리적 동치 법칙을 이용한 논리적 동치 판별

• 합성 명제들 중 항상 동치인 합성 명제를 모아 법칙으로 정리한 것이 논리적 동치 법칙이다.
• 이러한 논리적 동치 법칙을 이용하면 복잡하게 표현된 합성 명제를 단순한 표현의 합성 명제로 바꿀 수 있다.

법칙	논리적 동치
항등 법칙(Identity Law)	$p \land$ T $≡ p$	$p \lor$ F $≡ p$
지배 법칙(Domination Law)	$p \land$ F $≡$ F	$p \lor$ T $≡$ T
부정 법칙(Negation Law)	$p \land \neg p ≡$ F	$p \lor \neg p ≡$ T
이중 부정 법칙(Double Negation Law)	$\neg(\neg p) ≡ p$
멱등 법칙(Idempotent Law)	$p \land p ≡ p$	$p \lor p ≡ p$
교환 법칙(Commutative Law)	$p \land q ≡ q \land p$	$p \lor q ≡ q \lor p$
결합 법칙(Associative Law)	$(p \land q) \land r ≡ p \land (q \land r)$	$(p \lor q) \lor r ≡ p \lor (q \lor r)$
분배 법칙(Distributive Law)	$p \lor (q \land r) ≡ (p \lor q) \land (p \lor r)$	$p \land (q \lor r) ≡ (p \land q) \lor (p \land r)$
드 므로간의 법칙(De Morgan's Law)	$\neg (p \land q) ≡ \neg p \lor \neg q$	$\neg (p \lor q) ≡ \neg p \land \neg q$
흡수 법칙(Absorption Law)	$p \land (p \lor q) ≡ p$	$p \lor (p \land q) ≡ p$
함축 법칙(Implication Law)	$p → q ≡ \neg p \lor q$

※ $\lor = ∪, \; \land = ∩, \;$ T$= U, \;$ F $=  Ø$ 로 치환하여 집합의 법칙처럼 생각해도 된다.

 

• 논리적 동치 법칙을 합성 명제에 적용할 때, 결합 법칙을 적용해야 하는 경우와 분배 법칙을 적용해야 하는 경우를 잘 구분해야 한다.
  • 괄호 안의 논리 연산자와 괄호 밖의 논리 연산자가 같은 경우에는 결합 법칙을 적용한다.
    • $(p \land q) \land r ≡ p \land (q \land r)$
  • 괄호 안의 논리 연산자와 괄호 밖의 논리 연산자가 다른 경우에는 분배 법칙을 적용한다.
    • $p \lor (q \land r) ≡ (p \lor q) \land (p \lor r)$

 

논리적 동치 법칙을 이용하여 흡수 법칙 $p \land (p \lor q) ≡ p$ 증명하기

$p \land (p \lor q)$ $≡ (p \lor$F $) \land (p \lor q)$                            (∵ 항등 법칙) $≡ p \lor ($F $\land \; q)$                                      (∵ 분배 법칙) $≡ p \lor$ F                                                   (∵ 지배 법칙) $≡ p$                                                          (∵ 항등 법칙)

 

진리표를 이용하여 흡수 법칙 $p \land (p \lor q) ≡ p$ 증명하기

`p`	`q`	$p \lor q$	$p \land (p \lor q)$
T	T	T	T
T	F	T	T
F	T	T	F
F	F	F	F

 

예제

Q. 논리적 동치 법칙을 이용하여 다음 합성 명제의 논리적 동치 관계가 성립함을 증명하라.

(a) $p \lor p ≡ p$

(b) $(p → q) \land (p → \neg q) ≡ \neg p$

(c) $p → \{(p \land q) → q \} ≡$ T

 

(a) $p \lor p$

$≡ (p \lor p) \land$ T                    (∵ 항등 법칙)

$≡ (p \lor p) \land (p \lor \neg p)$      (∵ 부정 법칙)

$≡ p \lor (p \land \neg p)$                 (∵ 분배 법칙)

$≡ p \; \lor$ F                                (∵ 부정 법칙)

$≡ p$                                        (∵ 지배 법칙)

 

(b) $(p → q) \land (p → \neg q)$

$≡ (\neg p \lor q) \land (\neg p \lor \neg q)$     (∵ 함축 법칙)

$≡ \neg p \lor (q \land \neg q)$                   (∵ 분배 법칙)

$≡ \neg p \; \lor$F                              (∵ 부정 법칙)

$≡ \neg p$                                   (∵ 항등 법칙)

 

(c) $p → \{(p \land q) → q \}$

$≡ \neg p \lor \{\neg(p \land q) \lor q \}$     (∵ 함축 법칙)

$≡ \neg p \lor \{(\neg p \lor \neg q) \lor q \}$   (∵ 드 므로간의 법칙)

$≡ \neg p \lor \{ \neg p \lor (\neg q \lor q) \}$   (∵ 결합 법칙)

$≡ \neg p \lor (\neg p \; \lor$ T $)$                 (∵ 부정 법칙)

$≡ \neg p \lor$T                            (∵ 지배 법칙)

$≡$ T                                     (∵ 지배 법칙)