Introduction to Boolean Logic
Written by Harry Fairhead   
Article Index
Introduction to Boolean Logic
Binary arithmetic and flip-flops
Universal Gate

It may sound like a daunting topic, but Boolean logic is very easy to explain and to understand. It represents the simplest of all the logics and the very basics of computing.

Logic, logic everywhere

Computers and logic are inseparable - right?

They are now but at the start things were much more hazy.

The first computers were conceived as automatic arithmetic engines and while their creators were aware that logic had something to do with it all, they weren’t 100% clear as to the how or why.

Even today we tend to be over simplistic about logic and its role in computation and understanding the world. Even George Boole the man who started it all off was a bit over the top with the titles of his books on the subject -

Mathematical Analysis of Thought and An Investigation of the Laws of Thought.

Boole’s work certainly started modern logic off on the right road, but it certainly wasn’t anything to do with the “laws of thought”.

The fact of the matter is that even today we have no clear idea what laws govern thought and if we did the whole subject of artificial intelligence would be a closed one.

Boolean logic is very easy to explain and to understand.

  • You start off with the idea that some statement P is either true or false, it can’t be anything in between (this called the law of the excluded middle).
  • Then you can form other statements, which are true or false, by combining these initial statements together using the fundamental operators And, Or and Not.

Exactly what a "fundamental" operator is forms an interesting question in its own right - something we will return to later when we ask how few logical operators do we actually need?

The way that all this works more or less fits in with the way that we used these terms in English.

For example, if P is true then Not(P) is false So, if “today is Monday” is true then “Not(today is Monday)” is false. We often translate the logical expression into English as “today is Not Monday” and this makes it easier to see that it is false if today is indeed Monday.

Are you following?

Well this is the problem with this sort of discussion. It very quickly becomes convoluted and difficult to follow and this is part of the power of Boolean logic. You can write down arguments clearly in symbolic form.

Truth Tables

The rules for combining expressions are usually written down as tables listing all of the possible outcomes. These are called truth tables and for the three fundamental operators these are:

 

P Q P AND Q
F F F
F T F
T F F
T T T

 

P Q P OR Q
F F F
F T T
T F T
T T T

 

P NOT P
F T
T F

 

Notice that while the Boolean And is the same as the English use of the term, the Boolean Or is a little different.

When you are asked would you like "coffee OR tea" you are not expected to say yes to both!

In the Boolean case however “Or” most certainly includes both. When P is true and Q is true the combined expression (P Or Q) is also true.

There is a Boolean operator that corresponds to the English use of the term “or” and it is called the “Exclusive or” written as EOR or XOR. Its truth table is

P Q P XOR Q
F F F
F T T
T F T
T T F

 

and this one really would stop you having both the tea and the coffee at the same time (notice the last line is True XOR True = False).

Practical truth tables

All this seems very easy but what value has it?

It most certainly isn’t a model for everyday reasoning except at the most trivial “coffee or tea” level.

We do use Boolean logic in our thinking, well politicians probably don’t but that’s another story, but only at the most trivially obvious level.

However, if you start to design machines that have to respond to the outside world in even a reasonably complex way then you quickly discover that Boolean logic is a great help.

For example, suppose you want to build a security system which only works at night and responds to a door being opened. If you have a light sensor you can treat this as giving off a signal that indicates the truth of the statement:

P = It is daytime.

Clearly Not(P) is true when it is night-time and we have our first practical use for Boolean logic!

What we really want is something that works out the truth of the statement:

 R= Burglary in progress

from P and

 Q = Window open

A little raw thought soon gives the solution that

 R = Not(P) And Q

That is the truth of “Burglary in progress” is given by the following truth table:

 

P Q NOT(P)
NOT(P)AND Q
F F T F
F T T T
T F F F
T T F F

 

From this you should be able to see that the alarm only goes off when it is night-time and a window opens.

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.

 

Banner

 

<ASIN:1603861254>

<ASIN:1855065835>

<ASIN:0780334264>

<ASIN:0486427854>

<ASIN:1593271042>

<ASIN:0486483851>



 
 

   
RSS feed of all content
I Programmer - full contents
Copyright © 2014 i-programmer.info. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.