[이산수학] 3강 - 증명

✅ 1. 기본사항

(1) 공리 - 정의

• 공리: 명제들을 증명하기 위해 전제로 사용되는 가장 기본적인 가정으로, 별도의 증명 없이 참으로 이용되는 명제를 공리라함.
• 즉, 공리는 매우 기본적인 이 세상의 근본적인 참을 의미 할 수 있음. 가장 기본적인 참인 명제
• 예를 들면, "어떤 자연수도, 그 수의 다음 수가 존재한다." 라는 말은 굳이 증명을 하지 않더라도 참임을 알고 있는데, 이것이 공리임.

(2) 증명 - 정의

• 증명: 특정한 공리들을 가정한 상태에서 그 가정하에 제안된 명제가 참임을 입증하는 작업을 의미한다.
• 쉽게 말해, 공리를 제외한 참인 명제들은 정리라고 부르며, 이러한 공리와 정리를 통해서 특정 명제에 대한 참임을 밝히는 작업을 증명이라고 하며, 정리(증명된 명제) 또한, 결국 타고 타고 올라가면 가장 밑바닥에는 공리로 증명이 되고 있음.

(3) 정리 - 정의

• 정리: 공리로부터 증명된 명제를 의미한다. ( 타 정리와 공리를 활용해서 명제를 증명하면 얻을 수 있음. )
• 보조정리: 정리를 증명하는 과정 중에 사용되지 증명된 명제를 의미한다.
• 따름정리: 정리로부터 쉽게 도출되는 부가적인 명제를 의미한다.

(4) 증명 방법 - 종류

• 직접 증명법: 공리와 정의, 정리를 논리적으로 직접적으로 연결하여 증명하는 방법을 의미함.

• 수학적 귀납법: 자연수 n에 대한 명제의 성질을 증명하는 데 유용한 증명 방법이다. 기본단계, 귀납가정, 귀납단계를 이용함.
• 쉽게 말해, 자연수 n에 대한 무한한 연쇄 고리를 수식적 인과관계로 압축하여 정리한 논리의 수식으로 볼 수 있음. 
• 간접 증명법: 직접 증명으로 어려울 때, 사용하는 증명법으로 증명해야 할 명제를 증명하기 쉬운 형태로 변형하여 증명하는 방법임.
• 간접 증명법의 종류로는 대우 증명법, 모순 증명법, 반례 증명법, 존재 증명법 등이 존재한다.
• 그 외: 전수 증명법, 조합적 증명법, 컴퓨터 이용 증명법 등이 존재함.

---

✅ 2. 직접증명법

• 직접증명법: 공리와 정의, 이미 증명된 정리를 논리적으로 연결해 직접적으로 증명하는 방식의 방법을 의미한다.
• 특징으로는 명제를 변형하지 않고 직접 증명하며, 직접증명법은 다른 말로는 연역법이라고도 함.
• 연역법: 이미 증명된 명제들을 전제로 새로운 명제를 결론으로 이끌어내는 것을 의미함.

---

✅ 3. 수학적 귀납법

• 수학적 귀납법: 모든 자연수 n에 대해 명제를 증명하는 데 유용한 방법임.
• 1단계(기본단계): n의 출발점에서 명제가 성립하는가 확인
• 2단계(귀납가정): n = k 일 때 명제가 성립한다고 가정
• 3단계(귀납단계): n = k+1 일 때도 명제가 성립함을 증명
• 쉽게 말해, 기본단계에서 n = 1일 때, 명제가 성립하는지를 확인 한 뒤, 귀납가정 단계에서 n = k 일 때 성립이 한다고 가정한 뒤, 귀납단계에서 n = k+1 일 때 즉, n = 1~k 까지를 의미하며 이때에도 명제가 성립함이 증명이 된다면 이것은 증명이 된 것이다.
• 수학적 귀납법은 위와 같이 3단계 과정을 거치며, 출발점에서 자연수 n에 대해서 명제가 성립하는지 확인 한 뒤, 귀납가정을 통해 자연수 n에 입력 데이터 k 가 명제가 성립한다고 가정하며, 귀납단계를 통해 n = k+1 로 모든 자연수를 반복해서 대입하는 수식으로 성립함을 증명하는 것임.

• (1) 기본단계: n이 1인 경우 1 = 1(1+1)/2 이므로 성립함.
• (2) 귀납가정: k가 참이라고 가정을 함. 1 + 2 + ... + k = k(k+1)/2
• (3) 귀납단계: 귀납가정을 증명하는 단계이다.
• 수학적 귀납법에 의해서 주어진 명제는 참임을 증명한 것이다.

---

✅ 4. 간접증명법

(1) 간접증명법 이란?

• 간접증명법: 직접 증명이 어려울 때 사용하는 방법으로, 증명해야 할 명제를 증명하기 쉬운 형태로 변형하여 증명하는 방법임.
• 즉, 명제를 그대로 증명하기 어려울 때 증명하기 쉬운 형태로 변형하는 방법을 의미함.
• 대표적으로 대우증명법, 모순증명법, 반례증명법, 존재증명법 등이 있음.

(2) 간접증명법 - 대우증명법

• 대우증명법: 명제의 논리적 동치성을 이용하는 대표적인 간접증명법임.
• 쉽게 말해, 어떤 명제 P -> Q(P이면 Q이다)를 직접 증명하기 어려울 때, 그 명제의 대우 ~Q -> ~P(Q가 아니면 P가 아니다)가 참임을 증명하여 본래의 명제가 참임을 보이는 방식임.

(3) 간접증명법 - 모순증명법

• 모순증명법: 명제의 결론을 부정했을 때 논리적인 모순이 발생함을 보여서, 원래의 명제가 참일 수밖에 없음을 증명하는 방식
• 즉, 결론을 부정했을 때 모순이 발생함을 보여 원 명제가 참임을 입증함.(유리수라고 가정하면 모순이 생기므로 무리수이다)
• 쉽게 말해, 결론이 거짓이라고 가정했더니 말도 안되는 결론(0 = 1 등)이 나오니 반드시 결론은 참이어야만 한다는 주장

(4) 간접증명법 - 반례증명법

• 반례증명법은 전체한정자가 사용된 명제가 거짓임을 증명하는 것으로 볼 수 있음.
• 존재증명법은 존재한정자가 사용된 명제가 참임을 증명하는 것으로 볼 수 있음.

• 반례증명법: 어떤 명제가 거짓(False)임을 증명할 때 사용하는 방법임.
• 쉽게 말해, 수학적 명제가 "모든 x에 대하여 P(x)이다"라고 주장할 때, 그 주장이 틀렸음을 보이려면 단 하나의 예외만 찾아내면 됩니다. 이 예외를 바로 반례(Counterexample)라고 부름.

(5) 간접증명법 - 구성적 존재증명법

• 존재증명법: 조건을 만족하는 대상이 있음을 보이는 증명방법임.
• 구성적 존재증명법: 실제 그 대상을 찾거나 찾는 과정을 보여줌. 
• 쉽게 말해, 조건을 만족하는 구체적인 사례를 직접 제시하거나, 찾는 방법(알고리즘)을 보여주는 방식이로 "여기 봐, 진짜 있지?"라고 실물을 보여주는 것과 같음. ( 구체적인 사례를 직접 제시하는게 구성적인 것으로 볼 수 있음. )

(6) 간접증명법 - 비구성적 존재증명법

• 비구성적 존재증명법: 대상을 직접 찾지는 않지만 논리적으로 존재할 수밖에 없음을 우회적으로 보아 증명하는 방법
• 주로 귀류법(모순증명법)이나 비둘기집 원리를 사용하여, "존재하지 않는다고 가정하면 모순이 발생함"을 보여줌.

---

✅ 5. 다양한 증명방법

(1) 전수증명법

• 전수증명법: 가능한 모든 경우의 수가 적을 때 하나하나 전부 조사하여 증명하는 방식임.
• 전수 조사를 해서 직접 하는 것임. 바보같은 방법이라고 하던데..

(2) 조합적 증명법

• 조합적 증명법: 두 집합의 원소 개수가 같음을 증명할 때 사용하는 방식이며, 일대일 대응을 보이는 '전단증명'과 두 가지 방식으로 개수를 세어 결과가 같음을 보이는 '중복산정' 방식이 있음.
• 전단증명: 두 집합간의 원소가 일대일 관계임을 통해서 원소 개수가 같음을 증명하는 방식임.
• 중복산정: 동일한 집합에 대해서 유한개의 원소를 세는 방법이 각 집합 양쪽마다 다른 방법으로 산정을 하는데, 이때 그 결과가 동일하다는것을 증명하는 방법.

(3) 컴퓨터를 이용한 증명

• 컴퓨터를 이용한 증명: 증명하기 복잡한 경우에 컴퓨터의 데이터 처리능력을 이용하여 증명하는 방법임.