이산수학/증명 - 기타증명법

증명의 이해

모순증명

• 결론을 부정하였을 때 모순이 발생함을 보여 결론이 성립함을 증명하는 방법

  예시 ) √2는 무리수임을 보이시오.
  
  증명)
  √2가 유리수라고 가정하자.
  유리수에 정의에 의하여 어떤 서로소인 정수 a, b가 존재하여
  √2 = a/b이다.
  양변에 b를 곱하면 b√2=a가 되고 제곱을 하면 2b²=a²이 된다.
  따라서 a²이 2의 배수이므로 a는 짝수이다.
  이제 a를 2로 나눈 몫을 k라고 하면 a=2k가 되고 2b²=a²에 대입하면 2b²=4k²이므로 b²=2k²이 되어 b도 2의 배수가 된다.
  그런데 a와 b는 서로소 이므로 둘이 동시에 2의 배수인 것은 가정에 모순이다.
  √2는 무리수이다.

동치증명법

• 주어진 명제와 동치인 명제를 증명하여 본 명제가 참임을 증명하는 방법

  예시) 두 정수 m,n의 곱이 홀수이면 m,n은 모두 홀수임을 증명하라
  p : 두 정수 m,n의 곱이 홀수이다. = > ~p : 두정수 m,n의 곱이 짝수이다.
  q : m,n은 모두 홀수이다. = > ~q : m,n이 모두 홀수는 아니다.
  
  증명)
  p → q와 ~q → ~p가 동치이므로 ~q → ~p임을 보이면 충분하다.
  
  m이 짝수라고 가정하자. m을 2로 나눈 몫을 k라고 하면 m = 2k가 되고 mn = 2kn이 되어 두 수의 곱은 짝수이다.
  따라서 두 정수 m,n의 곱은 짝수이다.
  n이 짝수라고 가정하여도 똑같은 방법으로 증명 가능하다.

존재증명법

• 주어진 명제가 존재성을 증명하는 문제일 때 명제를 만족하는 예를 찾아 증명하는 방법

  예시 ) 임의의 실수 a,b에 대하여 a < b라고 하자. 이 때 a < x < b를 만족하는 x가 존재함을 보이시오.
  
  증명)
  x = a+b/2라고 하자. 이는 정확히 a와 b의 중간에 있는 숫자이므로 a < x < b를 만족한다.
  따라서 a < x < b를 만족하는 x가 존재한다.