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

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-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:

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.

2012-03-31 01:19:53

gottschall@gmx.de