명제, 참과 거짓을 따지는 문장

명제와 조건

참인지 거짓인지를 분명하게 판별할 수 있는 문장이나 식을 명제라 합니다. '3은 홀수이다'(참), '2 + 3 = 6'(거짓)은 모두 명제입니다. 거짓이어도 명제입니다. 반면 '오늘은 덥다'처럼 사람마다 판단이 다른 문장은 명제가 아닙니다.

'x는 2의 배수이다', 'x + 1 = 3'처럼 문자 x의 값에 따라 참이 되기도 거짓이 되기도 하는 문장을 조건이라 합니다. 조건은 그 자체로는 명제가 아니지만, x에 값을 넣으면 명제가 됩니다.

진리집합과 조건의 부정

전체집합 U에서 조건 p를 참이 되게 하는 원소 전체의 집합을 조건 p의 진리집합이라 하고 보통 P로 씁니다. 조건 p의 부정 ~p는 'p가 아니다'이며, 그 진리집합은 P의 여집합 $P^{c}$입니다.

1. 1
   6의 약수 → P = {1, 2, 3, 6}
2. 2
   ~p의 진리집합 $= P^{c} = \{4, 5\}$

'모든'과 '어떤'의 부정

'모든 x에 대하여 p이다'는 U의 모든 원소가 p를 만족할 때(P = U) 참이고, 하나라도 만족하지 않으면 거짓입니다. '어떤 x에 대하여 p이다'는 p를 만족하는 원소가 하나라도 있으면$(P \ne \varnothing )$ 참입니다. 두 명제의 부정은 '모든'과 '어떤'이 서로 바뀌고 조건이 부정됩니다.

p → q의 참과 거짓

두 조건 p, q로 만든 명제 'p이면 q이다'를 p → q로 쓰고, p를 가정, q를 결론이라 합니다. p를 만족하는 x가 모두 q도 만족하면 참이므로, 진리집합으로 말하면 $P \subset Q$이면 p → q는 참입니다. $P \not\subset Q$이면 거짓이고, 이때 P에는 속하지만 Q에는 속하지 않는 원소를 반례라 합니다.

1. 1
   $p: x^{2} = 4$의 진리집합 P = {−2, 2}, q: x = 2의 진리집합 Q = {2}
2. 2
   $-2 \in P$이지만 $-2 \notin Q$이므로 $P \not\subset Q$
3. 3
   따라서 거짓이고, 반례는 x = −2

역, 이, 대우

명제 p → q에서 가정과 결론을 바꾼 것을 역, 가정과 결론을 각각 부정한 것을 이, 바꾸고 부정까지 한 것을 대우라 합니다.

$P \subset Q$이면 $Q^{c} \subset P^{c}$이므로, 명제와 그 대우는 참·거짓이 항상 일치합니다. 마찬가지로 역과 이는 서로 대우 관계라 참·거짓이 일치합니다. 그러나 원명제가 참이라고 역이 참인 것은 아닙니다(위 표의 예처럼).

삼단논법

p → q가 참이고 q → r이 참이면, $P \subset Q$이고 $Q \subset R$이므로 $P \subset R$, 즉 p → r도 참입니다. 이렇게 두 명제를 이어 새로운 참인 명제를 얻는 것을 삼단논법이라 합니다.

충분조건과 필요조건

명제 p → q가 참일 때 기호로 $p \Rightarrow q$라 씁니다. 이때 p만 성립하면 q가 따라오므로 p는 q이기 위한 충분조건, q가 성립하지 않으면 p도 성립할 수 없으므로 q는 p이기 위한 필요조건이라 합니다. 진리집합으로는 작은 쪽$(P \subset Q$의 P)이 충분, 큰 쪽(Q)이 필요입니다.

1. 1
   두 조건의 진리집합 P, Q를 구합니다.
2. 2
   $P \subset Q$인지, $Q \subset P$인지 확인합니다. (숫자 몇 개를 넣어 보면 빠릅니다)
3. 3
   $P \subset Q$이면 $p \Rightarrow q: p$는 충분조건, q는 필요조건
4. 4
   $Q \subset P$이면 $q \Rightarrow p: q$는 충분조건, p는 필요조건
5. 5
   어느 쪽도 포함되지 않으면 아무 조건도 아닙니다.

1. 1
   P = {4, 8, 12, …}, Q = {2, 4, 6, 8, …}
2. 2
   4의 배수는 모두 2의 배수이므로 $P \subset Q \to p \Rightarrow q$
3. 3
   반대로 $2 \in Q$이지만 $2 \notin P$이므로 $q \Rightarrow p$는 아님
4. 4
   따라서 p는 q이기 위한 충분조건 (q는 p이기 위한 필요조건)

필요충분조건

$p \Rightarrow q$이고 동시에 $q \Rightarrow p$이면 기호로 $p \Leftrightarrow q$라 쓰고, p는 q이기 위한 필요충분조건이라 합니다(q도 p이기 위한 필요충분조건). 진리집합으로는 $P \subset Q$이고 $Q \subset P$, 즉 P = Q입니다.

정의, 증명, 정리

정의는 약속이므로 증명하지 않습니다. 정리는 반드시 증명을 거쳐야 하며, 한 번 증명된 정리는 다음 증명의 근거로 쓸 수 있습니다.

대우를 이용한 증명과 귀류법

명제 p → q를 직접 증명하기 어려우면, 참·거짓이 같은 대우 ~q → ~p를 증명해도 됩니다. 예를 들어 '자연수 n에 대하여 $n^{2}$이 짝수이면 n은 짝수이다'는 대우 'n이 홀수이면 $n^{2}$은 홀수이다'를 보이면 됩니다: n = 2k + 1이면 $n^{2} = 4k^{2} + 4k + 1 = 2(2k^{2} + 2k) + 1$이므로 홀수입니다.

귀류법은 명제의 결론을 부정했다고 가정하고 논리를 이어 가며 모순이 생김을 보여 원래 명제가 참임을 증명하는 방법입니다. '~이 아니다', '무리수이다'처럼 직접 보이기 어려운 명제에 씁니다.

1. 1
   결론을 부정: $\sqrt{2}$가 유리수라고 가정하면 서로소인 두 자연수 m, n에 대하여 $\sqrt{2} = \dfrac{n}{m}$ 으로 쓸 수 있다.
2. 2
   양변을 제곱하여 정리: $2\,\mathrm{m}^{2} = n^{2}$. 따라서 $n^{2}$은 짝수이고, 위에서 증명한 성질에 의해 n도 짝수 → n = 2k (k는 자연수)
3. 3
   대입: $2\,\mathrm{m}^{2} = (2k)^{2} = 4k^{2} \to m^{2} = 2k^{2}$. 따라서 $m^{2}$도 짝수이고 m도 짝수
4. 4
   m, n이 모두 짝수이면 공약수 2를 가지므로 'm, n은 서로소'라는 가정에 모순
5. 5
   따라서 가정이 틀렸고, $\sqrt{2}$는 무리수이다.