L'algèbre de Boole

Introduction du cours

Nous allons dans ce tuto étudier l'algèbre de boole. Derrière ce nom barbare se cache en fait quelque chose que tout programmeur, même débutant, utilise sans le savoir, dans les conditions.
Il est assez peu utile dans la plupart des cas :p , mais il peut avoir son utilité en algorithmique, pour la recherche de performances au niveau des conditions, en SQL, pour les requêtes, ou en électronique, pour limiter le nombre de câblage de portes logiques.

Les variables booléennes

L'algèbre de Boole est une structure algébrique qui ne contient que deux éléments, que l'on appelle couramment variables booléennes. Ces variables ne peuvent avoir que deux états, 1 ou 0 (true ou false dans certains langages de programmation), et respectent quelques règles de calcul que nous détaillerons plus loin.

Mais quel est le rapport avec les conditions ? o_O

J'y viens ^^ . En fait n'importe quel test exécuté dans une condition est une variable booléenne.
Prenons un exemple

SI (A=B) ALORS ...

Le test (A=B) peut avoir deux valeurs : 1 si A est réellement égal à B et 0 sinon. On dit que c'est la variable booléenne associée au test A=B.

Les opérateurs logiques

L'algèbre de Boole utilise plusieurs opérateurs que l'on nomme opérateurs booléens, opérateurs logiques, ou encore fonctions logiques ou portes logiques (terme plus propre à l'électronique).
En voici les principaux.

L'opérateur OU

Il correspond à la réunion de deux conditions. Par exemple : je souhaite acheter une voiture bleue OU climatisée. Les voitures correspondant à mon choix seront donc soit bleue, soit climatisée, soit les deux à la fois.

On symbolise l'opérateur OU dans les conditions par un OR ou ||
En algèbre de Boole, il est symbolisée par un +
La matheux préfèrent quant à eux la symbolisation $\vee$

Exemple :

if(a==1 OR a==2){

Équivaut à

SI((a=1)+(a=2)) alors

Si on prend des variables booléennes, on obtient :
$a \operatorname{OU} b \Leftrightarrow a+b$

Table de vérité :

a

b

a+b

0

0

0

1

0

1

0

1

1

1

1

1

Dans ce tableau on voit le résultat du test $a+b$ en fonction des valeurs de $a$ et de $b$

L'opérateur ET

Il correspond à l'intersection de deux conditions. Par exemple : je souhaite acheter une voiture bleue ET climatisée. correspondant à mon choix seront donc à la fois bleues et climatisées.

On symbolise l'opérateur ET dans les conditions par un AND ou &&
En algèbre de Boole, il est symbolisée par un $\cdot$
En maths on écrira plutôt $\wedge$

Exemple :

if(a==1 AND a==2){

Équivaut à

SI((a=1).(a=2)) alors

Si on prend des variables booléennes, on obtient :
$a \operatorname{ET} b \Leftrightarrow a \cdot b$

Table de vérité :

a

b

a.b

0

0

0

1

0

0

0

1

0

1

1

1

Dans ce tableau on voit le résultat du test $a \cdot b$ en fonction des valeurs de $a$ et de $b$

L'opérateur NON

Il correspond au complément à 1 d'une condition. Par exemple : je souhaite acheter une voiture NON polluante. Les voitures correspondant à mon choix seront donc écologiques.

L'opérateur NON est souvent représenté dans les conditions par un !
En algèbre de Boole, il est symbolisée par une barre au dessus de(s) variable(s)
En maths on utilise le symbole $\neg$
Exemple :

if(a!=1){

Équivaut à

SI $\left(\overline{a=1}\right)$ alors ...

Si on prend des variables booléennes, on obtient :
!a équivaut à $\bar{a}$

Table de vérité :

a

$\bar{a}$

0

1

1

0

Dans ce tableau on voit le résultat du test $\bar{a}$ en fonction des valeurs de $a$

L'opérateur XOR (OU exclusif)

Il correspond à l'intersection de deux conditions, privée de la réunion de ces deux conditions. Par exemple : le menu propose du fromage OU EXCLUSIF un dessert : Je peux prendre soit l'un soit l'autre, mais pas les deux.

L'opérateur XOR est représenté dans les conditions par un XOR
En algèbre de Boole, il est symbolisée par un $\oplus$
Exemple :

$a\operatorname{XOR}b\Leftrightarrow a\oplus b$

Table de vérité :

a

b

a$\oplus$b

0

0

0

1

0

1

0

1

1

1

1

0

Dans ce tableau on voit le résultat du test $a\oplus b$ en fonction des valeurs de $a$ et de $b$

Note : $a\oplus b=\overline{a}\cdot b+a\cdot \overline{b}$

L'opérateur NXOR (NON OU exclusif)

Cet opérateur n'a pas de symbolisation propre, on le note simplement NXOR

Table de vérité :

a

b

a NXOR b

0

0

1

1

0

0

0

1

0

1

1

1

Cet opérateur est appelé opérateur coincidence. En effet le test "$a \operatorname{NXOR} b$" n'est vrai que si a et b sont dans le même état logique (0 ou 1)

Note : $a \operatorname{NXOR} b=a \cdot b + \overline{a} \cdot \overline{b}$

L'opérateur NAND (NON ET) ou connecteur de Sheffer

La fonction NAND est l'enchainement de la fonction ET et de la fonction NON. On la symbolise par ↑

Table de vérité :

a

b

a$\uparrow$b

0

0

1

1

0

1

0

1

1

1

1

0

L'opérateur NAND est appelé opérateur universel : il est possible de recréer n'importe quelle fonction logique uniquement en utilisant la fonction NAND. Nous verrons plus loin dans ce tuto comment.

Note : $a \uparrow b}=\overline{a \cdot b}=\overline{a} + \overline{b}$

L'opérateur NOR (NON OU)

La fonction NOR est l'enchainement de la fonction OU et de la fonction NON. On la symbolise par ↓

Table de vérité :

a

b

a$\downarrow$b

0

0

1

1

0

0

0

1

0

1

1

0

L'opérateur NOR est également un opérateur universel.

Note : $a \downarrow b}=\overline{a + b}=\overline{a} \cdot \overline{b}$

Régles de simplification

Entrons maintenant dans le vif du sujet en apprenant les règles de l'algèbre, qui vont nous permettre de simplifier nos conditions.

Règle 1 : la commutativité

Même si elle parait évidente, il me semble bon de la préciser :

$a + b = b + a$$a \cdot b = b \cdot a$

Règle 2 : l'idempotence

Un nom barbare pour une propriété simple :