카르노맵(Karnaugh map)

 1. 카르노맵이란?

복잡한 형태의 복합 논리 게이트를 단순화 하기 위하여 카르노맵을 이용한다.

2. 2변수 카르노 맵

$$\bar{A} \cdot \bar{B} + \bar{A} \cdot B$$

위 식이 주어졌을 때 진리표를 카르노 맵의 형태로 바꾸어보면 다음과 같다.

위의 경우는 B에 관계없이 A가 0이면 출력이 1이므로 위 게이트는 A'으로 단순화 될 수 있다.

아래와 같이 불 대수 법칙으로 정리해도 성립한다.

$$\bar{A} * \bar{B} + \bar{A} \cdot B = \bar{A} \cdot (\bar{B} + B) = \bar{A}$$

2. 3변수 카르노 맵

2변수를 묶은 부분의 순서는 00, 01, 11, 10 순으로 진행되어야 한다.

(앞뒤가 서로 중첩되는 부분이 존재해야 하기 때문이다.)

위의 예시와 같이 출력이 1인 부분을 직사각형의 형태로 2^n 개씩 묶는다. (n >= 0, 자연수)

위아래, 양옆으로 잘린 부분은 서로 묶을 수 있다.

노란색 부분은 A가 1이고 C가 0일때 B와 관계없이 1이 출력된다.

$$A \cdot \bar{C}$$

초록색 부분은 A가 0이고 B가 1일때 C와 관계없이 1이 출력된다.

$$\bar{A} \cdot B$$

따라서 전체 식은 이 둘을 모두 만족해야 하므로 다음과 같다.

$$Y = A \cdot \bar{C} + \bar{A} \cdot B$$

3. 4변수 카르노 맵

바로 예시를 들어보자

위와 같이 구간을 나누면 아래의 식을 세울 수 있다.

$$Y = B \cdot \bar{C} + \bar{A} \cdot \bar{B} \cdot D + A \cdot \bar{B} \cdot C \cdot \bar{D}$$