🤣

[Discrete Mathematics] 1. Set and Logics

고교 과정과 안겹치는 내용 위주로 이산수학을 정리해보도록 하겠습니다.
성균관대학교 2021 여름학기 GEDB007_42 수업을 바탕으로 작성되었습니다.

Sets

은 고교 과정과 정확히 일치하므로 생략

Logics

Conditional Proposition

p → q 를 Conditional Proposition (조건명제) 라고 합니다. 이때 p를 Hypothesis (가정) q를 Conclustion(결론) 이라고 합니다.
∧(AND), ∨(OR), ~(NOT), → 등이 같은 조건식에 쓰여져 있을때, 연산 순위는 →가 가장 후순위입니다. 따라서, p or q → ~r 은 (p or q) → (~r) 과 동치입니다.
Converse(역), Contrapositive(대우)입니다.

Logically Equivalant

논리적 동치라고 하며 ≡라고 쓴다.

De Morgan's Law for Logic

집합의 드모르간 법칙이 명제에서도 비슷하게 성립하는데,
~(p∨q) ≡ ~p ∧ ~q 이고,
~(p∧q) ≡ ~p ∨ ~q 이다.
또한,
p→q ≡ ~p ∨ q 임도 알아두자.

Inference

Deductive Reasoning (연역 추론)

여러 Hypothesis들을 바탕으로 Conclusion을 만들어내는 것
p1,p2,p3...pnp_1, p_2, p_3...p_n등이 모두 참 → qq가 참 일때, 이를 Valid하다고 함.

Rules of Inference

Modus Ponens (전건 긍정)
pqp \rightarrow q 가 참이고, pp가 참이면, qq가 참
Modus Tollens (후건 부정)
pqp\rightarrow q가 참이고, ~qq가 참이면, ~pp가 참
Addition
pp가 참이면 pqp \vee q가 참
Simplication
pqp \wedge q가 참이면 pp가 참
Conjunction
pp, qq가 참이면, pqp \wedge q가 참
Hypothetical Syllogism (삼단논법)
pq,qqp\rightarrow q, q\rightarrow q가 참이면 prp\rightarrow r
Disjunctive Syllogism
pqp \vee q, p\sim p 가 참이면, qq가 참
레이텍 문법 귀찮군