[Discrete Mathematics] 수학적 논리(Mathematical Logic)_2

코로나19로 유명한 벚꽃 거리들은 제한되었네요ㅠㅠ

(술집에는 사람들이 왜 이렇게 많은지...)

아무튼 서로 조심해서 더 이상 확산되지 않고

빠르게 마무리되었으면 하는 바람과 함께 학습을 시작하겠습니다

지난 시간에 명제 논리와 논리 연산자에 대해 알아보았고

이번 시간은 이어서 논리적 동치부터 학습을 진행하겠습니다

[정의] 논리적 동치(logically equivalent)

쌍방 조건 p≡q가 항진 명제이면, 합성 명제 p,q는 논리적 동치라 한다

논리적 동치의 정의에서 항진 명제(tautology)가 등장하네요

항진 명제는 합성 명제 내의 단순 명제들의 진리값에 관계없이

그 합성 명제의 진리값이 언제나 참인 명제입니다

추가로 모순 명제(contradiction)은 합성 명제의 진리값이

언제나 거짓인 명제를 말하고

항진도 모순도 아닌 명제를 사건 명제(contingency)라고 합니다

아래의 표는 중요한 논리적 동치들인데

이것들을 이용하여 더 복잡한 논리적 동치를 찾아낼 수도 있습니다

논리적 동치	법칙
p∧T≡p p∨F≡p	항등 법칙(identity laws)
p∨T≡T p∧F≡F	지배 법칙(domination laws)
p∨p≡p p∧p≡p	멱등 법칙(idempotent laws)
~(~p)≡p	이중 부정 법칙(double negation laws)
p∨q≡q∨p p∧q≡q∧p	교환 법칙(commutative laws)
(p∨q)∨r≡p∨(q∨r) (p∧q)∧r≡p∧(q∧r)	결합 법칙(associative laws)
p∨(q∧r)≡(p∨q)∧(p∨r) p∧(q∨r)≡(p∧q)∨(p∧r)	분배 법칙(distributive laws)
~(p∧q)≡~p∨~q ~(p∨q)≡~p∧~q	드 모르간의 법칙(De Morgans laws)
(p→q)≡(~q→~p)	대우

[정의] 논리적 함축(logically implication)

합성 명제 P, Q가 주어졌을 때, 조건적 함축 P→Q가 항진 명제이면, P는 논리적으로 Q를 함축한다고 하고, P⇒Q라고 표기한다.

아래는 논리적 함축을 나열한 것입니다

논리적 함축	논법
p⇒(p∨q)	추가(addition)
(p∧q)⇒p	단순화(simplification)
(p→F)⇒~p	모순(absurdity)
[p∧(p→q)]⇒q	긍정 논법(modus ponens)
[(p→q)∧~q]⇒~p	부정 논법(modus tollens)
[(p∨q)∧~p]⇒q	논리적 삼단 논법(disjunctive syllogium)
p⇒[q→(p∧q)]
[(p↔q)∧(q↔r)]⇒(p↔r) [(p→q)∧(q→r)]⇒(p→r)	이행(transitivity)
(p→q)⇒[(p∨r)→(q∨r)] (p→q)⇒[(p∧r)→(q∧r)] (p→q)⇒[(p→r)→(q→r)]

이것으로 오늘의 학습을 마치고

다음에 증명부터 학습해보도록 하겠습니다

그럼 이만-_-