[ 이산수학 ] 6. 명제의 동치

항진 명제와 모순 명제

항진 명제는 합성명제에서 명제를 구성하는 단순명제의 진리값에 관계없이 항상 참인 명제를 의미하며, 모순 명제는 단순명제의 진리값에 관계 없이 항상 거짓인 명제를 의미한다. 참고로 항진명제도 아니고 모순명제도 아닌 경우네는 불확정ㅁㅇ제라고도 한다. 여기서 약자를 사용하여 항진명제를 t, 모순명제는 c라고도 표시한다.

 

논리적 동치

두 복합명제 p,q에 대하여 가능한 모든 경우에 대하여 같은 진리값을 가지면 p, q는 논리적 동치라고 한다.

즉, p↔q가 항진명제이면 p,q는 논리적 동치이며 p≡q라고 표현한다. 이 때, ≡는 논리연산자가 아닌 논리적 동치를 ㅛ현하는 기호이며, ⇔를 사용하기도 한다.

 

조건-논리합 동치

: p→q는 ~p∨q와 논리적 동치이다. 이것을 조건-논리합 동치라고 부른다.

 

드 모르간 법칙

:드 모르간 법칙이란 부정에 관한 것으로 ∧의 부정은 ∨가 되며, ∨의 부정은 ∧이다.

 

교환법칙

p∨q ⇔ q∨p

p∧q ⇔ q∧p

 

분배법칙

p∧(q∨r) ≡ (p∧q) ∨ (p∧r)

p∨(q∧r)≡(p∨q)∧(p∨r)

 

결합 법칙

(p∧q)∧r≡p∧(q∧r)

(p∨q)∨r≡p∨(q∨r)

 

항등법칙

p∧t≡p

p∨c≡p

 

지배법칙

p∧c≡c

p∨t≡t

 

이중 부정 법칙

~(~p) ≡ p

 

흡수법칙

p∧(p∨q)≡p

p∨(p∧q)≡p

 

부정법칙

p∧~p≡c

p∨~p≡t

 

여기서 t는 항진명제, c는 모순명제를 의미한다.

※드 모르간 법칙의 일반화

드 모르간 법칙은 아래와 같이 ∧와 ∨를 사용하여 표시할 수 있다.

연역적 추론

위에서의 증명된 동치를 이용하면 새로운 명제를 만들거나 동치인지 진리표를 쓰지 않고도 확인 수 있다. 이와 같은 증명법을 연역적 추론이라고 한다.