드모르간 법칙 증명(proof of De Morgan law)

 

 

검색어 유입에 드모르간 관련한 게 있길래 증명해봅니다.

 

먼저 여러 가지 정의들을 알아야 합니다.

 

(A, B is a set, and x is every element)

A⊆B ⇔x∈A → x∈B

x∈~A ⇔  x∉A  (A is a set)

x∈A∩B ⇔ x∈A ∧ x∈B

x∉A∩B ⇔ x∉A ∨ x∉B 

x∈A∪B ⇔ x∈A ∨ x∈B

x∉A∪B ⇔ x∉A ∧ x∉B

등호(=)의 증명법은 A⊆B ∧ B⊆A  ⇔ A=B로 됩니다.

 

x∉A∩B ⇔ x∉A ∨ x∉B 

x∉A∪B ⇔ x∉A ∧ x∉B

 

이 두 식은 De Morgan law of logic을 전제합니다. 즉, ~(p∨q) ≡ ~p∧~q, ~(p∧q) ≡ ~p∨~q를 전제합니다.

(이는 진리표를 그려서 확인하시길 바랍니다)

 

 

1. ~(P∩Q) = ~P∪~Q

 

 

i) ~(P∩Q) ⊆ ~P∪~Q

every element x에 대해서 x∈~(P∩Q)라고 가정하자.

 

가정에 의해서 x∉(P∩Q)이다.

이는 x∉A ∨ x∉B이다.

 

즉, (x∈~P)∨(x∈~Q)이다.

 

이는 x∈~P∪~Q와 동치이다.

 

x∈~(P∩Q) → x∈~P∪~Q 이므로  ~(P∩ Q) ⊆ ~P∪~Q이다.

 

 

ii)  ~P∪~Q ⊆ ~(P∩Q)

 

x∈~P∪~Q를 가정하자.

 

곧 x∈~P ∨ x∈~Q이고 x∉P ∨ x∉Q이다.

 

x∉P ∨ x∉Q는 정의에 의해서 x∉P∩Q다.

 

이는 x∈~(P∩Q)와 동치이다.

 

x∈~P∪~Q → x∈~(P∩Q)이므로   ~P∪~Q ⊆ ~(P∩Q)이고

 

i) ii)에 의해서  ~(P∩Q) = ~P∪~Q이다.

 

 

 

2. ~(P∪Q) ⇔ ~P∩~Q

 

1과 같은 방식으로 진행하면 된다.