[DiscreteMath]증명

📚기본사항

📄공리

공리는 어떤 다른 명제들을 증명하기 위해 전제로 사용되는 가장 기본적인 가정입니다. 증명 없이 참으로 이용되는 명제입니다.

📄증명

증명이란 특정한 공리들을 가정하고, 제안된 명제가 참임을 입증하는 작업입니다.

📄정리

정리는 공리로부터 증명된 명제를 말합니다.

• 피타고라스의 정리
• 페르마의 마지막 정리
• 유클리드 정리

📚직접증명법

직접증명법은 연역법이라고도 합니다. 명제를 변형하지 않고 공리와 정의 그리고 이미 증명된 정리들을 논리적으로 직접 연결하여 증명합니다.

📚수학적 귀납법

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

1. 기본단계: 출발점이 되는 n의 값에서 P(n)이 성립함을 증명

2. 귀납가정: n = k일 때, P(k)가 성립한다고 가정

3. 귀납단계: n = k + 1일 때, P(k + 1)도 성립함을 증명

📚간접증명법

증명해야 할 명제를 증명하기 쉬운 형태로 변형하여 증명하는 방법입니다.

📄대우증명법

명제 p→q가 주어졌을 때 ~q→~p임을 보임으로써 주어진 명제를 증명합니다.

📄모순증명법

명제 p→q가 주어졌을 때 p→~q를 가정하면 모순에 빠진다는 것을 보임으로써 주어진 명제를 증명합니다.

📄반례증명법

전체한정자가 사용된 명제함수 ∀xP(x)가 거짓임을 증명하기 위해 반례를 찾는 방법입니다.

📄구성적 존재증명법

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

📄비구성적 존재증명법

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

📚다양한 증명방법

📄전수 증명법

명제에서 유도될 수 있는 모든 경우의 수를 조사하는 방법입니다.

📄조합적 증명법

두 집합의 원소의 개수가 같다는 것을 증명할 때 사용되는 증명법입니다.

• 전단증명: 원소가 n개인 집합 A와 원소의 개수가 m인 집합 B에 대해, 두 집합이 일대일 관계임을 보여 n = m을 증명하는 방법입니다.

• 중복산정: 동일한 집합의 원소를 서로 다른 두 가지 방법으로 센 다음, 각각의 결과값이 동일할 수 밖에 없다는 사실을 이용하여 해당 집합과 관련된 성질이나 명제를 증명하는 방법입니다.

📄컴퓨터를 이용한 증명

컴퓨터를 이용한 증명은 수학적 증명과정 중에 컴퓨터를 이용한 계산이 포함된 경우를 말합니다. 4색정리에대한 증명이 대표적인 예입니다.