[이산수학] 증명

증명: 새로운 수학적 진술이 참임을 입증하는 데 필요한 논증. 특정 공리들을 가정하고 그 가정 하에 제안된 명제가 참임을 입증한다.

공리: 다른 명제들을 증명하기 위해 전제로 사용되는 가장 기본적인 가정. 별도의 증명 없이 참으로 이용된다

정리: 공리들을 바탕으로 논리적으로 증명된 결론

 

 

직접증명법 (연역)

• 명제 변형 없이 공리와 정의, 이미 증명된 정리를 논리적으로 직접 연결해 증명

 

수학적 귀납법

• 모든 자연수 n에 대해 명제 성립 증명하는 데 유용함
• 기본단계 > 귀납가정 > 귀납단계

 

간접증명법

• 명제를 증명하기 쉬운 형태로 변형
• 대우증명법
• 모순증명법
  • p → ~q를 가정하면 모순임을 증명
• 반례증명법
• 구성적 존재증명법
  • P(x)를 참으로 만드는 x를 주어진 정의역에서 찾는다
• 비구성적 존재증명법
  • 직접적으로 x를 찾지 않고 우회적인 방법으로 증명

 

전수증명법

조합적 증명법

• 전단증명
• 중복산정