Part of the server side of the Gateway to Logic is a propositional optimizer using an exremely fast, non-exhaustive, heuristic version of the Quine-McCluskey algorithm. Technically speaking, to any given CDNF this algorithm constructs an equivalent DNF at least as short as the CDNF given (and usually much shorter).
Quine-McCluskey optimization (named after the contemporary philosopher W.V.O. Quine and the human McCluskey) is most useful and, therefore, most often used in the field of digital electronics where there is sometimes a strong preference for using the truth-table of a proposition instead of the proposition itself.
That's why, unlike most other tasks of the Gateway, Quine-McCluskey optimization is available in two versions, a standard version accepting plain propositions (just like the other tasks of the Gateway), and a version accepting truth-value assignments (see below).
The standard version
The standard version of the Quine-McCluskey optimizer is, umh, quite standard. It accepts a proposition in the standard notation used by the Gateway, optimizes it and displays the result of this optimization.
An example
To optimize the proposition (A & B & ~C) v (A & ~B & D) v (A & ~B), please observe the following steps:
- Enter the proposition (A & B & ~C) v (A & ~B & D) v (A & ~B) in the input area.
- Select the task "Quine-McCluskey-optimization" (not "Quine-McCluskey (input table)")
- Start the optimizer by selecting "Execute". The optimizer reduces the proposition to A & ~B v A & ~C.
To try out the example for yourself, click here.
The table version
The table-based version of the optimizer requires the user to enter a table of all truth-value assignments under which the proposition to be optimized is true. An example might clarify the meaning of the preceding sentence:
An example being uttermost helpful
Assume that you are looking for a proposition whose truth table is the following:
A B C | -------+-------- 1 1 1 | 1 1 1 0 | 0 1 0 1 | 0 1 0 0 | 0 0 1 1 | 1 0 1 0 | 1 0 0 1 | 1 0 0 0 | 1
This proposition is true in the first, fifth, sixth, seventh and eight line (i.e. evaluation). That is, the evaluations under which the proposition is true are the following:
A B C ----- 1 1 1 0 1 1 0 1 0 0 0 1 0 0 0
It is these valuations that must be fed to the Quine-McCluskey optimizer.
Each valuation is to be input as one line, devoid of any trailing, leading or
intervening space characters. For example, the first evaluation must be input
as
In other words, the user has to supply the following input in the input area of the Gateway:
111 011 010 001 000
Note that this table of valuations can be interpreted as a CDNF, (A & B & C) v (~A & B & C) v (~A & B & ~C) v (~A & ~B & C) v (~A & ~B & ~C). This is the CDNF mentioned in the first paragraph to which the optimizer constructs an equivalent DNF.
Quine-McCluskey optimization ponders your input a little bit and then outputs a proposition which is equivalent to the one you have input but which is (usually) shorter. In the case of our example, the optimizer produces b & c v ~a as its result. Although not exactly shorter than A->(B&C), it is much shorter than the CDNF the algorithm started with. Furthermore, being a DNF it is structurally simpler than A->(B&C) and easier to implement with standard digital circuits.
Now you should try out this example for yourself: Just select this link.