Lecture 8: Branching II (switch) / Boolean Algebra


Boolean Algebra

George Boole 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 7) we have seen how we can control the flow of the program by the branching instructions if ... and if ... 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)
    if (x>-2)
      printf("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) && (x>-2))
    printf("Error");
which means 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 && condition2;
  if (condition3)
    instruction;

logical operators in C

&& and
|| or

Another important logical operation is XOR, although it is not implemented for Boolean calculation in C.  a XOR b means "a or b true, but not both!". We will use it later for integer logical operations. Others that are not implemented include NAND and NOR which are only important at the electronic level and are not very useful at the programming level.
Finally, there is the boolean negator !. It means taking the opposite; if a is false (0), !a is true (1), and vice verse. Whereas && and || need two operands (for example a || b), ! needs only one (!a).
With these 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 
C
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)
    printf("TRUE");
  else
    printf("FALSE");

(a>0)                  TRUE
(b>0)                  FALSE
(a>0) && (b>0)         FALSE
(a>0) || (b>0)         TRUE
!(a>0)                 FALSE
(! (a>0)) || (b>0)     FALSE
(2==b) || (!(2==b))    TRUE


Boolean algebra for integers

We can also apply boolean algebra to complete numbers (char, int, long int, 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". To avoid confusion, the symbols for operations on numbers are differents from the ones given above, namely "&" for "AND", "|" for "OR", "^" for "XOR" and "~" for "NOT"
 
 operation  C 
 AND
&
 OR
|
 XOR
^
 NOT
~

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 = 
0 0 1 1 0 0 0 1  
24 = 
0 0 0 1 1 0 0 0  
  49 | 24 = 
0 0 1 1 1 0 0 1  = 57 
49 & 24 =
0 0 0 1 0 0 0 0  = 16
49 ^ 24 =
0 0 1 0 1 0 0 1  = 41
~49 =
1 1 0 0 1 1 1 0  = 206
~24 =
1 1 1 0 0 1 1 1  = 231
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

In the table on the left, also the other operations with the numbers 49 and 24 are given.

Note the bit-wise inverter ~ depends on the size of the variable:
For a byte (unsigned char) ~49 = ~(00110001) = (11001110) = 128 + 64 + 8 + 4 + 2 = 206, while for an unsigned int ~49 = ~(0000000000110001) = (1111111111001110) = 65486.


Multiple branching: switch

In the previous lecture (see aula 7) we have seen how to use the if ... 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 switch  instruction.
Imagine the following program that asks from what year the student is:

  main()
   // outputs the lectures to follow on basis of year
  {

    int ano;

    printf("From what year are you?\n");
    scanf("%d", &ano);
    if (ano==1)
      printf("primeiro ano: MAT-1, CALC-1\n");
    else
      if (ano==2)
        printf("segundo ano: INF, LIN-ALG\n");
      else
        if (ano==3)
          printf("terceiro ano: ELEC, FYS\n");
        else
          if (ano==4)
            printf("quarto ano: QUI, MAT-2\n");
          else
            if (ano==5)
              printf("quinto ano: PROJECTO\n");
            else
              printf(">5: AINDA NAO ACABOU?\n");
  }

(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 switch. Whereas in "if (condition) instruction1;" the condition is necessarily of the boolean type (true or false), in switch 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).
 

 switch (expression)
 {
   case value1: instruction1; 
        break;
   case value2: instruction2;
        break;
          |
   case valueN: instructionN;
        break;
   default: instructionE;
 }

The expression needs to result in a value of any countable type (for example: int, long int, but also char. Not, for example: float). 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, but cannot contain expressions or variables; they have to be of constant type.
The special reserved word "default" means that it will execute this instruction if the expression doesn't result in any of the values value1 .. valueN.
The break statement forces the program to jump to the end of the loop (the switch-loop in this case).
As an example the above program rewritten to make use of switch:

  main()
   // same program as above, but with switch statement
  {
    int ano;

    printf("From what year are you?\n");
    scanf("%d", &ano);
    swicth (ano)
     {
      case 1: printf("primeiro ano: MAT-1, CALC-1\n");
              break;
      case 2: printf("segundo ano: INF, LIN-ALG\n");
              break;
      case 3: printf("terceiro ano: ELEC, FYS\n");
              break;
      case 4: printf("quarto ano: QUI, MAT-2\n");
              break;
      case 5: printf("quinto ano: PROJECTO\n")
              break;
      default: printf(">5: AINDA NAO ACABOU?\n");
     }
  }

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

Lecture 8:    (2==b) || (! (2==b))William Shakespear

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, 28 October 2002