0
\$\begingroup\$

Can a product of sum function be simplified using the Quine-McCluskey algorithm?

If so, how?

I saw this post on Math SE addressing the same question, however the answer does not explain how the algorithm would work out exactly and the reason for the method working is also not very clear.

Since (A+B)(A+B') = A, QM should work on CNF as well as DNF. I don't see that there is any difference between grouping by 0's or 1's. The only purpose of that (as far as I understand it) is to assure that mergable clauses are in adjacent groups, and nothing in the same group is mergable. I.e., no two clauses with the same number of 1s are mergable, and not two clauses with the same number of zeros is mergable.

Specifically (for the answer on Math SE), I am unsure if the method indicated means grouping based on number of zeroes in the first stage of the QM algorithm and then proceeding as you would for SOP (?!)

Also I don't understand what the post is referring to when it comes to "mergeable clauses" as part of the explanation for why QM should work for POS. Thus, I am not sure on the reasoning for QM working for POS.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ It seems bizarre that you are asking on EE about a question on math.SE. Do you have a reason for this? \$\endgroup\$
    – Andy aka
    Sep 8, 2020 at 17:27
  • \$\begingroup\$ My bad, I encountered this in my digital electronics course, so I thought it wouldn't be an issue, however I see your point... \$\endgroup\$
    – idunno
    Sep 8, 2020 at 17:41

1 Answer 1

1
\$\begingroup\$

The Quine-McCluskey algorithm is a method used for minimization of Boolean functions. In the process, we can arrive at either canonical disjunctive normal form (minterm canonical term, "sum of products") or canonical conjunctive normal form (maxterm canonical form, "product of sums"), depending on how we encode the logical function. If we use minterms for encoding, the result is CDNF (sum of products); if we use maxterms, the result is CCNF (product of sums). The standard approach is to use minterms, and the Wikipedia article Disjunctive normal form use the wording "Quine–McCluskey algorithm — obtains a minimal DNF for a given Boolean function" to refer to the QMC article.

But the Math.SE poster is right: nothing prevents us from using the maxterm encoding in QMC. I'm going to demonstrate it, changing the example from the Wikipedia article to use CCNF (SOP).

The Wikipedia article demonstrates minimization of the function $$f_{A,B,C,D} = A'BC'D' + AB'C'D' + AB'CD' + AB'CD + ABC'D' + ABCD$$ with don't cares d(9,14).

From its truth table, we have the minterm representation

$$f(A,B,C,D) = \sum{m(4,8,10,11,12,15)} + d(9,14)$$

Let us minimize a function, whose inputs K,L,M,N can be considered the inverts of inputs A,B,C,D:

$$g(K,L,M,N) = (K'+L+M'+N')(K+L'+M'+N')(K+L'+M+N')(K+L'+M+N)(K+L+M'+N')(K+L+M+N)$$ with don't cares d(6,1), because new indices in the truth table are $$i_{new} = 15-i_{old}$$ Encoding with maxterms, we also re-calculate indices: $$g(K,L,M,N) = \prod{M(11,7,5,4,3,0)}$$

Place all maxterms that evaluate to zero in a maxterm table, but only group maxterms in groups of zero's count in the maxterm's binary representation, with increasing count of zeroes in the next group. I do not print out the truth table, you can derive it form the Wikipedia example. When selecting maxterms into table, remember only that g(K,L,M,N) = ¬f(A,B,C,D) (omitting don't cares):

one zero
M7      0111
M11     1011

two zeros
M3      0011
M5      0101
(M6)    0110

three zeros
(M1)    0001
M4      0100

four zeros
M0      0000

Then we start combining maxterms with other maxterms; the process, which the Math.SE poster names "merging of min terms from adjacent groups" -- in our example, "merging of maxterms". The name "merging" is not the math poster's invention, see the article that also uses this wording. The process proceeds as it does for CDNF (SOP), one finds bit sequences differing exactly one position and fills this position with a dash:

merge one-zero and two-zero adjacent groups
M(7,6)      011-
M(7,5)      01-1
M(7,3)      0-11
M(11,3)     -011 *

merge two-zero and tree-zero adjacent groups
M(3,1)      00-1
M(5,1)      0-01
M(5,4)      010-
M(6,4)      01-0

merge tree-zero and four-zero adjacent groups
M(1,0)      000-
M(4,0)      0-00

Then we combine ("merge") the already combined terms into the size 4 implicants:

merge one/two-zero and two/three-zero combined terms
M(7,6,5,4)  01-- *
M(7,5,3,1)  0--1 *

merge two/three-zero and three/four-zero combined terms
M(5,4,1,0)  0-0- *

Now, we construct an essential prime implication table:

             0  3  4  5  7 11
M(11,3)         +           +
M(7,6,5,4)         +  +  +
M(7,5,3,1)      +     +  +
M(5,4,1,0)   +     +  +

M(11,3) and M(5,4,1,0) are essential implicants, we add any one of the other implicants, and the source expression $$g(K,L,M,N) = (K'+L+M'+N')(K+L'+M'+N')(K+L'+M+N')(K+L'+M+N)(K+L+M'+N')(K+L+M+N)$$ is minimized to $$g(K,L,M,N) = (L' + M + N)(K' + M')(K' + L)$$ Summing up: you group maxterms based on number of zeroes, sorting groups in the increasing order, in the first stage of the QM algorithm, and then proceed as you would for "SOP", only you work with maxterms, not minterms.

The question to think over: why the "standard" implementation of QMC works with SOP rather than POS? The answer may bear on electronic device design.

Electronics is multidisciplinary: its subject embraces many areas of science, mathematics, and technology. You are right when posting the questions like this here.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.