수학의 모든 정리는 명제이고, 증명은 명제들을 논리 규칙으로 이은 것이다. 이 단원에서는 명제를 결합하는 논리 연산과 진리표, 그리고 ‘조건문과 대우’라는 증명의 기본 도구를 다룬다.
핵심 개념
- 명제: 참인지 거짓인지 분명히 판별할 수 있는 문장
- 부정 $\lnot p$, 그리고 $p\land q$, 또는 $p\lor q$
- 조건문 $p\to q$: ‘$p$이면 $q$이다’. $p$가 참이고 $q$가 거짓일 때만 거짓이다.
- 역 $q\to p$, 이 $\lnot p\to\lnot q$, 대우 $\lnot q\to\lnot p$
- 필요충분조건 $p\leftrightarrow q$: $p\to q$와 $q\to p$가 모두 참
- 항진명제: 항상 참인 명제
핵심 정리
- 조건문과 그 대우는 참거짓이 항상 같다. ($p\to q\equiv\lnot q\to\lnot p$)
- 드모르간 법칙: $\lnot(p\land q)\equiv\lnot p\lor\lnot q$, $\lnot(p\lor q)\equiv\lnot p\land\lnot q$
- $p\to q\equiv\lnot p\lor q$
증명 보기
진리표로 확인한다. $p,q$의 참거짓 조합은 $4$가지뿐이므로 모든 경우를 확인하면 증명이 된다.
- $p\to q$: (T,T)→T, (T,F)→F, (F,T)→T, (F,F)→T
- $\lnot q\to\lnot p$: (T,T)에서 $\lnot q=$F이므로 T, (T,F)에서 $\lnot q=$T, $\lnot p=$F이므로 F, (F,T)에서 T, (F,F)에서 $\lnot q=$T, $\lnot p=$T이므로 T
두 열이 같다. 드모르간 법칙과 $\lnot p\lor q$도 같은 방법으로 확인된다. $\blacksquare$
역과 이는 원래 명제와 참거짓이 다를 수 있다. ‘$x=2$이면 $x^2=4$’는 참이지만 역 ‘$x^2=4$이면 $x=2$’는 거짓이다($x=-2$).
예제
- ‘$n^2$이 짝수이면 $n$은 짝수이다’를 증명하려면 대우 ‘$n$이 홀수이면 $n^2$은 홀수이다’를 증명하면 된다: $n=2k+1$이면 $n^2=2(2k^2+2k)+1$
- ‘$x>0$이고 $y>0$’의 부정은 ‘$x\le0$ 또는 $y\le0$’
확인 문제
$x=1$은 $x^2=1$이기 위한 어떤 조건인가?
풀이 보기
$x=1\Rightarrow x^2=1$은 참이고, $x^2=1\Rightarrow x=1$은 거짓($x=-1$)이다. 따라서 $x=1$은 $x^2=1$이기 위한 충분조건이지만 필요조건은 아니다.
정리
- 조건문 = 대우 (참거짓이 같음), 역과 이는 다를 수 있다.
- 부정할 때 ‘그리고’와 ‘또는’이 바뀐다 (드모르간).
