3
$\begingroup$

I have come across a couple questions while doing my digital logic work.

1) Is it possible to simplify these, while keeping each a product of sums? (I'm leaning towards no--the only way I could see to simplify them would be to distribute.) They're separate problems. $(a+b+c)(a'+b'+c')$ $(x+y)(x'+y+z')$

2) Find the minimum sum of products expression (I honestly didn't even know how to begin this one, if you could just get me started...): $x_1'x_3'x_5'+x_1'x_3'x_4'+x_1'x_4x_5+x_1x_2'x_3'x_5$ - The hint was to use the consensus theorem: $xy+yz+x'z=xy+x'z$

3) Find the minimum product of sums expression (again, if you could just help me get started) $x_1x_3'+x_1x_2+x_1'x_2'+x_2'x_3$

Any help is greatly appreciated! Thanks!

2 Answers 2

1

1b)

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

can be simplified to

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

Convince yourself using a thruth table.

2)

$x_1'x_3'x_5'+x_1'x_3'x_4'+x_1'x_4x_5+x_1x_2'x_3'x_5$

can be simplified to

$x_1'x_3' + x_1'x_4x_5 + x_2'x_3'x_5$

Such simplifications can be done using a Karnaugh-Veitch map.

3)

$x_1x_3'+x_1x_2+x_1'x_2'+x_2'x_3$

is a sum of products.

It can be minimized to

$x_1 + x_2'x_3$

Written in Conjunctive Normal Form (CNF):

$(x_1 + x_2')(x_1 + x_3)$

0

1b)

$(x+y)(x'+y+z')=\text{ (Distribution)}$

$y+x(x'+z')= \text{ (Reduction)}$

$y +xz'$

This is actually an instance of a General Reduction Theorem that says that:

General Consensus Theorem

$PQ+PQ'R=PQ+PR$

$(P +Q)(P+Q'+R)=(P+Q)(P+R)$

We can also use this for 2):

$x_1'x_3'x_5'+x_1'x_3'x_4'+x_1'x_4x_5+x_1x_2'x_3'x_5=\text{ (Distribution)}$

$x_1'(x_3'x_5'+x_3'x_4'+x_4x_5)+x_1x_2'x_3'x_5=\text{ (Consensus)}$

$x_1'(x_3'x_5'+x_3'x_4'+x_4x_5+x_3'x_5)+x_1x_2'x_3'x_5=\text{ (Adjacency)}$

$x_1'(x_3'+x_3'x_4'+x_4x_5)+x_1x_2'x_3'x_5=\text{ (Absorption)}$

$x_1'(x_3'+x_4x_5)+x_1x_2'x_3'x_5=\text{ (Distribution)}$

$x_1'x_3'+x_1'x_4x_5+x_1x_2'x_3'x_5=\text{ (General Reduction)}$

$x_1'x_3'+x_1'x_4x_5+x_2'x_3'x_5$

Finally, the Consensus Theorem also works great for 3):

$x_1x_3'+x_1x_2+x_1'x_2'+x_2'x_3=\text{ (Consensus)}$

$x_1x_3'+x_1x_2+x_1'x_2'+x_2'x_3+x_1x_2'=\text{ (Adjacency)}$

$x_1x_3'+x_1+x_2'+x_2'x_3=\text{ (Absorption)}$

$x_1+x_2'$