카르노 맵

1. 카르노 맵이란

카르노 맵은 진리표를 격자로 다시 그린 것입니다. 1953년 벨 연구소의 모리스 카르노가 스위칭 회로를 눈으로 보고 간소화하려고 고안했으며, 작은 불 함수를 손으로 최소화하는 가장 빠른 방법으로 여전히 쓰입니다. 대수도, 외울 법칙도 필요 없고 직사각형만 있으면 됩니다.

맵의 각 칸은 진리표의 한 행을 담습니다. 단순한 재배열 이상으로 만들어 주는 것은 그 행들을 놓는 순서입니다. 서로 붙어 있는 칸은 정확히 한 변수만 다릅니다.

이 성질 하나가 모든 일을 합니다. 이웃한 두 칸이 모두 참이라면, 그 사이에서 값이 바뀌는 변수는 식을 참으로 만드는 원인일 수 없습니다. 그래서 그 변수는 사라지고 하나의 항이 두 칸을 함께 덮습니다. 간소화란 결국 가능한 한 큰 직사각형을 그리는 일이 됩니다.

2. 열 순서가 이상해 보이는 이유

카르노 맵의 열은 00, 01, 10, 11로 세지 않습니다. 00, 01, 11, 10으로 갑니다. 이웃한 값이 한 비트만 다른 반사 그레이 코드입니다. 이진수 순서대로 세면 01 옆에 10이 오는데, 둘은 두 비트가 다르므로 이웃한 칸에서 아무것도 읽어 낼 수 없습니다.

가장자리끼리도 이웃입니다. 맨 왼쪽 열과 맨 오른쪽 열은 한 변수만 다르고, 맨 위 행과 맨 아래 행도 마찬가지여서, 묶음이 한쪽 끝을 넘어 반대쪽에서 이어질 수 있습니다. 네 변수 맵의 네 모서리가 한 묶음이 되는 것도 그 때문입니다. 카르노 맵은 사실 원환면 위에 그려져 있고, 평평한 종이는 편의일 뿐입니다.

3. 1을 묶기

맵에서 최소 곱의 합을 읽어 내려면 1이 있는 칸을 모두 직사각형 묶음으로 덮습니다. 규칙은 네 가지입니다.

• 묶음은 1, 2, 4, 8 … 칸의 직사각형이며, 각 변의 길이는 2의 거듭제곱입니다.
• 묶음은 맵의 가장자리를 넘어 가로로, 세로로, 또는 양쪽으로 감쌀 수 있습니다.
• 묶음끼리 겹쳐도 됩니다. 한 칸을 두 번 덮어도 손해가 없지만, 덮지 않고 남기면 함수가 달라집니다.
• 각 묶음은 최대한 크게 만들고, 그런 다음 모든 1을 덮을 수 있는 가장 적은 수의 묶음을 씁니다.

묶음 하나가 항 하나가 됩니다. 읽는 방법은 묶음 전체에서 값이 그대로인 변수를 찾는 것입니다. 그 변수들이 항에 들어가고(1이면 그대로, 0이면 부정), 값이 바뀌는 변수는 모두 사라집니다. 두 칸짜리 묶음은 변수 하나를, 네 칸은 둘을, 여덟 칸은 셋을 잃습니다. 최소 식은 이 항들의 논리합입니다.

4. 예제 풀이

(A ∧ B) ∨ (¬A ∧ C) ∨ (B ∧ C ∧ D)를 봅시다. 맵은 네 변수이고 행이 A와 B, 열이 C와 D입니다.

두 묶음이 모든 1을 덮습니다. 하나는 A = 0인 두 행과 C = 1인 두 열이 만나는 네 칸 블록입니다. 그 안에서 B와 D가 모두 바뀌므로 사라지고 항은 ¬A ∧ C가 됩니다. 다른 하나는 A와 B가 모두 1인 행 전체로, 네 열에 걸쳐 있습니다. C와 D가 그 행을 따라 바뀌므로 A ∧ B가 남습니다.

따라서 최소 형태는 (¬A ∧ C) ∨ (A ∧ B)입니다. 원래 식의 셋째 항 B ∧ C ∧ D는 사라졌습니다. 그 항이 덮던 칸은 이미 두 묶음 가운데 하나가 덮고 있었기 때문입니다. 눈으로 볼 수 있게 그린 흡수법칙이 바로 이것입니다.

5. 주 함의와 필수 주 함의

더 크게 만들 수 없는 묶음을 주 함의(프라임 임플리컨트)라고 합니다. 주 함의를 모두 나열하는 것은 문제의 쉬운 절반이고, 그중 무엇을 남길지 고르는 것이 어긋나기 쉬운 절반입니다.

어떤 칸을 덮는 주 함의가 단 하나뿐이라면 그 주 함의는 필수입니다. 그 칸을 덮는 것이 달리 없으므로 어떤 최소 형태에서도 뺄 수 없습니다. 필수 주 함의를 먼저 고르고, 남은 칸은 나머지 묶음 가운데 가능한 한 적은 수로 덮습니다.

탐욕적으로, 즉 매번 남아 있는 가장 큰 묶음을 고르는 방법은 솔깃하지만 늘 통하지는 않습니다. 어떤 주 함의도 필수가 아니고 모든 칸이 두 번씩 덮이는 순환 표에서는 탐욕적 선택이 최선의 답보다 항이 하나 더 많아질 수 있습니다. 이 사이트의 맵은 대신 남은 선택지를 모두 탐색하며, 네 변수에서는 그 비용이 사실상 없습니다.

6. 대신 0을 묶기

위의 모든 내용은 0에도 똑같이 적용됩니다. 같은 직사각형으로 0을 덮고, 각 묶음을 리터럴을 부정해서 읽으며(묶음 전체에서 1인 변수는 부정으로, 0인 변수는 그대로), 묶음들을 ∨ 대신 ∧로 잇습니다.

결과는 합의 곱입니다. 논리합들의 논리곱으로, 식이 거짓인 칸에서 정확히 거짓이 되고 나머지 모든 곳에서 참이 됩니다. 어느 형태가 더 짧은지는 함수에 달려 있습니다. 1이 적은 식은 곱의 합이 짧고, 0이 적은 식은 합의 곱이 짧으므로, 고르기 전에 맵에서 둘 다 읽어 보는 편이 좋습니다.

7. 더 큰 맵과 무관 조건

다섯 변수와 여섯 변수는 네 변수 맵을 둘 또는 넷 겹쳐 그리고, 이웃한 층의 같은 위치 칸을 인접한 것으로 셉니다. 되기는 하지만, 이 방법을 눈에 보이게 만들어 주던 인접성이 이제는 보는 것이 아니라 외우는 것이 됩니다. 그 이상에서는 콰인-매클러스키 알고리즘이 표의 형태로 같은 일을 합니다. 바로 이 묶기를 기계화한 것이며, 이 사이트의 맵 뒤에서 돌아가는 것도 그것입니다.

하드웨어 설계에는 개념이 하나 더 있습니다. 어떤 입력 조합은 결코 나타나지 않아서 - 이진화 십진수 자리는 1010이 될 수 없습니다 - 회로가 그 입력에 무엇을 내놓든 설계자는 상관하지 않습니다. 그런 칸은 X로 표시하고 묶음을 더 크게 만드는 쪽 값으로 읽어도 됩니다. 이 계산기의 맵은 식에서 만들어지고 모든 할당에 값이 있으므로, 무관 조건인 칸은 없습니다.

8. 직접 해 보기

두 변수에서 네 변수까지의 식을 계산기에 입력하면 진리표 아래에 맵이 그려지고, 각 묶음이 저마다의 색으로 둘러싸이며 그 아래에 최소 형태가 적힙니다. 합의 곱으로 바꾸면 0이 묶이는 모습을 볼 수 있습니다.