I'm having some trouble with reducing the Sum of Products expressions for some questions on an upcoming exam. Below is the table (which is correct) for the first part of the question, the second part is to simplify the SOP.

a b c y SOP 0 0 0 0 - 0 0 1 0 - 0 1 0 0 ¬A B ¬C 0 1 1 1 ¬A B C 1 0 0 0 - 1 0 1 1 A ¬B C 1 1 0 1 - 1 1 1 1 A B C

So this results in the SOP being: ¬AB¬C + ¬ABC + A¬BC + ABC

But I still need to simplify this into its most basic form.

Is there a method you can use indefinitely to reduce SOP expressions?

  • $\begingroup$ One possible step for first two terms: ¬AB¬C + ¬ABC = ¬AB(¬C + C) = ¬AB1 = ¬AB $\endgroup$ – CiaPan May 23 '14 at 11:38
  • $\begingroup$ @Ciapan I assume that you take what is common (¬AB) and disregard what is uncommon (¬C/C) as either way, as long as ¬AB is true it doesn't matter what C is? $\endgroup$ – Connor Cartwright May 23 '14 at 11:45
  • $\begingroup$ For the sake of Boole, NO! I do NOT discard any different things! I just make use of the fundamental axioms and theorems of the boolean algebra to simplify the expression: associativity allows me to treat (¬AB) as a single subexpression in ¬ABC=(¬AB)C, then thanks to distributivity I can exclude the common term (¬AB) from a sum, next the law of excluded middle reduces (¬C+C) to 1, and finally 1 is an identity element of logical conjunction, so - only at that place - can be 'discarded'. $\endgroup$ – CiaPan May 23 '14 at 15:14

So we have, from the truth-table:

$$¬AB¬C + ¬ABC + A¬BC + ABC$$

By using the distributive law (DL), twice, we can further simplify the expression:

$$\begin{align}\color{blue}{¬AB}¬C + \color{blue}{¬AB}C + \color{red}{A}¬B\color{red}{C} + \color{red}{A}B\color{red}{C} & = \color{blue}{\lnot AB}(\lnot C + C) + \color{red}{AC}(\lnot B + B)\\ \\ &= \lnot AB(1) + AC(1)\\ \\ &= \lnot AB + AC\end{align}$$

  • $\begingroup$ So what you're doing is finding what is common between the outputs, and putting them together? Does it matter how you do this, E.g. if you had ¬ABC + A¬BC + AB¬C + ABC, could you put each of the first three into the last, to come out with BC + AC + AB? $\endgroup$ – Connor Cartwright May 23 '14 at 12:17
  • $\begingroup$ You could pull out BC from $\lnot ABC$ and $ABC$ to get $BC(\lnot A +A) = BC$. The middle two terms have only $A$ in common, and will not reduce to AC + AB: $A\lnot BC + AB \lnot C = A(\lnot BC+B\lnot C) \neq AC + AB$. $\endgroup$ – Namaste May 23 '14 at 12:24
  • $\begingroup$ Can you only put each one into another once: you put ¬ABC into ABC to get BC, does that mean that using ABC is now off limits? Or could it still be used with A¬BC and AB¬C? $\endgroup$ – Connor Cartwright May 23 '14 at 12:48
  • $\begingroup$ Yes, ABC is done, and we cannot use it again, since we transform $ABC + \lnot ABC$ into BC. $\endgroup$ – Namaste May 23 '14 at 12:52

As you have only three variables/inputs, maybe you can use Karnaugh Maps?

  • $\begingroup$ I'm looking into Karnaugh Maps now, thanks for the suggestion :D. $\endgroup$ – Connor Cartwright May 23 '14 at 12:15

¬AB¬C + ¬ABC + A¬BC + ABC

¬AB(C + ¬C) + AC(¬B + B)

¬AB + AC

Similar SOP upto 3 variables can be solved using Karnaugh Maps and greater than 3 can be solved either by using the laws of Boolean algebra (mainly DeMorgans Law, Complimentary Law, Assosciative law etc) or a more complicated method called quine mccluskey method

  • $\begingroup$ So here you've pushed the first output into the second and combined them to make ¬AB, and put the third output into the fourth to get AC? Does it matter which outputs you put into the others? E.g. if you had ¬ABC + A¬BC + AB¬C + ABC, could you put each of the first three into the last, to come out with BC + AC + AB? $\endgroup$ – Connor Cartwright May 23 '14 at 12:12
  • $\begingroup$ Most informative answer here. $\endgroup$ – Doug Spoonwood May 24 '14 at 0:21

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.