[이산수학] 증명

증명의 기본 사항

1. 공리
   
   • 어떤 명제들을 증명하기 위해 전제로 사용되는 가장 기본적인 가정
     
     
2. 증명
   
   • 특정한 공리들을 가정하고 명제가 참임을 입증하는 작업
     
     
3. 정리
   
   • 가정으로부터 증명된 명제
     
     
4. 증명방법
   
   1) 직접 증명법
   
   - 연역법이라고도 함
   - 명제를 변형하지 않고 증명
   
   2) 수학적 귀납법
   
   - 모든 자연수 n에 대해 명제가 성립함을 증명하는데 유용
   - 세가지 단계로 나뉘어 증명
   * 기본단계 : 출발점이 되는 n의 값
   * 귀납가정 : n=k일 때 성립한다고 가정
   * 귀납단계 : n+k+1일 때도 성립함을 증명
   
   3) 간접 증명법
   
   - 대우 증명법
   : 함축명제 p→q가 ~q→~p와 동치임을 이용하여 증명하는 방법
   - 모순 증명법
   : 함축명제 p→q가 ~ (p∧~q)와 동치임을 이용하여 증명하는 방법
   - 반례 증명법
   : 주어진 명제에 모순이 되는 예를 찾아 증명하는 방법
   - 존재 증명법
   : 주어진 명제에 참이 되는 예를 찾아 증명하는 방법
   
   4) 기타 증명법
   
   - 전수 증명법
   - 조합적 증명법 : 전단 증명 / 중복 산정
   - 컴퓨터를 이용한 증명
   등…