Changing from product of sums to sum of products

Question

I have a function that compares two 2 bit numbers and this is the function for it in what I think is product of sums form but I need it in sum of products form. How do I convert it to the latter?

EQU = (~A[1] | B[1]) & (A[1] | ~B[1]) & (A[0] | ~B[0]) & (~A[0] | B[0]);

Answer 1

Use:

Distribution

$P \land (Q \lor R) \Leftrightarrow (P \land Q) \lor (P \land R)$

This can be generalized to:

$(P \lor Q) \land (R \lor S) \Leftrightarrow (P \land R) \lor (P \land S) \lor (Q \land R) \lor (Q \land S)$

And with even more terms (as in your case), the pattern is: find all ways in which to pick one of the disjuncts from each of the conjuncts.

In your case that would give you 2*2*2*2=16 disjuncts each consisting of 4 conjuncts ... But we can anticipate a bunch of these to be removable. E.g. as soon as you combine $\neg A1$ with $A1$ you get a contradiction, so that term can be removed. So, if you look at your terms, you see that there are only two non-contradictory ways to pair up elements from the first two terms, and likewise for the third and fourth term, giving you only four 'viable' terms:

$(\neg A1 \land \neg B1 \land \neg A0 \land \neg B0) \lor (\neg A1 \land \neg B1 \land A0 \land B0) \lor (A1 \land B1 \land \neg A0 \land \neg B0) \lor (A1 \land B1 \land A0 \land B0)$

If that goes a little bit too quick for you:

First rewrite the first two terms:

$(\neg A1 \lor B1) \land (A1 \lor \neg B1) \Leftrightarrow $

$(\neg A1 \land A1) \lor (\neg A1 \land \neg B1) \lor (B1 \land A1)\lor (B1 \land \neg A1) \Leftrightarrow $

$\bot \lor (\neg A1 \land \neg B1) \lor (B1 \land A1) \lor \bot \Leftrightarrow $

$(\neg A1 \land \neg B1) \lor (A1 \land B1)$

Similarly, terms three and four work out to:

$(\neg A0 \land \neg B0) \lor (A0 \land B0)$

And so finally you get:

$((\neg A1 \land \neg B1) \lor (A1 \land B1)) \land ((\neg A0 \land \neg B0) \lor (A0 \land B0)) \Leftrightarrow $

$(\neg A1 \land \neg B1 \land \neg A0 \land \neg B0) \lor (\neg A1 \land \neg B1 \land A0 \land B0) \lor (A1 \land B1 \land \neg A0 \land \neg B0) \lor (A1 \land B1 \land A0 \land B0)$