07 - Booléens

Introduction : la logique au quotidien

La logique est une forme de raisonnement qui permet de déterminer si une affirmation est vraie ou fausse. Considérons deux phrases :

« S’il fait beau ce soir et si j’ai fini mon travail, j’irai me promener. »

Ici, la promenade dépend de deux conditions qui doivent être simultanément vraies. Les différentes situations sont représentées dans une table de vérité :

Comparons avec : « L’accusé sera disculpé si l’enquête révèle qu’il s’agit d’un suicide ou s’il peut prouver qu’il était ailleurs. »

Dans le premier cas, les deux conditions doivent être simultanées. Dans le second, une seule suffit.

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

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 :

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.

Circuit électrique : un interrupteur normalement fermé. Le voyant s’allume tant que l’interrupteur n’est pas actionné.

Table de vérité :

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.

Circuit électrique : deux interrupteurs en série. Le voyant ne s’allume que si les deux sont actionnés simultanément.

Table de vérité :

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.

Propriétés :

L’opérateur OU (disjonction)

Le booléen \(a + b\) est égal à 1 si au moins l’un des deux est égal à 1.

Circuit électrique : deux interrupteurs en parallèle. Le voyant s’allume dès que l’un des interrupteurs est actionné.

Table de vérité :

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

Notation : \(s = a + b\) ou \(s = a \lor b\) — En Python : a or b

Propriétés :

Propriétés algébriques

Les opérateurs ET et OU obéissent à des règles similaires à celles de l’arithmétique, avec quelques particularités.

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 :

# 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}\)

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é).

L’analogie avec les circuits électriques est la suivante :

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 :

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)

C’est pourquoi les circuits électroniques utilisent souvent des portes NAND comme brique de base.

À retenir

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