4. Algèbre de Boole

4.1. Introduction

L'algèbre de Boole, du nom du mathématicien, logicien et philosophe britannique George Boole (1815-1864), est une partie des mathématiques qui s'intéresse à une approche algébrique de la logique, alors que la logique se fonde sur des systèmes de réécriture qui consistent à manipuler des symboles. La logique possède bien évidemment un volet sémantique et l'algèbre de Boole vient renforcer la sémantique logique en remplaçant le vrai et le faux par le 1 et le 0, le et et le ou par les opérateurs $+$ et $.$ (addition et multiplication).

Cette vision arithmétique de la logique a permis de mettre au point un système de calcul qui possède des applications dans la mise au point de circuits électroniques et autorise à aborder les problèmes de la logique sous un angle différent, ce qui peut, dans certains cas, donner la possibilité de résoudre un problème beaucoup plus simplement ou rapidement (cf. Chapitre 9, section 9.7 du livre Programmation Assembleur x86 32 et 64 bits sous Linux Ubuntu).

4.2. Définitions

4.3. Fonction booléenne, table de vérité

4.3.1. Définition

On appelle fonction booléenne, une application de ${\sc A}^n$ dans $\sc A$, avec pour rappel ${\sc A} = \{ 0, 1 \}$ : $$ (x_1, x_2, ⋯, x_n) → f(x_1, x_2, ⋯, x_n) $$

Prenons par exemple une fonction $f_1(x,y,z)$. Elle comporte 3 variables, elle est donc définie par une table de vérité composée de $2^3=8$ lignes numérotées de $0$ à $(8-1)$.

Pour définir la table de vérité de $f_1$, on pourrait donc écrire :

4.3.2. Expression booléenne à partir de la table de vérité

A partir de la table de vérité d'une fonction, on est en mesure de donner une expression de celle-ci sous forme algébrique en tant que somme de monômes, un monôme étant un produit de variables booléennes :

• il suffit d'exprimer les monômes pour les lignes pour lesquelles la fonction $f_1(x,y,z) = 1$
• si une variable est à $0$ dans cette ligne, on utilise son complément.

Avec l'exemple précédent, on obtient :

On remarque dans la table de vérité que les variables $x$, $y$ et $z$ suivent la notation binaire et que pour la ligne 6, on a bien $x=1, y=1, z=0$ qui correspond à $110_2 = 6$.

4.3.3. Fonctions booléennes de deux variables

Dans le cas particulier des fonctions à 2 variables $f(x,y)$, on peut définir 16 fonctions différentes dont certaines ont été nommées. On retrouve notamment :

• $or(x,y)$, c'est à dire le ou logique : $x + y$
• $and(x,y)$, le et logique : $x . y$
• $nor(x,y) = \ov{or(x,y)}\ $, le non ou : $\ov{\table x + y; }\ $
• $nand(x,y) = \ov{and(x,y)}\ $, le non et : $\ov{\table x . y; }\ $
• $xor(x,y)$, le ou exclusif (eXclusive OR) qui est vrai uniquement si l'une de ses opérandes est vraie mais lorsque les deux opérandes sont égales, le $xor$ est faux : $\ov{\table x;}\ . y + x . \ov{\table y;}\ = x ⊕ y$

4.3.3.a  La fonction ET/AND

Le ET logique vaut 1 uniquement si ses deux opérandes $x$ et $y$ valent 1.

En d'autres termes, pour que la condition if (x and y) soit vraie, il faut que les deux sous-conditions $x$ et $y$ soient vraies.

if ((0 < a) and (a < 11)) {
    // a est compris entre 1 et 10
} else {
    // a est en dehors de l'intervalle [1..10]
}

4.3.3.b  La fonction OU/OR

Le OU logique vaut 0 uniquement si ses deux opérandes $x$ et $y$ valent 0.

En d'autres termes, pour que la condition if (x or y) soit vraie, il faut que l'une des deux sous-conditions $x$ ou $y$ (ou les deux) soient vraies.

if ((a > 10) or (a < 1)) {
    // a est en dehors de l'intervalle [1..10]
} else {
    // a est compris entre 1 et 10
}

4.3.3.c  La fonction OU Exclusif/XOR

Le OU Exclusif logique vaut 0 uniquement si ses deux opérandes $x$ et $y$ ont la même valeur.

En d'autres termes, pour que la condition if (x xor y) soit vraie, il faut que l'une des deux sous-conditions $x$ ou $y$ soit vraie, mais pas les deux en même temps.

if ((est_un_poisson(a) xor vole(a))) {
    // élimine les poissons volants
    // Traite les poissons ou les animaux qui volent
    // mais pas les deux en même temps
} 

4.3.3.d  Lois de De Morgan

Les lois de De Morgan (mathématicien et logicien britannique, 1806-1871) permettent d'exprimer la transformation de la négation d'un ET ou d'un OU logique.

• NON( $x$ ET $y$ ) est équivalent à NON($x$) OU NON($y$), que l'on peut énoncer sous la forme : le complémentaire du produit est la somme des complémentaires
  $$ \ov{\table x . y;} = \ov{\table x;} + \ov{\table y;} $$
  
• NON( $x$ OU $y$ ) est équivalent à NON($x$) ET NON($y$), que l'on peut énoncer sous la forme : le complémentaire de la somme est le produit des complémentaires
  $$ \ov{\table x + y;} = \ov{\table x;} . \ov{\table y;} $$

Par exemple, soit la condition (0 < a) and (a < 11) vue précédemment dans l'exemple sur le ET. Il existe différentes manières d'en prendre la négation :

• not( (0 < a) and (a < 11) )
• not(0 < a) or not(a < 11), transformation par De Morgan
• (0 >= a) or (a >= 11), application du not sur chaque sous-condition
• (a <= 0) or (a >= 11)
• (a < 1) or (a > 10)

4.3.4. Simplification des fonctions booléennes de plusieurs variables

L'intérêt de l'algèbre de Boole est qu'elle permet de simplifier les fonctions booléennes comme on le ferait d'une expression algébrique sur les entiers ou les réels.

Essayons d'appliquer ces règles pour simplifier la fonction $f_2(x,y,z)$ définie par :

Cette fonction peut être réécrite sous une forme simplifiée en :

La fonction ainsi réduite possède deux termes et est plus facile à concevoir sous forme de schéma électronique car elle utilise moins de symboles donc moins de portes logiques. Ces portes logiques sont implantées sous forme de transistors. Si on utilise moins de transistors on peut réduire la taille des circuits électroniques.

On utilise également d'autres formules de simplification parmi lesquelles:

4.4. AND, OR et le binaire

typedef struct {
	int force;
	int agilite;
    ...
	int points_de_vie;
	int role; 
} EtreVivant;

const int PERSONNAGE  = 1
const int ARMES       = 2  // Maîtrise des armes
const int MAGIE       = 3  // Maîtrise de la magie
const int MONSTRE     = 4
const int PETIT       = 5
const int GRAND       = 6
const int ENORME      = 7  

const int PERSONNAGE  = 1
const int ARMES       = 2  // Maîtrise des armes
const int MAGIE       = 4  // Maîtrise de la magie
const int MONSTRE     = 8
const int PETIT       = 16
const int GRAND       = 32
const int ENORME      = 64  

Guerrier =  PERSONNAGE | ARMES | GRAND
Magicien =  PERSONNAGE | MAGIE | GRAND
Elfe     =  PERSONNAGE | MAGIE | MAITRISE_ARMES | GRAND
Nain     =  PERSONNAGE | ARMES | PETIT
Gobelin  =  MONSTRE | PETIT
Troll    =  MONSTRE | GRAND
Dragon   =  MONTRE | ENORME | MAGIE 

if (p.role == MONSTRE) {
    ...
}

if ((p.role & MONSTRE) != 0) {
    ...
}

if ((p.role & MONSTRE) == MONSTRE) {
    ...
}

if ((p.role & (PERSONNAGE | ARMES)) == (PERSONNAGE | ARMES)) {
   ...
}

p.role = p.role | MAGIE;

4.5. Exercices

4.6. Définitions à savoir

Définir les termes suivants :

• fonction booléenne
• table de vérité