🤣

[Discrete Mathematics] 2. Proof

고교 과정과 안겹치는 내용 위주로 이산수학을 정리해보도록 하겠습니다.
성균관대학교 2021 여름학기 GEDB007_42 수업을 바탕으로 작성되었습니다.

Mathematical Systems

Axioms (공리) : 참이라고 여겨지는 것 (assumed to be true)
Theorem (정리) : 참이라고 증명된 명제
Lemma (보조정리) : 다른 정리들을 증명할때 사용되는 정리
Corollary (따름정리) : 다른 정리로부터 쉽게 증명되는 정리
* 쉽게..? 얼마나 쉽게..?
Undefined Term (무정의 용어) : 정의하지 않고 사용하는 용어 정리나 공리등을 증명할 때 사용

Direct Proof

모든 x1,x2...xnx_1 , x_2 ... x_n에 대해 p(x1,x2....xn)q(x1,x2....xn)p(x_1, x_2.... x_n) \rightarrow q(x_1, x_2.... x_n)

Counter Examples

반례 들기

Proof by Contradiction

귀류법

Proof by Cases

다 해보기

Proofs of Equivalance

pq(pq)(qp)p \leftrightarrow q \equiv (p\rightarrow q) \wedge (q \rightarrow p) 임을 보이기

Mathematical Induction

수학적 귀납법

Strong Form of Mathematical Induction

S(n)S(n)이 propositional function이고, D={nNnn0}D = \{n \in \N |n \geq n_0\} 에 대해 S(n0)S(n_0)가 참임을 보이면 된다.
예를 들어, 4이상의 모든 정수를 2와 5의 합으로 나타낼 수 있음을 증명하려면,
n=4 일때 가능, n=5일때 가능,
6이상 n미만일 때 가능하다고 가정하면, n-2를 나타낼 수 있고, 따라서 n을 나타낼 수 있으므로 증명되는 그런 방식.... 고교 과정의 귀납법이랑 비슷하면서도 다르다.