# Lecture 9: Branching II / Boolean Algebra

## Boolean Algebra

George Boole (1815-1864)

English mathematician. His work "The mathematical analysis of logic"  (1847) established the basis of modern mathematical logic, and his boolean algebra can be used in designing computers.
Boole's system is essentially two-valued. This can be symbolized by
 0     or   1 "binary representation" TRUE  or FALSE "truth representation" 0 V   or  5 V "TTL electronics (transistor-transistor logic)" 0 pC  or  1 pC  (pC = pico-Coulomb) "the charge in a condensator, the elementary memory unit in (dynamic) RAM"

In the previous lecture (aula 8) we have seen how we can control the flow of the program by the branching instructions if ... then and if ... then ... else. We used conditions like (x<1.0). Now imagine we apply this to calculate the square-root of (x2- 4). Clearly, this doesn't have an answer for x between -2 and +2. It would be nice to check if x is in this range or not. We could solve this with
if (x<2) then
if (x>-2) then
WriteLn('Error');
Much nicer would be if we could do this in a single condition. We will now see that exactly that is possible
if ((x<2) AND (x>-2)) then WriteLn('Error');
which obviously mean that both conditions (x<2 and x>-2), should be true for the complete condition to be true.
This is an example of a Boolean calculation
condition3 := condition1 AND condition2;
if condition3 then instruction;
Other Boolean algebra operators that can be used in PASCAL are OR and XOR. (Others that are not implemented include NAND and NOR). The AND and OR operations are obvious. The XOR operation is a little complicated. a XOR b means "a or b true, but not both!"
Finally, there is the boolean negator NOT. It means taking the opposite; if a is TRUE, NOT a is FALSE, and vice cerse. Wheras AND, OR and XOR need two operands (for example a XOR b), NOT needs only one (NOT a).
With these four operators we can calculate all possible conditions we will need.

For completeness sake, here is the complete calculation tables ("truth tables") for the four Boolean operators used in modern programming languages.

 Boolean operator AND OR XOR NOT
AND
 a b a AND b TRUE TRUE TRUE TRUE FALSE FALSE FALSE TRUE FALSE FALSE FALSE FALSE
OR
 a b a OR b TRUE TRUE TRUE TRUE FALSE TRUE FALSE TRUE TRUE FALSE FALSE FALSE
XOR
 a b a XOR b TRUE TRUE FALSE TRUE FALSE TRUE FALSE TRUE TRUE FALSE FALSE FALSE

NOT
 a NOT a TRUE FALSE FALSE TRUE

Examples:

a := 1;
b := -2;
c := 3;
d := 3;

if (a>0) then
WriteLn('TRUE')
else
WriteLn('FALSE');

(a>0)                     TRUE
(b>0)                     FALSE
(a>0) AND (b>0)           FALSE
(a>0) OR (b>0)            TRUE
(a>0) XOR (b>0)           TRUE
NOT (a>0)                 FALSE
(NOT (a>0)) OR (b>0)      FALSE
(2=b) OR (NOT (2=b))      TRUE
(NOT (c>0)) XOR (d>0)     TRUE

## Boolean algebra for integers

We can also apply boolean algebra to complete numbers (byte, word, integer, longint, see aula 5). Although this was not in the original idea of Boole, we can easily perform the same type of calculations with numbers, as long as we do this "one bit at a time" and use the representations "1 = TRUE" and "0 = FALSE". With this convention, the truth tables for bit-wise boolean algebra become.
AND
 a b a AND b 1 1 1 1 0 0 0 1 0 0 0 0
OR
 a b a OR b 1 1 1 1 0 1 0 1 1 0 0 0
XOR
 a b a XOR b 1 1 0 1 0 1 0 1 1 0 0 0
NOT
 a NOT a 1 0 0 1
 49 = 1 1 0 0 0 1 24 = 0 1 1 0 0 0 49 OR 24 = 1 1 1 0 0 1 = 57
As an example, imagine we want to calculate 49 OR 24
First we have to convert these numbers to the binary system (see aula 3):
49 = 1*32 + 1*16 + 0*8 + 0*4 + 0*2 + 1*1 = 110001
24 = 0*32 + 1*16 + 1*8 + 0*4 + 0*2 + 0*1 = 011000
Then we do a bitwise calculation with the conventions as in the table above (1 OR 1 = 1, 1 OR 0 = 1, 0 OR 1 = 1, 0 OR 0 = 0), which will give  111001
This we then convert back to the decimal system and we get
111001 = 1*32 + 1*16 + 1*8 + 0*4 + 0*2 + 1*1 = 57

## Multiple branching: Case ... Of

In the previous lecture (see aula 8) we have seen how to use the if ... then instruction to branch between two possible parts of the program. In some cases, we want that there are more than two possible ways the program continues. For this we have the Case ... Of instruction.
Imagine the following program that asks from what year the student is:

PROGRAM Years;

VAR ano: integer;

begin
WriteLn('From what year are you?');
if (ano=1) then
writeln('primeiro ano: MAT-1, CALC-1')
else
if (ano=2) then
writeln('segundo ano: INF, LIN-ALG')
else
if (ano=3) then
writeln('terceiro ano: ELEC, FYS')
else
if (ano=4) then
writeln('quarto ano: QUI, MAT-2')
else
if (ano=5) then
writeln('quinto ano: PROJECTO')
else
writeln('>5: AINDA NAO ACABOU?');
end.

(Note the structure of the program, with indentations. Also note the missing ; before every else).
This program will run without problem
From what year are you?
1
primeiro ano: MAT-1, CALC-1

From what year are you?
4
quarto ano: QUI, MAT-2

The structure is not very readable, though. To make it better, we can use case ... of. Whereas in "if condition then instruction1" the condition is necessarily of the boolean type (TRUE or FALSE), in case ... of we can use any type of variable that has discreet values (in contrast to floating point variables which do not have discreet, whole number values).

 Case expression of    value1: instruction1;     value2: instruction2;           |    valueN: instructionN;    else instructionE;  end;

The expression needs to result in a value of any countable type (for example: integer, byte, boolean, but also char. Not, for example: real or string). This can be a simple variable or a calculation resulting in a value. The values value1 to valueN also have to be of the same type;
As an example the above program rewritten to make use of case ... of:

PROGRAM Years;

VAR ano: integer;

begin
WriteLn('From what year are you?');
Case ano of
1: writeln('primeiro ano: MAT-1, CALC-1');
2: writeln('segundo ano: INF, LIN-ALG');
3: writeln('terceiro ano: ELEC, FYS');
4: writeln('quarto ano: QUI, MAT-2');
5: writeln('quinto ano: PROJECTO')
else writeln('>5: AINDA NAO ACABOU?');
end;
end.

This progam will have the same output as the program before, but now it is more readable.

Aula 9:    (2*B) OR (NOT (2*B))

## Quick test:

To test your knowledge of what you have learned in this lesson, click here for an on-line test. Note that this is NOT the form the final test takes!

Peter Stallinga. Universidade do Algarve, 1 março 2002