[Discrete Mathematics] 2. Proof

고교 과정과 안겹치는 내용 위주로 이산수학을 정리해보도록 하겠습니다.

성균관대학교 2021 여름학기 GEDB007_42 수업을 바탕으로 작성되었습니다.

* 쉽게..? 얼마나 쉽게..?

모든 $x_1 , x_2 ... x_n$에 대해 $p(x_1, x_2.... x_n) \rightarrow q(x_1, x_2.... x_n)$

반례 들기

귀류법

다 해보기

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

수학적 귀납법

$S(n)$이 propositional function이고, $D = \{n \in \N |n \geq n_0\}$ 에 대해 $S(n_0)$가 참임을 보이면 된다.

예를 들어, 4이상의 모든 정수를 2와 5의 합으로 나타낼 수 있음을 증명하려면,

n=4 일때 가능, n=5일때 가능,

6이상 n미만일 때 가능하다고 가정하면, n-2를 나타낼 수 있고, 따라서 n을 나타낼 수 있으므로 증명되는 그런 방식.... 고교 과정의 귀납법이랑 비슷하면서도 다르다.