Lecture 1: An Introduction to Boolean Algebra
The operation of almost all modern digital computers is based on two-valued or binary systems. Binary systems were known in the ancient Chinese civilisation and by the classical Greek philosophers who created a well structured binary system, called propositional logic. Propositions may be TRUE or FALSE, and are stated as functions of other propositions which are connected by the three basic logical connectives: AND, OR, and NOT. For example the statement:
"I will take an umbrella with me if it is raining or the weather forecast is bad"
Figure 1: A simple Proposition
connects the proposition I will take an umbrella with me functionally to the two propositions it is raining and the weather forecast is bad. We can see that the umbrella proposition can be fully determined by the raining and weather ones. In functional terms we can be consider the truth value of the umbrella proposition as the output of the truth values of the other two. We can represent this by means of a simple block diagram (Figure 1).
The meaning of the OR connective is that the corresponding output is TRUE if either one of the input propositions is TRUE, otherwise it is FALSE. Since there are only two possible values for any proposition, we can easily calculate a truth value for I will take an umbrella for all possible input conditions. This produces the Truth Table of the basic OR function:
Raining Bad Forecast Umbrella FALSE FALSE FALSE FALSE TRUE TRUE TRUE FALSE TRUE TRUE TRUE TRUE
We can make the propositions as complex as we require. For example, if we want to include the proposition I will take the car, we may make a statement such as: "If I do not take the car then I will take the umbrella if it is raining or the weather forecast is bad". However, to find the correct block diagram we have to state the proposition in a well structured way using brackets to indicate how the proposition is composed. The correct representation is:
(Take Umbrella) = ( NOT (Take Car ) ) AND ( (Bad Forecast ) OR (Raining ) )
Figure 2: Another Proposition
Notice that we have changed the IF verbal construction into an equation with binary variables. The block dia- gram is shown in Figure 2. To simplify the handling of complex binary connectives, the mathematician George Boole developed Boolean Algebra in the last century, us- ing ordinary algebraic notation, and 1 for TRUE and 0 for FALSE. In this course we will use the symbol · for the AND and + for the OR connectives which we call Boolean operators. The NOT operator, which is unary, we will denote with a post fix prime, eg A′ means NOT A. (Alternatives that you may see in books are ∧ for AND, ∨ for OR, and either over-score or prefix ¬ for NOT). Sometimes, when the meaning is clear from the context, we may omit the AND symbol. Using the values 1 for TRUE and 0 for FALSE the truth tables of the three basic operators are as follows.
AND · A B R 0 0 0 0 1 0 1 0 0 1 1 1