1.15 NAND 게이트와 NOR 게이트의 기능적 완전성 증명

1. 기능적 완전성의 정의

불 연산자의 집합 $S$ 가 기능적으로 완전(Functionally Complete)하다 함은, 임의의 불 함수 $f: \mathbb{B}^n \rightarrow \mathbb{B}$ 가 $S$ 에 속하는 연산자의 유한 조합으로 표현 가능하다는 것을 의미한다. 집합 $\{\wedge, \vee, \neg\}$ 가 기능적으로 완전하다는 것은 이미 확인하였다. 따라서 어떤 연산자 집합 $S$ 가 기능적으로 완전함을 증명하려면, $S$ 의 연산자만으로 $\wedge$ , $\vee$ , $\neg$ 를 모두 구현할 수 있음을 보이면 충분하다.

단일 연산자만으로 기능적 완전성을 달성하는 연산자를 세퍼 스트로크(Sheffer Stroke) 또는 보편 게이트(Universal Gate)라 한다. NAND와 NOR은 이 성질을 갖는 유일한 두 개의 2-입력 불 연산자이다.

2. NAND 연산의 정의

NAND(Not AND) 연산은 논리곱의 부정이다. 두 불 변수 $p$ , $q$ 에 대해:

$p \uparrow q = \overline{p \cdot q} = \neg(p \wedge q)$

기호 $\uparrow$ 는 셰퍼 스트로크(Sheffer Stroke)로 불리며, 헨리 셰퍼(Henry M. Sheffer)가 1913년 “A Set of Five Independent Postulates for Boolean Algebras, with Application to Logical Constants“에서 이 연산의 기능적 완전성을 증명하였다.

NAND의 진리표:

$p$	$q$	$p \uparrow q$
0	0	1
0	1	1
1	0	1
1	1	0

NAND 게이트의 기능적 완전성 증명

$\{\text{NAND}\}$ 가 기능적으로 완전함을 증명하려면, NAND 연산만으로 NOT, AND, OR를 모두 구현할 수 있음을 보이면 된다.

NOT의 구현

부정 $\neg p$ 는 NAND의 두 입력에 동일한 값을 인가하여 구현한다:

$p \uparrow p = \overline{p \cdot p} = \overline{p} = \neg p$

검증:

$p = 0$ : $0 \uparrow 0 = \overline{0 \cdot 0} = \overline{0} = 1 = \neg 0$ ✓
$p = 1$ : $1 \uparrow 1 = \overline{1 \cdot 1} = \overline{1} = 0 = \neg 1$ ✓

2.1 AND의 구현

논리곱 $p \wedge q$ 는 NAND 출력을 다시 부정하여 구현한다. 이미 NOT이 NAND로 구현 가능함을 보였으므로:

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

검증: NAND의 출력 $p \uparrow q = \overline{p \cdot q}$ 에 대해, $(p \uparrow q) \uparrow (p \uparrow q) = \overline{\overline{p \cdot q}} = p \cdot q$ ✓

OR의 구현

논리합 $p \vee q$ 는 드모르간 법칙을 통해 NAND로 구현한다. 드모르간 제2법칙의 역에 의해:

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

검증:

$p$	$q$	$p \uparrow p = \neg p$	$q \uparrow q = \neg q$	$(\neg p) \uparrow (\neg q) = \overline{\neg p \cdot \neg q}$	$p \vee q$
0	0	1	1	0	0
0	1	1	0	1	1
1	0	0	1	1	1
1	1	0	0	1	1

모든 행에서 결과가 $p \vee q$ 와 일치한다. ✓

2.2 증명의 완결

NOT, AND, OR이 모두 NAND만으로 구현 가능하고, $\{\text{NOT}, \text{AND}, \text{OR}\}$ 가 기능적으로 완전하므로, $\{\text{NAND}\}$ 도 기능적으로 완전하다. $\blacksquare$

3. NOR 연산의 정의

NOR(Not OR) 연산은 논리합의 부정이다. 두 불 변수 $p$ , $q$ 에 대해:

$p \downarrow q = \overline{p + q} = \neg(p \vee q)$

기호 $\downarrow$ 는 퍼스 화살표(Peirce Arrow)로 불리며, 찰스 샌더스 퍼스(Charles Sanders Peirce)에 의해 연구되었다.

NOR의 진리표:

$p$	$q$	$p \downarrow q$
0	0	1
0	1	0
1	0	0
1	1	0

NOR 게이트의 기능적 완전성 증명

NOT의 구현

$p \downarrow p = \overline{p + p} = \overline{p} = \neg p$

3.1 OR의 구현

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

AND의 구현

드모르간 제1법칙의 역에 의해:

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

검증:

$p$	$q$	$p \downarrow p = \neg p$	$q \downarrow q = \neg q$	$(\neg p) \downarrow (\neg q) = \overline{\neg p + \neg q}$	$p \wedge q$
0	0	1	1	0	0
0	1	1	0	0	0
1	0	0	1	0	0
1	1	0	0	1	1

모든 행에서 결과가 $p \wedge q$ 와 일치한다. ✓

NOT, OR, AND가 모두 NOR만으로 구현 가능하므로, $\{\text{NOR}\}$ 는 기능적으로 완전하다. $\blacksquare$

4. NAND와 NOR의 유일성

2-입력 불 함수는 $2^{2^2} = 16$ 개가 존재한다. 이 16개의 함수 중 단독으로 기능적 완전성을 달성하는 것은 NAND와 NOR 두 가지뿐이다.

이를 확인하기 위해, 포스트의 기능적 완전성 정리(Post’s Functional Completeness Theorem)를 참조한다. 포스트(Emil Post)는 1941년 “The Two-Valued Iterative Systems of Mathematical Logic“에서 불 함수의 집합이 기능적으로 완전하기 위한 필요충분조건을 확립하였다.

포스트의 정리에 따르면, 불 함수의 집합 $S$ 가 기능적으로 완전하려면, $S$ 가 다음 다섯 가지 폐쇄 클래스(Closed Class) 중 어느 것에도 완전히 포함되지 않아야 한다:

$T_0$ : 0-보존 함수 ( $f(0, 0, \ldots, 0) = 0$ )
$T_1$ : 1-보존 함수 ( $f(1, 1, \ldots, 1) = 1$ )
$M$ : 단조 함수 (입력이 증가하면 출력이 감소하지 않음)
$S$ : 자기 쌍대 함수 ( $f(\overline{x_1}, \ldots, \overline{x_n}) = \overline{f(x_1, \ldots, x_n)}$ )
$L$ : 선형 함수 ( $f = a_0 \oplus a_1 x_1 \oplus \cdots \oplus a_n x_n$ )

NAND의 경우:

$\text{NAND}(0,0) = 1 \neq 0$ → $T_0$ 에 속하지 않음
$\text{NAND}(1,1) = 0 \neq 1$ → $T_1$ 에 속하지 않음
$\text{NAND}(0,1) = 1 > \text{NAND}(1,1) = 0$ 이므로 단조가 아님 → $M$ 에 속하지 않음
자기 쌍대 확인: $\text{NAND}(\overline{0},\overline{0}) = \text{NAND}(1,1) = 0$ , $\overline{\text{NAND}(0,0)} = \overline{1} = 0$ . $\text{NAND}(\overline{0},\overline{1}) = \text{NAND}(1,0) = 1$ , $\overline{\text{NAND}(0,1)} = \overline{1} = 0$ . $1 \neq 0$ → $S$ 에 속하지 않음
선형 확인: NAND는 $\overline{pq} = 1 \oplus pq = 1 \oplus p \oplus q \oplus p \oplus pq$ 로 XOR의 선형 조합으로 표현되지 않음 → $L$ 에 속하지 않음

다섯 클래스 어디에도 속하지 않으므로, $\{\text{NAND}\}$ 는 기능적으로 완전하다. NOR에 대해서도 동일한 분석이 성립한다.

5. 실용적 의의

NAND와 NOR 게이트의 기능적 완전성은 디지털 회로 설계에서 지대한 실용적 의의를 갖는다.

5.1 제조 공정의 단순화

단일 유형의 게이트만으로 모든 논리 함수를 구현할 수 있으므로, 집적 회로의 제조 공정에서 하나의 기본 셀(Standard Cell)만을 대량 생산하여 다양한 논리 회로를 구성할 수 있다. 이는 제조 비용과 복잡도를 현저히 절감한다.

5.2 CMOS 기술과의 자연적 부합

CMOS 기술에서 기본 게이트 구조는 반전(Inverting) 출력을 자연스럽게 생성한다. NAND와 NOR은 반전 게이트이므로 CMOS의 기본 구조와 직접 대응하며, AND나 OR보다 적은 트랜지스터로 구현 가능하다. 2-입력 CMOS NAND 게이트는 4개의 트랜지스터를 요구하는 반면, 2-입력 AND 게이트는 NAND + 인버터로 6개의 트랜지스터를 요구한다.

5.3 게이트 수의 최소화

실제 회로 설계에서는 NAND-NAND 또는 NOR-NOR 네트워크를 사용하여 논리 함수를 구현하는 것이 일반적이다. 논리합 정규형(SOP)은 AND-OR 네트워크로 구현되는데, 이를 이중 부정하면 NAND-NAND 네트워크로 직접 변환된다:

$f = \sum m_i = \overline{\overline{\sum m_i}} = \overline{\prod \overline{m_i}}$

이는 2단(Two-Level) NAND-NAND 회로에 해당하며, 최소 게이트 지연으로 임의의 불 함수를 구현한다.

NAND와 NOR의 쌍대적 대칭

NAND와 NOR은 불 대수의 쌍대 원리(Duality Principle) 하에서 완전히 대칭적이다. NAND에 관한 모든 구현은 $\wedge$ 와 $\vee$ 를 교환하고 0과 1을 교환함으로써 NOR에 관한 대응 구현으로 변환된다. 이 쌍대성은 두 게이트가 기능적으로 동등한 보편적 구성 능력을 가짐을 보장한다.

NAND와 NOR 게이트의 기능적 완전성은 단일 유형의 물리적 소자만으로 임의의 계산을 수행할 수 있음을 의미하며, 이는 디지털 컴퓨터의 설계에서 물리적 단순성과 논리적 보편성의 양립이 가능함을 보증하는 근본적 정리이다.