Find the Simplified Sum of Products of a Boolean expression

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 thi开发者_C百科s case?

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

Incidentally WolframAlpha is great for doing (checking) Boolean maths in which case the format for your example is:

~A && B && C || A && ~B && C || A && B && ~C || A && B && C

Also your specific expression is actually on this page as an example, done differently to the other answer given.

You would benefit from understanding some basic logic concepts:

• De Morgan's Laws explain how to translate ANDed terms into ORed terms (and vice versa). This is a very powerful concept worth learning, it allows the translation of a logic expression into pure NAND or pure NOR form for which there are very good reasons

• A Karnaugh map can be used to visually translate logic expressions into their first canonical form. Using a Karnaugh map is impractical in many real life cases but a really great learning technique

One straightforward way of finding the first canonical form for any logic expression is to generate the appropriate truth table and then examine the inputs that result in an output of 1.

For each row in a truth table where the output is 1, you can relatively easily form a logic expression for that row only. The full logic expression comes from ORing all the expressions for each row. This will be a minimal expression (there may be others, none will be more minimal).

Another explanation.

We have (1):

(not(A) and B and C ) or (A and not(B) and C) or (A and B and not C) or (A and B and C).

We know that:

A = A or A.

So we can rewrite (1) to (2):

(not(A) and B and C ) or (A and B and C) or
(A and not(B) and C) or (A and B and C) or
(A and B and not C) or (A and B and C)

We also know that:

(A and B) or (A and not B) = A and (B or not B) = A

So we can rewrite (2) to (3):

(B and C) or (A and C) or (A and B)

The idea is to find groups that can be (partially) eliminated to simplify the equation.