[이산수학] 논리적 동치

1. 논리적 동치란?

 논리적 동치란 두 개의 논리식이 논리적으로 동일하다는 의미이다. 우리는 논리적 동치를 활용하여 다양한 논리 규칙들을 증명할 수 있다. 

예를 들어 p,q에 대하여 p↔q가 항진명제라면 p와q는 논리적 동치이다.

2. 드모르간 법칙

논리학과 불대수(Boole algebra)에서 사용되는 중요한 법칙 중 하나로, 이 법칙을 통해 논리식을 단순화하거나 변환하는 데 사용할 수 있다.

첫 번째 드모르간 법칙 (De Morgan's First Law)

• ¬(A ∧ B) = ¬A ∨ ¬B
• 즉, 두 개의 조건 A와 B가 모두 거짓이 아닌 경우, 그 논리 부정(Not)은 A의 부정 또는 B의 부정과 동일하다.

두 번째 드모르간 법칙 (De Morgan's Second Law):

• ¬(A ∨ B) = ¬A ∧ ¬B
• 즉, 두 개의 조건 A와 B 중 적어도 하나가 거짓인 경우, 그 논리 부정은 A의 부정과 B의 부정이 동일하다.

3. 다양한 논리적 동치 법칙

1. 항등법칙 (Identity Law):
   • 기호: A ∧ T = A, A ∨ F = A
   • 이름: AND 게이트의 입력으로 1을 사용하거나 OR 게이트의 입력으로 0을 사용할 때, 결과는 항상 해당 입력과 동일하다.
2. 지배법칙 (Domination Law):
   • 기호: A ∧ F = F, A ∨ T = T
   • 이름: AND 게이트의 입력으로 0을 사용하거나 OR 게이트의 입력으로 1을 사용할 때, 결과는 항상 0 또는 1이다.
3. 등가법칙 (Idempotent Law):
   • 기호: A ∧ A = A, A ∨ A = A
   • 이름: 같은 조건 A를 두 번 AND 또는 OR 연산하더라도 결과는 항상 A이다.
4. 교환법칙 (Commutative Law):
   • 기호: A ∧ B = B ∧ A, A ∨ B = B ∨ A
   • 이름: AND와 OR 연산에서 입력 순서를 변경해도 결과는 같다.
5. 결합법칙 (Associative Law):
   • 기호: (A ∧ B) ∧ C = A ∧ (B ∧ C), (A ∨ B) ∨ C = A ∨ (B ∨ C)
   • 이름: 연속적인 AND 또는 OR 연산에서 괄호의 위치를 변경해도 결과는 같다.
6. 분배법칙 (Distributive Law):
   • 기호: A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C), A ∨ (B ∧ C) = (A ∨ B) ∧ (A ∨ C)
   • 이름: AND와 OR 연산 사이에 배분 법칙을 적용하면 논리식을 단순화할 수 있다.
     
7. 등멱 법칙 (Identity Law):
   • 기호: A ∧ T = A, A ∨ F = A
   • 이름: AND 게이트의 입력으로 1을 사용하거나 OR 게이트의 입력으로 0을 사용할 때, 결과는 항상 해당 입력과 동일합니다.
     이 법칙은 논리식의 항등원을 나타내기도 한다.
8. 이중 부정 법칙 (Double Negation Law):
   • 기호: ¬(¬A) = A
   • 이름: 어떤 조건 A에 대한 부정을 두 번 적용하면 원래의 조건 A와 동일하다. 즉, 부정을 두 번 적용하면 원래의 상태로 돌아온다.

4. 조건문을 포함한 논리적 동치

2023.10.09 - [코딩/이산수학] - [이산수학] 조건문을 포함한 논리적 동치

[이산수학] 조건문을 포함한 논리적 동치