16편에서 부울대수(Boolean algebra, 참·거짓 두 값만 다루는 대수 체계)의 공리와 법칙(교환법칙, 결합법칙, 분배법칙, 드모르간 법칙, 흡수법칙)을 정리했다. 그 법칙들은 종이 위에서 논리식을 손으로 간소화할 때 쓰는 도구였다. 이 편에서는 그 논리식이 실제로 어떤 전자 부품(게이트)으로 구현되는지, 그리고 손으로 대수 법칙을 하나씩 적용하는 대신 그림만으로 빠르게 간소화하는 카르노 맵을 다룬다. 독학사 이산수학 시험에서는 진리표 완성, 게이트 조합 해석, 카르노 맵 최소화가 계산형 문제로 자주 나온다.

기본 논리게이트: 부울 연산을 전자회로로

쉽게 말하면: 논리게이트는 0과 1을 입력받아 부울 연산 하나를 그대로 수행하는 전자 부품이다.

게이트(gate, 논리 연산을 수행하는 회로 소자)는 하나 이상의 입력을 받아 부울 연산 결과를 출력으로 내보낸다. 입력·출력은 항상 0(거짓) 또는 1(참) 두 값 중 하나다.

AND, OR, NOT — 가장 기본이 되는 세 게이트

NOT은 입력이 하나뿐이다. $\overline{0} = 1$, $\overline{1} = 0$이다.

NAND, NOR — AND·OR 뒤에 NOT을 붙인 게이트

NAND(Not-AND, AND 다음에 NOT을 붙인 게이트)와 NOR(Not-OR, OR 다음에 NOT을 붙인 게이트)는 각각 AND, OR의 출력을 그대로 뒤집은 것이다.

표에서 보듯 NAND 열은 AND 열을 그대로 뒤집은 값이고, NOR 열은 OR 열을 그대로 뒤집은 값이다(검산 완료).

XOR — 서로 다를 때만 참

XOR(eXclusive OR, 배타적 논리합 — “둘 중 하나만” 참일 때 참이라는 뜻에서 “배타적”)는 두 입력이 서로 다를 때만 1을 출력한다.

• $\oplus$: XOR 기호, “에이 엑스오어 비”로 읽는다

일상 비유로는 스위치 두 개로 복도 전등을 켜고 끄는 3로 스위치 회로가 XOR과 같은 동작이다. 두 스위치가 같은 위치(둘 다 위 또는 둘 다 아래)면 불이 꺼지고, 서로 다른 위치면 불이 켜지도록 배선하는 것이 실생활에서 XOR을 쓰는 예다.

부울식과 회로의 대응

쉽게 말하면: 부울식의 곱(AND)·합(OR)·부정(NOT)을 그대로 게이트로 바꿔 이으면 회로가 된다.

부울식 $F = AB + \overline{A}C$를 회로로 옮겨보자. 이 식은 “$A$와 $B$를 AND한 것”과 “$A$를 NOT한 것과 $C$를 AND한 것”을 OR로 합친 것이다.

검산. $A=1, B=0, C=1$을 대입해보자. $AB = 1 \cdot 0 = 0$이고, $\overline{A}C = 0 \cdot 1 = 0$이므로 $F = 0+0 = 0$이다. 회로도로도 같은 경로를 따라가면, $A=1$이 AND1에 들어가지만 $B=0$이라 AND1 출력은 0, $A=1$을 NOT하면 0이 되어 AND2도 0을 출력하므로 최종 OR 출력은 0이다. 대수식 계산과 회로 추적 결과가 일치한다(검산 완료).

NAND는 만능 게이트다

만능 게이트(universal gate, 이 게이트 하나만으로 AND·OR·NOT을 전부 만들 수 있는 게이트)라는 개념이 시험에 종종 나온다. NAND 하나만으로 NOT, AND, OR을 모두 만들 수 있다는 것을 확인해보자.

NOT 만들기. NAND의 두 입력에 같은 신호 $A$를 넣으면 $\overline{A \cdot A}$가 되는데, $A \cdot A = A$이므로 결과는 $\overline{A}$다.

AND 만들기. NAND 출력을 다시 NAND(자기 자신과 묶어서, 즉 NOT)에 통과시키면 이중 부정이 되어 원래 AND가 남는다.

OR 만들기. 드모르간 법칙(16편)을 거꾸로 이용한다. $A$와 $B$를 각각 NAND-NOT으로 뒤집어 $\overline{A}$, $\overline{B}$를 만든 뒤, 이 둘을 NAND에 넣으면 된다.

세 번째 줄은 드모르간 법칙 $\overline{XY} = \overline{X}+\overline{Y}$에서 $X=\overline{A}$, $Y=\overline{B}$를 대입한 것과 같다($\overline{\overline{A}} = A$, $\overline{\overline{B}}=B$이므로 결과가 $A+B$가 된다). NAND만으로 세 기본 연산을 모두 구현할 수 있으므로, 실제 반도체 칩은 종류를 줄이기 위해 NAND(또는 NOR) 게이트만으로 대부분의 회로를 만든다.

카르노 맵: 진리표를 그림으로 간소화한다

쉽게 말하면: 진리표의 결과를 그레이 코드 순서로 배열한 격자에 옮기고, 인접한 1들을 사각형으로 묶으면 그 묶음이 곧 간소화된 항이 된다.

부울 대수 법칙을 순서대로 적용해 논리식을 간소화하는 것(16편)은 식이 길어질수록 어느 법칙을 어디에 적용해야 할지 찾기 어려워진다. 카르노 맵(Karnaugh map, K-map)은 진리표를 격자에 옮겨 놓고 눈으로 인접한 1들을 묶기만 하면 간소화된 식을 바로 읽어낼 수 있는 방법이다.

핵심은 그레이 코드(Gray code, 이웃한 두 값이 딱 1비트만 다르게 배열한 이진수 순서) 순서로 칸을 배열하는 것이다. 2변수라면 $00, 01, 11, 10$ 순서로 두며(보통의 이진수 순서 $00,01,10,11$이 아니다), 이렇게 하면 격자에서 물리적으로 이웃한 칸은 항상 논리적으로도 1비트 차이만 나서, 이웃한 칸끼리 묶으면 달라지는 변수 하나가 정확히 사라진다.

2변수 카르노 맵 예제

함수 $F(A,B)$가 $F(0,1)=1$, $F(1,1)=1$이고 나머지는 0이라 하자(진리표: $A=0,B=0 \to 0$; $A=0,B=1\to1$; $A=1,B=0\to0$; $A=1,B=1\to1$).

$B=1$ 열의 두 칸이 모두 1이고 세로로 인접해 있으므로 이 둘을 하나로 묶는다. 이 묶음에서 $A$는 0과 1이 섞여 있으니 소거되고, $B$는 두 칸 모두 1이니 그대로 남는다.

검산. 원래 진리표에서 $F$는 $B=1$일 때만 1이고 $B=0$일 때는 $A$ 값과 상관없이 항상 0이다. 간소화된 식 $F=B$도 정확히 같은 규칙이므로 일치한다(검산 완료).

3변수 카르노 맵 예제

함수 $F(A,B,C) = \Sigma m(0,2,4,5,6)$을 간소화해보자. $\Sigma m(\ldots)$는 “괄호 안 번호에 해당하는 최소항(minterm)에서 $F=1$“이라는 표기다. 최소항 번호는 $(A,B,C)$를 이진수로 읽은 값이다: $m_0=(0,0,0)$, $m_2=(0,1,0)$, $m_4=(1,0,0)$, $m_5=(1,0,1)$, $m_6=(1,1,0)$.

1단계: 진리표를 완성한다.

2단계: 카르노 맵에 옮긴다. 세로축은 $A$, 가로축은 $BC$를 그레이 코드 순서($00,01,11,10$)로 둔다.

3단계: 인접한 1을 묶는다. 카르노 맵은 맨 왼쪽 열과 맨 오른쪽 열도 원통처럼 이어진다는 점을 이용한다.

• 묶음 1(4칸). $BC=00$ 열과 $BC=10$ 열은 원통 구조로 서로 인접하고, 이 두 열의 $A=0$행·$A=1$행이 전부 1이다($m_0, m_2, m_4, m_6$ 네 칸). 이 네 칸에서 $A$는 0과 1이 섞여 소거되고, $B$는 $BC=00$일 때 0, $BC=10$일 때 1로 섞여 소거되며, $C$는 두 열 모두 0이므로 그대로 남는다. → 이 묶음은 $\overline{C}$ 항이 된다.
• 묶음 2(2칸). $A=1$행에서 $BC=00$과 $BC=01$이 인접한 2칸이다($m_4, m_5$). 이 두 칸에서 $A$는 둘 다 1이라 남고, $B$는 둘 다 0이라 남으며, $C$는 0과 1이 섞여 소거된다. → 이 묶음은 $A\overline{B}$ 항이 된다.

두 묶음을 합치면 $m_0, m_2, m_4, m_5, m_6$이 모두 적어도 한 번씩 포함되어 모든 1이 커버된다(묶음 1이 $m_0,m_2,m_4,m_6$을 담당하고, 묶음 2가 $m_5$를 추가로 담당하며 $m_4$는 두 묶음에 겹쳐서 포함되는데, 겹치는 것은 허용된다).

4단계: 묶음들을 OR로 연결한다.

검산. 진리표의 $C=0$인 네 행($m_0,m_2,m_4,m_6$)을 보면 모두 $F=1$이므로 $\overline{C}$만으로 이 네 개가 정확히 설명된다. 남은 $m_5$($A=1,B=0,C=1$)는 $A\overline{B}=1\cdot1=1$로 설명되고, $m_1, m_3, m_7$($F=0$인 행)은 $\overline{C}$도 $A\overline{B}$도 만족하지 않는지 하나씩 확인하면 된다 — 예를 들어 $m_7=(1,1,1)$은 $C=1$이라 $\overline{C}=0$이고, $A=1$이지만 $B=1$이라 $\overline{B}=0$이므로 $A\overline{B}=0$, 합쳐서 $F=0$이 되어 진리표와 일치한다(검산 완료).

자주 틀리는 점

• 그레이 코드 순서 대신 보통 이진수 순서($00,01,10,11$)로 배열하면 이웃 칸이 2비트씩 차이 나서 잘못된 묶음이 나온다.
• 카르노 맵이 원통 구조라는 것을 잊고 맨 끝 행·열끼리는 인접하지 않는다고 착각한다.
• 묶음 크기는 반드시 $1, 2, 4, 8$처럼 2의 거듭제곱이어야 한다. 3칸이나 5칸으로는 묶을 수 없다.
• 묶음이 클수록 소거되는 변수가 많아지므로, 항상 가능한 가장 큰 묶음부터 찾아야 항의 개수가 최소가 된다.

핵심 정리

• AND는 곱, OR은 합, NOT은 부정이며, NAND·NOR은 각각 AND·OR 뒤에 NOT을 붙인 것이다. XOR은 두 입력이 다를 때만 1이다.
• 부울식의 AND·OR·NOT을 그대로 게이트로 바꿔 연결하면 회로가 되고, NAND 하나만으로 NOT·AND·OR을 모두 구현할 수 있다(만능 게이트).
• 카르노 맵은 그레이 코드 순서 격자에서 인접한 1을 2의 거듭제곱 크기로 묶어 논리식을 간소화하는 방법이며, 좌우·상하가 원통처럼 이어진다.

마무리 복습

참고 자료

• 국가평생교육진흥원 독학학위제 
• IEEE Standards Association