조지 불(George Boole)은 논리 문제를 서로 겹치지 않는 0·1 부류로 전개하고 식으로 계산했습니다. 입력이 많아지면 전개한 항도 빠르게 늘어납니다. 한 세기 뒤 모리스 카르노는 진리표 값을 특별한 순서의 지도에 놓아, 합칠 수 있는 항을 눈으로 찾는 방법을 발표했습니다. 이번에는 불의 식이 지도에서 어떻게 짧아지는지 직접 확인합니다.
01 · 불이 풀려던 문제
모든 경우를 적은 뒤, 같은 뜻의 긴 식을 어떻게 줄일까요?
x, y, z가 만드는 여덟 부류는 xyz, xy(1−z), x(1−y)z처럼 각 입력의 해당·비해당을 모두 적어 나타낼 수 있습니다. 불의 전개는 가능한 경우를 빠짐없이 드러냅니다. 그러나 출력이 1인 항을 모두 합치면 식이 길어지고, 어느 항들을 합칠 수 있는지 한눈에 찾기 어렵습니다.
예를 들어 xy(1−z)와 xyz는 z만 다릅니다. 두 부류를 합치면 xy[(1−z)+z]=xy가 됩니다. z가 0이든 1이든 같은 결과이므로 이 묶음에서는 z를 적을 필요가 없습니다. 이 불 대수의 흡수·결합을 지도 위의 이웃으로 보여주는 것이 이번 활동의 핵심입니다.
불이 제시한 부류 기호와 전개 법칙이 식을 줄이는 계산의 출발점입니다. 카르노맵은 불이 만든 그림이 아닙니다. 모리스 카르노(Maurice Karnaugh)가 1953년 조합 논리 회로의 합성을 위해 발표한 후대 방법입니다.
02 · 불의 식에서 후대의 지도법으로
한 칸 차이인 이웃을 묶으면 달라지는 기호가 사라집니다
카르노맵의 열은 yz=00, 01, 11, 10 순서입니다. 보통 숫자 순서 00, 01, 10, 11과 달리 이웃한 두 열 사이에서 한 값만 바뀝니다. 맨 왼쪽 00과 맨 오른쪽 10도 가장자리를 넘어 이웃합니다. 행은 x=0과 x=1이므로 위아래 이웃도 한 입력만 다릅니다.
출력 1인 칸을 1, 2, 4, 8칸 크기의 직사각형으로 묶습니다. 큰 묶음에서 값이 바뀌는 입력은 지우고, 모든 칸에서 같은 입력만 남깁니다. 2칸 묶음 두 개가 겹쳐도 됩니다. 겹침으로 더 큰 묶음을 만들거나 모든 1을 적은 수의 항으로 덮을 수 있기 때문입니다. 이 과정은 불 논리의 같은 출력을 더 짧은 불 대수 식으로 나타냅니다.
03 · 진리표를 카르노맵으로
1을 눌러 만들고, 자동으로 제안된 큰 묶음을 확인하세요
| x \ yz | 00 | 01 | 11 | 10 |
|---|
같은 값을 행 순서로 확인
| 행 | x | y | z | F | 묶음 |
|---|
처음 지도에는 101, 110, 111 세 칸이 1입니다. 110·111을 묶으면 xy, 101·111을 묶으면 xz가 남아 F=xy+xz가 됩니다. 111은 두 묶음에 함께 들어갑니다. ‘가장자리 묶음’을 누르면 왼쪽과 오른쪽 열이 맞닿는다는 점도 확인할 수 있습니다.
04 · 표에서 얻은 발견
큰 묶음일수록 식에서 더 많은 입력이 사라집니다
한 칸은 x, y, z 세 기호가 모두 필요합니다. 이웃한 2칸은 한 기호가 달라져 두 기호만 남습니다. 4칸 묶음은 두 기호가 달라져 한 기호만 남고, 8칸 전체가 1이면 식은 1입니다. 지도에서 묶음 크기가 두 배가 될 때마다 식의 기호가 하나 줄어드는 셈입니다.
지도의 이웃은 칸이 종이에 가깝다는 뜻만이 아닙니다. 정확히 한 입력만 다른 조합입니다. 열 순서를 00, 01, 11, 10으로 정한 까닭도 여기에 있습니다. 대각선 칸은 두 입력이 달라서 하나의 2칸 묶음으로 합칠 수 없습니다.
묶음 안에서 x가 모두 1이면 x를 남깁니다. y가 모두 0이면 1−y를 남깁니다. 0과 1이 함께 나타나는 입력은 결과를 가르지 않으므로 지웁니다. 각 묶음의 항을 +로 합치면 출력 1인 칸을 덮는 식이 됩니다.
05 · 오늘의 실제 적용
작은 논리 회로와 규칙을 더 적은 항으로 만들 수 있습니다
카르노가 1953년 발표한 논문의 제목은 「The Map Method for Synthesis of Combinational Logic Circuits」입니다. 논문은 불 대수 식과 논리 함수를 회로로 옮길 때 지도법으로 필요한 항을 정리합니다. 입력이 적은 회로에서는 게이트 수와 연결을 줄이는 과정을 손으로 확인하기 좋습니다.
업무 규칙에서도 같은 생각을 쓸 수 있습니다. 여러 행이 결과 ‘승인’을 내고 한 조건만 달라진다면, 그 조건을 규칙에서 뺄 수 있는지 검토합니다. 식이 짧아지면 구현과 시험 항목이 줄 수 있지만, 실제 업무에서 미확인·예외 상태가 두 값 표 밖에 남아 있지 않은지 먼저 확인해야 합니다.
① 요구사항에서 입력과 출력을 0·1로 정의합니다. ② 진리표로 모든 조합을 검토합니다. ③ 1을 카르노맵에 옮깁니다. ④ 가능한 큰 2의 거듭제곱 묶음으로 덮습니다. ⑤ 얻은 짧은 식이 원래 표의 여덟 출력을 모두 재현하는지 다시 시험합니다.
06 · 바르게 쓰는 기준
지도는 정의한 두 값 세계에서만 완전합니다
0은 확인된 비해당이고 빈칸이나 미확인이 아닙니다. 값이 알려지지 않은 상태를 0으로 넣으면 지도는 깔끔해져도 규칙의 의미가 달라집니다. ‘상관없음’으로 처리하는 입력 조합도 실제로 0과 1 어느 쪽이든 허용되는지 근거를 남겨야 합니다.
자동 제안은 모든 1을 덮는 항의 수를 먼저 줄이고, 같은 항 수라면 남는 기호 수를 줄입니다. 같은 길이의 식이 여러 개일 수도 있습니다. 이 지도는 한 가지 최소 덮음을 보여주며, 유일한 표현이라고 주장하지 않습니다.
입력이 네다섯 개를 넘으면 지도를 손으로 다루기 어려워집니다. 그때는 퀸–매클러스키 방법이나 현대 논리 합성 도구가 이어서 쓰입니다. 이들 역시 불보다 뒤의 발전입니다.
불의 문제: 전개된 여러 부류와 식을 계산 가능한 법칙으로 다루기. 불의 제안: 0·1 부류와 보충 부류를 이용해 항을 전개하고 결합하기. 오늘의 쓰임: 카르노맵에서 한 입력만 다른 1들을 묶어 회로나 규칙의 식을 줄이기.
07 · 자료와 출처
불의 원전과 카르노의 원논문
- 조지 불, 『An Investigation of the Laws of Thought』(1854), 제5장 — 논리 함수를 구성 부류로 전개하는 원리.
- 조지 불, 「The Calculus of Logic」(1848) — 0·1 경우에 따른 전개식과 결합 법칙의 원전.
- Maurice Karnaugh, “The Map Method for Synthesis of Combinational Logic Circuits,” 1953 — 카르노맵을 제안한 원논문 DOI.
- NIST Dictionary of Algorithms and Data Structures, Karnaugh map — 지도법의 정의와 1953년 원논문 서지.
- 조지 불 초상 판화 · Wikimedia Commons — 1865년 1월 21일 게재, 공개 영역.