불 대수와 논리 회로

요약

참·거짓을 1·0으로 쓰면 논리식이 덧셈·곱셈 같은 계산이 되고, 그 식은 그대로 전자 회로(논리 게이트)로 만들 수 있다. 식을 간단히 하면 게이트 수가 줄어 회로가 작고 빨라진다. 놀랍게도 NAND 게이트 한 종류만으로 모든 회로를 만들 수 있다. 다만 불 대수에서는 1 + 1 = 1이라 보통 산술과 규칙이 다르다.

예시로 보기

한 자리 2진수 두 개를 더하는 회로(반가산기)를 만든다. 가능한 입력은 네 가지뿐이다.

\(a\)	\(b\)	합 \(s\)	올림 \(c\)
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

합의 열은 “둘 중 하나만 1”이므로 \(a \oplus b\), 올림의 열은 “둘 다 1”이므로 \(a \cdot b\)다. XOR 게이트 하나와 AND 게이트 하나로 끝난다. 반가산기에 아래 자리의 올림까지 받는 전가산기를 만들어 4개 이으면 4비트 덧셈기가 된다. CPU의 덧셈 회로가 이렇게 시작한다.

정의

불 대수는 값 \(\{0, 1\}\)과 세 연산으로 이루어진다¹.

불 합 \(a + b\) (OR): 하나라도 1이면 1. 그래서 \(1 + 1 = 1\)이다.
불 곱 \(a \cdot b\) (AND): 둘 다 1일 때만 1.
보수 \(\bar a\) (NOT): \(\bar 0 = 1\), \(\bar 1 = 0\).

입력 \(n\)개, 출력 하나인 함수 \(f: \{0,1\}^n \to \{0,1\}\)을 불 함수라 한다. 진리표의 \(2^n\)행마다 0이나 1을 고르므로 불 함수는 모두 \(2^{2^n}\)개다.

논리적 동치의 법칙이 그대로 불 대수의 법칙이다. \(\vee\)를 \(+\)로, \(\wedge\)를 \(\cdot\)로, \(\neg\)를 \(\bar{\ }\)로 바꿔 읽는다. 예: 드모르간 \(\overline{a \cdot b} = \bar a + \bar b\), 흡수 \(a + a b = a\). 보통 산술과 다른 법칙도 있다: \(a + a = a\), \(a + 1 = 1\), \(a + b c = (a + b)(a + c)\).

논리 게이트. 불 연산을 하는 전자 부품이다. AND, OR, NOT에 더해 NAND(\(\overline{ab}\)), NOR(\(\overline{a + b}\)), XOR(\(a \oplus b\))이 있다.

기능적 완전성

모든 불 함수는 AND, OR, NOT만으로 만들 수 있다. 나아가 NAND 하나만으로도 만들 수 있다¹.

증명

진리표가 있는 모든 불 함수는 DNF(곱들의 합)로 쓸 수 있다. DNF는 AND, OR, NOT만 쓴다.
NAND로 셋을 만든다. \(\bar a = \text{NAND}(a, a)\), \(\ ab = \overline{\text{NAND}(a, b)} = \text{NAND}(\text{NAND}(a,b), \text{NAND}(a,b))\), \(\ a + b = \text{NAND}(\bar a, \bar b)\)(드모르간). ∎

모형이 보장하는 것과 보장하지 않는 것. 이 모형(조합 회로)의 출력은 지금의 입력만으로 정해진다. 하지만 신호가 게이트를 지나는 데 걸리는 시간(전파 지연)은 다루지 않아서, 입력이 바뀌는 순간 출력이 잠깐 틀린 값을 낼 수 있다(글리치). 또 값을 기억하지 못한다. 기억하려면 출력을 입력으로 되돌린 순차 회로(플립플롭)가 필요하다².

예제

4비트 덧셈 추적. \(0101_2 + 0011_2\) (5 + 3)을 전가산기 네 개로 더한다. 전가산기는 합 \(s = a \oplus b \oplus c_{\text{in}}\), 올림 \(c_{\text{out}} = ab + c_{\text{in}}(a \oplus b)\)를 낸다.

flowchart LR
  CIN["c_in = 0"] --> FA0["전가산기 0: a0, b0"]
  FA0 -->|"올림 c1"| FA1["전가산기 1: a1, b1"]
  FA1 -->|"올림 c2"| FA2["전가산기 2: a2, b2"]
  FA2 -->|"올림 c3"| FA3["전가산기 3: a3, b3"]
  FA3 -->|"올림 c4"| OUT["맨 위 올림"]
  FA0 --> S0["s0"]
  FA1 --> S1["s1"]
  FA2 --> S2["s2"]
  FA3 --> S3["s3"]

전가산기마다 같은 자리의 \(a_i\), \(b_i\)와 바로 아래 자리에서 올라온 올림을 받는다. 올림이 그림의 왼쪽에서 오른쪽으로 한 칸씩 넘어가므로, 맨 위 자리의 합은 아래 세 칸이 끝나야 정해진다³.

자리	\(a\)	\(b\)	\(c_{\text{in}}\)	\(s\)	\(c_{\text{out}}\)
0 (1의 자리)	1	1	0	0	1
1	0	1	1	0	1
2	1	0	1	0	1
3	0	0	1	1	0

결과는 \(1000_2 = 8\)이다. 올림이 아래에서 위로 물결처럼 전해져 리플 캐리 가산기라 부른다. 자리가 \(n\)개면 최악의 경우 올림이 \(n\)단계를 지나가야 해서 느리다. 실제 CPU는 올림을 미리 계산하는 회로를 쓴다.

식 줄이기. \(ab + a\bar b = a(b + \bar b) = a \cdot 1 = a\). 게이트 네 개(AND 둘, NOT 하나, OR 하나)가 선 하나로 준다.

검증: 반가산기, 4비트 가산기로 0~15의 모든 쌍 256개 덧셈, 예제의 올림 비트, NAND로 NOT·AND·OR·XOR, 2입력 불 함수 16개, 불 대수 법칙, x & (x-1) — 05_boolean-algebra_verify.py

활용

하드웨어. CPU의 산술 논리 장치, 멀티플렉서, 주소 해독기가 모두 조합 회로다. 회로 설계 도구는 식을 줄여 게이트 수를 최소화한다.
비트마스크. 정수 하나의 비트들을 불 값 여러 개로 쓴다. 플래그 켜기 x | FLAG, 끄기 x & ~FLAG, 확인 x & FLAG. x & (x - 1)은 가장 낮은 1비트를 지워서, 0이 될 때까지 되풀이하면 1비트 개수를 센다.
XOR의 쓰임. 패리티(1의 개수가 홀수인지) 검사, 두 값의 비교, 간단한 암호(같은 키로 두 번 XOR하면 원래대로)에 쓴다.
알고리즘에서: 원소 \(n\)개의 부분집합이나 방문한 방 같은 상태를 수 하나의 비트로 다루는 방법은 비트 연산과 비트마스크에 있다. 미로 탈출은 함정에 들어갈 때마다 그 비트를 XOR로 뒤집어 들어간 횟수의 홀짝을 기억하고, 길이 뒤집혔는지는 양 끝 방의 켜짐을 XOR해서 정한다.

연결

선수: 논리적 동치와 정규형
같은 구조: 집합의 합·교·여집합과 불 대수의 \(+\), \(\cdot\), 보수는 법칙이 같다. 진법과 자릿수의 2진수가 회로의 입력이다.

과목별 관점

어셈블리어 (2-1학기). 불 연산을 프로세서가 비트에 하는 기본 동작으로 소개한다. 값은 참(T)과 거짓(F)으로 적고, 비트로는 1이 참, 0이 거짓이다. 연산은 NOT, AND, OR 셋이고 기호는 논리식의 것을 쓴다.

이 문서의 표기	논리식의 표기	읽기
\(\bar x\)	\(\neg X\)	NOT X
\(x \cdot y\)	\(X \wedge Y\)	X AND Y
\(x + y\)	\(X \vee Y\)	X OR Y

계산 순서. 괄호가 없으면 NOT을 가장 먼저, 그다음 AND, 마지막에 OR를 한다⁴.

식	순서
\(\neg X \vee Y\)	NOT 다음 OR
\(\neg (X \vee Y)\)	OR 다음 NOT
\(X \vee (Y \wedge Z)\)	AND 다음 OR

진리표. 불 함수는 불 값을 하나 이상 받아 불 값 하나를 내놓고, 진리표는 모든 입력과 그때의 출력을 적은 표다. 입력이 셋인 \((Y \wedge S) \vee (X \wedge \neg S)\)의 진리표는 다음과 같다.

\(X\)	\(Y\)	\(S\)	\(Y \wedge S\)	\(\neg S\)	\(X \wedge \neg S\)	출력
F	F	F	F	T	F	F
F	T	F	F	T	F	F
T	F	F	F	T	T	T
T	T	F	F	T	T	T
F	F	T	F	F	F	F
F	T	T	T	F	F	T
T	F	T	F	F	F	F
T	T	T	T	F	F	T

위 네 줄(\(S\) = F)의 출력은 \(X\)와 같고, 아래 네 줄(\(S\) = T)의 출력은 \(Y\)와 같다. \(S\)가 두 입력 가운데 하나를 골라 내보낸다. 이 회로가 2입력 멀티플렉서다.

같은 세 연산을 레지스터의 비트 32개에 한꺼번에 하는 명령이 비트 논리 명령이다. 논리 게이트로 만든 회로가 컴퓨터의 여러 층 가운데 맨 아래층이라는 이야기는 가상 기계 계층에 있다.

컴퓨터 구조 (2-1학기). 이 문서의 게이트와 가산기를 프로세서의 부품으로 키운다⁵.

표에서 회로로, 그리고 지연. 진리표에서 출력이 1인 줄마다 AND 항을 만들고 OR로 묶으면 어떤 표든 회로가 된다. 입력이 바뀐 뒤 출력이 자리 잡는 시간은 게이트를 가장 많이 거치는 길이 정한다: 논리 게이트와 조합 회로.
고르는 회로. 위 어셈블리어 단락의 2입력 멀티플렉서를 32비트 너비로, 입력 32개짜리로 키우고, 번호를 선 하나로 바꾸는 디코더와 짝지어 쓴다: 멀티플렉서와 디코더.
가산기. 예제의 4비트 리플 캐리 가산기를 32비트로 늘리고, 같은 회로로 뺄셈을 하고, 결과가 넘쳤는지 알아내고, 올림을 기다리지 않고 미리 구한다: 가산기. 그 문서는 전가산기의 올림을 “세 입력 가운데 둘 이상이 1”로 읽어 \(c_{\text{out}} = ab + a c_{\text{in}} + b c_{\text{in}}\)으로 쓴다. 위 예제의 \(ab + c_{\text{in}}(a \oplus b)\)와 입력 여덟 가지 모두에서 같은 값이다⁶.
기억하는 회로. “모형이 보장하지 않는 것”에서 말한 플립플롭은 래치와 플립플롭에서 게이트 두 개를 맞물려 만든다.

확인 문제

C1 반가산기의 합과 올림을 불 식으로 쓰고, 각각 어떤 게이트로 만드는가?

답: 합 \(s = a \oplus b\)(XOR 게이트), 올림 \(c = a \cdot b\)(AND 게이트).

C2 4비트 리플 캐리 가산기로 0101 + 0011을 계산할 때, 아래 자리부터 각 자리의 올림 출력과 최종 결과를 쓰라.

답: 올림 출력은 1, 1, 1, 0이고 결과는 1000(8)이다.

흔한 오답: 두 번째 자리에서 올림을 빠뜨려 0 + 1 = 1로 계산하는 것. 아래에서 올라온 1까지 더하면 \(0 + 1 + 1 = 2\)라 합 0, 올림 1이다.

C3 NAND 게이트만으로 NOT, AND, OR를 만드는 방법을 쓰고, 이것이 왜 “NAND로 모든 회로를 만들 수 있다”를 보여 주는지 설명하라.

답: \(\bar a = \text{NAND}(a, a)\), \(ab = \text{NAND}(\text{NAND}(a,b), \text{NAND}(a,b))\), \(a + b = \text{NAND}(\text{NAND}(a,a), \text{NAND}(b,b))\). 모든 불 함수는 AND·OR·NOT으로 된 DNF로 쓸 수 있으므로, 이 셋을 NAND로 바꿔 끼우면 NAND만으로 된다.

C4 불 식 \((Y \wedge S) \vee (X \wedge \neg S)\)에서 \(X\) = T, \(Y\) = F일 때 \(S\) = F와 \(S\) = T의 출력을 각각 구하라. 이 식이 하는 일을 한 문장으로 쓰라.

답: \(S\) = F이면 T, \(S\) = T이면 F. 이 식은 \(S\)가 거짓이면 \(X\)를, 참이면 \(Y\)를 그대로 내보낸다(2입력 멀티플렉서).
이유: \(S\) = F이면 \(Y \wedge S\)는 늘 F이고 \(X \wedge \neg S\)는 \(X\)와 같다. \(S\) = T이면 반대로 \(Y \wedge S\)가 \(Y\)와 같고 \(X \wedge \neg S\)는 늘 F다.
흔한 오답: \(\neg S\)를 \(X \wedge\)보다 나중에 계산하는 것. NOT이 가장 먼저다⁴.

C5 전가산기의 올림을 \(ab + c_{\text{in}}(a \oplus b)\)로 쓴 식과 \(ab + a c_{\text{in}} + b c_{\text{in}}\)으로 쓴 식은 모양이 다르다. 두 식이 늘 같은 값인 이유를 대라.

답: 두 식이 다를 수 있는 것은 \(c_{\text{in}}(a \oplus b)\)와 \(c_{\text{in}}(a + b)\)가 다를 때, 곧 \(c_{\text{in}} = 1\)이고 \(a = b = 1\)일 때뿐이다. 그때는 앞의 \(ab\)가 이미 1이라 두 식 모두 1이다.
이유: \(a \oplus b\)와 \(a + b\)는 \(a = b = 1\)인 한 줄에서만 다르다. 둘째 식은 “셋 가운데 둘 이상이 1”이라는 뜻이 바로 읽힌다⁶.

Rosen, Discrete Mathematics and Its Applications 7판, 12장 “Boolean Algebra”(불 함수, 불 함수의 표현, 논리 게이트, 회로의 최소화). 불 함수의 개수와 기능적 완전성 포함. ↩ ↩²
전파 지연·글리치·순차 회로는 디지털 논리 설계 과목의 내용이다. 올림을 미리 계산하는 회로는 캐리 예측 가산기(carry-lookahead adder)다. ↩
‘예제’의 4비트 리플 캐리 가산기 설명과 전가산기 식을 연결 그림으로 그렸다. ↩
진리표 여덟 줄과 “S가 거짓이면 X, 참이면 Y”는 02_virtual-machine-levels_verify.py로 확인했다. ↩ ↩²
근거는 링크한 각 문서의 각주에 있다. ↩
두 올림 식이 여덟 줄 모두 같다는 것과 카드 C5는 07_adder-circuit_verify.py로 확인했다. 다수결 꼴의 식은 UC Berkeley CS61C 강의 노트 “Adder/Subtractor”(https://notes.cs61c.org/content/sds-blocks/adder-subtractor)에 있다. ↩ ↩²