0
$\begingroup$

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?

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

Logic Friday 1 came up with:

Q'  + S U  + S' R  + S' V 
$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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'$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.