Electronic Design Automation

6.2.4. Boolean representation conversion

6.2.4.1. CNF vs. DNF

SOP-to-POS and POS-to-SOP conversions can be achieved by applying double complements. By applying De Morgan's Law, an SOP (a POS) formula ϑ becomes a POS (an SOP) one ϑ′ after the first complement. We can then convert the POS (SOP) formula ϑ′ to an SOP (a POS) one ϑ” by the distributive law. Finally, applying De Morgan's Law again for the second complement, we convert the SOP (POS) formula ϑ” to a POS (an SOP) one ϑ‴. Note that the conversions may suffer from an exponential blow-up in formula sizes due to the intermediate step of applying the distributive law.

Example 6.25

The 2n-input Achilles heel function (x¹ + y¹)(x² + y²) … (xⁿ + yⁿ) has 2ⁿ product terms in an SOP representation ...