왜 카르노맵이 필요한가

09편에서 불 대수 법칙을 한 줄씩 적용해 논리식을 간소화하는 법을 배웠다. 하지만 이 방법에는 두 가지 약점이 있다. 첫째, 어떤 항끼리 묶어야 할지 스스로 판단해야 하므로 변수가 많아지면 시행착오가 늘어난다. 둘째, 지금 얻은 결과가 정말 더 이상 줄일 수 없는 최소형인지 확신하기 어렵다.

카르노맵(Karnaugh map, K-map)은 이 문제를 그림으로 해결한다. 진리표의 값을 특수한 순서로 배열된 격자에 옮겨 적으면, 어떤 항을 묶어야 하는지가 눈에 보이는 패턴으로 드러난다. 대수적 계산 없이 격자 위에서 사각형을 그리는 것만으로 10편에서 배운 표준 SOP를 최소형으로 바꿀 수 있다.

쉽게 말하면: 카르노맵은 진리표를 그림으로 바꿔서, 어떤 항끼리 묶어야 식이 짧아지는지 눈으로 바로 찾게 해주는 도구다.

카르노맵의 축은 왜 그레이 코드 순서인가

쉽게 말하면: 격자에서 옆으로 한 칸 움직이면 반드시 딱 1비트만 바뀌도록 만든 특수한 순서가 그레이 코드다.

카르노맵의 가로축·세로축은 그레이 코드(Gray code) 순서로 배열한다. 그레이 코드란 연속된 두 값 사이에 정확히 1비트만 달라지는 이진수 배열이다. 2비트 그레이 코드는 00, 01, 11, 10 순서다. 일반적인 이진수 순서인 00, 01, 10, 11과 다르다는 점이 핵심이다(01에서 10으로 넘어가면 두 비트가 동시에 바뀌므로 일반 순서는 카르노맵에 쓸 수 없다).

이렇게 배열하면 격자 위에서 물리적으로 붙어 있는 칸은 항상 논리적으로도 딱 1비트만 다르다. 두 최소항이 1비트만 다르다는 것은, 그 두 최소항을 OR로 묶었을 때 나머지 변수는 전부 같고 딱 그 1비트에 해당하는 변수만 $X+X'=1$(보수법칙)로 소거된다는 뜻이다. 즉 카르노맵에서 이웃한 두 칸을 묶는 행위는, 09편에서 손으로 했던 “공통 인수로 묶고 보수법칙을 적용하는” 대수적 과정을 그림으로 대신하는 것이다.

자주 틀리는 점: 순서를 헷갈림

• 가로축·세로축을 이진수 오름차순(00,01,10,11)으로 그리는 실수가 가장 흔하다. 이렇게 그리면 01과 10 칸이 옆에 붙어 있는데도 실제로는 2비트가 달라서, 그 두 칸을 묶으면 완전히 틀린 식이 나온다.
• 그레이 코드는 항상 대칭이다. 4개 값이면 앞의 절반(00,01)을 그대로 두고 뒤의 절반을 거꾸로 뒤집어 붙인 것(11,10)이라고 기억하면 외우기 쉽다.

카르노맵의 원통 구조

쉽게 말하면: 카르노맵은 평평한 표가 아니라, 좌우 끝과 상하 끝이 서로 붙어 있는 도넛(원통) 모양이라고 생각해야 한다.

그레이 코드 순서로 배열한 맨 끝 값과 맨 처음 값도 1비트만 다르다(2비트 그레이 코드에서 마지막 10과 처음 00은 1비트 차이). 그래서 카르노맵은 맨 왼쪽 열과 맨 오른쪽 열이 서로 인접하고, 맨 위 행과 맨 아래 행도 서로 인접한 것으로 취급한다. 종이에 그리면 평평해 보이지만 실제로는 좌우를 붙이면 원통이 되고, 그 원통의 위아래를 다시 붙이면 도넛(토러스, torus) 모양이 된다.

자주 틀리는 점: 원통 구조를 놓침

• 맨 왼쪽 열과 맨 오른쪽 열이 이웃이 아니라고 생각해 그 사이의 묶음을 놓치는 경우가 4변수 카르노맵에서 특히 자주 나온다. 네 모서리 칸이 모두 1이면, 이 네 칸도 하나의 유효한 4칸 묶음이다(원통·도넛 구조 덕분에 네 모서리가 서로 다 인접하기 때문이다).

2변수 카르노맵

2변수 함수는 $2\times2$ 격자로 그린다. 가로축은 $B$, 세로축은 $A$를 그레이 코드 순서(2변수는 그냥 0, 1 두 값뿐이라 순서 문제가 없다)로 놓는다.

각 칸에는 그 위치의 최소항 번호를 적어 두면 진리표와 맵을 대조하기 쉽다. $m_0=A'B'$, $m_1=A'B$, $m_2=AB'$, $m_3=AB$이다.

예제: F(A,B) = sum m(1,2,3)

결과 해석: $(1,1)$ 칸은 두 묶음(A행, B열)에 동시에 포함되었다. 카르노맵에서는 한 칸이 여러 묶음에 겹쳐 포함되어도 상관없다. 오히려 이렇게 겹치게 묶어야 각 묶음이 최대한 커져서 더 짧은 항이 나온다.

3변수 카르노맵

3변수는 $2\times4$ 격자로 그린다. 세로축에 변수 1개($A$), 가로축에 변수 2개($BC$)를 그레이 코드 순서(00,01,11,10)로 놓는다.

가로축이 00,01,11,10 순서이기 때문에 열 번호와 최소항 번호가 이진수 오름차순으로 나열되지 않는다는 점을 주의해야 한다($BC=10$ 열이 세 번째가 아니라 네 번째에 온다).

예제: F(A,B,C) = sum m(0,1,2,4,6)

결과 해석: 원래 SOP는 5개의 3변수 곱항이 필요했지만 최소형은 2개 항(하나는 리터럴 1개, 하나는 리터럴 2개)으로 줄었다. 이처럼 카르노맵은 가장 큰 사각형부터 우선 찾는 것이 요령이다. 작은 묶음(1칸)부터 찾으면 더 큰 묶음으로 합칠 기회를 놓치기 쉽다.

4변수 카르노맵

4변수는 $4\times4$ 격자로 그린다. 세로축에 $AB$, 가로축에 $CD$를 각각 그레이 코드 순서(00,01,11,10)로 놓는다.

4변수 맵에서는 원통 구조가 가로 방향과 세로 방향 모두에 적용된다. 맨 왼쪽 열과 맨 오른쪽 열이 인접하고, 맨 위 행과 맨 아래 행도 인접한다. 따라서 네 모서리 칸($m_0, m_2, m_8, m_{10}$)이 모두 1이면, 이 네 칸을 하나의 4칸 묶음으로 볼 수 있다(가로로 양 끝, 세로로 양 끝이 모두 붙어 있으므로).

예제: F(A,B,C,D) = sum m(0,2,5,7,8,10,13,15)

결과 해석: $F = B'D' + BD$는 사실 $B \oplus D$의 보수인 XNOR($B$와 $D$가 같을 때 1)와 정확히 같은 식이다(09편에서 배운 XNOR 진리표를 떠올려보면 $B'D'+BD$가 바로 그 식이다). 8개의 4변수 최소항이 단 두 개의 2변수 항으로 줄어드는, 카르노맵의 효과를 극적으로 보여주는 예제다.

손계산 절차 정리

자주 틀리는 점 총정리

• 묶음 크기는 반드시 1, 2, 4, 8, 16처럼 2의 거듭제곱이어야 한다. 3칸이나 5칸, 6칸으로 묶으면 안 된다.
• 큰 묶음을 놓치고 작은 묶음(1칸, 2칸)으로만 답을 내면 표준형에 가까운 형태가 나와 최소형이 아니게 된다. 항상 가장 큰 사각형부터 시도해야 한다.
• 한 칸이 여러 묶음에 겹쳐 포함되는 것은 정상이며 오히려 권장된다. 겹치지 않게 나누려다 묶음 크기를 줄이는 것이 오히려 실수다.
• 4변수 맵에서 네 모서리, 또는 위아래 두 행이나 좌우 두 열이 원통 구조로 인접한다는 것을 놓치는 경우가 매우 흔하다. 표의 물리적 배치만 보지 말고 항상 “그레이 코드 순서상 1비트 차이인가”를 기준으로 판단해야 한다.

핵심 정리

• 카르노맵은 그레이 코드 순서(00,01,11,10)로 배열한 격자이며, 물리적으로 인접한 칸은 항상 논리적으로 1비트만 다르다는 성질을 이용해 최소항을 묶는다.
• 카르노맵은 좌우·상하가 서로 이어진 원통(도넛) 구조이며, 4변수 맵에서는 네 모서리 칸도 서로 인접한 것으로 취급한다.
• 손계산 절차는 진리표 옮기기 → 가장 큰 사각형(2의 거듭제곱 크기)부터 묶기 → 모든 1을 커버할 때까지 반복 → 변하지 않는 변수만 남기기 → OR(또는 AND)로 합치기의 순서로 진행한다.

마무리 복습

참고 자료

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