[이산수학] Chapter 1. Logic and proofs

1. Propositions : 명제 

  - 만약 p, q가 명제라면, connective를 이용해 새로운 compound proposition을 만들 수 있다.

  (conjunction AND, inclusive disjunction OR, exclusive disjunction OR(XOR), negation, implication, double implication)

 

2. Conditional propositions(조건명제) and logical equivalence(동치)

 - conditional proposition : p->q "if p then q", "p only if q"

   p : 가정, 충분조건 / q : 결론, 필요조건

 

 - logically equivalent (converse(역), contrapositive(대우), double implication(p<->q), tautology(항진명제, 항상 참인 명제), contradict(모순 명제, 항상 거짓임))

 - De Morgan's law : 드모르간의 법칙

 

3. Quantifiers : 한정기호

 - propositional function P(x)는 변수 x를 포함하고 있는 명제임

 - Domain : x가 될 수 있는 범위, 정의역

 

 1) universal quantifier : 모든~

 2) existential quantifier : 어떤~

 3) de morgan's law의 일반화 : 모든~ 의 부정은 어떤, 어떤~의 부정은 모든

 

4. Nested Quantifier : 여러개의 quantifier의 곱

  ex) 모든 x에 대해 어떤 y가 참이다. 

 

 

5. Proofs

  1) Undefined terms : 무정의 술어, 구체적인 정의를 내리지 않고 그 성질을 공리로 규정하는 수학적 개념

     definition : 정의

     axiom : 공리, 증명없이 true로 인정되는 명제

     theorem : 정리, 논리적 단계에 의해 참임이 증명되는 명제

 

  2) proofs 

   - direct proof : p->q를 직접 증명

   - indirect proof 

     ⓐ contradiction 증명 (귀류법) : p->q를 증명하기 위해 p->q가 거짓이라고 가정하면 말이 안됨을 밝힘

     ⓑ contrapositive 증명 (대우 명제 증명)

     ⓒ 그 밖에 :

        proof by cases(exhaustive proof) : p1 v p2 v ... v pn -> p를 증명하기 위해 p1->q, p2->q...pn->q를 증명

        proof of equivalence : p<->q 증명하기 위해 p=>q. q=>p 각각을 증명

        existence proof : ∃x P(x) 를 증명하기 위해서는 그냥 저거 하나 만족하는 x 찾으면 됨

 

  3) Valid arguments 

   - Deductive reasoning : propositions의 sequence로부터 q라는 결론에 도달하기 까지의 과정 

   -