드 모르간의 법칙 증명
📂집합론드 모르간의 법칙 증명
정리
- [1] 드 모르간의 법칙:
¬(p∧q)⟺¬p∨¬q¬(p∨q)⟺¬p∧¬q
- [2] 드 모르간의 정리:
(A∪B)c=Ac∩Bc(A∩B)c=Ac∪Bc
설명
드 모르간의 법칙와 드 모르간의 정리는 각각 명제, 집합에 대한 정리지만 실제로 말을 하면서는 별로 구분하지 않는다. 법칙이든 정리든 드 모르간- 만 붙으면 부정이나 여집합을 취하면 괄호 안의 명제, 집합과 기호가 ‘뒤집히는’ 모양새라고 알아듣기 때문이다.
한편 수학적 귀납법에 따라 다음과 같은 일반화는 물론, 인덱스 패밀리까지 확장이 가능하다.
(i=1⋃∞Xi)c=i=1⋂∞(Xi)c(i=1⋂∞Xi)c=i=1⋃∞(Xi)c&(α∈∀⋃Xα)c=α∈∀⋂(Xα)c(α∈∀⋂Xα)c=α∈∀⋃(Xα)c
증명
[1]
진리표로 증명한다.
Part 1. ¬(p∧q)⟺¬p∨¬q

Part 2. ¬(p∨q)⟺¬p∧¬q

■
[2]
Part 1. (A∪B)c=Ac∩Bc
x∈(A∪B)c⟺⟺⟺⟺⟺¬(x∈A∪B)¬(x∈A∨x∈B)¬(x∈A)∧¬(x∈B)x∈Ac∧x∈Bcx∈(Ac∩Bc)
Part 2. (A∩B)c=Ac∪Bc
x∈(A∩B)c⟺⟺⟺⟺⟺¬(x∈A∩B)¬(x∈A∧x∈B)¬(x∈A)∨¬(x∈B)x∈Ac∨x∈Bcx∈(Ac∪Bc)
■