이산수학/증명 - 직접 증명과 반례

증명의 이해

공리(Axiom)

• 별도의 증명 없이 항상 참으로 이용되는 명제
  • 예) 어떤 자연수 n에 대하여 n + 1이 존재한다.

정의(Definition)

• 용어 또는 기호의 의미를 확실하게 규정한 문장이나 식
  • 예) n != n X (n - 1) X ... 3 X 2 X 1

정리(Theorem)

• 공리와 정의를 통해 참으로 확인된 명제
  • 예) 피타고라스의 정리

증명(Proof)

• 명제가 진릿값을 확인하는 과정

직접증명

• 조건명제 p → q를 증명하기 위해 p를 참이라 가정한 상태에서 q도 참임을 증명하는 방법

  예시 ) 짝수와 홀수를 더하면 홀수가 됨을 보여라.
  p : 숫자 m은 짝수이고 숫자 n은 홀수이다.
  q : m + n은 홀수이다.
  
  증명)
  정의에 의하여 m은 2로 나누어 떨어지는 수고, n은 2로 나누었을 때 나머지가 1인 수이다.
  따라서 m을 2로 나누었을 때의 몫을 k라고 하고 n을 2로 나누었을 때의 몫을 l이라고 하면,
  m = 2k 　　　　n = 2l +1
  이 된다.
  
  이 때 m + n = 2k + 2l + 1 = 2(k + l) + 1이고, 이를 2로 나눈 몫은 k + l 이고 나머지는 1인 홀수이다.
  
  짝수와 홀수를 더하면 홀수이다는 참이다.

반례증명법

• 주어진 명제에 모순이 되는 예를 찾아서 명제가 거짓임을 증명하는 방법

  예시) 다음 명제의 진릿값을 구하시오
  모든 양수 x에 대하여 X² > x 이다
  
  증명)
  x = 0.1 일 때 X²은 0.01이고 x는 0.1이므로 0.1² < 0.1 이다.
  반례가 존재하므로 모든 양수 x에 대하여 X² > x 성립한다는 명제는 거짓인 명제이다.