드모르간의 법칙

드모르간의 법칙은 논리 연산(logical operation)과 집합 연산(set operation)에서
'부정(¬ 또는 complement)'이 논리곱(∧)과 논리합(∨) 또는 교집합(∩)과 합집합(∪)에 어떻게 분배되는지를 보여주는 기본적인 규칙이다.

이 법칙은 19세기 영국의 수학자 오거스터스 드모르간(Augustus De Morgan)이 제시했으며,
논리적 사고를 수학적으로 체계화하는 데 중요한 기여를 했다.

---

드모르간의 법칙 – 논리학적 표현

어떤 두 명제가 AAA와 BBB가 있을 때, 드모르간의 법칙은 다음과 같이 표현된다.

¬(A∧B)=(¬A)∨(¬B)
¬(A∨B)=(¬A)∧(¬B)

즉,

• “A와 B가 모두 참이 아니다”는 “A가 거짓이거나 B가 거짓이다”와 같다.
• “A 또는 B가 참이다”의 부정은 “A도 거짓이고 B도 거짓이다”와 같다.

---

진리표로 확인하기

A	B	A ∧ B	¬(A ∧ B)	¬A	¬B	¬A ∨ ¬B
T	T	T	F	F	F	F
T	F	F	T	F	T	T
F	T	F	T	T	F	T
F	F	F	T	T	T	T

→ 두 열 ¬(A ∧ B)와 ¬A ∨ ¬B가 완전히 일치함을 확인할 수 있다.
같은 방식으로 두 번째 식도 검증할 수 있다.

---

집합론에서의 드모르간의 법칙

논리 연산은 집합 연산과 1대1 대응 관계를 가진다.

논리학	집합론
∧ (AND)	∩ (교집합)
∨ (OR)	∪ (합집합)
¬ (NOT)	‘여집합(complement)’

따라서 드모르간의 법칙은 집합에서도 다음과 같이 성립한다.

(A∩B)′=A′∪B′
(A∪B)′=A′∩B′

즉,

• "A와 B의 교집합의 여집합"은 "A의 여집합과 B의 여집합의 합집합"이다.
• "A와 B의 합집합의 여집합”은 “A의 여집합과 B의 여집합의 교집합"이다.

---

시각적 이해 — 벤 다이어그램

드모르간의 법칙은 벤 다이어그램으로 표현하면 매우 직관적이다.

• (A∩B)′: A와 B가 겹치는 영역 외의 부분 전체
• A′∪B′: A가 아닌 부분 또는 B가 아닌 부분 전체

→ 두 영역은 완전히 동일하다.

이처럼 부정은 교집합을 합집합으로, 합집합을 교집합으로 바꾸면서 적용된다는 점이 핵심이다.

---

응용 예시

(1) 논리 회로 설계

디지털 논리회로에서 AND, OR, NOT 게이트의 관계를 변환할 때 드모르간의 법칙은 필수적이다.
예를 들어,

¬(A∧B)=¬A∨¬B

는 회로 설계 시 NAND 게이트 ↔ OR 게이트 + NOT의 변환 관계를 나타낸다.
이는 회로 단순화, 최소화 과정에서 매우 중요하다.

(2) 프로그래밍 조건문

프로그래밍에서도 조건식 최적화에 자주 활용된다.

 

# 예시
not (A and B)  ==  (not A) or (not B)

이런 변환을 통해 코드의 논리를 더 명확하게 만들 수 있다.

(3) 집합의 확률 계산

확률론에서 사건의 여집합을 계산할 때도 적용된다.

P((A∪B)′)=1−P(A∪B)=1−[P(A)+P(B)−P(A∩B)]

이때 드모르간의 법칙을 이용하면 복잡한 확률식을 더 간단히 정리할 수 있다.

---

요약

구분	수식	의미
논리형식 1	¬(A ∧ B) = ¬A ∨ ¬B	“모두 참이 아님” ↔ “하나라도 거짓”
논리형식 2	¬(A ∨ B) = ¬A ∧ ¬B	“하나라도 참”의 부정 ↔ “모두 거짓”
집합형식 1	(A ∩ B)' = A' ∪ B'	교집합의 여집합 ↔ 여집합들의 합집합
집합형식 2	(A ∪ B)' = A' ∩ B'	합집합의 여집합 ↔ 여집합들의 교집합

 

드모르간의 법칙은 논리적 사고의 가장 기본적인 원리이면서,
논리회로, 알고리즘, 데이터베이스 질의, 수학 증명 등
수많은 분야에서 응용되는 보편적 논리 변환 규칙이다.

이 법칙을 이해하고 활용할 수 있다는 것은,
결국 복잡한 논리 구조를 단순하고 명확하게 재구성할 수 있는 사고력을 갖추었다는 의미이기도 하다.