Algorithms – Chapter 4

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
01
10

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, ^, &&
FGF^G
000
010
100
111

In logical conjunction, if both values are true (1) then the result is true (1).

Disjunction

OR, v, ||
FGFvG
000
011
101
111

In logical disjunction, if either value is true (1) then the result is true (1).

Implication

==>
FGF==>G
001
011
100
111

In logical implication, a value of false is only given if the first value is true (1) and the second false (0).

Equivalence

<==>
FGF<==>G
001
010
100
111

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 >>

Leave a comment