[Quine-McCluskey Method] For Incompletely Specified Functions

적용 방법

이 포스트에서는 'don't care'에 해당되는 minterm이 있을 때,
Quine-McCluskey Method를 어떻게 적용할 것인가 하는 문제를 다룰 것이다.
방법은 기존과 거의 비슷하므로, 대략적인 차이에 대해서 먼저 설명해 보면,
일단 prime implicant를 찾는 과정에서는, don't care들을 모두 1인 것으로 간주하여 prime implicant를 찾는다. 
그래야만, 각 term에서 최대한 많은 variable을 제거할 수 있다. (product 내의 각 variable을 literal이라고 한다.)
제거하는 과정에서 필요한 don't care들이 자동적으로 포함되는 셈이다.

한편, prime implicant chart를 그릴 때에는 don't care의 minterm들을 제외하여 그려야 한다.
Cover해야하는 minterm들이 되도록이면
작은 term안에 포함될 수 있으면 그것이 곧 minimum solution이기 때문에,
포함 될 필요가 없는 don't care들을 굳이 포함시킬 필요는 없다.
즉, don't care인 minterm는 essential prime implicant가 될 수 없음을 생각해 보면 된다.

예제

위와 같은 형태의 function의 minimum solution을 구하기 위해서 먼저 prime implicant를 구해보면,

방식은 기존과 동일하나, don't care minterm들도 모두 포함된 것을 볼 수 있다.
3번째 column에만 prime implicant들이 남아있게 되었다. '
이를 토대로 prime implicant chart를 그려보면,

2번, 7번, 13번이 essentail prime implicant를 만드는 minterm들 이므로, 먼저 가로선을 긋고,
가로선이 지나는 X에 각각 세로선을 긋는다.
더 이상의 가로선을 그을 필요 없이 모든 minterm들을 cover하므로,
이로써 최종적으로 minimum solution F = B'C + CD + AD 가 완성되었다.