명제와 논리

수학의 모든 정리는 명제이고, 증명은 명제들을 논리 규칙으로 이은 것이다. 이 단원에서는 명제를 결합하는 논리 연산과 진리표, 그리고 ‘조건문과 대우’라는 증명의 기본 도구를 다룬다.

핵심 개념

  • 명제: 참인지 거짓인지 분명히 판별할 수 있는 문장
  • 부정 $\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, q에 대한 부정, 그리고, 또는, 조건문, 대우의 진리표
진리표: $p\to q$와 대우 $\lnot q\to\lnot 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$이기 위한 충분조건이지만 필요조건은 아니다.

정리

  • 조건문 = 대우 (참거짓이 같음), 역과 이는 다를 수 있다.
  • 부정할 때 ‘그리고’와 ‘또는’이 바뀐다 (드모르간).
알림: 보호된 콘텐츠입니다.