카르노맵(K-Map) 완벽 정리 및 불 대수 논리식 간소화 기법

1. 카르노맵(Karnaugh Map)이란?

카르노맵(줄여서 K-Map)은 미국의 통신공학자 모리스 카르노(Maurice Karnaugh)가 고안한 그래픽 기반의 불 대수(Boolean Algebra) 간소화 도구입니다.

진리표(Truth Table)나 불 대수 공식을 이용해 논리식을 정리할 때 가장 큰 문제는 식의 전개 과정이 복잡하고, 드모르간 법칙이나 분배 법칙을 적용하다가 실수하기 쉽다는 점입니다. 카르노맵은 2차원 표의 기하학적 인접성을 활용하여 논리식의 인접 항( $A + \overline{A} = 1$ )을 눈으로 바로 찾아내어 최적의 최소화 식을 직관적으로 도출할 수 있도록 돕습니다.

2. 카르노맵의 핵심 원리: 그레이 코드(Gray Code) 배치

카르노맵의 행과 열 레이블을 작성할 때 일반적인 이진수 순서( $00 \rightarrow 01 \rightarrow 10 \rightarrow 11$ )를 쓰지 않고, 반드시 **그레이 코드 순서( $00 \rightarrow 01 \rightarrow 11 \rightarrow 10$ )**로 배열합니다.

이유: 기하학적으로 이웃한 칸(Cell)끼리는 오직 1개의 변수만 값이 달라져야( $0 \leftrightarrow 1$ ) 공통 인수를 묶어 변수를 소거( $X\overline{Y} + XY = X(\overline{Y} + Y) = X$ )할 수 있기 때문입니다.
순환성(Torus 구조): 표의 맨 왼쪽 열과 맨 오른쪽 열, 맨 위쪽 행과 맨 아래쪽 행 역시 오직 1개 비트만 차이가 나므로 양 끝단끼리 원통처럼 말려서 서로 맞닿아 있는 인접한 칸으로 취급합니다.

3. 변수별 카르노맵 구조 및 민텀(Minterm) 번호

시험에서는 3변수( $2^3 = 8\text{칸}$ )와 4변수( $2^4 = 16\text{칸}$ ) 카르노맵이 주로 출제됩니다. 각 칸의 십진 민텀 번호( $m_0 \sim m_{15}$ ) 위치를 암기해 두면 진리표를 빠르게 옮겨 적을 수 있습니다.

1) 3변수 카르노맵 ( $A, B, C$ )

행: $A$ ( $0, 1$ )
열: $BC$ ( $00, 01, 11, 10$ )

$A \backslash BC$	00	01	11	10
0	$m_0$ ( $000$ )	$m_1$ ( $001$ )	$m_3$ ( $011$ )	$m_2$ ( $010$ )
1	$m_4$ ( $100$ )	$m_5$ ( $101$ )	$m_7$ ( $111$ )	$m_6$ ( $110$ )

(주의: 3번째 열이 $m_3$ , 4번째 열이 $m_2$ 로 자리가 바뀝니다.)

2) 4변수 카르노맵 ( $A, B, C, D$ )

행: $AB$ ( $00, 01, 11, 10$ )
열: $CD$ ( $00, 01, 11, 10$ )

$AB \backslash CD$	00	01	11	10
00	$m_0$	$m_1$	$m_3$	$m_2$
01	$m_4$	$m_5$	$m_7$	$m_6$
11	$m_{12}$	$m_{13}$	$m_{15}$	$m_{14}$
10	$m_8$	$m_9$	$m_{11}$	$m_{10}$

(주의: 행과 열 모두 3번째와 4번째 줄의 순서가 뒤바뀝니다. 3번째 행은 $11(12, 13, 15, 14)$ 이고, 4번째 행이 $10(8, 9, 11, 10)$ 입니다.)

4. 카르노맵 묶기(Grouping) 6대 절대 규칙

논리식을 가장 간단한 최소항의 합(SOP)으로 유도하기 위해 1들을 묶을 때 지켜야 할 규칙입니다.

$2^n$ 단위로 묶기: 묶음의 크기(칸 수)는 반드시 $1, 2, 4, 8, 16$ 개 중 하나여야 합니다. (3개나 6개짜리 직사각형은 묶을 수 없습니다.)
무조건 직사각형 또는 정사각형: 대각선 묶음이나 L자, T자 모양은 절대 불가능하며, 오직 직선 형태의 직사각형 또는 정사각형만 허용됩니다.
가능한 한 크게 묶기: 묶음의 크기가 클수록 소거되는 변수의 개수가 많아져 최종 곱항이 간단해집니다.
- 2개 묶음: 변수 1개 소거
- 4개 묶음: 변수 2개 소거
- 8개 묶음: 변수 3개 소거
- 16개 묶음: 모든 변수 소거 ( $F = 1$ )
외곽 및 모서리 순환 활용:
- 좌우 끝 열 묶기: 1열과 4열을 나란히 붙여서 묶을 수 있습니다.
- 상하 끝 행 묶기: 1행과 4행을 나란히 붙여서 묶을 수 있습니다.
- 4개 모서리 묶음: $m_0, m_2, m_8, m_{10}$ 4개의 꼭짓점은 하나의 4개짜리 정사각형 묶음이 되어 $\overline{B}\,\overline{D}$ 로 간소화됩니다 (가장 빈출되는 함정).
중복 허용: 이미 다른 묶음에 포함된 1이라도, 아직 묶이지 않은 다른 1을 더 크게 묶어주기 위해서라면 얼마든지 중복해서 포함시킬 수 있습니다.
잉여 묶음(Redundant Group) 제거: 모든 1이 이미 다른 묶음들에 의해 각각 커버되었다면, 그들로만 이루어진 불필요한 추가 묶음은 반드시 버려야 합니다. (필수 주항, Essential Prime Implicant만 남기기)

5. SOP(최소항의 합) vs POS(최대항의 곱) 간소화

구분	SOP (Sum of Products, 최소항의 합)	POS (Product of Sums, 최대항의 곱)
표기법	$F = \sum m(1, 3, 5, 7)$	$F = \prod M(0, 2, 4, 6)$
묶는 대상	카르노맵 상의 1들을 묶음	카르노맵 상의 0들을 묶음
게이트 구성	AND-OR 2단 논리 회로 (또는 NAND-NAND)	OR-AND 2단 논리 회로 (또는 NOR-NOR)
문자 표기 규칙	변수 값이 $1 \rightarrow X$ , 변수 값이 $0 \rightarrow \overline{X}$	변수 값이 $0 \rightarrow X$ , 변수 값이 $1 \rightarrow \overline{X}$ (반대)
풀이 요령	시험 문제의 80% 이상이 SOP를 요구	0의 개수가 1의 개수보다 훨씬 적을 때 POS로 풀면 훨씬 빠름

6. 무관 조건(Don’t Care, $d$ 또는 $X$ )의 활용 전략

BCD 코드처럼 10진수 $0 \sim 9$ 까지만 사용하고 $10 \sim 15$ 는 입력으로 들어올 수 없는 회로에서는 해당 입력 조합의 출력을 0으로 두든 1로 두든 상관이 없습니다. 이를 **무관 조건(Don’t Care)**이라고 하며 기호 $d$ 또는 $X$ 로 표시합니다.

전략적 포함: 무관 조건( $X$ )은 1을 더 크게 묶을 수 있는 경우에만 1로 취급하여 묶음에 포함시킵니다.
배제: 1을 크게 묶는 데 도움이 되지 않는 고립된 $X$ 는 0으로 취급하여 그냥 버립니다. (굳이 $X$ 만을 감싸기 위한 묶음을 만들 필요는 절대 없습니다.)

7. 시험에 자주 나오는 핵심 문제 풀이 팁

팁 1: 4모서리 묶음 암산 테크닉 (단골 출제)

4변수 맵에서 네 꼭짓점( $m_0, m_2, m_8, m_{10}$ )에 1이 있는 경우:

$m_0 = \overline{A}\,\overline{B}\,\overline{C}\,\overline{D}$
$m_2 = \overline{A}\,\overline{B}\,C\,\overline{D}$
$m_8 = A\,\overline{B}\,\overline{C}\,\overline{D}$
$m_{10} = A\,\overline{B}\,C\,\overline{D}$ $A$ 와 $\overline{A}$ , $C$ 와 $\overline{C}$ 가 각각 상쇄되므로 남는 식은 항상 ** $\overline{B}\,\overline{D}$ **입니다.

팁 2: XOR / XNOR 체커보드 패턴 판별

카르노맵 상에서 1들이 체스판(체커보드)처럼 대각선 방향으로 인접하여 서로 이웃하지 않고 번갈아 배치되는 경우, 묶음으로 간소화되지 않고 XOR( $\oplus$ ) 또는 XNOR( $\odot$ ) 게이트로 묶입니다.

3변수 기수 패리티(Odd Parity, 1이 홀수 개): $m_1, m_2, m_4, m_7 \implies A \oplus B \oplus C$
3변수 우수 패리티(Even Parity, 1이 짝수 개): $m_0, m_3, m_5, m_6 \implies \overline{A \oplus B \oplus C}$

8. 관련 기출문제 풀어보기

실제 공무원 9급 국가직 및 지방직 전자공학개론에 출제된 카르노맵 및 논리식 간소화 관련 기출문제 모음입니다. 각 링크를 클릭하면 해당 문제 풀이 및 상세 해설로 즉시 이동합니다.

카르노맵(K-Map) 완벽 정리 및 불 대수 논리식 간소화 기법

1. 카르노맵(Karnaugh Map)이란?

2. 카르노맵의 핵심 원리: 그레이 코드(Gray Code) 배치

3. 변수별 카르노맵 구조 및 민텀(Minterm) 번호

1) 3변수 카르노맵 ( $A, B, C$ )

2) 4변수 카르노맵 ( $A, B, C, D$ )

4. 카르노맵 묶기(Grouping) 6대 절대 규칙

5. SOP(최소항의 합) vs POS(최대항의 곱) 간소화

6. 무관 조건(Don’t Care, $d$ 또는 $X$ )의 활용 전략

7. 시험에 자주 나오는 핵심 문제 풀이 팁

팁 1: 4모서리 묶음 암산 테크닉 (단골 출제)

팁 2: XOR / XNOR 체커보드 패턴 판별

8. 관련 기출문제 풀어보기

📌 지방직 9급 전자공학개론

📌 국가직 9급 전자공학개론

1. 카르노맵(Karnaugh Map)이란?

2. 카르노맵의 핵심 원리: 그레이 코드(Gray Code) 배치

3. 변수별 카르노맵 구조 및 민텀(Minterm) 번호

1) 3변수 카르노맵 (A,B,CA, B, CA,B,C)

2) 4변수 카르노맵 (A,B,C,DA, B, C, DA,B,C,D)

4. 카르노맵 묶기(Grouping) 6대 절대 규칙

5. SOP(최소항의 합) vs POS(최대항의 곱) 간소화

6. 무관 조건(Don’t Care, ddd 또는 XXX)의 활용 전략

7. 시험에 자주 나오는 핵심 문제 풀이 팁

팁 1: 4모서리 묶음 암산 테크닉 (단골 출제)

팁 2: XOR / XNOR 체커보드 패턴 판별

8. 관련 기출문제 풀어보기

📌 지방직 9급 전자공학개론

📌 국가직 9급 전자공학개론

1) 3변수 카르노맵 ( $A, B, C$ )

2) 4변수 카르노맵 ( $A, B, C, D$ )

6. 무관 조건(Don’t Care, $d$ 또는 $X$ )의 활용 전략