In the Boolean algebra blog post I proved a weird looking rule with the using a couple of the little tables.

Those tables are called truth tables.

They depict what outputs occur as the conditions of an input.

You can use truth tables to prove logical statements.

**Proving DeMorgan Theorem**

As ever writing is nothing without context

So as an exercise in truth tables I'm going to look at the two rules of DeMorgan theorem.

These two rules are

/(A + B) = /A . /B

and

/(A. B) = /A + /B

This is easier to do on paper than it is on a computer screen writing in text, but here goes...

First we need to look at how many inputs we have,

We have A and B, so we need two columns.

Our first conditions are

NOT ( A OR B )

So to start with we'll draw the truth table for

A OR B

A B | Q1

=======

0 0 | 0

0 1 | 1

1 0 | 1

1 1 | 1

Then we need to apply the NOT operation to the output Q1

Q1 | /Q1

0 => 1

1 => 0

1 => 0

1 => 0

So we know that the output of the truth table for /(A+B) looks like 1, 0, 0, 0 (for states 0,1,2,3)

Now we'll investigate the truth table for /A . /B

Lets start with A AND B

A B | Q

======

0 0 | 0

0 1 | 0

1 0 | 0

1 0 | 1

But what about NOT A and NOT B

/A /B | Q

1 1 | 1

1 0 | 0

0 1 | 0

0 0 | 0

So we know that the output of the truth table for /A . /B looks like 1, 0, 0, 0 (for states 0,1,2,3)

It's the same.

For a more complex problem it might be better to draw everything out inside a single truth table:

We'll do this to prove Demorgans second rule:

/(A . B) = /A + /B

A B | /A /B | A . B | /(A.B) | /A + /B

===========================

0 0 | 1 1

**| 0 | 1 | 1**

0 1 | 1 0 | 0 | 1 | 1

1 0 | 0 1 | 0 | 1 | 1

1 1 | 0 0 | 1 | 0 | 0

You see that the last two columns are the the statements used in DeMorgan theorem, and they do indeed prove DeMorgan theorem is correct.

**States.**

One thing mentioned above was that the states of inputs could be assigned names.

Where you have defined input names that are ordered, A, B, C or In1, In2, In3 you can assign the different states values in accordance with the binary numbering system

A B C = State name

0 0 0 = 0

0 0 1 = 1

0 1 0 = 2

0 1 1 = 3

1 0 0 = 4

1 0 1 = 5

1 1 0 = 6

1 1 1 = 7

## No comments:

Post a Comment