1. 증명과 명제, 공리 (Proof, Proposition and Axioms)
증명Proof은 어떠한 것이 참/거짓임을 밝히는 것을 의미한다. 증명의 예시는 다음과 같다.
- 관측과 실험: 물체가 지구로 떨어진다. -> 중력이 존재한다.
- 반대 사례 찾기: A씨는 개를 싫어한다. -> "모든 사람이 개를 좋아한다."는 거짓이다.
- 판결: 법에 따라, 살인은 죄이다. -> 법이라는 기준에 따라 판결
특히, 수학적 증명은 공리axiom들에 기반한 논리적 추론logical deduction을 통해, 어떠한 명제proposition를 증명하는 것을 의미한다.
명제Proposition
명제는 참이나 거짓이 분명한 문장을 말한다.
- 2+3=5
- 5−2≠5
- 백지오는 2020년 기준, 21살이다.
- ∀n∈N,n2+n+41 is a prime number.
술어Predicate
술어는 참/거짓이 변수에 의해 바뀌는 명제를 말한다.
오일러의 거듭제곱의 합 추측Euler's Conjecture이 유명한데, 오일러는 아래 식의 양의 자연수 해가 존재하지 않는다고 추측했다.
a4+b4+c4=d4
이 추측을 식으로 나타내면 아래와 같다.
∄a,b,c,d∈N+,a4+b4+c4=d4
그러나, 위 식은 a=95800,b=217519,c=414560,d=432481에서 성립하므로 위 명제는 거짓이다. 위 명제는 변수에 따라 일부 성립하는 술어이다.
∃a,b,c,d∈N+,a4+b4+c4=d4
함축Implication
"p이면 q이다.", "p는 q를 함축한다.", "p는 q의 충분조건이다."와 같이, 두 사건의 인과관계가 연관된 경우를 함축이라 하고, ⇒ 기호로 나타내고, 조건명제라 부른다.
함축 p⇒q은 p가 거짓이거나 q가 참일때 참이다.
p | q | p⇒q |
T | T | T |
T | F | F |
F | T | T |
F | F | T |
쌍방조건명제Biconditional
명제 p와 q가 서로 동시에 조건이며 명제인 경우에는 쌍방조건명제라 부른다. 이때, p와 q는 서로를 필요충분조건으로 갖는다.
p | q | p⇒q (충분조건) |
q⇐p (필요조건) |
p⇔q (필요충분조건) |
T | T | T | T | T |
T | F | F | T | F |
F | T | T | F | F |
F | F | T | T | T |
공리Axioms
공리는 참으로 추측되는 명제이다. 명제를 증명하기 위한 근거 중, 가장 기본이 되는 진리와 같은 명제를 공리라 한다. 예를들어, a=b,b=c⇒a=c는 공리이다.
공리계는 일관성Consistent 혹은 완결성Complete을 가져야한다.
일관성은 증명할 수 없지만 확연한 진리를 의미하고(a=b⇒a+c=b+c), 완결성은 공리계의 모든 명제가 참/거짓으로 증명될 수 있는 경우를 의미한다.
한 명제가 일관성과 완결성을 모두 가질 수는 없으므로, 수학적으로 증명할 수 없는 명제가 존재할 수밖에 없다.(괴델의 불완전성 정리)
'학부 수업 > 이산수학' 카테고리의 다른 글
4. 정수론: 최대공약수 (Number Theory: Great Common Divisor) (1) | 2020.10.14 |
---|---|
3.5 Unstacking Game 강한 귀납법으로 증명하기 (0) | 2020.10.14 |
3.5 귀납법을 통한 문자 퍼즐 문제 증명 (0) | 2020.10.14 |
3. 좋은 증명과 강한 수학적 귀납법 (Good Proof and Strong Induction) (1) | 2020.10.14 |
2. 수학적 귀납법과 예제를 통한 증명 (Proof by Induction) (2) | 2020.09.27 |
댓글
이 글 공유하기
다른 글
-
3.5 Unstacking Game 강한 귀납법으로 증명하기
3.5 Unstacking Game 강한 귀납법으로 증명하기
2020.10.14 -
3.5 귀납법을 통한 문자 퍼즐 문제 증명
3.5 귀납법을 통한 문자 퍼즐 문제 증명
2020.10.14 -
3. 좋은 증명과 강한 수학적 귀납법 (Good Proof and Strong Induction)
3. 좋은 증명과 강한 수학적 귀납법 (Good Proof and Strong Induction)
2020.10.14 -
2. 수학적 귀납법과 예제를 통한 증명 (Proof by Induction)
2. 수학적 귀납법과 예제를 통한 증명 (Proof by Induction)
2020.09.27
댓글을 사용할 수 없습니다.