PROOF 112
증명하라.
드모르간 법칙
명제 논리 위에서.
한 줄씩, 이유를 따라가 봅시다
먼저 이미 주어진 것과 앞으로 보여야 할 것을 나누어 읽어 보세요. 다음 줄로 넘어갈 때마다 어떤 정의나 앞의 결과를 사용했는지 묻습니다. 연결이 보이지 않으면 결론을 외우기보다 그 전제로 잠시 돌아가도 좋습니다.
정의 D1
두 명제가 모든 진리값 배정에서 같은 값을 가질 때 두 명제는 동치라 하고 ⟺ 로 쓴다.
증명.
동치는 두 식이 같은 뜻이라는 주장이 아니라, 값이 언제나 함께 움직인다는 주장이다.약속
∎
정의 D2
x ∈ A ∩ B 는 (x ∈ A) ∧ (x ∈ B) 를, x ∈ A ∪ B 는 (x ∈ A) ∨ (x ∈ B) 를, x ∈ Aᶜ 는 ¬(x ∈ A) 를 뜻한다.
증명.
세 집합 연산은 각각 연언·선언·부정을 원소의 자리로 옮겨 쓴 것이다.약속
∎
보조정리 L1
모든 명제 p 는 참이거나 거짓이다.
증명.
(1)p ∨ ¬pA4
(2)선언이 참이므로 p 가 참이거나 ¬p 가 참이다.(1), A2
(3)¬p 가 참이면 p 는 거짓이다.A3
(4)그러므로 p 는 참이거나 거짓이다.(2), (3)
∎
보조정리 L2
p 와 q 에 참·거짓을 배정하는 네 경우 각각에서 ¬(p ∧ q) 와 ¬p ∨ ¬q 의 값은 같다.
증명.
(1)p 참, q 참: p ∧ q 는 참이므로 ¬(p ∧ q) 는 거짓이다. ¬p 와 ¬q 가 모두 거짓이므로 ¬p ∨ ¬q 도 거짓이다.A1, A2, A3
(2)p 참, q 거짓: p ∧ q 는 거짓이므로 ¬(p ∧ q) 는 참이다. ¬q 가 참이므로 ¬p ∨ ¬q 도 참이다.A1, A2, A3
(3)p 거짓, q 참: p ∧ q 는 거짓이므로 ¬(p ∧ q) 는 참이다. ¬p 가 참이므로 ¬p ∨ ¬q 도 참이다.A1, A2, A3
(4)p 거짓, q 거짓: p ∧ q 는 거짓이므로 ¬(p ∧ q) 는 참이다. ¬p 와 ¬q 가 모두 참이므로 ¬p ∨ ¬q 도 참이다.A1, A2, A3
(5)네 경우 모두에서 두 식의 값이 같다.(1), (2), (3), (4)
∎
정리 T1
모든 명제 p, q 에 대하여 ¬(p ∧ q) ⟺ ¬p ∨ ¬q
증명.
(1)p 는 참이거나 거짓이고, q 도 그러하다.L1
(2)그러므로 p 와 q 에 값을 배정하는 방법은 네 가지뿐이다.(1)
(3)그 네 경우 모두에서 두 식의 값이 같다.L2
(4)모든 배정에서 값이 같으므로 두 식은 동치다.(2), (3), D1
∎
정리 T2
모든 명제 p, q 에 대하여 ¬(p ∨ q) ⟺ ¬p ∧ ¬q
증명.
(1)T1 은 모든 명제에 대하여 성립하므로 p 자리에 ¬p, q 자리에 ¬q 를 넣으면 ¬(¬p ∧ ¬q) ⟺ ¬¬p ∨ ¬¬qT1
(2)¬¬p ⟺ p 이고 ¬¬q ⟺ qA5
(3)¬(¬p ∧ ¬q) ⟺ p ∨ q(1), (2), E
(4)양변을 부정하면 ¬¬(¬p ∧ ¬q) ⟺ ¬(p ∨ q)(3), E
(5)¬¬(¬p ∧ ¬q) ⟺ ¬p ∧ ¬qA5
(6)¬(p ∨ q) ⟺ ¬p ∧ ¬q(4), (5), E
∎
따름정리 C
전체집합의 부분집합 A, B 에 대하여 (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ
증명.
(1)x ∈ (A ∩ B)ᶜ ⟺ ¬(x ∈ A ∩ B)D2
(2) ⟺ ¬((x ∈ A) ∧ (x ∈ B))(1), D2, E
(3) ⟺ ¬(x ∈ A) ∨ ¬(x ∈ B)(2), T1
(4) ⟺ (x ∈ Aᶜ) ∨ (x ∈ Bᶜ)(3), D2, E
(5) ⟺ x ∈ Aᶜ ∪ Bᶜ(4), D2
(6)두 집합은 같은 원소를 가지므로 (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ(1), (5), A6
(7)같은 방법으로 T2 에서 (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ 을 얻는다.T2, D2, A6
∎
비고
A4 는 이 증명에서 제거할 수 있는가.
네 경우를 계산하는 일과 그 네 경우가 전부라고 말하는 일은 다르다. 어느 쪽이 배중률에 기대는지 확인하라.