6-1주차(Chapter3 The Karnaugh Map)

letter 는 상수를 말하고 literal은 letter와 letter에 complement를 말한다. 

F(0,1,1,0) = 1이 된다.

 

 

Product term

1, x1, x1'x2 - O

x1,x2,x1' - X(같은 letter가 반복되었다.)

x1+x2' - X(Sum term 이다.)

 

Sum term

0, x1, x1+x2' - O

x1'x2 - X(Product term)

x1+x2+x1' - X(같은 letter가 반복되었다.)

 

---

Boolean function

---

Karnaugh Map

SOP가 위와 같을 때 canonical SOP가 위와 같이 나오는 이유는 SOP에서 정해진 것이 아니라면 나머지는 아무거나 와도 상관없기 때문이다. 예를 들어 BD가 SOP 에서 주어졌을 때, canonical SOP에서는 A'BC'D, A'BCD, ABC'D, ABCD를 모두 표현해 주어야 한다.

Karnaugh Map

주어진 F를 이용하여 Karnaugh Map을 만들면 위와 같고 implicant를 빨간색으로 묶어봤다. 여기서 00,01,11,10 순인 이유는 인접한 bit끼리 single-bit difference를 유지하기 위해서이고, single-bit difference를 유지해야 implicant를 묶는데 문제가 없다.

핑크색 부분이 Prime Implicant

Prime Implicant란 더 큰 implicant에 속하지 않는 implicant이다.

파란색 부분은 다른 prime implicant에 포함되지 않는 부분.

Essential Prime Implicant 란 하나의 prime Implicant를 형성하고 있는 1들 중에서 적어도 하나는 다른 implicant에 속하지 않고 자신의 Prime Implicant 묶음에만 속하는 Prime Implicant이다. 파란색 영역 덕분에 핑크색으로 둘러싸인 prime implicant는 모두 Essential Prime Implicant가 된다.

해당 Karnaugh Map에서 BC+AC'은 보라색 형광펜으로 친 부분 때문에 Essential prime implicant가 된다. AB는 prime implicant도 안되고 redundant가 되버린다.