카르노맵으로 식 줄이기

진리표에서 출력이 1인 행을 전부 식으로 쓰면 길어집니다. 카르노맵은 한 비트만 다른 입력들을 이웃으로 놓아 사라지는 변수를 눈으로 찾는 도구입니다. 선택 심화인 이 절은 부울대수와 최소항을 먼저 익힙니다.

인접한 칸은 한 비트만 다르다

2변수 맵은 x=0,1 두 행과 y=0,1 두 열입니다. 3변수 맵은 x의 두 행, yz의 네 열을 00,01,11,10 순서로 놓습니다. 4변수는 xy 행과 zw 열을 각각 같은 Gray 순서로 놓습니다. 보통 이진 순서 00,01,10,11로 놓으면 가운데 이웃이 두 비트 달라 묶는 원리가 깨집니다.

좌우 끝 열과 위아래 끝 행도 이웃입니다. 1칸 또는 2·4·8·16칸의 직사각형 묶음을 만들 수 있고, 대각선만 맞닿은 칸은 묶을 수 없습니다. 겹치는 묶음은 허용하지만 선택한 묶음에 0인 칸이 있으면 안 됩니다. 모든 1을 덮어야 합니다.

고정된 변수만 남긴다

3변수 F가 최소항 m(0,2,4,6)에서 1이라 합시다. 이진 입력은 000,010,100,110이며 z는 항상 0이고 x,y는 바뀝니다. 맵에서는 yz=00,10 끝 열 두 개와 x의 두 행을 한 묶음으로 잡을 수 있습니다. x,y가 변해 사라지고 F=$\bar z$만 남습니다.

4변수 F의 1인 입력이 m(0,1,4,5)라면 0000,0001,0100,0101입니다. x=0,z=0만 고정되고 y,w가 바뀌므로 F=$\bar x\bar z$입니다. 먼저 비트값으로 검산하면 도표에서 끝을 감싼 묶음이 어려워도 식을 확인할 수 있습니다.

2변수 F의 1이 01,11이라면 두 칸은 x만 다르고 y=1이 고정되므로 F=y입니다. 이는 앞 절의 $\bar x y+xy=y$를 시각적으로 계산한 것입니다.

무관조건은 모델의 약속이다

입력에서 절대로 발생하지 않거나 출력값이 상관없는 경우를 d로 표시할 수 있습니다. 간단한 식을 얻기 위해 d를 0 또는 1로 선택해 이용하되 필요 없으면 묶지 않아도 됩니다. 실제로 그 입력이 발생하는데 '모르니까 d'로 쓰면 회로 동작을 보장하지 못합니다. 최소화는 주어진 입력 모델 안에서만 유효합니다.

스스로 풀어보기

문제 1. 3변수 F=Σm(1,3,5,7)을 줄이세요. 변수 순서는 x,y,z입니다.

풀이: 001,011,101,111에서 z=1만 고정됩니다. 네 칸을 묶어 F=z입니다. x,y의 모든 값이 나타나서 두 변수는 식에서 빠집니다.

문제 2. 3변수 m(0)과 m(3) 두 칸만 1일 때 두 칸을 한 묶음으로 잡을 수 있나요?

힌트: 000과 011의 바뀌는 비트 수를 셉니다.

풀이: 두 비트 y,z가 달라 인접 칸이 아닙니다. 둘만 묶어 변수 둘을 제거하면 다른 0 입력까지 1로 바뀝니다. 각 칸을 따로 최소항으로 두어 $\bar x\bar y\bar z+\bar x yz$를 얻습니다. 더 큰 묶음에 넣을 다른 1이나 허용 d가 없는 조건입니다.

묶음 크기·0 포함·전체 1 덮기 세 항목을 확인한 뒤 모든 입력을 진리표로 검산하세요. 논리적 표현을 수학적으로 검토하는 기본은 동치입니다.