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 maps are a bit more complex and work up to 5 variables (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 humans.

Now I try to explain the algorithm to you. It contains of 3 steps.
Step 1:
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.
Step 2:
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.
Step 3:
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).

Log in or register to write something here or to contact authors.