Introduction to Boolean Logic
Written by Harry Fairhead   
Friday, 28 September 2018
Article Index
Introduction to Boolean Logic
Binary arithmetic and flip-flops
Flip Flops - Time Enters the Logic
More Logic

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 basis of computing.

A Programmers Guide To Theory
First Draft

There is a more recent version of this:

Now available as a paperback and ebook from Amazon.

A Programmers Guide To Theory - NP & Co-NP

theorycover

Contents

  1. What Is Computable?
  2. Finite State Machines
  3. What is a Turing Machine? 
  4. Computational Complexity
  5. Non-computable numbers
  6. The Transfinite
  7. Axiom Of Choice
  8. Lambda Calculus
  9. Grammar and Torture
  10. Reverse Polish Notation - RPN
  11. Introduction to Boolean Logic
  12. Confronting The Unprovable - Gödel And All That
  13. The Programmer's Guide to Fractals
  14. The Programmer's Guide to Chaos*
  15. Prime Numbers And Primality Testing
  16. Cellular Automata - The How and Why
  17. Information Theory
  18. Coding Theory
  19. Kolmogorov Complexity

*To be revised

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 and 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.

What George Boole did to be recognized as the father of modern information technology was to come up with an idea that was at the same time revolutionary and simple.

This video, a trailer for a documentary celebrating the bicentenary of his birth on November 2, 1815 hints at how his radical discovery underpins the digital age:

 

 

Who was George Boole?

A contemporary of Charles Babbage, whom he briefly met, Boole is these days credited as being the "forefather of the information age". An Englishman by birth, in 1849 he became the first professor of mathematics in Ireland’s new Queen’s College (now University College) Cork. 

 

georgeboole

George Boole
November 2, 1815 - December 8, 1864

 

He died at the age of 49 in 1864 and his work might never have had an impact on computer science without Claude Shannon, who 70 years later recognised the relevance for engineering of Boole’s symbolic logic. As a result, Boole’s thinking has become the practical foundation of digital circuit design and the theoretical grounding of the the digital age. 

Boolean Logic 

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.

 

Banner

 <ASIN:1782050043>

<ASIN:1603861254>

<ASIN:1855065835>

<ASIN:0780334264>

<ASIN:0486427854>

<ASIN:1593271042>

<ASIN:0486483851>



Last Updated ( Friday, 28 September 2018 )