PROOF 26
증명하라.
귀류법은 정당하다
명제 논리 위에서.
한 줄씩, 이유를 따라가 봅시다
먼저 이미 주어진 것과 앞으로 보여야 할 것을 나누어 읽어 보세요. 다음 줄로 넘어갈 때마다 어떤 정의나 앞의 결과를 사용했는지 묻습니다. 연결이 보이지 않으면 결론을 외우기보다 그 전제로 잠시 돌아가도 좋습니다.
정의 D1
모순이란 q ∧ ¬q 꼴의 명제다. 이것을 ⊥ 로 쓴다.
증명.
어떤 명제와 그 부정이 함께 성립한다는 뜻이다.약속
∎
정의 D2
¬p 는 p 가 성립하지 않음 을 뜻한다.
증명.
부정은 성립 여부를 뒤집는다. p 와 ¬p 가운데 무엇이 성립하는지는 이 정의가 말하지 않는다.약속
∎
보조정리 L1
⊥ 는 성립하지 않는다.
증명.
(1)⊥ 는 q ∧ ¬q 이다.D1
(2)¬(q ∧ ¬q)A2
(3)그러므로 ⊥ 는 성립하지 않는다.(1), (2), D2
∎
보조정리 L2
p → ⊥ 이면 ¬p 이다.
증명.
(1)p 가 성립한다고 하자.가정
(2)p → ⊥ 이므로 ⊥ 가 성립한다.(1), 가정, A4
(3)⊥ 는 성립하지 않는다.L1
(4)그러므로 p 는 성립하지 않는다.(2), (3)
(5)즉 ¬p 이다.(4), D2
∎
정리 T
¬p 를 가정하여 모순을 얻으면 p 가 성립한다.
증명.
(1)¬p → ⊥ 라 하자.가정
(2)L2 를 ¬p 에 적용하면 ¬¬p 를 얻는다.(1), L2
(3)¬¬p 는 ¬p 가 성립하지 않음을 뜻한다.(2), D2
(4)p ∨ ¬pA1
(5)두 항 가운데 ¬p 가 성립하지 않으므로 p 이다.(3), (4), A3
∎
비고
A1 은 이 증명에서 제거할 수 있는가.
배중률은 증명된 것이 아니라 받아들이기로 한 규칙이다. 제거하면 어느 줄이 근거를 잃는지 확인하라.