Introduction to Boolean Logic

### New Book Reviews!

 Introduction to Boolean Logic
Article Index
Introduction to Boolean Logic
Binary arithmetic and flip-flops
Universal Gate

## From Truth Tables to Electronic Circuits

Not only does this little demonstration illustrate why Boolean logic is useful in designing such systems, it also explains why electronics circuits to perform Boolean logic are commonplace. You can buy integrated circuits that perform And, Or and Not and many other combinations of these operations in a single easy to use package.

Where is the “truth” in this?

Clearly Boolean logic works with “true” and “false” and this is certainly how Boole himself thought about it, however you can work with the same system of operators and results no matter what you call the two states - up/down, on/off or zero/one.

In the electronics case it is more natural to think of high and low voltage as representing the natural states that we are working with. An explanation that involves Boolean logic often sounds more appropriate when expressed in terms that belong to the underlying subject matter but it is still the same Boolean logic.

What has all of this got to do with computers?

The answer is two-fold. The first connection is that computers contain electronic circuitry that behaves in much the same way as the burglar alarm. In general Boolean logic helps when you need to design a circuit that has to give an output only when certain combinations of inputs are present.

Such a circuit is called “combinatorial logic” and there are lots of them inside a computer. You can specify the behavior of any piece of combinatorial logic using a truth table. The only difference is that in most cases the tables are very large and converting them into efficient hardware is quite a difficult job.

## Binary arithmetic

The second connection is actually just a special case of the first but it is very important and it often confuses people. Boolean logic can be used to implement binary arithmetic.

Notice that there is no suggestion that binary arithmetic and Boolean logic are the same thing - they aren’t. Binary arithmetic is just an example of a place value system for representing values. That is, we humans work in base 10 and computers find it easier to work in base two because they don’t have ten fingers.

However when you do binary arithmetic you follow standard rules that determine how you should combine bits together to produce result bits. These rule can be expressed as combinatorial logic - in other words a truth table.

You can easily construct a table showing how to add two bits together to give a result and a carry to the next place:

 A B Result Carry 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1

If you don't know how to add two bits together then simply accept that the table as your instructions for how to do it.

You can see that this is just another truth table and the combinatorial logic needed for it can be produced in the usual way. Actually this is only a half adder - yes this is the real technical term - in that it doesn’t add a carry bit that might have been generated by a previous pair of bits.

The table for a “full adder”, this too is the correct technical term is:

 A B C Result Carry 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 1 0 1 1 1 0 0 1 1 1 1 1 1

So combinatorial circuits are the main connection between Boolean logic and computer hardware but there is more to computer hardware than combinatorial logic.

Occasionally you will hear computers referred to just one huge piece of Boolean logic but this is an overstatement. Large chunks are just And, Or and Not gates but there are also huge chunks that are not describable in terms of pure Boolean logic.

## Flip-flops

Computers also include “sequential” logic, which includes an element of time.

For example, a flip-flop, again perfectly good jargon, is a circuit that changes state like a pendulum flips from side to side.

The odd thing is that you can make a flip-flop from two Not gates and it is true that most sequential logic can be understood in terms of combinations of logic gates. However, this is an incomplete explanation and requires something beyond Boolean logic.

For example, Boolean logic cannot cope with the statement:

`A = NOT A`

If A is true then NOT A is false and so A must be false but this means that NOT A is true, which means that A must be true, which means, and so on…

So from the point of view of Boolean logic this is nonsense.

Now imagine that the on one side of a blackboard you write “A is true” and on the other side you write “Not A is true”. Now when you read “A is true” you are happy with this. When you turn the blackboard over you see “Not A is true” and so conclude A is false. As you keep flipping the board over the value of A flips from true to false and back again.

This turning over of the blackboard is the extra part of the theory needed to deal with sequential logic - it shows how time changes things. So computer hardware is not just one large statement in Boolean logic, which just happens to be true or false.

Its state changes with every tick of its system clock.

## Boolean logic in programming

Boolean logic is fundamental to the design of computer hardware even if it isn’t the whole story. The same holds true for programming.

A program also needs the element of time built into it to make it work and this takes it beyond the bounds of simple Boolean logic. However there are times when simple common sense reasoning lets even the best programmer down.

For example, a common task is making a decision using an IF statement:

`IF (A>0 AND A<10) THEN do something`

The bracket following the IF is almost pure Boolean logic and the something only gets done if it works out to be true.

So far so simple, so simple in fact that many programmers decide that they don’t need to know anything about Boolean logic at all; a serious error.

Consider how you would change this example so that the “something” was done when the condition was false. The simplest way is to write:

`IF NOT(A>0 AND A<10) THEN do something`

However this offends some programmers who want to rewrite the condition not using the NOT.

Try it and see what you come up with.

A common mistake is to use:

`IF (A<=0 AND A>=10) THEN do something`

This isn’t correct and if you don’t believe it simply write out the truth table for both. The correct NOT of the condition is:

`IF (A<=0 OR A>10) THEN do something`

The switch from AND to OR shocks many experienced programmers and it is a source of many programming errors.

My advice is that if you can write a logical condition in a natural form but you really need the NOT of it then just write NOT in front of it!

Otherwise learn De Morgan’s laws:

`NOT(A AND B)=NOT(A) OR NOT(B)`

and

`NOT(A OR B) = NOT(A) AND NOT(B)`

Boolean logic is important as a fundamental way of thinking about very simple situations which involve combinations of two states.

What it is not is a theory of thought or of the way computers work. It is not even essential to designing or using a computer but it does make both tasks easier.

If you’re serious about computing you need to be at home with Boolean logic in much the same way that you are at home with arithmetic - binary arithmetic of course.

<ASIN:0965193403>

<ASIN:1782050043>

<ASIN:0471732788>

<ASIN:0962781592>

<ASIN:0071360573>