[이산수학] 증명법(proof method)

1. Proof method (증명법)

1-1. Direcct proof(직접증명법)

p → q 성질 이용, 순서대로 증명한다.

p True, q True
∴ p → q is True

 

 

1-2. Indirect proof(간접증명법) - 대우증명법, 모순증명법 2가지 존재

 

• proof by contraposition(대우증명법)

대우의 성질을 이용한다. (p → q가 True면 ¬q → ¬p 도 True)

¬q true , ¬p true
∴ p → q is True

 

 

• proof by contradiction(모순증명법) - 귀류법으로도 불린다.

¬p를 먼저 가정하고, ¬p가 일어나지 않음을 증명해서, 따라서 p → q 가 True임을 증명한다.

대표적인 예시인 √2 가 무리수임을 이용해 보이기:

 

 

irrationality of √2

수정: p^2 -> p 는 대우 증명법으로 증명한다

  

 

1-3. vacuous proof

p is False
∴ p → q is True

 p → q: p가 참, q가 거짓이면 p → q 는 거짓, 나머지 경우는 참임을 기억하기! )

- p가 거짓이면 p → q는 무조건 참이다.

참고: p → q 진리표와 예시

 

1-4. trivial proof

q is True
∴  p → q is True

- q가 참이면 p → q는 무조건 참이다.

 

 

 

1-5. proof by cases

모든 가능한 케이스에 대해 참임을 증명하면 전체가 참임을 증명하는 방법이다.

(P1 → q) ∧ (P2 → q) ∧ ···  ∧ (Pn → q)  is True       - 모든 케이스에 대해 참임을 증명
∴(P1 ∨P2 ∨ Pn) → q

 

 

1-6. proof of equivalence

(p → q) ∧ (q → p)
∴ p ≡ q

 

 

1-7. extence proof

P(c)가 True → ∃xP(x)는 True

전체중 하나의 케이스가 True라면, '전체에서 어떤 경우가 참이다' 는 True