이산수학

정수론이란, 정수의 성질을 연구하는 학문이다. 정수론은 주로 현대 암호학에 응용된다. 물통 채우기 $(a\leq b)$인 $a$리터 물병과 $b$리터 물병을 이용해 $m$리터 물통을 채워야 하는 문제를 생각해보자. $m|a$: $a$는 $m$으로 나누어 떨어진다. $\text{iff (if and only if)}$: 필요충분조건 $$ \text{Def 1.} m|a \text{, iff } \exists k \in \mathbb{Z}, a=km $$ $a =km$이 성립하는 정수 $k$가 존재할 때, $a$는 $m$으로 나누어 떨어지고 $m|a$처럼 나타낼 수 있다. $$\text{Theorem 1. if } m|a \text{ and } m|b \text{, then } m|\text{any poss..

좋은 수학적 증명은 다음 요소들을 갖는다. 올바름Correct 완전성Complete (과정을 생략하지 않음) 명료성Clear 간결성Brief 아름다움Elegant 잘 정돈됨Well-organized 보조 정리Lemma 활용 순서에 맞는 변수 활용 ($a, b, \cdots$) 반면, 나쁜 수학적 증명은 다음 요소들을 포함한다. 이미 알려진 공리나 이론을 불필요하게 많이 사용함 (피로한 증명) 적절하지 않은 예시를 통한 증명 (편향된 예시, 극소수의 예시 등) 강렬한 주장 등을 통한 증명 (= 우기기) 생략을 포함한 증명 사진을 이용한 증명 직관을 통한 증명 권위를 통한 증명 성가신 노테이션 지저분하고 직관적이지 않은 변수 사용 수학 증명 용어들 정의 (Definition): 수학 기호와 용어의 뜻 등을 ..

증명은 어떤 명제Proposition가 참 혹은 거짓임을 어떤 공리계Set of Axioms에 기반한 논리적 추론Logical Deductdion을 통해 보이는 것이다. 증명의 방법에는 크게 3가지가 있다. 직접 증명Direct Method 예제를 통한 증명by Contradiction $p$가 참이란 예제를 보이는 것 $\neg p$가 거짓이란 예제를 보이는 것 귀납법을 통한 증명by Induction "$p: \sqrt{2} $는 무리수이다" 예제로 증명하기 $\neg p: \sqrt{2} \text{ is rational.} $ $p$를 증명하기 위해, $\neg p$, "$\sqrt{2}$가 유리수이다"가 거짓임을 증명하면 된다. $\sqrt{2} = \frac{a}{b} \text{(fracti..

증명Proof은 어떠한 것이 참/거짓임을 밝히는 것을 의미한다. 증명의 예시는 다음과 같다. 관측과 실험: 물체가 지구로 떨어진다. -> 중력이 존재한다. 반대 사례 찾기: A씨는 개를 싫어한다. -> "모든 사람이 개를 좋아한다."는 거짓이다. 판결: 법에 따라, 살인은 죄이다. -> 법이라는 기준에 따라 판결 특히, 수학적 증명은 공리axiom들에 기반한 논리적 추론logical deduction을 통해, 어떠한 명제proposition를 증명하는 것을 의미한다. 명제Proposition 명제는 참이나 거짓이 분명한 문장을 말한다. $2+3=5$ $5-2\neq 5$ 백지오는 2020년 기준, 21살이다. $\forall n \in \mathbb{N} , n^2 + n + 41 \text{ is a ..