[ 이산수학 ] 9. 공리와 정의, 그리고 정리와 증명, 증명법

공리와 정의

- 공리 : 별도의 증명없이 참으로 가정한 진술(statement)을 의미

- 정의 : 기호의 의미를 확실하게 규정한 것을 의미하며 수학에서는 의미론적인 정의가 아니라 형식적인 정의를 사용한다. 형식적 정의란 현실에서의 의미를 중요시 여기는 것이 아니라, 기호적인 의미가 강한 것을 의미한다.

정리와 증명

- 정리 : 공리와 정의, 또는 다른 정리를 통해 참이라는 것을 확인할 수 있는 진술(statement)을 의미한다

1) 보조정리(lemma) : 정리를 증명하는 데 도움이 되는 정리를 의미한다.

2) 따름정리(corollary) : 증명된 정리로부터 직접적으로 귀결시킬 수 있는 정리

3) 가설(conjecture) : 직관이나 부분적 증거를 통해 참이라고 주장되는 문장

- 증명 : 특정한 명제가 참임을 확인시켜주는 정당한 논증의 과정을 의미한다.

증명법

(1) 직접 증명법 (direct proof)

: 증명하려고 하는 명제를 이미 알고 있는 공리나 정의, 증명들을 이용하여 그대로(순서대로) 증명하는 방법

(2) 대우 증명법 (proof by contraposition)

: 원래의 명제와 대우명제가 동치임을 이용하여 대우명제가 참임을 통해, 원래의 명제가 참임을 증명하는 방법

(3) 모순 증명법 (proof by contradiction)

: 귀류법, p→q에서 p를 참으로 가정하고 결론인 q를 부정했을 때 거짓이 되는 것을 이용하여 원래의 명제인 p→q가 참임을 이용하는 증명법

(4) 동치 증명법 (proof by equivalence)

: 상호조건문 p↔q가 (p→q) ∧ (q→p)와 동치임을 이용하는 증명법

(5) 반례 증명법 (proof by counter-example)

: 주어진 명제에 해당하지 않는, 즉 모순이 되는 단 1개의 명제가 존재함을 나타내어 명제가 거짓임을 증명하는 방법

(6) 존재 증명법 (existence proof)

: 특정한 조건을 만족하는 명제가 존재한다는 것을 증명하기 위해서 명제를 만족하는 하나의 경우를 보이는 증명법

(7) 수학적 귀납법(mathematical induction)

; 우선 첫번째가 성립함을 증명하고 n번째가 성립한다고 가정할 때, n+1이 성립하는 것을 증명하는 방법