왜 카르노맵만으로는 부족한가

11편과 12편에서 카르노맵(K-map)을 이용한 간소화를 배웠다. 카르노맵은 눈으로 인접한 칸을 묶어 직관적으로 최소 SOP(Sum of Products, 합의 곱 형태)를 찾아내는 방법이었다. 그런데 카르노맵은 변수가 4개를 넘어가면 칸을 2차원 평면 위에 배치하기 어려워지고(5변수부터는 맵을 두 장 겹쳐야 하는 등 시각적으로 복잡해진다), 사람이 눈으로 묶음을 찾다 보면 실수로 더 큰 묶음을 놓치기 쉽다.

퀴인-맥클러스키 방법(Quine-McCluskey method, 두 발견자 윌러드 콰인과 에드워드 맥클러스키의 이름을 딴 방법)은 이런 한계를 해결하기 위해 나온 표 기반의 체계적 간소화 절차다. 눈으로 묶는 대신, 최소항을 이진수로 적어두고 1의 개수(비트 중 1이 몇 개인지) 기준으로 그룹을 나눈 뒤, 정해진 규칙대로 비교·결합을 반복한다. 절차가 기계적이라서 컴퓨터 프로그램으로 자동화하기도 쉽고, 사람이 손으로 풀 때도 “묶음을 놓쳤나?” 하는 불안 없이 정해진 표만 채우면 끝까지 정답에 도달할 수 있다.

쉽게 말하면: 퀴인-맥클러스키는 카르노맵의 “눈으로 찾는 묶음”을 “표를 채워서 기계적으로 찾는 묶음”으로 바꾼 방법이다. 변수가 많아 눈으로 보기 어려울 때 특히 유용하다.

독학사 시험에서는 변수 3~4개 규모의 문제가 나오므로, 카르노맵으로도 풀리지만 “퀴인-맥클러스키 절차를 순서대로 적용할 수 있는가”를 확인하는 문제가 출제된다. 이번 편에서는 카르노맵과 똑같은 함수를 퀴인-맥클러스키로도 풀어 두 방법의 결과가 일치함을 직접 확인한다.

준비: 예제 함수와 최소항 표기

다음 3변수 함수를 예제로 쓴다.

여기서 $\sum m(\cdot)$은 “이 안에 적힌 번호의 최소항(minterm, 진리표에서 출력이 1인 각 행에 대응하는 곱항)들의 합”이라는 뜻이다. 최소항 번호는 입력 변수 $A, B, C$를 2진수 자리로 보고 $A$를 최상위 비트로 읽은 값이다. 예를 들어 최소항 5는 $101$이므로 $A=1, B=0, C=1$인 행을 뜻한다.

먼저 각 최소항을 이진수로 풀어 쓰고, 그 안에 있는 1의 개수를 함께 적는다.

1단계: 1의 개수로 그룹 나누기

퀴인-맥클러스키의 첫 단계는 1의 개수가 같은 최소항끼리 그룹으로 묶는 것이다. 이렇게 그룹을 나눠 두면, 다음 단계에서 “인접한 그룹끼리만” 비교하면 되므로 비교 횟수가 크게 줄어든다(1의 개수가 정확히 하나 차이 나는 두 항만 한 비트만 다를 가능성이 있기 때문이다).

자주 틀리는 점: 그룹을 1의 개수가 아니라 최소항 번호 크기순으로 나누는 실수가 흔하다. 반드시 “이진수로 풀었을 때 1이 몇 개인가”를 기준으로 나눠야 다음 단계의 비교가 성립한다.

2단계: 인접한 그룹끼리 짝지어 결합하기

인접한 그룹(1의 개수가 정확히 1 차이 나는 그룹, 즉 그룹 0과 그룹 1, 그룹 1과 그룹 2, 그룹 2와 그룹 3)의 항들을 한 쌍씩 비교한다. 두 항이 정확히 한 비트만 다르고 나머지 비트는 모두 같으면 결합할 수 있다. 결합한 결과는 다른 비트 자리를 대시(-, dash, “이 자리는 0이든 1이든 상관없다”는 의미)로 표시한다. 결합에 사용된 두 항에는 체크 표시를 남겨, 이후 “더 이상 결합되지 않고 혼자 남은 항”을 가려낼 수 있게 한다.

그룹 0과 그룹 1 비교:

• $000$ (0) vs $001$ (1): C 자리만 다르다(0 vs 1) → 결합 가능, 결과 $00\text{-}$, 두 항의 짝 (0, 1)
• $000$ (0) vs $010$ (2): B 자리만 다르다(0 vs 1) → 결합 가능, 결과 $0\text{-}0$, 두 항의 짝 (0, 2)

그룹 1과 그룹 2 비교:

• $001$ (1) vs $011$ (3): B 자리만 다르다 → 결합 가능, 결과 $0\text{-}1$, 짝 (1, 3)
• $001$ (1) vs $101$ (5): A 자리만 다르다 → 결합 가능, 결과 $\text{-}01$, 짝 (1, 5)
• $010$ (2) vs $011$ (3): C 자리만 다르다 → 결합 가능, 결과 $01\text{-}$, 짝 (2, 3)
• $010$ (2) vs $101$ (5): 두 자리(A, C)가 다르다 → 결합 불가능(한 비트 초과 차이는 결합하지 않는다)

그룹 2와 그룹 3 비교:

• $011$ (3) vs $111$ (7): A 자리만 다르다 → 결합 가능, 결과 $\text{-}11$, 짝 (3, 7)
• $101$ (5) vs $111$ (7): B 자리만 다르다 → 결합 가능, 결과 $1\text{-}1$, 짝 (5, 7)

이 단계에서 결합에 참여한 최소항은 0, 1, 2, 3, 5, 7 전부다. 즉 혼자 남아 체크되지 않은 항이 없으므로, 3변수 예제에서는 1단계 결합만으로 모든 최소항이 다음 단계로 넘어간다.

결합 결과를 다시 1의 개수(대시를 제외한 나머지 비트 중 1의 개수) 기준으로 정리하면 다음과 같다.

3단계: 크기 4 항으로 재결합

이제 방금 만든 두 비트 크기의 항들을 다시 한번 결합할 수 있는지 확인한다. 대시(-)가 놓인 자리가 서로 같고, 나머지 비트 중 한 자리만 다른 경우에만 결합할 수 있다.

• $00\text{-}$ (0,1)와 $01\text{-}$ (2,3): 대시 위치(C 자리)가 같고, B 자리만 다르다(0 vs 1) → 결합 가능, 결과 $0\text{-}\text{-}$, 포함 최소항 (0, 1, 2, 3)
• $0\text{-}0$ (0,2)와 $0\text{-}1$ (1,3): 대시 위치(B 자리)가 같고, C 자리만 다르다 → 결합 가능, 결과 $0\text{-}\text{-}$, 포함 최소항 (0, 2, 1, 3) — 위와 같은 항이므로 하나로 취급한다.
• $\text{-}01$ (1,5)와 $\text{-}11$ (3,7): 대시 위치(A 자리)가 같고, B 자리만 다르다 → 결합 가능, 결과 $\text{-}\text{-}1$, 포함 최소항 (1, 5, 3, 7)
• 나머지 조합(예: $01\text{-}$ 와 $\text{-}11$, 대시 위치 자체가 다름)은 대시 위치가 서로 달라 결합 규칙에 맞지 않으므로 결합하지 않는다.
• $1\text{-}1$ (5,7)은 다른 어떤 두 비트 항과도 대시 위치·나머지 한 비트 조건이 맞지 않아 더 이상 결합되지 않는다.

크기 4 항을 만드는 데 사용된 두 비트 항($00\text{-}$, $0\text{-}0$, $0\text{-}1$, $01\text{-}$, $\text{-}01$, $\text{-}11$)은 모두 체크되어 다음 단계로 넘어가지 않는다. 반면 $1\text{-}1$은 더 이상 결합되지 않았으므로 여기서 활동을 멈추고 프라임 임플리컨트로 확정된다.

4단계: 프라임 임플리컨트 확정

프라임 임플리컨트(prime implicant)란 “더 이상 다른 항과 결합할 수 없어서 확장을 멈춘 항”을 말한다. 결합이 멈췄다는 것은 이 항이 표현할 수 있는 가장 큰 직사각형 묶음(카르노맵으로 치면 가장 큰 크기의 묶음)이라는 뜻이다.

이번 예제에서 크기 4 항 $0\text{-}\text{-}$ 와 $\text{-}\text{-}1$은 서로 대시 위치가 다르고(전자는 B, C가 대시, 후자는 A, B가 대시), 남은 비트 자리 수도 다르므로 더 결합되지 않는다. 따라서 다음 세 항이 최종 프라임 임플리컨트다.

각 프라임 임플리컨트의 논리식은 대시가 아닌 자리만 읽어서 만든다. 예를 들어 $0\text{-}\text{-}$는 A 자리만 0으로 고정되어 있으므로 $\bar{A}$이고, $1\text{-}1$은 A와 C가 모두 1로 고정되어 있으므로 두 리터럴을 곱한 $AC$가 된다.

5단계: 프라임 임플리컨트 차트로 필수 항 고르기

프라임 임플리컨트를 모두 더한다고 항상 최소식이 되는 것은 아니다. 어떤 프라임 임플리컨트는 다른 프라임 임플리컨트에 가려져 없어도 되는 경우가 있기 때문이다. 이를 가려내기 위해 프라임 임플리컨트 차트(prime implicant chart)를 그린다. 가로축에는 원래 최소항을, 세로축에는 프라임 임플리컨트를 놓고, 각 프라임 임플리컨트가 커버하는 최소항 자리에 표시(가위표)를 한다.

이 표에서 어느 한 최소항 칸에 표시가 하나뿐인 프라임 임플리컨트를 찾는다. 이런 프라임 임플리컨트는 그 최소항을 커버할 방법이 그것 하나뿐이라는 뜻이므로 반드시 최소식에 포함되어야 한다. 이런 프라임 임플리컨트를 필수 프라임 임플리컨트(essential prime implicant)라고 부른다.

• 최소항 0 칸을 보면 표시가 $\bar{A}$ 하나뿐이다 → $\bar{A}$는 필수 프라임 임플리컨트다.
• 최소항 5 칸을 보면 표시가 $C$와 $AC$ 두 개다 → 아직 필수라고 단정할 수 없다.
• 최소항 7 칸도 $C$와 $AC$ 두 개다 → 역시 단정 불가.
• 최소항 1, 3 칸을 보면 $\bar{A}$와 $C$ 두 개씩이다.

일단 확정된 필수 프라임 임플리컨트 $\bar{A}$가 커버하는 최소항(0, 1, 2, 3)을 표에서 지운다. 남은 최소항은 5, 7뿐이다. 이 두 최소항을 커버하는 프라임 임플리컨트는 $C$와 $AC$인데, $C$ 하나만으로도 5와 7을 모두 커버할 수 있고 $AC$는 $C$가 커버하는 최소항의 부분집합만 커버한다(즉 $AC$가 커버하는 5, 7은 $C$도 이미 커버한다). 이런 경우 $AC$처럼 다른 항에 완전히 포함되는 프라임 임플리컨트를 중복(redundant) 프라임 임플리컨트라고 하며 최소식에서 제외한다. 따라서 남은 최소항 5, 7을 커버하기 위해 $C$를 선택한다.

6단계: 최소 SOP 완성과 카르노맵 결과 대조

필수 프라임 임플리컨트 $\bar{A}$와, 남은 최소항을 커버하기 위해 선택한 $C$를 더하면 최소 SOP가 완성된다.

11편에서 같은 함수 $\sum m(0,1,2,3,5,7)$을 카르노맵으로 풀면, $A=0$인 네 칸(0,1,2,3)이 한 줄로 묶여 $\bar{A}$가 나오고, $C=1$인 네 칸(1,3,5,7)이 한 줄로 묶여 $C$가 나와 정확히 같은 결과 $\bar{A} + C$를 얻는다. 이렇게 두 방법이 서로 다른 절차를 거치지만 항상 같은 정답에 도달한다는 사실이, 카르노맵의 “눈으로 찾은 묶음”이 실은 퀴인-맥클러스키의 “표로 찾은 프라임 임플리컨트”와 동일한 개념임을 보여준다.

쉽게 말하면: 카르노맵의 큰 사각형 묶음 하나하나가 퀴인-맥클러스키의 프라임 임플리컨트 하나하나에 대응한다. 다만 카르노맵은 눈으로, 퀴인-맥클러스키는 표로 그 묶음을 찾는다는 점이 다를 뿐이다.

카르노맵과 퀴인-맥클러스키 비교

don’t care가 있을 때 퀴인-맥클러스키 적용

12편에서 배운 don’t care(신경 쓰지 않음, 입력이 절대 발생하지 않거나 출력이 무엇이든 상관없는 경우)가 있는 함수도 퀴인-맥클러스키로 풀 수 있다. 절차는 다음과 같이 살짝만 바뀐다.

이 순서를 지키면, don’t care를 “결합에는 참여시키되 커버 의무에서는 빼는” 12편의 원칙이 퀴인-맥클러스키에서도 그대로 적용된다.

자주 틀리는 점

• 1의 개수 그룹을 건너뛰고 아무 항이나 비교하는 실수: 반드시 1의 개수가 1 차이 나는 인접 그룹끼리만 비교해야 한다. 인접하지 않은 그룹끼리는 두 비트 이상 달라 애초에 결합될 수 없다.
• 대시 위치가 다른 항끼리 억지로 결합하는 실수: 크기 4 이상 항을 만들 때는 대시가 놓인 자리가 완전히 같아야 결합할 수 있다. 대시 위치가 하나라도 다르면 결합 불가능하다.
• 결합에 쓰인 항을 지우지 않고 프라임 임플리컨트로 착각하는 실수: 다음 단계 결합에 성공적으로 쓰인 항(체크된 항)은 더 큰 프라임 임플리컨트에 흡수된 것이므로 최종 목록에서 제외해야 한다.
• 필수 프라임 임플리컨트 판정 없이 프라임 임플리컨트를 전부 더하는 실수: 프라임 임플리컨트를 전부 더하면 정답이 나오지 않을 수도 있고, 나오더라도 최소식이 아닐 수 있다(중복 항이 섞여 더 길어진다). 반드시 차트로 필수 여부를 확인하고, 남는 최소항만 최소 개수의 프라임 임플리컨트로 추가 커버해야 한다.
• don’t care 열을 프라임 임플리컨트 차트에 그대로 남겨 필수 여부를 잘못 판단하는 실수: don’t care는 결합에는 참여하되, 필수 판정 단계에서는 반드시 제외해야 한다.

핵심 정리

• 퀴인-맥클러스키는 카르노맵의 대안으로, 최소항을 1의 개수로 그룹화한 뒤 한 비트만 다른 항끼리 결합해 나가는 표 기반 절차다.
• 더 이상 결합되지 않는 항이 프라임 임플리컨트이며, 프라임 임플리컨트 차트에서 유일하게 어떤 최소항을 커버하는 항이 필수 프라임 임플리컨트다.
• 필수 프라임 임플리컨트로 커버되지 않는 최소항이 남으면, 그 최소항을 커버하는 프라임 임플리컨트 중 최소 개수만 추가로 선택한다.
• 카르노맵과 퀴인-맥클러스키는 항상 같은 최소 SOP에 도달하며, 변수가 많거나 실수 없이 절차적으로 풀고 싶을 때는 퀴인-맥클러스키가 유리하다.
• don’t care 항은 결합 단계에는 참여시키되, 프라임 임플리컨트 차트의 필수 판정에서는 제외한다.

마무리 복습

참고 자료

• 국가평생교육진흥원 독학학위제  — 독학사 논리회로 과목 평가영역·출제범위 공식 안내.
• IEEE Standards Association  — 디지털 논리 설계 관련 표준화 자료를 확인할 수 있는 공신력 있는 기관 자료.