이산수학 3. 증명

1. 증명의 이해

• 증명(proof): 하나의 명제가 참(\(T\))임을 확인하는 과정
• 공리(axiom): 별도의 증명 없이도 항상 참(\(T\))이라고 판단되는 명제
  • 예) 1은 자연수
• 정의(definition): 개념이나 기호의 의미를 확실하게 규정한 문장
• 정리(theorem): 공리와 정의를 통해 참(\(T\))으로 확인된 명제

2. 직접 증명법

• 직접 증명법(direct proof): \(p \rightarrow q\)가 참(\(T\))임을 증명하기 위해 전제 \(p\)를 참(\(T\))으로 가정햇을 때, 결론 \(q\)도 참(\(T\))임을 증명하는 방법
• 예)
  • 두 짝수 \(m\)과 \(n\)의 합이 짝수임을 증명
    • \(p \rightarrow q\): 두 정수 \(m\)과 \(n\)이 짝수이면, \(m\)과 \(n\)의 합은 짝수이다.
    • \(p\): 두 정수 \(m\)과 \(n\)이 짝수이다.
    • \(q\): \(m\)과 \(n\)의 합은 짝수이다.
    • 증명
      • \(m = 2k \; (k \in \mathbf{Z})\), \(n = 2l \; (l \in \mathbf{Z})\)​
      • $m + n = 2k + 2l = 2(k + l) = 2a \; (a \in \mathbf{Z})$
  • 모든 정수 \(x\)에 대하여, \(x^2-x\)는 짝수임을 증명
    • \(p\): 정수 \(x\)는 짝수이다.
    • \(q\): 정수 \(x\)는 홀수이다.
    • \(r\): \(x^2-x\)​는 짝수이다.
    • \((p \land q) \rightarrow r\): 모든 정수 \(x\)에 대하여, \(x^2-x\)는 짝수이다.
    • 증명
      • $(p \land q) \rightarrow r \equiv (p \rightarrow r) \land (q \rightarrow r)$
      • \(p \rightarrow r\): \(x^2-x = (2k)^2-2k=2(2k^2-k)=2a\)
      • \(q \rightarrow r\): \(x^2-x=(2k-1)^2-(2k-1)=2(2k-1)(k-1)=2(2k^2-3k+1)=2a\)

3. 간접 증명법

모순 증명법(proof by contradiction)

\[\begin{align*} p \rightarrow q & \equiv \neg p \lor q\\ & \equiv \neg p \lor \neg(\neg q)\\ & \equiv \neg(p \land \neg q) \end {align*}\]

• 조건 명제 \(p \rightarrow q\)와 \(\neg (p \land \neg q)\)가 동치임을 이용해 \(p \land \neg q\)가 거짓(\(F\)​)임을 보이는 방법
  • \(p \land \neg q = F\)면 \(p = T\)이고, \(q = F\)
• 예)
  • 두 짝수 \(m\)과 \(n\)의 합이 짝수임을 증명
    • \(p \rightarrow q\): 두 정수 \(m\)과 \(n\)이 짝수이면, \(m\)과 \(n\)의 합은 짝수이다.
    • \(p\): 두 정수 \(m\)과 \(n\)이 짝수이다.
    • \(q\): \(m\)​과 \(n\)​의 합은 짝수이다.
    • \(\neg q\): \(m\)과 \(n\)의 합은 짝수가 아니다.(홀수이다.)
    • \(p \land \neg q\): 두 정수 \(m\)과 \(n\)이 짝수이고, \(m\)과 \(n\)의 합은 짝수가 아니다.
    • 증명
      • \(m = 2k \; (k \in \mathbf{Z})\), \(n = 2l \; (l \in \mathbf{Z})\)​
      • $m + n = 2k + 2l = 2(k + l) = 2a \; (a \in \mathbf{Z})$
      • 짝수이므로 \(p \land \neg q\)는 거짓, 따라서 \(p \rightarrow q\)는 참

대우 증명법(proof by contrapositive)

• 조건 명제 \(p \rightarrow q\)와 이에 대한 대우 명제 \(\neg q \rightarrow \neg p\)가 동치임을 이용하여 증명하는 방법
• 예)
  • \(5m+4\)가 \(4\)로 나누어 떨어지지 않으면, 정수 \(m\)도 \(4\)로 나누어 떨어지지 않음을 증명
    • \(p \rightarrow q\): \(5m+4\)가 \(4\)로 나누어 떨어지지 않으면, 정수 \(m\)도 \(4\)로 나누어 떨어지지 않는다.
    • \(p\): \(5m+4\)가 \(4\)로 나누어 떨어지지 않는다.
    • \(q\): 정수 \(m\)은 \(4\)로 나누어 떨어지지 않는다.
    • \(\neg p\): \(5m+4\)가 \(4\)로 나누어 떨어진다.
    • \(\neg q\): 정수 \(m\)이 \(4\)로 나누어 떨어진다.
    • \(\neg q \rightarrow \neg p\): 정수 \(m\)이 \(4\)로 나누어 떨어지면, \(5m+4\)는 \(4\)로 나누어 떨어진다.
    • 증명
      • \(m=4k\), \(k\)는 정수
      • \[5m+4 = 20k + 4 = 4(5k + 1) = 4a\]
      • \(a\)는 정수이므로 \(5m+4\)는 \(4\)의 배수

## 존재 증명법(existence proof)

• 명제가 참(\(T\))이 되는 예를 찾아서 증명하는 방법
• 예)
  • 어떤 소수 \(n\)에 대하여, \(n + 4\)도 소수인지 증명
    • \(3 + 4 = 7\), 3과 7 모두 소수

반례 증명법(proof by counter-example)

• 명제가 모순이 되는 예를 찾아서 증명하는 방법
• 예)
  • 모든 소수 \(n\)에 대하여, \(n + 4\)도 소수인지 증명
    • \(5 + 4 = 9\), 5는 소수이지만 9는 소수가 아님

4. 수학적 귀납법(mathematical induction)

• 0보다 크거나 같은 정수 범위에서 발생하는 일정한 규칙을 나타내는 명제 \(P(n)\)이 성립함을 증명하는 방법

• 수학적 귀납법의 절차

  1. 기본 가정: 명제의 논의영역 \(D\)의 첫 번째 값 \(d\)에 대하여, \(P(d)\)가 참(\(T\))임을 보인다.
  2. 귀납 가정: 논의영역에 속하는 임의의 값 \(k\)에 대하여, \(P(k)\)가 참(\(T\))이라고 가정한다.
  3. 귀납 증명: 기본 가정과 귀잡 가정을 이용해 논의영역에 속하는 값 \(k+1\)에 대하여, \(P(k+1)\)이 참(\(T\))임을 증명한다.

• 예)

  • \(n \ge 1\)인 자연수 \(n\)에 대하여 \(1 + 2 + \cdots + n = \frac{n(n+1)}{2}\)임을 증명

    • 논의영역 \(D = \{ n \mid n \ge 1, n \in N \}\)

    • 명제 \(P(n) = 1 + 2 + \cdots + n = \frac{n(n+1)}{2}\)

    • 기본 가정: \(P(1) = \frac{1 \times 2}{2}=1\), 참(\(T\))

    • 귀납 가정: \(P(k)=1 + 2 + \cdots + k = \frac{k(k+1)}{2}\)이 참(\(T\))이라고 가정

    • 귀납 증명 \(\begin{align*} P(k+1) & = P(k) + k + 1\\ & = \frac{k(k+1)}{2} + k + 1\\ & = \frac{k^2 + 3k + 2}{2}\\ & = \frac{(k+1)(k+2)}{2}\\ & = \frac{(k+1)((k+1)+1)}{2}\\ \end{align*}\)

    • 따라서 \(P(k+1)\)은 참(\(T\))

    • 따라서 명제 \(P(n)\)는 참(\(T\))