본 포스팅은 ‘Mano의 컴퓨터시스템구조’ 교재를 참고했습니다.
논리표현식은 부울 대수를 사용해서 간단히 만들 수 있으나 여러 가지 규칙이 있다. 맵 방법은 karnaugh 맵과 Veitch 다이어그램이 있다.
진리표에서 각 변수의 각 조합을 민텀(minterm)이라고 한다. n개의 변수가 있으면 $2^n$개의 민텀이 있다.
| A | B | C | F |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
<Truth Table 1>
위 진리표를 민텀으로 표현하면 아래와 같다.
$$ \begin{aligned} F(x,y,z) &= \sum (1,4,5,6,7) \ &= x{^\prime}y{^\prime}z+xy{^\prime}z{^\prime}+xy{^\prime}z+xyz{^\prime}+xyz \end{aligned} $$
맵은 여러 개의 사각형으로 이루어지고, 각 사각형의 구역은 각각의 민텀을 표시한다. 함수가 1이 될 때 해당 구역에 1을 넣고, 0일 땐 0을 넣거나 빈 칸으로 둔다.
맵은 두 변수일 땐 $2 \times 2$, 세 변수일 땐 $2 \times 4$, 네 변수일 땐 $4 \times 4$ 크기로 그린다. 그 이상은 맵 방식으로 하면 복잡하여 다른 방법을 사용한다. 아래는 그 예시이다.
B A | A | B |
|---|---|---|
| 1 | O | X |
| 2 | O | X |
<2 변수 맵 예제>
BC A | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 0 |
| 1 | 1 | 1 | 0 | 1 |
<3 변수 맵 예제>
CD AB | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 1 | 0 | 1 | 0 |
| 01 | 0 | 1 | 0 | 1 |
| 11 | 1 | 1 | 0 | 1 |
| 10 | 0 | 0 | 0 | 1 |
<4 변수 맵 예제>
카르노 맵을 이용한 간소화는 텍스트로 설명하면 이해하기 어렵다. 그 대신, 카르노 맵을 이용한 간소화를 매우 쉽게 설명한 ‘전기는빠지직(송건웅)‘님의 유튜브 영상을 첨부한다.