Ekluboko, K. (2018) Algorithme (Course material for Programmation : s’initier)
Introduction
- Mathematical intuition
- The logic of everyday life. (Common sense)
It is easy to see that some human problems cannot be solved by mathematics.
For example compare involvement and its counterpart,
“If it rains, I take my umbrella.”
“If I don’t take my umbrella, it doesn’t rain”
Or the argued conjunction,
“I don’t take my umbrella, so it doesn’t rain.”
All this should encourage us to be cautious. In programming you have to remain totally in the mathematical world.
Truth tables
O represents false and 1 represents true.
Negation
| NOT, ! | |
| F | !F |
| 0 | 1 |
| 1 | 0 |
In logical negation if the value operated on is true it will give a result of false and if false a result of true. In the table above F is operated on using negation so where F is false (0) it becomes true and vice versa.
Conjunction
| AND, ^, && | ||
| F | G | F^G |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
In logical conjunction, if both values are true (1) then the result is true (1).
Disjunction
| OR, v, || | ||
| F | G | FvG |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
In logical disjunction, if either value is true (1) then the result is true (1).
Implication
| ==> | ||
| F | G | F==>G |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
In logical implication, a value of false is only given if the first value is true (1) and the second false (0).
Equivalence
| <==> | ||
| F | G | F<==>G |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
In logical equivalence, a value of true is given only if both values are the same.
It should be noted that the basic logical connectors in programming are these elementary functions.
NO ( negation),
OR (the disjunction),
AND (the conjunction).
The other combinatorial logical functions are derived from the basic functions.
De Morgan’s laws
not (A or B) = not A and not B; and
not (A and B) = not A or not B
These could also be said as,
the negation of a disjunction is the conjunction of the negations; and
the negation of a conjunction is the disjunction of the negations;
or as,
the complement of the union of two sets is the same as the intersection of their complements; and
the complement of the intersection of two sets is the same as the union of their complements.
So far, we have written conditions for no more than two variables, built with operators of comparison. We’ve nested if…then, if not. We can now combine several conditions into one condition. This allows us to simplify the writing.
Example
To determine if number A is greater than the two numbers B and C we can write,
if A > B
then
if A > C
then write << A is bigger >>
if not then write << A is not bigger >>
if not write << A is not bigger >>or,
if A > B and A > C
then write << A is bigger >>
if not write << A is not bigger >>