PROOF 113
증명하라.
필요조건과 충분조건은 포함관계다
명제 논리 위에서.
한 줄씩, 이유를 따라가 봅시다
먼저 이미 주어진 것과 앞으로 보여야 할 것을 나누어 읽어 보세요. 다음 줄로 넘어갈 때마다 어떤 정의나 앞의 결과를 사용했는지 묻습니다. 연결이 보이지 않으면 결론을 외우기보다 그 전제로 잠시 돌아가도 좋습니다.
정의 D1
명제 p, q 에 대하여 p → q 가 성립할 때, p 를 q 의 충분조건이라 하고 q 를 p 의 필요조건이라 한다. 양쪽이 모두 성립하면 서로 필요충분조건이라 한다.
증명.
이 정의는 이름을 붙일 뿐이며, 그 이름이 왜 타당한지는 아직 말하지 않는다.약속
∎
정의 D2
전체집합 U 의 조건 p 에 대하여 P = {x ∈ U : p(x) 가 참} 을 p 의 진리집합이라 한다.
증명.
조건은 x 를 넣어야 참·거짓이 정해지는 문장이고, 진리집합은 그 조건을 참으로 만드는 원소를 모은 것이다.약속
∎
정의 D3
P ⊆ Q 는 P 의 모든 원소가 Q 의 원소임을 뜻한다.
증명.
포함은 원소 하나하나에 대한 주장이며, 두 집합의 크기를 비교하는 것이 아니다.약속
∎
정리 T1
p → q 일 때, p 가 참이라는 것 하나만으로 q 가 확정된다.
증명.
(1)p → q 라 하자.가정
(2)p 가 참이라 하자.가정
(3)분리 규칙에 의하여 q 가 참이다.(1), (2), A1
(4)p → q 이므로 p 는 q 의 충분조건이다.(1), (3), D1
∎
정리 T2
p → q 일 때, q 가 거짓이면 p 도 거짓이다.
증명.
(1)p → q 라 하자.가정
(2)p → q ⟺ ¬q → ¬pA2
(3)그러므로 ¬q → ¬p 이다.(1), (2), E
(4)q 가 거짓이라 하자. 즉 ¬q 가 참이다.가정, A3
(5)분리 규칙에 의하여 ¬p 가 참이다.(3), (4), A1
(6)즉 p 는 거짓이다.(5), A3
(7)q 가 성립하지 않으면 p 도 성립할 수 없다. 이것이 q 를 필요조건이라 부르는 근거다.(6), D1
∎
정리 T3
조건 p, q 에 대하여 모든 x 에서 p(x) → q(x) 가 성립하는 것을 p ⟹ q 로 쓴다. p ⟹ q 인 것과 P ⊆ Q 인 것은 서로 같다.
증명.
(1)모든 x 에서 p(x) → q(x) 라 하자.가정
(2)a ∈ P 라 하자. 즉 p(a) 가 참이다.가정, D2
(3)(1)에 x = a 를 넣으면 p(a) → q(a)(1), A4
(4)분리 규칙에 의하여 q(a) 가 참이므로 a ∈ Q(2), (3), A1, D2
(5)a 는 P 의 임의의 원소이므로 P ⊆ Q(4), D3
(6)거꾸로 P ⊆ Q 라 하자.가정
(7)임의의 a 에 대하여 a ∈ P 이면 a ∈ Q 이다.(6), D3
(8)즉 p(a) 가 참이면 q(a) 가 참이다.(7), D2
(9)그러므로 모든 x 에서 p(x) → q(x)(8)
(10)두 방향이 모두 성립하므로 둘은 같다.(5), (9)
∎
따름정리 C
조건 p, q 가 서로 필요충분조건인 것과 P = Q 인 것은 서로 같다.
증명.
(1)필요충분조건이라는 것은 p ⟹ q 와 q ⟹ p 가 함께 성립한다는 뜻이다.D1
(2)p ⟹ q 인 것은 P ⊆ Q 인 것과 같다.T3
(3)q ⟹ p 인 것은 Q ⊆ P 인 것과 같다.T3
(4)그러므로 필요충분조건인 것은 P ⊆ Q 이고 Q ⊆ P 인 것과 같다.(1), (2), (3)
(5)P ⊆ Q 이고 Q ⊆ P 인 것은 P = Q 와 같다.A5
(6)그러므로 필요충분조건인 것과 P = Q 인 것은 같다.(4), (5)
∎
비고
A2 는 이 증명에서 제거할 수 있는가.
두 이름을 따로 보라. 하나는 화살표를 앞에서 읽고, 다른 하나는 뒤에서 읽는다.