1.12 드모르간 법칙과 논리 동치 변환 규칙

1. 드모르간 법칙의 역사적 배경

오거스터스 드모르간(Augustus De Morgan, 1806–1871)은 영국의 수학자이자 논리학자로서, 유니버시티 칼리지 런던(University College London)의 수학 교수였다. 드모르간은 조지 불과 동시대에 논리학의 형식화에 기여하였으며, 특히 관계 논리학(Logic of Relations)의 선구적 연구로 알려져 있다.

드모르간 법칙(De Morgan’s Laws)은 1847년 드모르간이 “Formal Logic, or the Calculus of Inference, Necessary and Probable“에서 공식적으로 기술한 논리적 동치 관계이다. 이 법칙은 논리곱과 논리합, 그리고 부정 사이의 근본적인 관계를 규정하며, 논리식의 변환과 단순화에서 핵심적 역할을 수행한다.

2. 드모르간 법칙의 정의

드모르간 법칙은 두 개의 상호 쌍대적(Dual) 논리적 동치로 구성된다.

2.1 제1법칙

$\neg(p \wedge q) = \neg p \vee \neg q$

논리곱의 부정은 각 피연산자의 부정에 대한 논리합과 동치이다. 자연 언어로 표현하면, “ $p$ 이고 $q$ 이다“의 부정은 “ $p$ 가 아니거나 $q$ 가 아니다“와 동치이다.

제2법칙

$\neg(p \vee q) = \neg p \wedge \neg q$

논리합의 부정은 각 피연산자의 부정에 대한 논리곱과 동치이다. “ $p$ 이거나 $q$ 이다“의 부정은 “ $p$ 가 아니고 $q$ 가 아니다“와 동치이다.

3. 진리표에 의한 증명

3.1 제1법칙의 증명

$p$	$q$	$p \wedge q$	$\neg(p \wedge q)$	$\neg p$	$\neg q$	$\neg p \vee \neg q$
0	0	0	1	1	1	1
0	1	0	1	1	0	1
1	0	0	1	0	1	1
1	1	1	0	0	0	0

$\neg(p \wedge q)$ 와 $\neg p \vee \neg q$ 의 열이 모든 행에서 일치하므로, 두 식은 논리적으로 동치이다.

3.2 제2법칙의 증명

$p$	$q$	$p \vee q$	$\neg(p \vee q)$	$\neg p$	$\neg q$	$\neg p \wedge \neg q$
0	0	0	1	1	1	1
0	1	1	0	1	0	0
1	0	1	0	0	1	0
1	1	1	0	0	0	0

마찬가지로, $\neg(p \vee q)$ 와 $\neg p \wedge \neg q$ 가 모든 행에서 일치한다.

4. 대수적 증명

불 대수의 공리로부터 드모르간 법칙을 대수적으로 증명할 수 있다. 제1법칙의 증명을 기술한다.

$\neg(p \wedge q) = \neg p \vee \neg q$ 를 증명하려면, $\neg p \vee \neg q$ 가 $p \wedge q$ 의 보원(Complement)임을 보이면 된다. 즉, 다음 두 조건을 만족함을 증명한다:

(조건 1): $(p \wedge q) \wedge (\neg p \vee \neg q) = 0$

$\begin{aligned} (p \wedge q) \wedge (\neg p \vee \neg q) &= ((p \wedge q) \wedge \neg p) \vee ((p \wedge q) \wedge \neg q) \\ &= (p \wedge \neg p \wedge q) \vee (p \wedge q \wedge \neg q) \\ &= (0 \wedge q) \vee (p \wedge 0) \\ &= 0 \vee 0 = 0 \end{aligned}$

(조건 2): $(p \wedge q) \vee (\neg p \vee \neg q) = 1$

$\begin{aligned} (p \wedge q) \vee \neg p \vee \neg q &= ((p \wedge q) \vee \neg p) \vee \neg q \\ &= ((p \vee \neg p) \wedge (q \vee \neg p)) \vee \neg q \\ &= (1 \wedge (q \vee \neg p)) \vee \neg q \\ &= (q \vee \neg p) \vee \neg q \\ &= \neg p \vee (q \vee \neg q) \\ &= \neg p \vee 1 = 1 \end{aligned}$

두 조건이 모두 만족되므로, 보원의 유일성에 의해 $\neg(p \wedge q) = \neg p \vee \neg q$ 이다.

5. 집합론적 해석

드모르간 법칙은 집합론에서 다음과 같이 해석된다:

$\overline{A \cap B} = \overline{A} \cup \overline{B}$
$\overline{A \cup B} = \overline{A} \cap \overline{B}$

교집합의 여집합은 여집합의 합집합이고, 합집합의 여집합은 여집합의 교집합이다.

6. 드모르간 법칙의 일반화

드모르간 법칙은 2개의 변수에서 임의의 유한 개의 변수로 일반화된다:

$\neg\left(\bigwedge_{i=1}^{n} p_i\right) = \bigvee_{i=1}^{n} \neg p_i$

$\neg\left(\bigvee_{i=1}^{n} p_i\right) = \bigwedge_{i=1}^{n} \neg p_i$

이 일반화는 수학적 귀납법(Mathematical Induction)에 의해 증명된다.

7. 논리 동치 변환 규칙의 체계

드모르간 법칙은 논리식 변환에 사용되는 다수의 논리 동치 규칙(Logical Equivalence Rules) 중 하나이다. 논리식의 변환과 단순화에 사용되는 주요 동치 규칙을 체계적으로 기술한다.

7.1 기본 동치 규칙

이중 부정(Double Negation):
$\neg(\neg p) = p$

멱등법칙(Idempotent Laws):
$p \wedge p = p, \quad p \vee p = p$

교환법칙(Commutative Laws):
$p \wedge q = q \wedge p, \quad p \vee q = q \vee p$

결합법칙(Associative Laws):
$(p \wedge q) \wedge r = p \wedge (q \wedge r), \quad (p \vee q) \vee r = p \vee (q \vee r)$

분배법칙(Distributive Laws):
$p \wedge (q \vee r) = (p \wedge q) \vee (p \wedge r)$
$p \vee (q \wedge r) = (p \vee q) \wedge (p \vee r)$

7.2 항등 및 지배 규칙

항등법칙(Identity Laws):
$p \wedge 1 = p, \quad p \vee 0 = p$

지배법칙(Domination Laws):
$p \wedge 0 = 0, \quad p \vee 1 = 1$

보원법칙(Complement Laws):
$p \wedge \neg p = 0, \quad p \vee \neg p = 1$

흡수법칙(Absorption Laws)

$p \wedge (p \vee q) = p$
$p \vee (p \wedge q) = p$

조건문 변환 규칙

조건문의 논리합 변환:
$p \rightarrow q = \neg p \vee q$

대우(Contrapositive):
$p \rightarrow q = \neg q \rightarrow \neg p$

쌍조건문 전개:
$p \leftrightarrow q = (p \rightarrow q) \wedge (q \rightarrow p) = (p \wedge q) \vee (\neg p \wedge \neg q)$

8. 논리식 단순화에의 응용

드모르간 법칙과 동치 변환 규칙을 활용한 논리식 단순화 과정을 예시한다.

예제 1: $\neg(\neg p \vee q)$ 를 단순화하라.

$\neg(\neg p \vee q) = \neg(\neg p) \wedge \neg q = p \wedge \neg q$

드모르간 제2법칙을 적용한 후, 이중 부정 법칙을 적용하였다.

예제 2: $(p \wedge q) \vee (p \wedge \neg q)$ 를 단순화하라.

$\begin{aligned} (p \wedge q) \vee (p \wedge \neg q) &= p \wedge (q \vee \neg q) \quad (\text{분배법칙 역적용}) \\ &= p \wedge 1 \quad (\text{보원법칙}) \\ &= p \quad (\text{항등법칙}) \end{aligned}$

예제 3: $\neg(p \rightarrow q)$ 를 단순화하라.

$\begin{aligned} \neg(p \rightarrow q) &= \neg(\neg p \vee q) \quad (\text{조건문 변환}) \\ &= \neg(\neg p) \wedge \neg q \quad (\text{드모르간 제2법칙}) \\ &= p \wedge \neg q \quad (\text{이중 부정}) \end{aligned}$

정규형 변환

논리 동치 변환 규칙은 임의의 논리식을 정규형(Normal Form)으로 변환하는 데 체계적으로 사용된다.

논리합 정규형(Disjunctive Normal Form, DNF)

논리합 정규형은 최소항(Minterm)의 논리합으로 이루어진 형태이다:

$(p_1 \wedge p_2 \wedge \cdots) \vee (q_1 \wedge q_2 \wedge \cdots) \vee \cdots$

8.1 논리곱 정규형(Conjunctive Normal Form, CNF)

논리곱 정규형은 최대항(Maxterm)의 논리곱으로 이루어진 형태이다:

$(p_1 \vee p_2 \vee \cdots) \wedge (q_1 \vee q_2 \vee \cdots) \wedge \cdots$

임의의 논리식을 DNF 또는 CNF로 변환하는 체계적 절차는 다음과 같다:

조건문과 쌍조건문을 $\wedge$ , $\vee$ , $\neg$ 로 변환한다.
드모르간 법칙과 이중 부정 법칙을 적용하여 부정을 원자 명제(Atomic Proposition)에만 적용되도록 한다(부정 정규형, Negation Normal Form).
분배법칙을 적용하여 DNF 또는 CNF를 생성한다.

이 변환 절차는 완전히 기계적이며, 각 단계에서 적용할 규칙이 명확히 결정된다.

디지털 논리 설계에서의 응용

드모르간 법칙은 디지털 논리 회로 설계에서 핵심적으로 활용된다.

NAND 게이트에 의한 임의 논리 함수의 구현: 드모르간 제1법칙에 의해:

$p \wedge q = \neg(\neg p \vee \neg q)$

이를 이중 부정하면:

$\neg(p \wedge q) = \neg p \vee \neg q$

이 관계를 통해 AND, OR, NOT 연산을 모두 NAND 연산만으로 구현할 수 있음이 도출된다.

NOR 게이트에 의한 임의 논리 함수의 구현: 드모르간 제2법칙에 의해 유사한 결과가 도출되며, NOR 연산만으로도 모든 논리 함수를 구현할 수 있다.

프로그래밍에서의 응용

드모르간 법칙은 프로그래밍에서 조건문의 변환과 최적화에 직접적으로 사용된다. 예를 들어:

if not (A and B) then ...

이는 드모르간 법칙에 의해 다음과 동치이다:

if (not A) or (not B) then ...

이러한 변환은 코드의 가독성 향상, 조건 분기의 최적화, 단락 평가(Short-Circuit Evaluation)의 활용 등에서 실용적으로 중요하다.

드모르간 법칙과 논리 동치 변환 규칙은 불 대수의 기본 공리로부터 도출되는 정리이며, 논리식의 변환, 단순화, 정규화를 위한 체계적 도구로서 논리학, 디지털 회로 설계, 프로그래밍, 인공지능의 전 영역에서 근본적인 역할을 수행한다.