Geek Hideout
Quine-McClusky Method

The Quine-McClusky Method of Logic Reduction

The Quine-McClusky method is an algorithm for reducing a logic equation to its simplest reduced form. For anything but the most straight forward of equations, it can be an impressive time-saver when compared to other techniques such as traditional algebraic reduction and Karnaugh maps. It also has the advantage of being easily implemented with a computer or programmable calculator.

Hi, I'm still working on this. it is not ready yet.

Typically, the need to employ logic reduction comes from having a truth table and wanting to implement it in the real world--discrete logic, array logic, inside of a computer program, or whatever else your mind can dream up. The truth table is constructed by known what result is desired for a combinartion of inputs and outputs:

DBCAQ
00001
00010
00100
00111
01000
01010
01101
01111
10001
10010
10100
10111
11001
11010
11101
11111
The above truth table was made up randomly. The equation for it is:

Q = ~A~B~C~D + ~A~BCD + ~ABC~D + ~ABCD + A~B~C~D + A~BCD + ABC~D + ABCD
Here, a tilde (~) before a term indicates negation.

Reduction Step 1

Extract all the input combinations that produce a true result:

DBCAQ
00001
00111
01101
01111
10001
10111
11001
11101
11111

Reduction Step 2

Rearrange the rows so that the are sorted by the number of ones contained in the inputs:

DBCAQ# of 1's
000010
100011
001112
110012
011012
011113
101113
111013
111114
Reduction Step 3

This is the tricky step. Try to match each item in each group of ones with each item in the following group. If there is a one bit difference, replace that bit with an "X" and write it in a new table. If there are no matches that have a one bit difference, simply transfer the origial item to the new table. For example:

Matching 0 groups with 1 groups, we get:
DBCAQ# of 1's
X00010
X00011
X01112
110012
011X12
011X13
X01113
111X13
111X14
Reduction Step 4

Reduce the redundant groups:

DBCAQ# of 1's
X00010
X01112
110012
011X12
111X14
Reduction Step 4

Repeat the reduction process:

DBCAQ# of 1's
X00010
X01112
110012
X11X12
Reduction Step 4

Repeat the reduction process:

DBCAQ# of 1's
X00010
XX1X12
110012