Deriving a Boolean function from a table describing the output d of a Boolean function

Question

I have been presented with the following question:

The following table describes the output d of a Boolean fun with three input values a, b, and c.

 a  b  c  |  d 
----------+----
 0  0  0  |  1 
 0  0  1  |  1 
 0  1  0  |  1 
 0  1  1  |  0 
 1  0  0  |  0 
 1  0  1  |  0 
 1  1  0  |  0 
 1  1  1  |  0 

Give this Boolean function using a suitable combination of AND, OR, XOR, NOT, NAND, NOR or XNOR.

Why is the correct answer:

d := (((NOT a) AND (NOT b)) AND (NOT c)) OR
(((NOT a) AND (NOT b)) AND c) OR
(((NOT a) AND b) AND (NOT c))

My Answer. (((NOT a) AND (NOT b)) AND (NOT c))

a   b   c     d
===============
0   0   0     1      
.
. 
.

How is this derived?

Answer 1

The answer you give is called the sum-of-products (SOP) formulation. Look at the three large terms joined by ORs:

• ((NOT a) AND (NOT b)) AND (NOT c))
• ((NOT a) AND (NOT b)) AND c)
• ((NOT a) AND b) AND (NOT c)

Now look at the truth table, in which exactly three lines have a 1 in the d column. Each of these three lines corresponds to one of the three terms.

Briefer answers can be composed, such as d := (NOT a) AND (NOT(b AND c)), but they are not the sum-of-products formulation you have given.

Answer 2

• Check the upper half of the table. a has to be false for fun to be true.
• Also, both b and c can't be true simultaneously. So, it has to be !(b && c).
• This should boil fun down to !a && !(b && c)
• You can apply De Morgan's theorem to the second part and use !b || !c but a has to be false even then, so: !a && (!b || !c) is what you end up with.

Answer 3

For 3 variables, 8 entries (2^3) present an exhaustive combination of all possible variable between the 3 variables a, b, c. The variable d is (as can be seen) the output of some function say f(x).

Now, since the 8 entries include all the possible variations, what we can infer is that the output d is boolean 1 only when the specific combination occurs. The result is 0 in all other cases.

So we simply combine all the rows that have the output as 1. The result that you have follows this.

The procedure is simple:

• Take all the rows with the output as 1.
• For every row, output an expression which will result into a 1 for the value of the variables.
  • AND every variable. If any variable has the value 0, NOT it before ANDing it.
• OR all the 8 expressions found in the step above.

Answer 4

The easiest way to derive a function from a (complete) truth table is by reading only the lines with a one (or zero) as result and writing down the disjunctive (or conjunctive) normal form.

In your table there are fewer results 1 than 0, so disjunctive normal form will be shorter. As you can see from the table, d will be 1 in exactly 3 cases:

• a=0, b=0, c=0
• a=0, b=0, c=1
• a=0, b=1, c=0

Just put these together and you get: (! = not, & = and, v = or)

d = (!a & !b & !c) v (!a & !b & c) v (!a & b & !c)

This form automatically excludes all other cases. You can still simplify this formula. A closer look at the truth table tells you that the value of c doesn't matter if both a and b are 0. Thus the first two parts can be collapsed to get the following disjunctive form: (no longer the normal form)

d = (!a & !b) v (!a & b & !c)

It can get even shorter if you apply distributivity:

d = !a & (!b v (b & !c))

Almost done:

d = !a & (!b v b) & (!b v !c)   | applying (x v !x) == 1 and (1 & y) == y
  = !a & (!b v !c)              | applying De Morgan (!a v !b) == !(a & b)
  = !a & !(b & c)

Done.

Answer 5

As someone mention before you should have a look at Karnaugh map. check it on wikipedia It may look a bit complicate at first glance but once you get it it is extremely simple to derive the optimum expression for any truth table.

The figure below shows the Karnaugh map for the given truth table.

\ AB
C\  00  01  11  10
  \----------------
0 | 1 | 1 | 0 | 0 |
  |----------------
1 | 1 | 0 | 0 | 0 |
   ----------------

The first thing you have to do when using Karnaugh is to copy the truth table to the map. I'll let you figure out out to do this.

The next step is to group the ones, the wikipedia article describes how to do this.

Finally working out the solution

From the Karnaugh map it is possible to see that the output is true when (!A & !B) no matter the value of C, the output is also true when (!A & B & !C).

Hence the function can be written as: D = (!A & !B) OR (!A & B & !C)

an alternative solution is: D = (!A & !C) OR (!A & !B & C)