Quine-McClusky is an algorithm to reduce boolean
functions. The main use of this is to make electronic circuits cheaper.
For example look at the following boolean function:
f(x1,x2,x3) = x1^x2^x3 v x1^!x2^x3
Whether x2 is 0 or 1 does not influence the result. So one can easily reduce this function to: x1^x3.
For such a short function this is pretty easy, but for more complex functions it becomes nearly impossible to reduce a function just by looking at it. So some clever people developed algorithms to reduce fuctions. The easiest is the boolean cube
, but it only works up to 3 variables. Karnaugh map
s are a bit more complex and work up to 5 variable
s (they work for more variables, too, but they are practically useless). Quine-McClusky has no such limitations and has the major advantage that it is easily programable, so that a computer can do the working stuff for you. But as Quine-McClusky is non graphical algorithm
, it is harder to understand for human
Now I try to explain the algorithm to you. It contains of 3 steps.
Find the complete disjunctive normalized form(cdnf) of the function. This means that the function consists of all the conjunctions for which the function is equal to 1 (for example you have a function which is 1 for 00111, the the fitting conjunction is !x1^!x2^x3^x4^x5). All this conjunctions are disjunctively combined (with a OR). This is a for all boolean functions unique form (if two functions have the same cdnf then they are equal). And the last step of step 1 is to group conjunctions with the same number of 0s and 1s.
In step 2 you compare all the conjunctions of neighbouring groups (the ones with 0 0s and the and ones with 1 0s and so on). If two conjunctions are only different in one position these two can be merged (00111 and 10111 can be merged to -0111). Now you mark the two origin conjunctions (but they and the new one can be used for further merging).
If no further merging is possible step 2 is complete. Now you have got the prim-implicants of the boolean function.
This form of the boolean function still is unique for every boolean function. It is called the reduced disjunctive normalized form (rdnf). But some of the prim-implicants are often not needed.
This happens when you have for example 4 prim-implicants, from which one covers 3 allocations. But these 3 allocations are also covered by the three others. The way to find this out, is to make a table and mark all allocations which are only covered once. Now you have to "play" around with the others so that you get a function with as few conjunctions as possible. The word "play" already indicates, this process is not unique for a given boolean function. A boolean function can have more than one so called minimized disjunctive normalized forms (mdnf).