[이산수학] 증명 : 용어(공리, 정리) 직접 증명법, 귀납법, 간접 증명법(대우,모순,존재,전수)

본 게시글은 대학 전공수업을 들으며 노션에 정리한 내용을 블로그로 옮긴 것으로, 노션 웹을 통해 최적화된 형태로 읽으시길 권장드립니다.(➡️ 노션 링크)

증명

용어 개괄

공리(axiom)

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

ex) 두 점이 주어질 때, 두 점을 통과하는 직선을 그릴 수있다.(유클리드 기하학), 페아노의 공리, 공리적 집합론 . 등 자명한 사실.

증명(proof)

특정한 공리들을 가정하고, 그 가정하에 제안된 명제가 참임을 입증하는 작업

정리(theorem)

공리로부터 증명된 명제

1. 보조정리(lemma)
2. :정리를 증명하는 과정 중에 사용되는, 증명된 명제
3. 따름정리(corollary)
4. : 정리로부터 쉽게 도출되는 부가적인 명제

예: 피타고라스의 정리, 페르마의 마지막 정리 등.

증명 방법의 종류

직접 증명법

: 공리와 정의, 그리고 정리를 논리적으로 직접 연결하여 증명한다.

수학적 귀납법

: 자연수 n에 대한 명제의 성질을 증명하는 데 유용한 증명 방법. 기본단계, 귀납가정, 귀납단계를 이용한다.

간접 증명법

: 증명해야 할 명제를 증명하기 쉬운 형태로 변형하여 증명하는 방법이다. 대우 증명법, 모순 증명법, 반례 증명법, 존재 증명법 등이 있다.

직접증명법(direct proof)

• 다른말로 연역법(deduction, 이미 증명된 하나 또는 . 둘이상의 명제를 전제로하여, 새로운 명제를 결론으로 이끌어 냄)
• 명제를 변형하지 않고 증명한다.
• 주로, 공리와 정의, 그리고 이미 증명된 정리를 논리적으로 직접 연결해 증명하는 형식을 따른다.

예) 두 홀수의 합은 짝수임을 증명

두 홀수를 x,y라고 하고, 정수 a,b라고 하면
x = 2a + 1, y = 2b + 1 이고,

x + y = 2a + 2b + 2 = 2(a+b+1)

a+b+1은 정수이므로, ∴ x + y = 짝수.

이러한 방식으로 증명하는 것이 직접증명법

• 파스칼 삼각형대수적 방법 / 조합적인 방법(12강)으로 증명 가능.
• 대수적인 방법

수학적 귀납법(induction)

모든 자연수 n에 대해 명제를 증명하는데 유용

1. 기본단계(basis)
2. n의 출발점에서 명제가 성립하는가 확인
3. 귀납가정(inductive assumption)
4. n = k일때 명제가 성립한다고 가정
5. 귀납단계(inductive step)
6. n = k+1일때도 명제가 성립함을 증명

예 : 1+2+…+n = n(n+1) / 2 를 증명(n은 자연수)

① 기본단계

𝑺(𝟏)은 1 = 𝟏(𝟏+𝟏) / 𝟐 이므로 성립

② 귀납가정

𝑺(𝒌) 가 참이라고 가정. 즉, 𝟏 + 𝟐 + ⋯ + 𝒌 = 𝒌 * (𝒌+𝟏) / 𝟐 임을 가정

③ 귀납단계

S(k) + (k + 1) = S(k+1)임을 확인!

간접 증명법

: 증명해야할 명제를 증명하기 쉬운 형태로 변형하여 증명하는 방법

대우증명법(proof by transposition)

• 𝑷 → 𝑸 ⟺ ~ 𝑸 → ~ 𝑷
• 예) 𝒙^𝟐이 홀수라면 𝒙도 홀수임을 증명: “ x가 홀수가 아니라면, x^2도 홀수가 아니다.” 따라서, x는 짝수 : x = 2k(k는 정수)2k^2는 정수 → x^2 = 짝수. (대우가 성립한다.)
• ∴ 대우증명법에 의해 명제는 참이다.
• ⇒ x^2 = 4k^2 = 2(2k^2)
• 명제의 대우

모순증명법(proof by contradiction)

: 𝑷 → 𝑸를 증명할 때 ~ 𝑷를 가정하면 모순이 발생함을 보임.

다른 말로, 귀류법(오류로 귀착된다), 배리법(이치에 어긋나다.)

예: 루트𝟐가 유리수가 아님을 증명

반례증명법

전체한정자(∀)가 사용된 명제 $∀xP(x)$가 거짓임을 증명

• 예 “모든 실수 𝒂, 𝒃에 대해 𝒂𝟐 = 𝒃𝟐 이면 𝒂 = 𝒃 이다.”𝒂𝟐 = 𝒃𝟐을 만족하지만 𝒂 ≠ 𝒃 이다.
• ∴ 거짓
• 반례로서 𝒂 = −𝟐, 𝒃 = 𝟐 일 경우,

존재증명법

존재한정자(∃)가 사용된 명제 $∃xP(x)$가 참임을 증명

1. 구성적 존재증명법
   • 예 : a^b 이 무리수가 되는 유리수 a,b가 존재함을 증명⇒ 𝟐^(1/2) = 제곱근𝟐 (무리수)
   • ∴ 참 ■
   • 𝒂가 2, 𝒃가 𝟏/𝟐 이라고 하자.
2. 명제함수 ∃𝒙𝑷(𝒙)를 증명할 때 𝑷(𝒙)를 참으로 만드는
   𝒙를 찾거나 찾는 과정을 제시함
3. 비구성적 존재증명법

명제함수 ∃𝒙𝑷(𝒙)를 증명할 때, 𝑷(𝒙)를 참으로 만드는 𝒙 를 찾지 않고 우회적으로 명제가 타당함을 보이는 방법

• 예 : 𝒂𝒃이 유리수가 되는 무리수 𝒂, 𝒃가 존재함을 비구성적인 방법을 사용해 증명하시오.
•  
• 결론: 어떤 경우든지 aa와 bb가 무리수인데 abab가 유리수가 되는 경우가 존재함을 증명할 수 있다.

그 외 다양한 증명 방법

전수 증명법

:명제에서 유도될 수 있는 경우의 수가 적을 때 일일이 모든 경우의 수를 조사하는 방법

• 예제 *𝒏이 *5이하의 자연수 일 때 (𝒏 + 𝟏)𝟐≥ 𝟐𝒏임을 증명𝒏 = 𝟐일 때 (𝟐 + 𝟏)𝟐≥ 𝟐𝟐𝒏 = 𝟒일 때 (𝟒 + 𝟏)𝟐≥ 𝟐𝟒∴ 𝒏이 5이하의 자연수일 때 (𝒏 + 𝟏)𝟐≥ 𝟐𝒏 성립 ■
• 𝒏 = 𝟓일 때 (𝟓 + 𝟏)𝟐≥ 𝟐𝟓
• 𝒏 = 𝟑일 때 (𝟑 + 𝟏)𝟐≥ 𝟐𝟑
• [풀이] 𝒏 = 𝟏일 때 (𝟏 + 𝟏)𝟐≥ 𝟐𝟏

조합적 증명법

:두 집합의 원소의 개수가 동일함을 증명할 때 사용됨

1. 전단증명두 집합이 일대일 관계임을 보여 n = m임을 증명함.
2. 원소가 n개인 집합 A와 원소가 m개인 집합 B를 찾은 후,
3. 중복산정그 결과가 각각 n과 m이라면 n = m임을 증명함.
4. 동일한 집합의 원소를 두 가지 방법으로 센 다음,

컴퓨터를 이용한 증명

: 증명하기가 복잡한 경우 컴퓨터의 데이터 처리능력을 이용하여 증명함(계산의 양이 많거나, 경우의 수가 많을 때)

대표적 예시 : 4색정리( 평면을 여러 부분으로 나누어 각 부분에 색을 칠할 때, 맞닿은 부분을 다른색으로 칠할때 필요한 색은 4가지면 충분하다.)