[이산수학] KOCW 가천대학교 김철연 교수님 강의 2주차 정리

Quantifiers

• Predicates에 대한 T/F를 알 수 있음
• All → A 거꾸로 / E 뒤집어서
• Universal quantification: VxP(x) → 모든 x에 대해서 참인가?
• Existential quantification : ExP(x) → 어떤 x에 대해서 참인가?
• quantifier가 다른 모든 논리연산자보다 우선순위가 높다

Valid Arguments

• 주어진 사실로 새로운 사실을 깨닫는 것
• Premises (p1, p2, …, pn-1) 전제
• Conclusion (pn) 결론
• 모든 전제가 사실일 때 결론도 사실이다

Rules of Inference

• Inference : 이미 알고 있는 것으로 새로운 사실을 찾는 것
• p + p→q = q
• ㄱq + p→q = ㄱp
• p→q + →r = p→r
• pVq + ㄱp = q
• p = pVq
• p^q = p
• p + q = p^q
• pVq + ㄱpVr = qVr

Normal Forms

• and, or, not 만 씀
• product(and) sum(or)
• DNF(Disjunctive Normal Form) : and의 or (p→q)^ㄱq = (ㄱp^ㄱq) V (q^ㄱq)
• CNF(Conjunctive Normal Form) : or의 and (p→q)^ㄱq = (ㄱpVq)^ ㄱq
• Minterm : 다 F고 딱 하나만 T가 나오게 함
• Maxterm : 다 T가 나오게 함
• Principle Disjunctive Normal Form → 딱 하나만 T가 나오게 해서 or
• Principle Conjunctive Normal Form → 내가 원하는 위치들만 다 T가 나오게 해서 and
• 모든 설계를 다 할 수 있지만 and or not의 개수가 많아짐 (→ 다른 과목에서 이걸 줄이는 방법을 공부함)