• Propositional Logic(명제 논리) Proposition(명제): 참 또는 거짓을 가지는 문장

    NOT: ㄱ AND: V OR: Λ

    • 용어 implication / conditional statement (조건문): p→q, p(sufficient) q(necessary) biconditional: p↔q converse(역): q→p inverse(이): ~p→~q contrapositive(대우): ~q→~p

      consistent(일관): 모든 명제가 동시에 참이 될 수 있다 equivalent(동치): 두 명제의 진리표가 항상 동일 / p↔q is tautology tautology(항진): 항상 true contradiction(모순): 항상 false contigency(일부진명제): 항진도 모순도 아님 satisfiable: 참이 될 수 있다

    • 계산 법칙

      De Morgan ㄱ(pVq) = ㄱp Λ ㄱq
      Identity Law p Λ T = p, p V F = p
      domination law p V T = T, p Λ F = F
      idempotent law p Λ p = p, p V p = p
      Negation law p V ㄱp = T, p Λ ㄱp = F
      double nagation ㄱ(ㄱp) = p
      commutative law p V q = q V p, p Λ q = q Λ p
      associative law (pΛq)Λr = pΛ(qΛr), (pVq)Vr = pV(qVr)
      distribute law pV(qΛr) = (pVq)Λ(pVr), pΛ(qVr) = (pVq)Λ(pVr)
      absorption law pV(pΛq) = p, pΛ(pVq) = p
      implication p→q = ㄱp V q

    • DNF(Disjunction Normal Form, 논리합 정규형): Sum of product Truth table의 모든 T에 해당하는 Minterm 합

    • CNF(Conjunction Normal Form, 논리곱 정규형): Product of sum Truth table의 모든 F에 해당하는 Maxterm 곱

  • Predicate Logic(술어 논리) Propositional function P(x): x에 대한 명제 P를 나타낸 것

    • P(x) is “Proposition” when

      • variables can be replaced with values from domain
      • (or) variables are bounded by quantifier

    • Quantifier

      • Universal quantifier: ∀x ∀xP(x) = P(x1) Λ P(x2) Λ …
      • Existential quantifier: ∃x ∃xP(x) = P(x1) V P(x2) V …

      ㄱ(∀xP(x)) = ∃x(ㄱP(x)) ㄱ(∃xP(x)) = ∀x(ㄱP(x))

    • Argument form premises p1,p2, …, conclusion q ↔ (p1 ∧ p2 ∧ ….) → q is tautology

      • inference rule

        p→q p→q p→q p V q p ㄱp V q
        p ㄱq q→r ㄱp p p Λ q q p V r
        ∴q ∴ㄱp ∴p→r ∴q ∴p V q ∴p, ∴q ∴p Λ q ∴q V r
        Modus Ponens Modus tollens Hypothetical syllogism Disjuctive
        Syllogism Addition Simplification conjuction Resolution
        전건 긍정 후건 부정 가언적
        삼단 논법 선언적
        삼단 논법 consensus thm유사함
      ∀xP(x) any c, P(c) ∃xP(x) some c, P(c)
      any c, P(c) ∀xP(x) some c, P(c) ∃xP(x)
      Universal
      Instantiation Universal
      Generalization Existential
      Instantiation Existential
      Generalization

    • Proofs

      • terminology
        • theorem use definition, other theorem, Axiom(공리), rules of inference
        • lemma (보조 정리)
        • corollary(따름 정리)
        • conjecture(가설)
      • Methods
        • direct proof assume p is true, show q
        • contrapositive assume ㄱq, show p
        • biconditional show p→q and q→p
        • proof by cases: (p1 V p2 V … ) →q ≡ (p1 V q) ∧(p1 V q) ∧…. therefore proof pi→q for all cases.
        • Existence proofs find some c, P(c) → EG → ∃xP(x)
        • counterexamples find some c, ㄱP(c) since ∃xㄱP(x) ≡ ㄱ(∀xP(x)), ∀xP(x) is false
        • Uniqueness proofs Existence: show one example exists Uniqueness: assume y≠x, show P(y) don’t hold / show y=x