Copyright © 2006 Leaf Mindcraft
In this, the first of three Parts, I intend to discuss the mathematical science of logic, as it applies to programmers.
IntroductionLogic deals with statements that are either true of false and combinations of such statements using 'and', 'or' or 'not'. These articles, firstly, will discuss Boolean Algebra, which is a short hand used for writing such statements and manipulating them. Secondly, a diagram called a Venn diagram for representing various types of sets (collections of objects) will be discussed. Lastly, a special type of Venn diagram called a Karnaugh Map will be introduced. Karnaugh Maps help work out the particular logical statement one requires in a programming situation.
Boolean AlgebraWe shall deal with statements that are either true or false. Examples of such statements could be:-
"It is raining" or
"The end of the file has been reached" or
"The number is negative".
Such statements are represented in Boolean Algebra by a capital letter e.g. A. It turns out that to form any logical expression one only needs the operations 'and', 'or' or 'not'.
We shall represent 'and' by the multiplication symbol '.'
'or' by a plus symbol '+'
and 'not' by putting a bar above the expression to be notted.
e.g. A.B, or more normally, AB means 'A and B'
A+B means 'A or B'
_
A means 'not A'
The expression AB is only true when both A and B are true, otherwise it is false.
The expression A+B is true when either A or B or both A and B are true, otherwise it is false.
_
The expression A is only true when A is false.
Note the logical 'or' is called the 'inclusive or', because it includes both parts of it being true together. Commonly, when we speak, we say 'I am staying at home or going shopping', when the two events are mutually exclusive. This is called the 'exclusive or'.
To give some examples,
_
1. A B is true only when A is true and B is false.
_
2. A + B is true when A is true or B is false or both A is true and B is false.
In addition to the above notation, we shall use 0 (zero) for a false value,
(something that is definitely false), and
1 (one) for a true value,
(something that is definitely true).
We can now make statements such as:-
A.0 = 0 (if one statement in an 'and' is false, then the whole thing must be false)
A.1 = A (if one statement in an 'and' is true, then the final value depends on the other
statement)
A+0 = A (if one statement in an 'or' is false, then the final value depends on the other
statement)
A+1 = 1 (if one statement in an 'or' is true, then the whole thing must be true)
One should also note the following results:-
1. A(B+C) = AB + AC (the 'and' is said to be distributive over the 'or')
_ _ _
2. A + A = 1 (it follows that:- BA + BA = B(A+A)=B.1=B, a useful result)
_
3. A . A = 0 (think about it!)
_
_
4. A = A (a double negative results in a positive)
De Morgan's Laws are used for the derivation of the logical inverse of an expression.
The two basic results are that:-
____ _ _
1. A+B = A . B (the negation of an 'or' is an 'and' of negated quantities
e.g. not (living in Bracknell or working for B.Ae.)
is the same as not living in Bracknell and not working for B.Ae.
___ _ _
2. A.B = A + B (the negation of an 'and' is an 'or' of negated quantities)
De Morgan's Rule for negation of any expression is;-
1. Change all the 'or's to 'and's and all the previous 'and's to 'or's.
2. Negate all the capital letter variables.
e.g. consider the negation of A+BC
after step 1 we obtain:- A(B+C)
_ _ _ _ _ _ _
after step 2 we get the final result:- A(B+C) = AB + AC (by multiplying out).
In the second part, I intend to introduce the concept of Venn Diagrams.