부울 대수: 디지털 회로 설계의 기초

요약: 부울 대수는 AND, OR, NOT을 사용해 TRUE/FALSE 값을 다루는 형식 체계입니다. 항등, 흡수, 분배, 보수, 드 모르간 정리 등의 법칙을 통해 부울 식을 동등하면서도 더 단순한 형태로 변환할 수 있으며, 이는 곧 실리콘에서 게이트 수와 전파 지연의 감소로 직결됩니다.

19세기 중반에 형식화된 조지 불(George Boole)의 사고의 대수는 오늘날 모든 디지털 칩의 동작 수학이 되었습니다. 모든 마이크로프로세서, 메모리 셀, 그래픽 파이프라인은 결국 그가 정의한 AND, OR, NOT 연산으로 환원됩니다.

엔지니어나 컴퓨터 과학자에게 부울 법칙을 숙달하는 것은 학문적 관심사가 아닙니다. 부울 식을 간소화한다는 것은 게이트를 삭제하고, 와이어를 제거하며, 전파 지연에서 피코초를 깎아 내는 것을 의미합니다. 수학을 간소화할 수 있다면, 실리콘도 간소화할 수 있습니다.

세 가지 기본 연산: AND, OR, NOT

아무리 복잡한 디지털 논리라도 세 가지 기본 연산으로 만들어집니다. 이들을 이해하는 것은 디지털 설계의 알파벳을 이해하는 것입니다. digisim.io에서는 이들이 이산 컴포넌트로 표현되어, 함께 배선하면 임의로 복잡한 논리를 구성할 수 있습니다.

AND 게이트 컴포넌트 다이어그램

1. AND 연산

출력은 모든 입력이 TRUE일 때에만 TRUE(1)가 됩니다. 엄격한 요구 사항이라고 생각해 보세요. 중장비의 안전 시스템에서, 모터는 “시작 버튼”이 눌렸고 AND “안전 가드”가 닫혔을 때에만 동작해야 할 수 있습니다. 회로 측면에서 AND 게이트는 직렬 연결처럼 동작합니다 — 전류가 흐르려면 모든 스위치가 닫혀 있어야 합니다.

부울 식: $Y = A \cdot B$
컴포넌트 이름: AND

2. OR 연산

출력은 적어도 하나의 입력이 TRUE이면 TRUE(1)가 됩니다. 홈 보안 시스템에서는 “현관문이 열림” 또는 “뒤쪽 창문이 깨짐”이면 경보가 작동해야 합니다. 회로 측면에서 OR 게이트는 병렬 연결처럼 동작합니다 — 어떤 스위치라도 닫히면 전류가 흐릅니다.

부울 식: $Y = A + B$
컴포넌트 이름: OR

3. NOT 연산 (인버터)

출력은 단일 입력의 논리적 역입니다. 입력이 HIGH이면 출력은 LOW이고, 그 반대도 마찬가지입니다. 회로 측면에서 NOT 게이트(또는 인버터)는 신호 레벨을 뒤집어, 액티브 하이 신호를 액티브 로우로, 또는 반대로 변환합니다.

부울 식: $Y = \overline{A}$ (또는 $A'$ )
컴포넌트 이름: NOT

AND 게이트 동작 체험하기

이 게이트들을 처음 배울 때는 입력을 토글하고 진리표가 살아 움직이는 모습을 관찰할 수 있는 깨끗하고 격리된 환경이 매우 유용합니다.

기술 사양: 진리표

진리표는 디지털 논리의 기본 성적표입니다. 가능한 모든 입력 조합을 해당 출력에 매핑합니다.

AND 게이트 진리표

입력 A	입력 B	출력 Y
0	0	0
0	1	0
1	0	0
1	1	1

OR 게이트 진리표

입력 A	입력 B	출력 Y
0	0	0
0	1	1
1	0	1
1	1	1

NOT 게이트 진리표

입력 A	출력 Y
0	1
1	0

부울 대수의 법칙은 무엇인가?

기본 연산이 정의되었으니, 이제 논리 식을 다루고 간소화할 수 있는 법칙들을 살펴봅시다. 이들은 추상적인 규칙이 아닙니다 — 회로 변환입니다. 각 법칙은 구체적인 하드웨어 최적화에 대응합니다. 게이트를 제거하거나, 와이어를 없애거나, 전파 지연을 줄이는 것입니다.

OR 게이트 컴포넌트 다이어그램

항등 법칙과 흡수(소거) 법칙

이 법칙들은 변수가 상수 0과 1과 어떻게 상호 작용하는지 정의합니다. digisim.io에서 CONSTANT와 CONSTANT_ZERO 컴포넌트를 사용해 검증해 볼 수 있습니다.

항등 법칙(Identity Law): 변수가 해당 연산의 항등원과 결합되면 변하지 않습니다.
OR과 0: $A + 0 = A$ — OR 입력 하나를 그라운드에 연결해도 출력에 영향이 없습니다.
AND와 1: $A \cdot 1 = A$ — AND 입력 하나를 VCC에 연결해도 출력에 영향이 없습니다.
영(Null/Annihilation) 법칙: 변수가 우세 원소와 결합되면 그 원소가 됩니다.
OR과 1: $A + 1 = 1$ — OR 입력 하나가 영구적으로 HIGH이면 출력은 A와 무관하게 항상 HIGH입니다.
AND와 0: $A \cdot 0 = 0$ — AND 입력 하나가 영구적으로 LOW이면 출력은 A와 무관하게 항상 LOW입니다.

보수 법칙과 멱등 법칙

이 법칙들은 변수가 자기 자신 또는 자신의 역과 어떻게 상호 작용하는지를 다룹니다.

멱등 법칙(Idempotent Law): 변수를 자기 자신과 결합해도 변화가 없습니다.
$A + A = A$ — 동일한 신호를 OR 게이트의 두 입력에 연결하는 것은 직접 와이어와 동등합니다.
$A \cdot A = A$ — 동일한 신호를 AND 게이트의 두 입력에 연결하는 것은 직접 와이어와 동등합니다.
보수 법칙(Complement Law): 변수를 자신의 역과 결합하면 상수가 됩니다.
$A + \overline{A} = 1$ — 신호는 항상 HIGH 또는 LOW 중 하나이므로, 두 OR 입력 중 하나는 항상 1입니다.
$A \cdot \overline{A} = 0$ — 신호는 동시에 HIGH이면서 LOW일 수 없으므로, AND는 항상 0을 출력합니다.

교환, 결합, 분배 법칙

전통 대수에서 온 사람이라면 이 법칙들의 대부분은 익숙하게 느껴질 것입니다.

교환 법칙(Commutative): $A + B = B + A$ 및 $A \cdot B = B \cdot A$ — AND나 OR 게이트의 입력 순서는 중요하지 않습니다.
결합 법칙(Associative): $(A + B) + C = A + (B + C)$ 및 $(A \cdot B) \cdot C = A \cdot (B \cdot C)$ — 게이트를 어떤 그룹으로 캐스케이드해도 결과는 동일합니다.
분배 법칙(표준): $A \cdot (B + C) = A \cdot B + A \cdot C$ — 일반 대수와 똑같이 동작하며, 식을 자유롭게 인수분해하거나 전개할 수 있습니다.

그러나 부울 대수에는 실수 대수에 대응되는 것이 없는 두 번째 분배 법칙이 있습니다.

A + (B \cdot C) = (A + B) \cdot (A + C)

처음에는 직관에 반합니다. 일반 수학에서 $5 + (3 \times 4) = 17$ 이지만, $(5+3) \times (5+4) = 72$ 입니다. 둘은 같지 않습니다. 그러나 부울 논리의 이진 세계에서는 이 항등식이 성립합니다.

직관의 핵심: $A = 1$ 이면 양변이 즉시 1로 계산됩니다. $A = 0$ 이면 양변이 $B \cdot C$ 로 축소됩니다. 이차식처럼 우변을 “FOIL”하려 하지 마세요 — 부울 대수에는 $A \cdot A = A$ 이므로 제곱 항이라는 개념이 없습니다. 이 두 번째 분배 법칙은 임의의 부울 함수의 두 가지 표준 표현인 곱의 합(Sum-of-Products, SOP)과 합의 곱(Product-of-Sums, POS) 형태를 서로 변환하는 데 초석이 됩니다.

강력한 도구: 흡수 법칙과 드 모르간 정리

다음 법칙들은 항을 통째로 제거하고 식의 구조를 근본적으로 재편합니다. 실제 회로 간소화의 주력 도구입니다.

흡수 법칙: 중복 제거

흡수 법칙(Absorption Law)을 사용하면 동작을 바꾸지 않으면서 설계에서 게이트를 통째로 삭제할 수 있습니다.

$A + A \cdot B = A$
$A \cdot (A + B) = A$

첫 번째 형태의 직관: $A + A \cdot B$ 는 $A$ 가 참이거나, $A$ 와 $B$ 가 모두 참일 때 참입니다. 그러나 $A$ 가 이미 참이라면 $B$ 와 무관하게 전체 식이 참입니다. $A \cdot B$ 항은 완전히 중복입니다. 하드웨어에서는 AND 게이트와 OR 게이트를 제거하고 직접 와이어로 대체합니다.

덜 알려진 변형으로 **합의 정리(Consensus Theorem)**라 불리는 것도 있습니다:

$A \cdot B + \overline{A} \cdot C + B \cdot C = A \cdot B + \overline{A} \cdot C$

세 번째 항( $B \cdot C$ )은 다른 두 항이 이미 모든 경우를 포괄하기 때문에 중복입니다. 눈으로 보고 찾기는 어렵지만, 카르노 맵을 사용하면 시각적으로 분명해집니다.

드 모르간 정리: 부정의 분배

오거스터스 드 모르간(Augustus De Morgan)의 정리는 NOT 연산을 AND와 OR에 어떻게 분배하는지를 보여 주며, 반전된 식을 재구성할 수 있게 해 줍니다.

제1 법칙: $\overline{A \cdot B} = \overline{A} + \overline{B}$ — NAND 게이트는 입력이 반전된 OR 게이트와 동등합니다.
제2 법칙: $\overline{A + B} = \overline{A} \cdot \overline{B}$ — NOR 게이트는 입력이 반전된 AND 게이트와 동등합니다.

회로 측면에서, 이 쌍대성은 현대 칩 설계의 근본입니다. CMOS 기술에서 NAND와 NOR 게이트는 표준 AND, OR 게이트보다 물리적으로 더 작고 빠르기 때문에, 설계자들은 일상적으로 드 모르간 정리를 사용해 논리를 NAND만 또는 NOR만으로 구현되도록 변환합니다. 더 깊은 내용은 드 모르간 법칙의 실제 적용에 관한 별도 글을 참조하세요.

NAND 게이트 컴포넌트 다이어그램

범용 NAND 논리 탐색

digisim.io에서 시뮬레이션하기: 이론에서 손에 잡히는 증명으로

이 법칙들을 읽는 것과 동작하는 모습을 보는 것은 다릅니다. digisim.io 캔버스에서 흡수 법칙 $A + A \cdot B = A$ 를 증명해 봅시다.

단계별 검증

시뮬레이터 열기: digisim.io/circuits/new에서 새 프로젝트를 시작합니다.
입력 배치: INPUT_SWITCH 컴포넌트 두 개를 캔버스에 드래그합니다. TEXT 도구로 ‘A’와 ‘B’로 라벨링합니다.
복잡한 쪽 구성:

AND 게이트를 배치합니다. 입력에 ‘A’와 ‘B’를 연결합니다.
OR 게이트를 배치합니다. AND 게이트의 출력을 한 입력에 연결하고, ‘A’를 다른 입력에 직접 연결합니다.
OR 게이트의 출력을 OUTPUT_LIGHT에 연결합니다.

간소화된 쪽 구성:

‘A’를 두 번째 OUTPUT_LIGHT에 직접 연결합니다.

SimCast 순간: SimCast 기능으로 상호 작용을 녹화하세요. ‘A’와 ‘B’를 네 가지 조합 모두로 토글합니다. 두 등은 항상 일치합니다. ‘B’가 무엇을 하든, 첫 번째 등은 ‘A’만 신경 씁니다.

오실로스코프 검증: 전파 관찰하기

간소화되지 않은 회로의 “비용”을 진정으로 이해하려면, 캔버스에 OSCILLOSCOPE_8CH를 배치하세요. 채널 1을 입력 ‘A’에 연결하고 채널 2를 복잡한 OR 게이트의 출력에 연결합니다.

‘A’를 토글하면 오실로스코프의 파형에서 작은 지연이 보입니다. 이것이 전파 지연(propagation delay)( $t_{pd}$ )입니다. 모든 게이트는 신호가 전파되는 데 약간의 시간을 더합니다. $A + A \cdot B$ 를 단순히 $A$ 로 간소화함으로써, AND와 OR 두 게이트의 지연을 제거하고, 총 $t_{pd}$ 를 $t_{pd(AND)} + t_{pd(OR)}$ 에서 0으로 줄입니다. 고속 설계에서 이러한 절감은 더 높은 달성 가능 클록 주파수로 직결됩니다.

보안 시스템 템플릿 다이어그램

보안 알람 회로 열기

보안 알람 템플릿은 여러 게이트(AND, OR, NOT)가 실제 맥락에서 어떻게 함께 동작하는지 보여 주며, 간소화 법칙을 적용해 볼 수 있는 유용한 놀이터입니다.

실제 응용: 간소화가 빛을 발하는 곳

이는 단지 교실에서 게이트 몇 개를 절약하는 일이 아닙니다. 실제 시스템에서 간소화는 더 저렴하고, 더 빠르며, 더 전력 효율적인 하드웨어로 직결됩니다.

예 1: 고속 메모리 주소 디코딩

고전적인 Intel 8086 아키텍처에서 CPU는 주소선을 사용해 어떤 메모리 칩과 통신할지를 선택합니다. 특정 칩을 활성화하는 논리를 주소 디코더라고 합니다. 디코더 논리가 최적화되지 않으면, “Enable” 신호가 RAM 칩에 도달하는 데 더 오래 걸립니다. 이로 인해 CPU는 “wait state”를 삽입해야 합니다 — 본질적으로 논리가 너무 느려서 유휴 상태가 되는 것입니다. 부울 법칙을 디코더 회로에 적용함으로써, 엔지니어들은 전체 시스템을 더 높은 클록 속도로 실행시킬 만큼의 지연을 줄일 수 있습니다.

예 2: ALU 상태 플래그

ALU(Arithmetic Logic Unit, 산술 논리 장치)는 CPU의 계산 심장부입니다. 연산 후, FLAGS_REGISTER에 상태 플래그(예: Zero, Negative, Overflow)를 설정합니다. Overflow 플래그의 논리는 최상위 비트의 자리올림 입력과 자리올림 출력을 포함하므로 악명 높게 복잡합니다.

이를 간소화 없이 원시 논리로 만들면, 거대한 게이트 그물망이 됩니다. 드 모르간 법칙과 분배 속성을 사용함으로써, 설계자들은 이 논리를 몇 개의 고속 NAND 게이트로 압축할 수 있으며, 계산이 끝나는 즉시 플래그가 준비되도록 보장합니다.

커리큘럼의 관련 주제

digisim.io에서 디지털 논리를 계속 탐구해 나가면, 다음 관련 주제들이 이해를 깊게 해 줄 것입니다:

빠른 참조: 모든 법칙 한눈에 보기

법칙	OR 형식	AND 형식
항등	$A + 0 = A$	$A \cdot 1 = A$
영	$A + 1 = 1$	$A \cdot 0 = 0$
멱등	$A + A = A$	$A \cdot A = A$
보수	$A + \overline{A} = 1$	$A \cdot \overline{A} = 0$
교환	$A + B = B + A$	$A \cdot B = B \cdot A$
결합	$(A+B)+C = A+(B+C)$	$(AB)C = A(BC)$
분배	$A + BC = (A+B)(A+C)$	$A(B+C) = AB + AC$
흡수	$A + AB = A$	$A(A+B) = A$
드 모르간	$\overline{A+B} = \overline{A}\cdot\overline{B}$	$\overline{AB} = \overline{A}+\overline{B}$
이중 부정	$\overline{\overline{A}} = A$

직접 해 보기: 지식을 실전에 적용

부울 대수는 추상적인 아이디어와 동작하는 실리콘 사이의 간극을 잇는 언어입니다. 이 법칙들은 여러분이 논리를 빚어내고, 낭비를 제거하며, 정확하면서도 효율적인 설계를 만들기 위해 사용하는 수학적 도구입니다.

도전 과제: 식 $Y = A \cdot B \cdot C + A \cdot B \cdot \overline{C} + A \cdot \overline{B} \cdot C$ 를 취해 봅시다.

분배 법칙을 사용해 공통 항을 인수분해합니다: $Y = A \cdot B \cdot (C + \overline{C}) + A \cdot \overline{B} \cdot C$ .
보수 법칙( $C + \overline{C} = 1$ )과 항등 법칙( $A \cdot B \cdot 1 = A \cdot B$ )을 적용해 $Y = A \cdot B + A \cdot \overline{B} \cdot C$ 를 얻습니다.
다시 인수분해합니다: $Y = A \cdot (B + \overline{B} \cdot C) = A \cdot (B + C)$ . (마지막 단계는 흡수 변형 $B + \overline{B}C = B + C$ 를 사용합니다.)
digisim.io를 열고 원래의 3-민텀 회로와 간소화된 2-게이트 버전을 모두 만들어 보세요.
OSCILLOSCOPE를 사용해 전파 지연을 비교하세요.

이 시리즈의 다음 항목인 곱의 합(SOP)로 계속 진행하거나, AND 게이트 컴포넌트 레퍼런스를 열어 이 법칙 중 하나를 직접 배선해 보세요.