[Quine-McCluskey Method] Prime Implicant Chart

1단계

Quine-McCluskey method의 두번째 단계는 prime implicant chart를 통해서 minimum solution을 구하는 것이다. 
먼저 prime implicant chart는 다음과 같이 그릴 수 있다.

앞에서 우리가 구했던 prime implicant들이다.
각각의 term들은 minterm들의 조합으로 이루어져 있었다. Minterm의 번호는 왼쪽과 같이 적어주었다.

오른쪽 위에는 f에 속해있는 모든 minterm을 적는다.
그런 다음 각 term에 속해있는 해당 minterm들을 X로 표시한다.
그러고 나서 X표시를 살펴보았을 때, 각 열당 X가 단 하나뿐인 minterm이 보일 것이다.
여기서는 9번과 14번이 X가 하나뿐이다. 
이러한 minterm들을 포함하는 prime implicant는 essential prime implicant이다.
나열된 모든 minterm들은 f에 속해야 하는데, 9번과 14번을 포함하는 term은 b'c'와 cd' 뿐이다.
다시 말해서 이 term을 제외시키면, 곧 f를 완성할 수 없는 것과 같은 의미다. 즉 빠져서는 안되는 term이다.
따라서 essential prime implicant라고 할 수 있는 것이다.
9번과 14번에는 X 위에 동그라미를 추가적으로 그려준다.

2단계

위에서 찾아낸 essential prime implicant에 해당하는 X에 대해서 가로로 선을 긋는다.
이 예제에서는, b'c'와 cd'의 X에 대해서 각각 가로로 선을 긋는다.
여기서 지나간 X에 대해서 다시 세로로 선을 긋는다. 그러면 위와 같은 형태로 그려지게 된다.
여기서 선이 그어진 X들은 이미 해당 term에 포함된 minterm이라는 의미다.
다시 말해서 다른 term에서 해당 minterm을 포함하지 않아도 된다.
그림을 통해 보면, 이미 선이 그어진 X에 대해서는 다시 선을 그을 필요가 없다는 의미가 된다.

그리고 남아있는 X에 대해서도 선을 그어줘야 하는데,
가능한한 적은 수의 term을 선택하면서 모든 X에 선을 그을 수 있는 term들을 선택해야 한다.
여기서는 a'bd를 선택하게 되면 결국 모든 minterm을 cover하게 된다.
a'bd를 선택하면 a'bd위의 X에 선을 긋게 되고, 나머지 X에 대해서도 세로선으로 cover가 된다.
따라서 모든 X위에 선을 긋게 된 셈이다.
최종적으로 f = b'c' + cd' + a'bd 와 같은 minimum solution을 얻게 된다.

어떤 경우에는 세로선 혹은 가로선을 그을 수 없는 X도 있는데,
그 경우에는 긋지 않고 최종 expression에 해당 term을 넣으면 된다.

Minimum solution은 반드시 하나만 나오는 것이 아니라,
경우에 따라서는 2개 이상이 될 수 있다.
모든 minimum solution을 구하는 방법은 다음 포스트에서 설명하도록 하겠다.