07 - Booléens
Razik Ikhlef
Introduction : la logique au quotidien
La logique permet de décider si une affirmation est vraie ou fausse. Dans la vie courante, beaucoup de règles combinent plusieurs conditions avec les mots et et ou.
« Pour obtenir le permis de conduire, il faut réussir l’examen du code et l’examen de conduite. »
Le permis dépend de deux conditions qui doivent être simultanément vraies. Toutes les situations possibles se résument dans une table de vérité :
Introduction : la logique au quotidien (suite)
| Code réussi | Conduite réussie | Permis obtenu |
|---|---|---|
| Non | Non | Non |
| Non | Oui | Non |
| Oui | Non | Non |
| Oui | Oui | Oui |
Comparons avec : « On peut entrer dans la salle de cinéma avec un billet ou avec une carte d’abonnement. »
Introduction : la logique au quotidien (suite)
| Billet | Carte d’abonnement | Entrée autorisée |
|---|---|---|
| Non | Non | Non |
| Non | Oui | Oui |
| Oui | Non | Oui |
| Oui | Oui | Oui |
Avec et, les deux conditions doivent être réunies. Avec ou, une seule suffit, et l’entrée reste autorisée quand on a les deux.
Les booléens
Un booléen est une valeur qui ne peut être que l’une de deux possibilités : vrai (1) ou faux (0). Ce nom vient du mathématicien George Boole (1815-1864) qui a formalisé les règles du raisonnement logique.
En Python, les valeurs booléennes s’écrivent True et False (avec une majuscule). On convient de lire 0 comme « faux » et 1 comme « vrai ».
majeur = True
mineur = False
print(type(majeur)) # <class 'bool'>
Les booléens (suite)
Une fonction logique est une fonction qui prend en entrée un ou plusieurs booléens et renvoie un booléen en sortie. Une table de vérité montre la valeur de sortie pour toutes les combinaisons possibles des entrées.
Pour une fonction à \(n\) entrées, la table de vérité comporte \(2^n\) lignes (chaque entrée pouvant valoir 0 ou 1).
Les opérateurs de comparaison
Les comparaisons produisent des booléens :
| Opérateur | Signification | Exemple | Résultat |
|---|---|---|---|
== |
égal à | 5 == 5 |
True |
!= |
différent de | 5 != 3 |
True |
< |
strictement inférieur | 3 < 5 |
True |
> |
strictement supérieur | 3 > 5 |
False |
<= |
inférieur ou égal | 5 <= 5 |
True |
>= |
supérieur ou égal | 3 >= 5 |
False |
Les opérateurs de comparaison (suite)
Attention : ne pas confondre = (affectation) et == (comparaison).
Les trois opérateurs fondamentaux
Toute fonction logique peut être construite à partir de trois opérateurs de base : NON, ET et OU.
L’opérateur NON (négation)
L’opérateur NON inverse la valeur d’un booléen : il transforme vrai en faux et faux en vrai.
L’opérateur NON (négation) (suite)
Circuit électrique : un interrupteur normalement fermé. Le voyant s’allume tant que l’interrupteur n’est pas actionné.
L’opérateur NON (négation) (suite)
L’opérateur NON (négation) (suite)
Table de vérité :
| \(a\) | \(\overline{a}\) |
|---|---|
| 0 | 1 |
| 1 | 0 |
Notation : \(s = \overline{a}\) — En Python : not a
Propriété : \(\overline{\overline{a}} = a\) (double négation)
L’opérateur ET (conjonction)
Le booléen \(a \cdot b\) est égal à 1 si et seulement si \(a\) et \(b\) sont tous deux égaux à 1.
L’opérateur ET (conjonction) (suite)
Circuit électrique : deux interrupteurs en série. Le voyant ne s’allume que si les deux sont actionnés simultanément.
L’opérateur ET (conjonction) (suite)
L’opérateur ET (conjonction) (suite)
Table de vérité :
| \(a\) | \(b\) | \(a \cdot b\) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Notation : \(s = a \cdot b\) ou \(s = a \land b\) — En Python : a and b
Le résultat est identique à une multiplication. C’est pourquoi on note le ET par un point.
L’opérateur ET (conjonction) (suite)
Propriétés :
| Propriété | Formule |
|---|---|
| Élément neutre | \(a \cdot 1 = a\) |
| Élément absorbant | \(a \cdot 0 = 0\) |
| Idempotence | \(a \cdot a = a\) |
| Complémentarité | \(a \cdot \overline{a} = 0\) |
| Commutativité | \(a \cdot b = b \cdot a\) |
| Associativité | \((a \cdot b) \cdot c = a \cdot (b \cdot c)\) |
L’opérateur OU (disjonction)
Le booléen \(a + b\) est égal à 1 si au moins l’un des deux est égal à 1.
L’opérateur OU (disjonction) (suite)
Circuit électrique : deux interrupteurs en parallèle. Le voyant s’allume dès que l’un des interrupteurs est actionné.
L’opérateur OU (disjonction) (suite)
L’opérateur OU (disjonction) (suite)
Table de vérité :
| \(a\) | \(b\) | \(a + b\) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
C’est un OU inclusif : il inclut le cas où les deux conditions sont vraies. C’est le « ou » de « Je viendrai qu’il pleuve ou qu’il neige ».
L’opérateur OU (disjonction) (suite)
Notation : \(s = a + b\) ou \(s = a \lor b\) — En Python : a or b
Propriétés :
| Propriété | Formule |
|---|---|
| Élément neutre | \(a + 0 = a\) |
| Élément absorbant | \(a + 1 = 1\) |
| Idempotence | \(a + a = a\) |
| Tiers exclu | \(a + \overline{a} = 1\) |
| Commutativité | \(a + b = b + a\) |
| Associativité | \((a + b) + c = a + (b + c)\) |
Propriétés algébriques
Propriétés algébriques (suite)
Les opérateurs ET et OU obéissent à des règles similaires à celles de l’arithmétique, avec quelques particularités.
| Propriété | Pour le ET (\(\cdot\)) | Pour le OU (\(+\)) |
|---|---|---|
| Commutativité | \(a \cdot b = b \cdot a\) | \(a + b = b + a\) |
| Associativité | \((a \cdot b) \cdot c = a \cdot (b \cdot c)\) | \((a + b) + c = a + (b + c)\) |
| Idempotence | \(a \cdot a = a\) | \(a + a = a\) |
| Distributivité | \(a \cdot (b + c) = a \cdot b + a \cdot c\) | \(a + (b \cdot c) = (a + b) \cdot (a + c)\) |
Propriétés algébriques (suite)
Remarque : la distributivité du OU sur le ET (\(a + (b \cdot c) = (a + b) \cdot (a + c)\)) n’a pas d’équivalent en arithmétique classique. C’est une particularité de l’algèbre de Boole.
Lois d’absorption
Les lois d’absorption permettent de simplifier des expressions :
\[a + a \cdot b = a\] \[a \cdot (a + b) = a\]
Lois de De Morgan
Augustus De Morgan (1806-1871) a établi deux lois fondamentales qui permettent de transformer un ET en OU (et inversement) en ajoutant des négations :
\[\overline{a + b} = \overline{a} \cdot \overline{b}\] \[\overline{a \cdot b} = \overline{a} + \overline{b}\]
En langage courant : « ne pas (A ou B) » revient à « ne pas A et ne pas B ». Et « ne pas (A et B) » revient à « ne pas A ou ne pas B ».
Application en Python. Ces lois permettent de simplifier des conditions. Par exemple, les deux écritures suivantes sont équivalentes :
Lois de De Morgan (suite)
# Version originale (avec not sur un or)
if not (age < 18 or solde < 0):
print("Accès autorisé")
# Version simplifiée par De Morgan
if age >= 18 and solde >= 0:
print("Accès autorisé")
La seconde version est plus lisible. On a appliqué la première loi : \(\overline{a + b} = \overline{a} \cdot \overline{b}\), en sachant que la négation de < donne >=.
Le OU exclusif (XOR)
Le OU exclusif, noté \(a \oplus b\), vaut 1 si et seulement si exactement un des deux opérandes vaut 1. On peut l’exprimer comme : \(a \oplus b = \overline{a} \cdot b + a \cdot \overline{b}\)
| \(a\) | \(b\) | \(a \oplus b\) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Le OU exclusif (XOR) (suite)
C’est le « ou » de la phrase « Tu choisis : la mer ou la montagne », où l’on ne peut pas choisir les deux. En Python : a ^ b ou a != b (pour des booléens).
Des interrupteurs aux transistors
Dans un processeur, les opérations logiques sont réalisées par des portes logiques, elles-mêmes constituées de transistors. Un transistor se comporte comme un interrupteur commandé électriquement : il laisse passer le courant (régime saturé) ou le bloque (régime bloqué).
Des interrupteurs aux transistors (suite)
Des interrupteurs aux transistors (suite)
L’analogie avec les circuits électriques est la suivante :
| Circuit | Porte logique |
|---|---|
| Interrupteurs en série | Porte ET |
| Interrupteurs en parallèle | Porte OU |
| Interrupteur normalement fermé | Porte NON |
Des interrupteurs aux transistors (suite)
Des interrupteurs aux transistors (suite)
Shannon (1916-2001), qui a popularisé le mot « bit », a démontré que l’algèbre de Boole était applicable aux circuits électriques. Aujourd’hui, un processeur contient plusieurs milliards de transistors sur une puce de silicium de la taille d’un ongle.
Universalité de la porte NAND
La porte NAND (NON-ET), définie par \(\overline{a \cdot b}\), est dite universelle car elle permet de reconstruire les trois opérateurs fondamentaux :
Universalité de la porte NAND (suite)
| \(a\) | \(b\) | \(a \uparrow b = \overline{a \cdot b}\) |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
On peut exprimer :
- NON : \(\overline{a} = a \uparrow a\)
- ET : \(a \cdot b = (a \uparrow b) \uparrow (a \uparrow b)\) (double négation)
- OU : \(a + b = (a \uparrow a) \uparrow (b \uparrow b)\) (loi de De Morgan)
Universalité de la porte NAND (suite)
C’est pourquoi les circuits électroniques utilisent souvent des portes NAND comme brique de base.
À retenir
| Opérateur | Notation | Python | Résultat vrai si… |
|---|---|---|---|
| NON | \(\overline{a}\) | not a |
\(a\) est faux |
| ET | \(a \cdot b\) | a and b |
les deux sont vrais |
| OU | \(a + b\) | a or b |
au moins un est vrai |
| XOR | \(a \oplus b\) | a ^ b |
exactement un est vrai |
| NAND | \(\overline{a \cdot b}\) | not(a and b) |
NON-ET (porte universelle) |
| NOR | \(\overline{a + b}\) | not(a or b) |
NON-OU |
À retenir (suite)
Propriétés essentielles :
- Lois de De Morgan : \(\overline{a + b} = \overline{a} \cdot \overline{b}\) et \(\overline{a \cdot b} = \overline{a} + \overline{b}\)
- Distributivité : \(a \cdot (b + c) = a \cdot b + a \cdot c\) et \(a + (b \cdot c) = (a + b) \cdot (a + c)\)
- Les transistors réalisent les portes logiques dans les circuits ; la porte NAND est universelle