들어가기 전
What's Axiom?
- 어떤 다른 명제들을 증명하기 위해 전제로 사용되는 가장 기본적인 가정
별도의 증명 없이 참으로 이용되는 명제
예시
- 두 점이 주어졌을 때, 두 점을 통과하는 직선을 그릴 수 있다. / 유클리드 기하학
- 어떤 것도 포함하지 않는 집합이 존재한다. / 공리적 집학론What's Proof?
- 공리로부터 증명된 명제
1.보조정리 / Lemma : 정리를 증명하는 과정 중에 사용되는 증명된 명제
2.따름정리 / Corollary : 정리로부터 쉽게 도출되는 부가적인 명제
증명방법
1.직접증명법 : 공리와 정의, 정리를 논리적으로 직접 연결하여 증명
2.수학적 귀납법 : 자연수n에 대한 명제의 성질을 증명하는데 유용
3.간접 증명법 : 증명해야 할 명제를 증명하기 쉬운 형태로 변형하여 증명
*_대우 증명법, 모순 증명법, 반례 증명법, 존재 증명법 등_
4.그 외 : 전수 증명법, 조합적 증명법, 컴퓨터 이용 증명법1.직접증명법 / 연역법 / Direct Proof
- 명제를 변형하지 않고 증명
- 주로, 공리와 정의, 이미 증명된 정리를 논리적으로 직접 연결해 증명하는 형식
*연역법 : 이미 증명된 하나 또는 둘 이상의 명제를 전제로 하여 새로운 명제를 결론으로 이끌어냄
Q.두 홀수의 합은 짝수임을 증명하라.
A.두 홀수를 각각 𝒙, 𝒚라고 하자.
⇒ 𝒙 = 𝟐𝒂 + 𝟏, 𝒚 = 𝟐𝒃 + 𝟏 (단, 𝒂, 𝒃는 정수)
⇒ 𝒙 + 𝒚 = 𝟐𝒂 + 𝟏 + 𝟐𝒃 + 𝟏 = 𝟐(𝒂 + 𝒃 + 𝟏)
여기서 𝒂 + 𝒃 + 𝟏 은 정수이므로
∴ 𝒙 + 𝒚도 짝수이다.파스칼 삼각형 / Pascal’s triangle
참고-파스칼의 삼각형과 이항계수의 성질 / 강쌤
참고-이항정리① / 글이다수학
참고-이항정리와 파스칼의 삼각형 / Mathwitch
2.수학적 귀납법
- 모든 자연수 n에 대해 명제가성립함을 증명시 사용
3단계 과정
- 기본단계 / basis : n의 출발점에서 명제가 성립하는가 확인 (출발점이 되는 n의 값)
- 귀납가정 / inductive assumption : n = k 일 때 명제가 성립한다고 가정
- 귀납단계 / inductive step : n = k+1 일 때도 명제가 성립함을 증명
3.간접증명법
• 증명해야 할 명제를 증명하기 쉬운 형태로 변형하여 증명
대우증명법 / proof by transposition
𝑷 → 𝑸 ⟺ ~ 𝑸 → ~ 𝑷
모순증명법 / 귀류법 / 배리법/ proof by contradiction
𝑷 → 𝑸를 증명할 때 ~ 𝑷를 가정하면 모순이 발생함을 보임반례증명법
한정자(quantifer)가 포함된 명제의 증명
전체한정자(∀)가 사용된 명제가 거짓임을 증명 → 반례증명법
존재한정자(∃)가 사용된 명제가 참임을 증명 → 존재증명법 (구성적/비구성적) 구성적 존재증명법
명제함수 ∃𝒙𝑷(𝒙)를 증명할 때 𝑷(𝒙)를 참으로 만드는 𝒙를 찾거나 찾는 과정을 제시비구성적 존재증명법
명제함수 ∃𝒙𝑷(𝒙)를 증명할 때 𝑷(𝒙)를 참으로 만드는 𝒙 를 찾지 않고
우회적으로 명제가 타당함을 보이는 방법4.그 외
전수증명법
- 명제에서 유도될 수 있는 경우의 수가 적을 때 일일이 모든 경우의 수를 조사
조합적 증명법
- 두 집합의 원소의 개수가 동일함을 증명할 때 사용
1. 전단증명
원소가 n개인 집합 A와 원소가 m개인 집합 B를 찾은 후,
두 집합이 일대일 관계임을 보여 n = m임을 증명함.
2. 중복산정
동일한 집합의 원소를 두 가지 방법으로 센 다음,
그 결과가 각각 n과 m이라면 n = m임을 증명함.
Koreant🔨