조지 불(George Boole)은 부류의 공통 부분, 합, 보충 부분을 기호와 연산 법칙으로 다루었습니다. 여러 연산이 서로 어떻게 바뀌어 표현되는지도 그의 계산에서 중요한 문제였습니다. 이번에는 불의 연산을 후대의 NAND 하나로 다시 구성합니다. 목표 출력표를 먼저 고른 뒤 같은 종류의 소자를 거듭 연결해 그 표에 도달하는지 살펴보겠습니다.
01 · 불이 풀려던 문제
몇 가지 기본 연산으로 다양한 관계를 표현할 수 있을까요?
불은 1854년 『An Investigation of the Laws of Thought』에서 xy를 두 부류의 공통 부분, 1−x를 x의 보충 부분으로 다뤘습니다. 정해진 뜻과 법칙을 유지하면 복잡한 부류 관계도 식을 변형해 계산할 수 있었습니다. 핵심은 기호의 모양보다 각 연산이 어떤 대상을 고르는지에 있었습니다.
이 관점은 후대에 새로운 질문을 낳았습니다. 여러 논리 연산을 더 적은 종류의 연산으로 만들 수 있을까요? 한 종류만으로 충분하다면 설계자는 같은 기본 부품을 반복하면서 다양한 기능을 구성할 수 있습니다. 이 질문은 불의 대수 법칙을 논리 상수와 회로 구성의 문제로 확장합니다.
불은 부류 연산을 대수 법칙으로 계산하는 토대를 세웠습니다. 한 단일 연산만으로 다른 논리 연산을 정의하는 체계는 헨리 셰퍼(Henry M. Sheffer)가 1913년 논문에서 제시했습니다. 전자 NAND 소자로 구현하는 일은 그 뒤의 회로 기술입니다.
02 · 불의 연산에서 셰퍼와 NAND로
‘둘 다 1’만 0으로 바꾸는 연산을 반복합니다
NAND는 AND의 결과를 뒤집습니다. 두 입력이 모두 1인 11행에서만 0이고, 00·01·10행에서는 1입니다. 이 글에서는 x ↑ y=1−xy로 적겠습니다. 셰퍼의 1913년 논문은 논리 상수에 적용할 수 있는 단일 연산을 제시했습니다. 오늘날 이 계열의 연산을 셰퍼 스트로크와 연결해 설명합니다.
먼저 같은 입력을 두 자리에 넣으면 x ↑ x=1−x가 되어 NOT을 얻습니다. t=x ↑ y라고 두고 t ↑ t를 계산하면 xy가 됩니다. 각 입력을 먼저 뒤집은 뒤 (x ↑ x) ↑ (y ↑ y)를 계산하면 포괄적 OR가 됩니다.
XOR도 NAND 네 개로 만들 수 있습니다. t=x ↑ y, p=x ↑ t, q=y ↑ t를 차례로 구하고 p ↑ q를 출력하면 01·10행에서만 1입니다. 불이 직접 NAND 게이트를 설계한 것으로 읽기보다, 불의 연산 법칙이 단일 소자 조합에서 그대로 검증된다고 이해하는 편이 정확합니다.
03 · 불의 연산을 한 종류의 소자로
목표 연산을 고르고 각 NAND 단계의 출력을 따라가세요
| 입력 | 1단계 | 2단계 | 3단계 | 4단계 | 목표 | 비교 |
|---|
처음에는 NOT x가 선택됩니다. 00과 01에서 y가 달라도 출력이 같다는 점을 확인하세요. AND·OR·XOR로 목표를 바꾸면 필요한 NAND 개수와 중간 열이 달라집니다. 표의 네 행이 모두 일치해야 선택한 조합이 목표 연산을 구현했다고 말할 수 있습니다.
04 · 표에서 얻은 발견
같은 소자를 반복해도 연결 순서가 달라지면 다른 연산이 됩니다
NAND 하나의 출력표는 늘 같습니다. 달라지는 부분은 앞 단계의 출력을 다음 입력으로 보내는 연결입니다. x를 두 입력에 함께 넣으면 NOT, x ↑ y를 다시 자기 자신과 NAND하면 AND가 됩니다. 입력을 먼저 각각 뒤집어 NAND하면 OR가 됩니다.
XOR에서는 네 번째 출력까지 따라가야 00·11이 0, 01·10이 1이 됩니다. 중간값 t·p·q는 별도의 사람이나 장치 수가 아닙니다. 한 입력 조합을 회로가 통과할 때 생기는 0·1 신호입니다. 네 행은 가능한 입력 조합의 수이며 성공률이나 확률을 뜻하지 않습니다.
“NAND는 무엇이든 만든다”라고만 쓰기보다 “x ↑ x의 네 행이 1−x와 같고, t=x ↑ y를 다시 t ↑ t로 계산한 네 행이 xy와 같으므로 NOT과 AND를 NAND만으로 구성할 수 있다”라고 증거를 적습니다.
05 · 오늘의 실제 적용
표준 소자 조합과 회로 검증의 공통 언어가 됩니다
현대의 논리 회로 설계에서는 목표 불 함수를 게이트 연결로 옮기고, 각 입력 조합에서 출력이 요구표와 같은지 검증합니다. 사용할 소자의 종류가 정해져 있으면 AND·OR·NOT 같은 식을 그 소자만의 연결로 바꿉니다. NAND의 기능적 완전성은 이런 변환을 이해하는 대표 사례입니다.
미국 국립표준기술연구소(NIST)는 불 회로를 입력 노드·논리 게이트·출력 노드로 이루어진 방향성 비순환 그래프로 설명하며 AND·OR·NAND·XOR를 기본 게이트 예로 듭니다. 회로의 크기와 깊이를 줄이는 일도 실제 설계의 중요한 과제입니다. 이번 표에서는 소자 수와 단계 수를 나누어 보며 그 차이를 확인합니다.
① 목표 출력표를 정합니다. ② 사용할 기본 소자를 정합니다. ③ 각 단계의 중간 출력을 식으로 적습니다. ④ 모든 입력 행에서 최종 출력과 목표를 비교합니다. ⑤ 같은 기능이라면 소자 수·단계 수·물리적 제약을 별도로 평가합니다.
06 · 바르게 쓰는 기준
논리식의 완전성과 실제 회로의 성능을 구별합니다
기능적 완전성은 필요한 불 논리 함수를 그 연산 조합으로 표현할 수 있다는 뜻입니다. 이 성질만으로 가장 빠르거나 가장 작은 회로가 정해지지는 않습니다. 실제 구현에서는 게이트 지연, 전력, 배선, 소자 정격을 함께 검토합니다.
이 활동의 0과 1은 논리 상태입니다. 전자 장치에서는 정해진 전압 범위가 논리 상태를 구현합니다. NAND 식이 맞는지 확인하는 진리표와 물리 장치가 안전하고 안정적으로 작동하는지 확인하는 시험은 서로 다른 검토 항목입니다.
역사적 기여도 분리해 읽습니다. 불은 부류와 추론을 대수로 계산했고, 셰퍼는 1913년에 단일 논리 연산을 제시했으며, 섀넌은 1930년대에 불 대수를 계전기 회로 분석과 연결했습니다. NAND 게이트를 이용한 오늘의 구성은 이 발전을 바탕으로 한 현대적 실험입니다.
불의 문제: 여러 부류 관계를 일정한 대수 법칙으로 계산하기. 불의 제안: 곱·보충 등 기본 연산을 조합해 식을 변형하기. 오늘의 쓰임: 한 종류의 NAND 소자를 단계적으로 연결하고 목표 출력표와 전 행을 대조하기.
07 · 자료와 출처
불의 원전과 단일 연산·불 회로 자료
- 조지 불, 『An Investigation of the Laws of Thought』(1854), 제2장 — 부류 기호와 곱·보충 연산의 법칙.
- Henry M. Sheffer, “A Set of Five Independent Postulates for Boolean Algebras, with Application to Logical Constants”(1913) — 단일 연산과 논리 상수의 원논문.
- Claude E. Shannon, A Symbolic Analysis of Relay and Switching Circuits — 불 대수와 스위칭 회로의 연결.
- NIST CSRC, Circuit Complexity — 불 회로·게이트·입출력과 회로 크기·깊이의 공식 설명.
- 조지 불 초상 판화 · Wikimedia Commons — 1865년 1월 21일 게재, 공개 영역.