이산 수학 - 증명

공리

• 어떤 다른 명제들을 증명하기 위해 전제로 사용되는 가장 기본적인 가정
• 별도의 증명 없이 참으로 이용되는 명제

증명

• 증명이란 특정한 공리들을 가정하고, 그 가정하에 제안된 명제가 참임을 입증하는 과정

정리

• 공리로부터 증명된 명제를 정리라고 한다.

직접증명법

• 다른 말로 연역(deduction)이라고도 함
• 명제를 변형하지 않고 공리와 정의, 그리고 이미 증명된 정리를 논리적으로 직접 연결해 증명하는 방법이다.

수학적 귀납법(proof of mathematical induction)

• 모든 자연수 n에 대해 명제가 성립함을 증명하는 데 유용한 방법

수학적 귀납법의 기본 구조

1. 기본 단계(base case)
   • n = 1일 때 명제가 성립함을 증명한다.
   • 출발점이 되는 n의 값
2. 귀납 가정
   • n = k일 때 명제가 성립한다고 가정한다.
3. 귀납 단계

• n = k + 1일 때 명제가 성립함을 증명한다.

간접증명법

• 증명해야 할 명제를 증명하기 쉬운 형태로 변형하여 증명하는 방법
• 대우증명법과 모순증명법이 있다.

반례증명법

• 전체한정자가 사용된 명제함수가 거짓임을 증명하기 위해 반례를 찾는 방법

구성적 존재증명법

• 존재한정자가 사용된 명제함수를 증명하는 방법으로 P(x)를 참으로 만드는 x를 주어진 정의역에서 찾거나 x를 찾는 일련의 과정을 제시하는 것

비구성적 존재증명법

• 직접적으로 P(x)를 참으롬 만드는 x를 찾거나 x를 찾는 일련의 과정을 제시하는 것이 아니라 우회적인 방법을 통해서 명제가 타당함을 보이는 방법