직관 — 답이 하나만 다른 카드끼리 옆에 놓는다
네 가지 예·아니오 질문에 답한 카드 열여섯 장을 4×4 판에 늘어놓는다고 하자. 옆 칸의 카드끼리 답이 딱 하나만 다르게 놓으면, 붙은 두 장에 공통인 답은 나머지 세 개다. 판의 맨 왼쪽과 맨 오른쪽, 맨 위와 맨 아래도 답이 하나만 다르게 놓아서, 판을 둥글게 말아 붙인 것처럼 이웃으로 센다.
질문 하나가 부울 변수 하나, 카드 한 장이 입력 하나를 나타내는 칸이다. 붙은 칸들에 공통인 답만 남긴 곱이 그 칸들을 한꺼번에 나타내는 묶음의 식이다.
논리 회로에서는 3변수 카르노 맵으로 다수결 회로를 줄였다. 이 글은 같은 방법을 2변수와 4변수로 넓히고, 맨 위·맨 아래가 이웃인 이유와 겹쳐 묶기, 출력이 정해지지 않은 칸까지 다룬다. 식이 짧아지면 그 식으로 만든 회로의 게이트도 줄어든다.
카르노 맵은 이웃한 칸이 한 변수만 다르게 배치한 진리표다
카르노 맵(Karnaugh map, 줄여서 K-map)은 부울 함수의 진리표를 바둑판 모양으로 다시 배치해, 위아래·좌우로 붙은 칸끼리 입력이 한 변수만 다르게 만든 표다. 출력이 1인 칸에 1을 적고, 붙은 1을 묶어 곱의 합을 간소화한다. 카르노가 1953년에 제안했고, 보통 변수가 4개 이하일 때 쓴다.
붙은 두 칸이 하나로 줄어드는 까닭은 두 칸이 한 변수만 다르기 때문이다. 두 칸에 공통인 변수들의 곱을 , 두 칸에서 값이 다른 변수를 라 하자.
첫 등호는 분배법칙, 둘째 등호는 역법칙 과 항등법칙이다. 묶음이 커져도 같은 일이 되풀이된다. 묶음 안에서 0과 1을 모두 갖는 변수는 사라지고, 값이 하나로 정해진 변수만 곱으로 남는다.
| 기호 | 이름 | 원어 | 뜻 |
|---|---|---|---|
| 부울 변수 | Boolean variables | 맵의 행과 열 머리에 놓는 입력 | |
| 부울 함수 | Boolean function | 간소화할 출력 | |
| 공통인 곱 | common product | 붙은 칸들에서 값이 같은 변수들의 곱 | |
| 바뀌는 변수 | changing variable | 붙은 두 칸에서 값이 다른 변수 | |
| 변수의 개수 | number of variables | 맵의 칸은 개 | |
| 묶음의 칸 수 | group size | 한 묶음에 든 칸의 개수 | |
| 사라지는 변수의 개수 | eliminated variables | ||
| 남는 문자 수 | literals | 묶음의 곱에 남는 변수의 개수 |
교과서는 2변수에 , 3변수에 , 4변수에 를 쓴다. 이 글은 부울 함수와 논리 회로 글처럼 앞에서부터 를 쓰고, 보수는 윗줄로 나타낸다.
2변수 맵은 행에 와 , 열에 와 를 놓은 2×2 표다. 칸마다 행과 열의 곱이 들어간다.
식 (2)를 간소화해 보자.
세 항의 칸에 1을 적으면 다음과 같다. 윗줄 두 칸은 만 다르므로 묶으면 , 오른쪽 열 두 칸은 만 다르므로 묶으면 다. 칸은 두 묶음에 함께 들어간다.
| 1 | 1 | |
| 1 |
곱의 합에 나오는 변수 글자를 보수까지 모두 센 것을 문자 수라 하자. 식 (2)의 문자 6개가 식 (3)에서 2개로 줄었다.
2·3·4변수 카르노 맵은 어떻게 그리나
변수가 개면 칸이 개이므로 2변수는 2×2, 3변수는 2×4, 4변수는 4×4 표다. 두 변수를 한 머리에 놓을 때는 값을 11, 10, 00, 01 순서로 적는다.
| 변수 개수 | 행 머리 | 열 머리 | 칸 수 |
|---|---|---|---|
| 2 | 4 | ||
| 3 | 8 | ||
| 4 | 16 |
11, 10, 00, 01은 이웃한 두 값이 한 자리만 다르고, 끝의 01과 처음의 11도 한 자리만 다르다. 이렇게 이웃끼리 한 자리씩만 바뀌는 순서를 그레이 코드(Gray code)라 한다. 이진수 크기 순서 11, 10, 01, 00으로 적으면 가운데 10과 01이 두 자리가 다르다. 그러면 붙은 두 칸 와 를 묶어도 곱 하나가 되지 않는다. 둘에 공통인 는 네 칸을 뜻하기 때문이다.
그림 1은 4변수 맵의 칸마다 입력 를 적은 것이다. 행 머리가 의 값을, 열 머리가 의 값을 정한다. 예를 들어 둘째 행 넷째 열은 와 가 만나 1001이다.
figures/kmap_layout.py카르노 맵에서 맨 위·맨 아래와 양 끝은 왜 이웃인가
끝의 01에서 처음의 11로 돌아갈 때도 한 변수만 바뀌기 때문이다. 그래서 4변수 맵은 위아래와 좌우를 말아 붙인 고리처럼 읽고, 모든 칸이 정확히 네 칸과 이웃한다. 그림 1의 1111은 같은 행 맨 끝의 1101과 만, 같은 열 맨 아래의 0111과 만 다르다.
네 모서리 1111, 1101, 0111, 0101도 서로 이웃해 2×2 직사각형 하나가 된다. 네 칸 모두 , 이고, 와 는 0과 1을 다 가지므로 묶음의 곱은 다.
칸마다 이웃이 넷인 것은 변수 넷 가운데 하나만 바꾼 입력이 넷이기 때문이다. 3변수 맵은 위 이웃과 아래 이웃이 같은 칸이라 이웃이 셋이다. 변수가 다섯이면 칸마다 이웃이 다섯이어야 하는데, 바둑판의 칸에는 상하좌우 넷뿐이다. 그래서 카르노 맵은 보통 4변수까지 쓴다.
카르노 맵의 묶음은 왜 2의 거듭제곱 개 칸의 직사각형인가
묶음 안에서 사라질 변수들이 0과 1의 모든 조합을 한 번씩 가져야 곱 하나로 줄기 때문이다. 변수 개의 조합은 가지이므로 묶음은 칸이고, 곱에는 나머지 개의 변수가 남는다.
그림 2는 4변수 맵에서 8칸, 4칸, 2칸, 1칸 묶음이 각각 문자 1개, 2개, 3개, 4개인 곱이 되는 모습이다. 8칸 묶음 는 맨 위 행과 맨 아래 행을 잇는다. 맵 전체 16칸이 1이면 , 이라 이다.
figures/group_sizes.py직사각형이어야 하는 것도 같은 이유다. 행 쪽에서 이어진 1·2·4줄, 열 쪽에서 이어진 1·2·4칸을 고른 직사각형만 바뀌는 변수의 조합을 빠짐없이 한 번씩 담는다. 거꾸로 곱 하나가 뜻하는 칸들은 늘 이런 직사각형 하나다. 묶음이 클수록 곱이 짧으므로, 1마다 그 1을 담고 더 키울 수 없는 직사각형을 찾는다.
4변수 카르노 맵 간소화 순서 — 겹쳐 묶어야 짧아진다
카르노 맵으로 간소화할 때는 더 키울 수 없는 묶음을 모두 찾고, 그런 묶음 하나에만 들어가는 1부터 묶은 뒤, 남은 1을 가장 큰 묶음으로 덮는다. 이미 묶은 1을 다시 써서 묶음이 커지면 겹쳐 묶고, 다른 묶음들에 다 덮인 묶음은 지운다.
- 식의 항마다 해당하는 칸에 1을 적는다. 4변수 맵에서 문자가 셋인 곱은 2칸, 둘인 곱은 4칸이다.
- 각 1에 대해, 그 1을 담고 1만 든 묶음(칸 수가 2의 거듭제곱인 직사각형) 가운데 더 키울 수 없는 것을 모두 찾는다.
- 그런 직사각형 하나에만 들어가는 1부터 그 직사각형을 고른다.
- 남은 1을 되도록 적은 수의 큰 묶음으로 덮는다. 이미 묶인 칸을 다시 써도 된다. 고르는 방법이 여럿이면 묶음 수를, 그다음 문자 수를 비교한다. 3단계에서 고를 묶음이 없으면 첫 묶음을 바꿔 가며 결과를 견준다.
- 칸이 모두 다른 묶음들에 이미 덮인 묶음을 지운다.
- 묶음마다 바뀌지 않는 변수의 곱을 쓰고 부울 합으로 잇는다.
대표 예제로 식 (5)를 간소화하자.
는 셋째 행의 , 두 칸이고, 는 둘째 행의 같은 두 칸이다. 는 네 모서리, 는 가운데 두 행의 칸이다. 1은 모두 10칸이다.
그림 3에서 열과 열은 양 끝이라 이웃하고, 두 열의 8칸이 모두 1이다. 이 8칸에서 바뀌지 않는 변수는 뿐이므로 곱은 다. 남은 1은 1000과 0000 두 칸이다. 이 둘을 오른쪽 이웃 1001, 0001과 겹쳐 2×2로 묶으면 다.
figures/overlap_example.py겹치지 않게 1000과 0000만 묶으면 로 문자가 하나 더 붙는다. 겹쳐 묶은 덕분에 식 (5)의 문자 11개가 식 (6)에서 3개로 줄었다.
부울 대수 법칙으로도 같은 결과가 나오는지 확인하자. 식 (5)의 첫째·둘째 항은 만 다르므로 식 (1)로 묶인다.
셋째·넷째 항은 로 묶은 뒤, 괄호 안을 분배법칙의 첫 꼴과 역법칙으로 정리한다. 논리 회로 글의 식 (4)와 같은 계산이다.
여기서 로 멈추기 쉽다. 문자가 6개이고, 한 변수만 다른 두 항이 더는 보이지 않기 때문이다. 마지막 걸음은 드모르간의 법칙으로 가 의 보수임을 알아보는 것이다. 로 놓으면 식 (8)과 같은 꼴의 법칙 를 쓸 수 있다.
법칙으로는 어떤 항을 어떻게 묶을지 직접 찾아야 한다. 맵에서는 8칸 묶음 가 한눈에 보인다.
카르노 맵에서 가장 큰 묶음부터 고르면 왜 묶음이 남을 수 있나
가장 큰 묶음이 다른 꼭 필요한 묶음들로 이미 다 덮일 수 있기 때문이다. 그림 4의 가운데 4칸 는 가장 큰 묶음이지만, 바깥의 1 네 칸을 덮는 2칸 묶음 넷이 가운데 4칸도 모두 덮는다.
바깥의 1110은 이웃 가운데 1이 1010 하나뿐이어서 로만 묶인다. 1001, 0100, 0011도 각각 , , 로만 묶인다. 가운데 묶음을 먼저 고르면 묶음 5개, 문자 14개가 된다. 가운데 묶음을 빼면 묶음 4개, 문자 12개다.
figures/redundant_group.py그래서 간소화 순서의 셋째 단계는 가장 큰 묶음이 아니라, 더 키울 수 없는 묶음 하나에만 들어가는 1에서 시작한다. 가운데 1010은 와 두 묶음에 들어가므로 셋째 단계에서 고르지 않는다. 1000, 0000, 0010도 각각 와 2칸 묶음 하나에 함께 들어간다. 바깥 1의 2칸 묶음 넷을 고르면 가운데 4칸까지 덮이므로 넷째 단계에서 더 고를 묶음이 없다. 넷째 단계에서 고른 묶음이 뒤에 고른 묶음들에 다 덮이면 다섯째 단계에서 지운다.11 필요 없는 묶음이 쓸모없기만 한 것은 아니다. 실제 회로에서는 입력이 바뀌는 순간 출력이 잠깐 튀는 일을 막으려고 이런 묶음을 일부러 남기기도 한다.
카르노 맵의 X 칸(무관 조건)은 어떻게 묶나
들어올 일이 없거나 출력이 무엇이든 괜찮은 입력을 무관 조건(don't care)이라 하고, 맵에 X로 적는다. X는 묶음이 커질 때만 1로 보고, 필요 없으면 0으로 본다. 교과서 예제에는 없는 확장이지만, 맵을 회로 설계에 쓸 때 자주 만난다.
0부터 9까지의 수를 네 자리 이진수 로 받아, 5 이상이면 1을 내는 회로를 생각하자. 1010부터 1111까지, 곧 10부터 15까지는 입력으로 들어오지 않으므로 X다. 1은 0101, 0110, 0111, 1000, 1001의 다섯 칸이다.
그림 5에서 X를 1로 보면 위 두 행 8칸이 , 네 모서리가 , 맨 위·맨 아래 행의 왼쪽 두 칸씩이 로 묶인다.
figures/dont_care_digits.pyX를 모두 0으로 보면 가장 큰 묶음이 2칸이어서 다음과 같다.
0부터 9까지의 열 입력에서 식 (10)과 식 (11)의 출력은 같다. 문자 수는 9개에서 5개로 준다.
카르노 맵은 행과 열을 한 변수씩만 바뀌는 순서로 놓아 맨 위·맨 아래와 양 끝도 이웃이 되므로, 네 모서리까지 포함해 1을 2의 거듭제곱 개 칸의 직사각형으로 겹쳐 묶으면 묶음 안에서 바뀌는 변수가 사라진다.
카르노 맵에서 대각선으로 붙은 1도 한 묶음으로 묶을 수 있나요?
아니다. 카르노 맵에서 대각선으로 붙은 두 칸은 두 변수가 달라서 곱 하나로 줄지 않는다. 그림 1의 1111과 1010은 와 가 다르고, 둘에 공통인 는 1110, 1011까지 네 칸을 뜻한다. 대각선의 두 1은 각자 다른 이웃과 묶거나 따로 쓴다.
카르노 맵의 행과 열을 00, 01, 11, 10 순서로 그려도 되나요?
그렇다. 카르노 맵을 00, 01, 11, 10 순서로 그려도 이웃한 두 값과 끝의 10·처음의 00이 한 자리만 달라서, 같은 함수에서 같은 간소화 결과가 나온다. 칸의 자리만 달라져서 그 순서에서는 네 모서리가 다. 교과서와 논리 회로 글은 11, 10, 00, 01 순서를 쓴다.
카르노 맵으로 간소화한 답이 해설과 다르면 틀린 건가요?
아니다. 가장 짧은 곱의 합이 둘 이상인 함수가 있어서, 카르노 맵의 답이 해설과 달라도 맞을 수 있다. 출력이 1인 입력이 000, 001, 010, 101, 110, 111인 3변수 함수는 와 가 모두 문자 6개인 가장 짧은 꼴이다. 진리표의 여덟 행에서 출력이 같은지 대조하면 같은 함수인지 확인된다. 가장 짧은 꼴인지는 묶음 수와 문자 수가 해설과 같은지로 따로 확인한다. 예를 들어 도 같은 함수지만 문자가 8개라 가장 짧은 꼴이 아니다.
카르노 맵의 흔한 오해
- ㅜ 모양으로 이어진 1 네 칸은 한 묶음이다 — 그림 1의 1111, 1110, 1100, 1010은 ㅜ 모양으로 이어진 4칸이다. 네 칸에서 바뀌지 않는 변수는 뿐인데, 는 위 두 행의 8칸을 뜻한다. 직사각형이 아니면 칸 수가 2의 거듭제곱이어도 곱 하나가 되지 않는다.
- 묶음을 키우려고 0인 칸을 넣어도 된다 — 그림 3에서 가운데 두 행 8칸을 로 묶으면 0인 1010과 0010이 들어간다. 그러면 는 식 (5)에서 출력이 0인 입력 1010에서 1을 낸다. X가 아닌 0 칸은 묶음에 넣지 않는다.
직접 해보기
- 2변수 함수 를 2변수 맵에 적고 간소화하자.
- 3변수 함수의 출력이 입력 000, 001, 100, 101, 110에서만 1이다. 논리 회로 글과 같은 3변수 맵 배치로 간소화하자.
- 4변수 맵에서 네 모서리 칸과 가운데 2×2의 네 칸만 1이다. 간소화하고, 출력이 1인 입력의 공통점을 말로 쓰자.
- 를 곱의 합으로 펼쳐 4변수 맵에 적고 간소화하자. 결과를 분배법칙으로 확인하자.
- 0부터 9까지의 수를 로 받아 4 이상이면 1을 내는 함수를, X를 1로 쓸 수 있을 때와 X를 모두 0으로 볼 때 각각 간소화하자.
답과 풀이
- 는 아랫줄 두 칸, 는 윗줄 오른쪽 칸이다. 아랫줄을 묶으면 , 오른쪽 열을 묶으면 이고, 칸을 겹쳐 쓴다. 다.
- 1은 열과 열의 두 행 4칸, 그리고 행 칸의 110이다. 4칸을 묶으면 다. 110은 오른쪽 이웃 100과 겹쳐 묶어 가 된다. 다.
- 네 모서리는 , 가운데 네 칸은 · 행과 · 열이 만나는 곳이라 다. 이고, 와 의 값이 같을 때 1이다.
- 펼치면 이고, 1은 인 위·아래 행 8칸과 열의 가운데 두 칸으로 10칸이다. 맨 위·맨 아래 행을 이어 , 열 4칸을 겹쳐 묶어 다. 분배법칙의 첫 꼴로 가 되어 맞다.
- 1은 4부터 7까지인 맨 아래 행 4칸과 1000, 1001이다. X를 쓰면 위 두 행 8칸이 , 맨 위·맨 아래 행 8칸이 라 로 문자 2개다. X를 0으로 보면 맨 아래 행의 와 1000·1001의 로 , 문자 5개다.
더 읽기
- The map method for synthesis of combinational logic circuits — M. Karnaugh, 1953. Transactions of the AIEE, Part I, 72(5), 593–599. 카르노 맵을 처음 제안한 논문이다. 제목·저자·연도는 Crossref 서지로 확인했고, 정의 §의 제안 연도가 기댄다.
- MIT OCW 6.004 Computation Structures, 4.2.5 Karnaugh Maps — Chris Terman, 2017. 강의 자막에서 그레이 코드 순서, 양 끝이 이어진 표, 한 변이 1·2·4칸인 묶음, 필요 없는 묶음을 빼는 것과 가장 짧은 꼴이 하나가 아닐 수 있음을 확인했다. ‘가장 큰 묶음부터 고르면 왜 묶음이 남을 수 있나’ §와 해설과 답이 다른 경우의 질문이 기댄다.
- 우리교과서, 2022 이산 수학 — 112~116쪽 ‘카르노 맵’. 2·3·4변수 맵의 행·열 순서, 위아래·양 끝 인접, 2의 거듭제곱 개 칸의 직사각형 묶기를 대조했다.
영상 노트
- 00:00 카드 열여섯 장을 답이 하나만 다르게 늘어놓기
- 00:50 식 (1)로 붙은 두 칸이 하나로 주는 이유
- 01:40 2변수 맵에서 식 (2)를 식 (3)으로, 겹쳐 묶기 첫 장면
- 02:40 2·3·4변수 맵의 머리 순서 11, 10, 00, 01과 이진수 순서의 반례
- 03:40 그림 1에서 1111의 이웃 넷과 네 모서리
- 04:40 식 (4)와 그림 2, 묶음 칸 수와 남는 문자 수
- 05:40 여섯 단계 순서와 식 (5)를 그림 3으로 식 (6)까지
- 07:00 식 (7)~(9)로 같은 결과를 법칙으로 확인
- 08:10 그림 4의 필요 없는 묶음
- 09:00 그림 5의 X 칸과 식 (10)·(11) 비교
지도에서의 위치
- 2026-11-17 · 에이전트 초안 — 전수 검수에서 분리 제안된 유형
- 2026-11-17 · 전수 검수 반영 — 2·3·4변수 맵의 배치와 그레이 코드 순서, 위아래·양 끝 인접과 네 모서리 묶음, 묶음의 칸 수와 남는 변수, 겹쳐 묶는 4변수 예제와 법칙 풀이의 대조, 필요 없는 묶음, 무관 조건 한 예, 질문 셋·오해 둘·해보기 다섯을 채우고 부모 글에서 링크함. 간소화 순서를 더 키울 수 없는 묶음 기준과 덮인 묶음 지우기 단계로 바로잡고, 필요 없는 묶음 그림에 곱을 적고 작은 글자를 키움 (에이전트 수정, 그림 0→5)
- 2026-11-17 · 전수 검수(에이전트 편집·독립 검증) 통과 — 주인 요청으로 완성으로 올림