# Simplify the following expression using Boolean Algebra into sum-of-products (SOP) expressions

Simplify the following expression using Boolean Algebra into sum-of-products (SOP) expressions $Q.S.U + (Q' + S').(R + V) + U.(R + V) + Q' + S.T.U$

$.$ = AND

$+$ = OR

This is what I have so far

$Q.S.U + (Q' + S').(R + V) + U.(R + V) + Q' + S.T.U$

= $Q.S.U + Q'.(R+V) + S'.(R+V) + R.U + U.V + Q' + S.T.U$

= $Q.S.U + Q'.R + Q'.V + S'.R + S'.V + R.U + U.V + Q' + S.T.U$

Are there any more ways to simplify this expression?

• Is $Q'$ the negative of $Q$ ? In this case note that $Q'+QSU=Q'+SU$ and $Q'+Q'R = Q'$. – user10676 Apr 25 '13 at 16:23

Logic Friday 1 came up with:

Q'  + S U  + S' R  + S' V


Of course one could work harder, but I just used Binary Decision Diagrams:

from cudd import Cudd
m = Cudd()
Q,S,U,R,V,T = (m.bddVar() for i in range(6))
F = Q & S & U | (~Q | ~S) & (R | V) | U & (R | V) | ~Q | S & T & U
G = ~Q | S & U | ~S & R | ~S & V
print(F == G)

and confirmed the answer by @AxelKemper. Incidentally, the code snippet above proves equivalence, but $G$ is also obviously a minimum-cost SOP.

Put the following 3 equivalences immediately into your toolbox!

Absorption: $P + PQ = P$

Adjacency: $PQ + PQ' = P$

Reduction: $P+P'Q = P+Q$

From what you have, $Q'$ absorbs both $Q'R$ and $Q'V$ so you can get rid of those.

Also, $Q'$ reduces $QSU$ to $SU$, which absorbs $STU$. So now you have:

$SU + S'R + S'V + RU + UV + Q'$

Use Adjacency to expand $UV$ to $SUV+S'UV$ ... Then $SUV$ gets absorbed by $SU$ and $S'UV$ by $S'V$

Likewise, use Adjacency to expand $RU$ to $RUS+RUS'$ ... Which get absorbed by $SU$ and $S'R$ respectively, giving you:

$SU + S'R + S'V + Q'$

So, again, the whole thing from what you have:

$Q.S.U + Q'.R + Q'.V + S'.R + S'.V + R.U + U.V + Q' + S.T.U$ = (Absorption)

$Q.S.U + S'.R + S'.V + R.U + U.V + Q' + S.T.U$ = (Reduction)

$S.U + S'.R + S'.V + R.U + U.V + Q' + S.T.U$ = (Absorption)

$S.U + S'.R + S'.V + R.U + U.V + Q'$ = (Adjacency)

$S.U + S'.R + S'.V + R.U.S + R.U.S' + S.U.V + S'.U.V. + Q'$ = (Absorption)

$S.U + S'.R + S'.V + Q'$