Logic isn't the most exciting of subjects and you might think that it had its day with the Greeks, but you would be wrong. Logic isn't just part of programming, it can be all of  it!  

If your computer was intelligent then it would be easy for it to join in a sensible argument.

The sort of thing I have in mind is:

Mother: If is sunny we will have a picnic.

Child: (Looks out of window)  
              It is sunny today.

Mother:  Get the picnic basket.

Of course this sort of argument is so slight that it almost doesn't deserve the dignity of the title.

Even so, imagine a world where the logical connection between such simple statements isn't obvious - well that's how it is with computers.

If you place the statement 'if it is sunny we will have a picnic' and 'it is sunny today' in a database then they will just sit there and nothing will happen.

No conclusions will be drawn from the facts stored in a database because the machine doesn't have the slightest idea how to manipulate facts to produce new facts.

Trying to implement human reasoning on a computer would seem to be a good place to start the task of creating an intelligent computer because reasoning is so easy - isn't it?

The Greeks Had A Word For It

From the earliest times people, philosophers mainly, have been trying to work out the rules that make an argument valid.

The reasons for this interest was that people really didn't know what constituted a proof that something was true.

For example, Pythagoras suggested that the sum of the squares on the two short sides of a triangle always equalled the square on the longer side.

He had tried it out on a few triangles that happened to be lying around and it was true, as far the accuracy of his measuring instruments would go - but is it true for all triangles?

What more has to be done to establish that this fact is true for all triangles?

In this case we are looking at the problem of mathematical proof but the same difficulties exist in every day argument. If two people have access to the same facts and yet come to different conclusions how do you decide which one is right?

In an attempt to solve all of these difficulties the Greeks created the subject of logic.

Logic

Logic is the study of how the known truth of one set of statements can be used prove the truth of other statements.

Notice that this view of the problem was something of a breakthrough in its own right.

Previously people had been worried about establishing absolute truth but logic is about deriving the truth of one set of statements - the theorems - from another set of statements - the premises - that are assumed to be true.

For example, if you know that two statements A and B are true then you can claim that the combined statement A AND B is true.

If statement A is

"The weather is good"

and B is

"We are at the seaside"

then A AND B is

"The weather is good AND we are at the seaside".

Clearly in this case if A is true and B is true then:

"The weather is good AND we are at the seaside"

is also true.

You may think that this is trivial but in this simple idea lies all of traditional computing and most of the future too. One of the problems in trying to understand what logic is all about is that it tends to be littered with old fashioned jargon based on the original Greek and Latin terms - like premises, theorems etc. Don't be put off by the jargon, it is no more difficult than any other jargon.

The Greeks wrote down many different standard forms of acceptable argument.

For example, the little dialogue about picnics is a case of the modus ponens law which is in general:

IF A implies B
AND A is true 
THEN DEDUCE B is true

The only other basic law of logical argument that they proposed was the chain law which is

IF A implies B 
 AND B implies C
THEN DEDUCE A implies C

From these two forms of argument the Greeks could deduce everything else.

George Boole

Not very much important happened in the study of logic until George Boole noticed that what it was really all about was a sort of arithmetic of truth. 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. 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 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. 

George Boole
November 2, 1815 - December 8, 1864

If you take the relationship between the truth of A and the truth of B and the resulting truth of A AND B then you can draw up a table of the possibilities where T and F stand for True and False respectively.

This looks very much like a sort of multiplication table showing how two truth values are combined. Boole extended this idea to include all of the other possible ways of combining truth values.

The best known of these are AND, OR and NOT.

A compound statement A OR B is true if either or both A and B are true. NOT A simply 'flips' the truth value of A, if it is true then NOT A is false and vice versa.

Boole very quickly arrived at an algebra of truth values that we now call Propositional Calculus or Boolean logic in honour of the man himself.

The rules of Boolean logic, some are obvious some less so, are -

Commutative laws

 A AND B  =  B AND A     
  A OR B  =  B OR A     

Associative laws

A AND (B AND C) = (A AND B) AND C     
 A OR  (B OR C)  = (A OR B) OR C

Distributive laws

A AND (B OR C) = (A AND B) OR (A AND C)      
A OR (B AND C) = (A OR B) AND (A OR C)

De Morgans laws

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

You might have come across Boolean logic before because it is the basis of a lot of computer science. The circuits that go to make up a computer work in terms of two voltages but these are combined in exactly the same way as truth values in Boolean logic. If you are a programmer then you will certainly have used AND, OR and NOT within  IF statements to make complex selections and choices.

To give you an example of the sort of use that Boolean logic is conventionally put what is the truth value of

 (NOT A AND B) OR (A OR NOT B)

The answer is easy to find using the laws of Boolean logic -

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

using De Morgans law on the second bracket which gives.

(NOT A AND B) OR NOT(NOT A AND B)

which is always TRUE because the brackets are identical and the whole expression is like C OR NOT C which is always true (think about how it could be false!).

<ASIN:3540006788>

<ASIN:0792314476>

<ASIN:0763773379>

<ASIN:0198538324>

<ASIN:1782050043>

<ASIN:1871962439>