|
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:
| DBCA | Q |
| 0000 | 1 |
| 0001 | 0 |
| 0010 | 0 |
| 0011 | 1 |
| 0100 | 0 |
| 0101 | 0 |
| 0110 | 1 |
| 0111 | 1 |
| 1000 | 1 |
| 1001 | 0 |
| 1010 | 0 |
| 1011 | 1 |
| 1100 | 1 |
| 1101 | 0 |
| 1110 | 1 |
| 1111 | 1 |
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:
| DBCA | Q |
| 0000 | 1 |
| 0011 | 1 |
| 0110 | 1 |
| 0111 | 1 |
| 1000 | 1 |
| 1011 | 1 |
| 1100 | 1 |
| 1110 | 1 |
| 1111 | 1 |
Reduction Step 2
Rearrange the rows so that the are sorted by the number of ones contained in the inputs:
| DBCA | Q | # of 1's |
| 0000 | 1 | 0 |
| 1000 | 1 | 1 |
| 0011 | 1 | 2 |
| 1100 | 1 | 2 |
| 0110 | 1 | 2 |
| 0111 | 1 | 3 |
| 1011 | 1 | 3 |
| 1110 | 1 | 3 |
| 1111 | 1 | 4 |
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:
| DBCA | Q | # of 1's |
| X000 | 1 | 0 |
| X000 | 1 | 1 |
| X011 | 1 | 2 |
| 1100 | 1 | 2 |
| 011X | 1 | 2 |
| 011X | 1 | 3 |
| X011 | 1 | 3 |
| 111X | 1 | 3 |
| 111X | 1 | 4 |
Reduction Step 4
Reduce the redundant groups:
| DBCA | Q | # of 1's |
| X000 | 1 | 0 |
| X011 | 1 | 2 |
| 1100 | 1 | 2 |
| 011X | 1 | 2 |
| 111X | 1 | 4 |
Reduction Step 4
Repeat the reduction process:
| DBCA | Q | # of 1's |
| X000 | 1 | 0 |
| X011 | 1 | 2 |
| 1100 | 1 | 2 |
| X11X | 1 | 2 |
Reduction Step 4
Repeat the reduction process:
| DBCA | Q | # of 1's |
| X000 | 1 | 0 |
| XX1X | 1 | 2 |
| 1100 | 1 | 2 |
|
