Chapitre 5: Les booléens
Au XIXe siècle, le britannique Georges Boole crée une algèbre pour traduire les raisonnements logiques en opérations. Plus tard, au début de l’informatique dans les années 1930, Claude Shannon montre dans sa thèse qu’il devrait également être possible d’utiliser des arrangements de relais électriques pour résoudre des problèmes d’algèbre booléenne. La route était ouverte à l’apparition des premiers ordinateurs électriques, et bientôt électroniques.
![Le mathématicien britannique Georges Boole (1815-1864) est le fondateur de la logique symbolique moderne.](../../../../img/nESwF_lGu7-300.webp)
Dans ce cours, nous allons nous intéresser à un type simple, les booléens qui ne possèdent que deux valeurs et qui sont donc codés que sur un seul bit:
- FAUX: dont la syntaxe peut varier suivant les langages de programmation;
0
False
,false
… - VRAI: noté
0
,True
,true
…
Ces types sont extrêmement utilisés en informatique notamment pour l’exécution conditionnelle
de code en fonction des conditions. La fameuse instruction if ... else
.
Comme il n’existe que deux valeurs booléennes, les opérations ne sont pas les mêmes qu’avec les nombres.
1 Introduction à l’algèbre de Boole
Dans le monde noir et blanc des idéaux, il y a une vérité absolue. C’est-à-dire que tout est vrai ou faux. Dans ce contexte philosophique, considérons les exemples suivants:
“Un plus un égal deux.” Vrai ou faux?
C’est (sans doute) vrai!
“1 + 1 = 2” ET “2 + 2 = 4” Vrai ou faux?
C’est aussi vrai.
Mais qu’en est-il:
“1 + 1 = 3” OU “Sydney est en Australie” Vrai ou faux?
C’est vrai! Bien que 1 + 1 = 3 ne soit pas vrai, le OU
dans l’instruction a indiqué que, si
l’une ou l’autre partie de l’instruction est vraie, l’instruction entière l’est également.
Considérons maintenant un exemple plus déconcertant
“2 + 2 = 4” OU “1 + 1 = 3” ET “1 - 3 = -1” Vrai ou faux?
La vérité ou la fausseté des déclarations dépend de l’ordre dans lequel vous évaluez la déclaration. Si vous
évaluez d’abord “2 + 2 = 4 OU
1 + 1 = 3”, la déclaration est fausse et sinon vraie. Comme en
algèbre ordinaire, il est nécessaire de définir certaines règles pour régir l’ordre d’évaluation, afin
d’éviter toute ambiguïté.
Avant de décider dans quel ordre évaluer les énoncés, nous faisons ce que la plupart des mathématiciens aiment faire, remplacer les phrases par des symboles ces symboles représentent ce que l’on appelle des variables propositionnelles:
- Soit la vérité ou la fausseté de l’énoncé 2 + 2 = 4.
- Soit la vérité ou la fausseté de l’énoncé 1 + 1 = 3.
- Soit la vérité ou la fausseté de l’énoncé 1 - 3 = -1.
Ensuite, l’exemple ci-dessus peut être récrit de manière plus compacte:
Pour aller encore plus loin, les mathématiciens remplacent également les opérations par des signes OU par et ET par , l’énoncé devient:
Il faut également établir l’ordre de priorité. Nous évaluons ET
en premier, puis OU
avec le P.
La déclaration est vraie on peut écrire:
2 Opérations fondamentales et notations
Dans ce cours on notera les valeurs et .
L’algèbre booléenne est construite à partir de 3 opérations fondamentales, les notations dépendent du domaine d’étude (logique, électronique, algèbre…), on utilisera une notation proche de langages de programmation usuels tels que le C ou le javascript.
Opération | Écriture utilisée | Écritures rencontrées |
---|---|---|
ET | & |
ou ou |
OU | | |
ou |
NON | ! |
P’, ~P, , |
Le ET logique (&
) est prioritaire sur le OU (|
).
On notera dans ce cours les variables booléennes avec des lettres majuscules: , , … On parle de variable propositionnelle.
Dans les langages informatiques, les syntaxes peuvent être encore différentes!
Opération | python | javascript |
---|---|---|
Valeurs booléennes | ||
VRAI = 1 | True |
true |
FAUX = 0 | False |
false |
Opérateurs booléens | ||
NON (!) | not a |
!a |
ET (&) | a and b |
a && b |
OU (|) | a or b |
a || b |
3 Tables de vérités
- Tables de vérité
-
Une table de vérité donne tous les résultats possibles d’une opération booléenne en fonction de la ou les entrées.
Nous allons dans un premier temps nous intéresser aux tables de vérité des trois fonctions logiques fondamentales:
3.1 Fonction NON LOGIQUE: !
La fonction logique NON
n’a qu’un argument.
Elle renvoie l’inverse de son argument FAUX
si l’argument est VRAI
, et
vice-versa.
P | !P |
---|---|
0 0 |
1 0 |
3.2 Fonction ET LOGIQUE: &
La fonction ET LOGIQUE
a deux arguments, elle renvoie VRAI
si les deux arguments
ont pour valeur VRAI
.
P | Q | P & Q |
---|---|---|
0 0 1 1 |
0 1 0 1 |
0 0 0 1 |
On voit bien grâce à cette table pourquoi on utilise parfois le signe x
pour désigner la
fonction ET LOGIQUE.
3.3 Fonction OU LOGIQUE: |
La fonction OU LOGIQUE
a deux arguments, elle renvoie VRAI
si au moins un des
deux arguments a pour valeur VRAI
.
P | Q | P | Q |
---|---|---|
0 0 1 1 |
0 1 0 1 |
0 1 1 1 |
On voit grâce à cette table que le signe +
utilisé pour désigner la fonction OU LOGIQUE
fonctionne à peu près comme le +
de notre algèbre traditionnelle.
3.4 Tables de vérité composées
Les trois tables de vérité présentées ci-dessus sont les plus élémentaires et servent de jeux de construction pour les plus complexes.
Supposons que nous voulions construire une table de vérité pour P & Q | R (c-à-d P ET Q OU R).
Remarquez que cette table implique trois variables (P, Q et R), nous nous attendons donc à ce qu’elle soit plus grande que les précédentes.
Pour construire une table de vérité, nous écrivons d’abord toutes les combinaisons possibles des trois variables:
P Q R
---------
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
Nous complétons ensuite le tableau à la main en calculant la valeur que chaque combinaison produira en utilisant l’expression P&Q | R.
P Q R | P & Q | R
-----------|----------
0 0 0 | 0
0 0 1 | 1
0 1 0 | 0
0 1 1 | 1
1 0 0 | 0
1 0 1 | 1
1 1 0 | 1
1 1 1 | 1
La procédure que nous suivons pour produire des tables de vérité est maintenant claire. Voici quelques exemples supplémentaires de tables de vérité.
Vous pouvez consulter la page d’exercices pour vous entraîner.
4 Équivalence d’expressions booléennes
En algèbre ordinaire, deux expressions peuvent être équivalentes, par exemple:
La même chose peut être dite de l’algèbre booléenne. Construisons des tables de vérité pour:
et
P Q R | P & R | Q & R
--------------------------
0 0 0 | 0
0 0 1 | 0
0 1 0 | 0
0 1 1 | 1
1 0 0 | 0
1 0 1 | 1
1 1 0 | 0
1 1 1 | 1
P Q R | (P | Q) & R
------------------------
0 0 0 | 0
0 0 1 | 0
0 1 0 | 0
0 1 1 | 1
1 0 0 | 0
1 0 1 | 1
1 1 0 | 0
1 1 1 | 1
En comparant les deux tableaux, vous aurez remarqué que les résultats(c’est-à-dire la dernière colonne) des deux tableaux sont identiques!
- Équivalence d’expressions booléennes
-
Nous disons que deux expressions booléennes sont équivalentes si la sortie de leurs tables de vérité est la même. L’équivalence d’expressions booléennes est notée avec le signe =.
5 Les lois de l’algèbre de BOOLE
Il n’est pas demandé d’apprendre ces lois, mais vous devez savoir les démontrer.
Nom de la loi | Écriture mathématique |
---|---|
Éléments neutres | |
Éléments absorbants | |
Complémentarité | |
Idempotence | |
Commutativité | |
Associativité | |
Distributivité | |
Lois de De Morgan |
Ces lois peuvent facilement être démontrées à l’aide de tables de vérité.
- https://en.m.wikibooks.org/wiki/High_School_Mathematics_Extensions/Logic
- http://info.blaisepascal.fr/nsi-les-booleens
- https://www.maxicours.com/se/cours/simplification-de-l-expression-logique-a-l-aide-des-regles-de-l-algebre-booleenne/
- http://www.courstechinfo.be/MathInfo/FctLogiques1.html
- https://www.plymouth.ac.uk/uploads/production/document/path/3/3760/PlymouthUniversity_MathsETStats_Boolean_algebra_ET_logic_gates.pdf