[이산수학] 중요한 논리적 동치 (Key Logical Equivalences)

[Discrete Mathematics] p.32-35

 

https://midoriprogramming.tistory.com/11

[이산수학] 드 모르간 법칙 (De Morgan's Law)

 

지난 시간에 드 모르간 법칙에 대해서 알아봤다.

 

이번에는 중요한 논리적 동치에 대해서 알아보겠다.

 

 

 

 

○ 항등 법칙 (Identity Laws)

여기서 T는 항상 참인 복합명제, F는 항상 거짓인 복합명제를 나타낸다.

 

어떤 명제 p를 항상 참인 T와 논리곱 연산을 할 경우 T는 이미 참이므로 p 값에 의해 결과가 결정된다.

또한 거짓인 명제 F와 논리합 연산을 할 경우 F는 이미 거짓이므로 이 역시 p 값에 의해 결과가 결정된다.

 

 

 

○ 지배 법칙 (Domination Laws)

 

 

어떤 명제 p를 항상 참인 T와 논리합 연산을 할 경우 T가 이미 참으로 p의 값과 상관없이 항상 참이 된다.

또한 거짓인 명제 F와 논리곱 연산을 할 경우 F가 이미 거짓으로 p의 값과 상관없이 항상 거짓이 된다.

 

 

 

 

○ 등멱 법칙 (Idempotent Laws)

 

 

어떤 명제 p를 자기 자신과 논리합, 논리곱 연산을 수행할 경우 자기 자신이 나온다.

 

 

 

○ 이중 부정 법칙 (Double Negation Law)

 

어떤 명제를 두 번 부정하면 다시 자기 자신이 된다.

 

 

 

 

○ 부정 법칙 (Negation Laws)

 

 

어떤 명제를 명제의 부정과 논리합 연산할 경우 둘 중 하나는 반드시 T이고 나머지는 반드시 F이므로, 항상 참이다.

또한 반대의 경우에는 T와 F의 논리곱 연산이므로 반드시 거짓이다.

 

 

 

 

 

○ 교환 법칙 (Commutative Laws)

 

논리곱과 논리합의 앞, 뒤 명제의 순서를 바꿔도 무방하다

 

 

 

 

○ 결합 법칙 (Associative Laws)

 

같은 논리합 연산자, 논리곱 연산자를 가졌다면 계산 순서를 바꿔도 무방하다.

 

 

 

 

○ 분배 법칙 (Distributive Laws)

 

사실 논리합 연산자를 수학에서의 +, 논리곱 연산자를 x으로 생각하면 사칙연산의 분배법칙과 동일하다.

 

 

 

 

○ 흡수 법칙 (Absorption Laws)

 

 

흡수 법칙의 경우 연산을 통해서 증명하기는 어렵고 다이아그램을 통해 이해하는 편이 좋다.

 

p와 q가 있고 p논리곱q는 p와 q의 교집합으로 생각할 수 있다.

이 교집합과 p의 합집합은 결국 p 자기 자신이므로 위와 같은 흡수 법칙이 성립한다.

 

다른 경우에 대해서도 똑같은 방식으로 증명할 수 있다.

 

 

 

 

9가지의 법칙에 대해서 봤다.

마지막 흡수법칙을 제외하고는 특별히 외우지 않아도 자명한 이치라 한번씩 생각해보면 이해할 수 있을거라고 생각한다.