9
\$\begingroup\$

How to convert a Sum of Products (SOP) expression to Product of Sums (POS) form and vice versa in Boolean Algebra?

e.g.: F = xy' + yz'

\$\endgroup\$
  • 8
    \$\begingroup\$ Actually this is very much on topic to digital logic. It's equivalent to saying how do I change a circuit that consists of a bunch of and gates feeding an or gate to one consisting of a bunch of or gates feeding an and gate. \$\endgroup\$ – Chris Stratton Feb 7 '11 at 7:44
  • 1
    \$\begingroup\$ What's SOP and POS? \$\endgroup\$ – AndrejaKo Feb 7 '11 at 9:25
  • 3
    \$\begingroup\$ SOP = sum of products. POS = product of sums, e.g. (x + y)(~x + ~y). Logical "OR" is a sum, while "AND" is a product. \$\endgroup\$ – Eryk Sun Feb 7 '11 at 11:03
  • \$\begingroup\$ This is certainly taught in undergrad digital logic courses, but tyblu is right that this belongs in math SE. @TheLameProgrammer, Look up Karnaugh maps (K maps) and DeMorgan's theorem. \$\endgroup\$ – Eryk Sun Feb 7 '11 at 12:50
  • 2
    \$\begingroup\$ ... use DeMorgan's Laws? also, the example provided in the question is not a canonical SOP because all variables should be present in all terms right? \$\endgroup\$ – vicatcu Feb 7 '11 at 17:17
15
\$\begingroup\$

I think the easiest way is to convert to a k-map, and then get the POS. In your example, you've got:

  \ xy
 z \  00    01    11    10
    +-----+-----+-----+-----+
 0  |     |  x  |  x  |  x  |
    +-----+-----+-----+-----+
 1  |     |     |     |  x  |
    +-----+-----+-----+-----+

In this case, excluding the left column gives (x+y), and excluding the two bottom middle boxes gives (z' + y'), giving an answer of (x + y)(z' + y')

\$\endgroup\$
  • \$\begingroup\$ But it should be F = (x + y)(y' + z'). \$\endgroup\$ – Eryk Sun Feb 8 '11 at 3:20
  • \$\begingroup\$ Whoops you're right. It's been a while since I've done k-maps so I read it wrong. I've fixed the answer. \$\endgroup\$ – FryGuy Feb 8 '11 at 22:30
5
\$\begingroup\$

F= xy' + yz' it is in SOP form

This can also be soved using Simple Boolean Algebra techniques as:

Applying Distributive Law :- F=( xy') + y . z'

F= (xy' + y).( xy' + z') which is now converted to POS form.

\$\endgroup\$
4
\$\begingroup\$

Another method is just take the compliment of the given expression:

As: xy' + yz'

Taking its compliment:
(xy' + yz')'

=(xy')'.(yz')' {Using De Morgans Law's (a+b)'=a'.b'}

=(x'+y)(y'+z)

Which is also POS form...!

\$\endgroup\$
  • 6
    \$\begingroup\$ This gives a POS.But it's the complete opposite of the given expression. \$\endgroup\$ – Nirmal Seneviratne May 21 '16 at 15:47
2
\$\begingroup\$

Use DeMorgan's law twice.

Apply the law once:

F' = (xy' + yz')'
   = (xy')'(yz')'
   = (x'+y)(y'+z)
   = x'y' + x'z + yy' + yz
   = x'y' + x'z + yz

Apply again:

F=F''
 =(x'y'+x'z+yz)'
 =(x'y')'(x'z)'(yz)'
 =(x+y)(x+z')(y'+z')
 =(x+y)(y'+z')

Verify the answer using wolframalpha.com

xy' + yz'

(x+y)(y'+z')

Edit: The answer can be simplified one more step by the boolean algebra law of consensus

\$\endgroup\$
1
\$\begingroup\$

If you want to check your work after doing it by hand you could use a program like Logic Friday.

\$\endgroup\$
1
\$\begingroup\$

It is in a minimum/Sum of Products [SOP] and maximum/Product of Sums [POS] terms, so we can use a Karnaugh map (K map) for it.

For SOP, we pair 1 and write the equation of pairing in SOP while that can be converted into POS by pairing 0 in it and writing the equation in POS form.

For example, for SOP if we write \$x \cdot y \cdot z\$ then for pos we write \$x+y+z\$.

\$\endgroup\$
0
\$\begingroup\$

See the procedure at Conjunctive Normal Form: Converting from first-order logic.

This procedure covers the more general case of first order logic, but propositional logic is a subset of first order logic.

Simplifying by ignoring first order logic, it's:

  • Eliminate implications
  • Move negations inwards by applying DeMorgan's law
  • Distribute disjunctions over conjunctions

Obviously if your input is already in DNF (aka SOP), then obviously the first and second steps don't apply.

\$\endgroup\$
0
\$\begingroup\$

Let x = ab'c + bc'

x' = (ab'c + bc')'

By DeMorgan's theorem, x' = (a' + b + c')(b' + c)

x' = a'b' + a'c + bb' + bc + c'b' + c'c

x' = a'b' + a'c + bc + c'b'

Employing DeMorgan's theorem again, x = (a'b' + a'c + bc + c'b')'

x = (a + b)(a + c')(b' + c')(c + b)

\$\endgroup\$
  • \$\begingroup\$ Welcome to Electrical Engineering StackExchange. If you provide a new answer to an old question you should make it clear what you have added to the previous answers, or what was incorrect in previous answers. By the way, isn't your second line in POS form? The OP did not ask about reducing the equation so the rest of your answer could be confusing. \$\endgroup\$ – Joe Hass Nov 24 '13 at 15:50
  • \$\begingroup\$ This is correct. \$\endgroup\$ – Nirmal Seneviratne Jun 2 '16 at 3:18