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).