Find the Simplified Sum of Products of a Boolean expression

math theory boolean-logic algebra truthtable
Jake Pillandfall picture Jake Pillandfall · Apr 30, 2011 · Viewed 15.8k times · Source

Just having some problems with a simple simplification. I am doing a simplification for the majority decoder with 3 inputs A, B and C. Its output Y assumes 1 if 2 or all 3 inputs assume 1. Y assumes 0 otherwise. Select its correct switching function Y=f(A,B,C).

So, after doing out a truth table I found the Canonical Sum of Products comes to

NOT(A).B.C + A.NOT(B).C + A.B.NOT(C) + A.B.C

This, simplified, apparently comes to Y = A * B + B * C + A * C

What are the steps taken to simply an expression like this? How is it done? How was this value gotten in this case?

Answer

highBandWidth picture highBandWidth · Apr 30, 2011

First, note that for a Boolean expression:

A= A + A

Now, see that 

NOT(A).B.C + A.NOT(B).C + A.B.NOT(C) + A.B.C
= NOT(A).B.C + A.NOT(B).C + A.B.NOT(C) + A.B.C + A.B.C + A.B.C
= (NOT(A)+A).B.C + A.(NOT(B)+B).C + A.B.(NOT(C)+C)
= B.C + A.C + A.B

Related questions

Subtracting a large unsigned binary number from a smaller one

I'm taking a computer organization and assembly language course. The written part of our lab this week has a question on it that has me stumped. The question reads... Subtract the following unsigned binary numbers (show the borrow and overflow …

Read More
Is the time complexity of the empty algorithm O(0)?

So given the following program: Is the time complexity of this program O(0)? In other words, is 0 O(0)? I thought answering this in a separate question would shed some light on this question. EDIT: Lots of good answers here! We …

Read More
How to test randomness (case in point - Shuffling)

First off, this question is ripped out from this question. I did it because I think this part is bigger than a sub-part of a longer question. If it offends, please pardon me. Assume that you have a algorithm that …

Read More