[B.4] Valeurs booléennes, opérateurs booléens et portes logiques

Les valeurs booléennes

Vrai ou faux

Un ordinateur ne manipule que des 0 et des 1 (il y a de l’électricité ou il n’y en a pas). Ces deux valeurs peuvent aussi être vues comme des “valeurs de vérité” :

• 0 = faux (en anglais False)
• 1 = vrai (en anglais True)

Ce type de donnée (qui ne peut prendre que ces deux valeurs) est une valeur booléenne (ou un booléen), du nom du mathématicien anglais George Boole (1815-1864). Un booléen tient donc, en théorie, sur un seul bit : c’est le plus petit type de donnée possible.

C’est la réponse naturelle à une question fermée : « l’interrupteur est-il allumé ? », « 3 est-il plus grand que 2 ? », « la porte est-elle ouverte ? »

Deux notations pour la même chose

Dans ce cours nous utiliserons surtout 0 et 1, plus lisibles dans les tableaux.

Opérateurs booléens et portes logiques

Opérateurs et portes

On peut combiner des booléens avec des opérateurs booléens (ou opérateurs logiques) : NON, ET, OU, auxquels on ajoute le OU exclusif.

Exemple : quelle est la réponse à la question : “la porte est-elle fermée ET la lumière allumée ?”

Dans un ordinateur, chaque opérateur est réalisé physiquement par un composant électronique : une porte logique. Elle reçoit un ou deux signaux en entrée et produit un signal en sortie. Un processeur moderne en contient plusieurs milliards. Chaque porte a un symbole utilisé dans les schémas.

Dans un schéma, les entrées sont à gauche, la sortie à droite, et les traits qui les relient sont les fils : ils transportent une valeur, 0 ou 1. Un fil peut se diviser pour alimenter plusieurs portes, mais deux fils ne peuvent jamais arriver sur une même entrée.

Pour décrire complètement un opérateur (ou une porte), il suffit d’énumérer tous les cas possibles dans une table de vérité.

NON (NOT)

Le NON est unaire : il ne prend qu’une entrée, et l’inverse.

Notations : NON a, not a (Python), $\overline{a}$ ou $\lnot a$ (maths).

ET (AND)

Le ET vaut 1 si et seulement si ses deux entrées valent 1 : « il faut le badge et le code ».

Notations : a ET b, a and b (Python), $a \land b$ ou $a \cdot b$ (maths).

OU (OR)

Le OU vaut 1 dès qu’au moins une des deux entrées vaut 1. Attention : c’est un OU inclusif, il vaut aussi 1 quand les deux valent 1.

Notations : a OU b, a or b (Python), $a \lor b$ ou $a + b$ (maths).

OU exclusif (XOR)

Le OU exclusif vaut 1 quand les deux entrées sont différentes. C’est le « ou » du restaurant : fromage ou dessert, mais pas les deux.

Le symbole est celui du OU, avec une barre supplémentaire à l’arrière.

Notations : a XOR b, a != b (Python, il n’y a pas de mot-clé xor), $a \oplus b$ (maths).

Opérateurs dérivés : NAND, NOR

On rencontre souvent les versions niées de ET et OU, plus simples à fabriquer avec des transistors. Leur symbole est celui du ET ou du OU, suivi du petit rond :

• a NAND b = NON (a ET b)
• a NOR b = NON (a OU b)

Récapitulatif des symboles

Simulation

Nous utiliserons un simulateur de circuits logiques (depuis Capytale) : on y place des entrées, des portes, une sortie, puis on bascule les entrées pour observer la sortie.

Combinaison de portes logiques

Principe

Dès qu’on assemble plusieurs portes, la sortie de l’une devient l’entrée d’une autre. Pour comprendre ce que fait le circuit, on établit sa table de vérité.

Les colonnes intermédiaires sont le point essentiel : on ne cherche jamais à deviner la sortie directement, on avance porte par porte.

Exemple détaillé

Ce circuit a 3 entrées et 3 portes :

• une porte ET qui reçoit E1 et E2, de sortie A,
• une porte OU qui reçoit E2 et E3, de sortie B,
• une porte XOR qui reçoit A et B, et donne la sortie S.

E2 alimente deux portes : le fil se divise. Avec 3 entrées, la table a $2^3 = 8$ lignes :

La sortie vaut donc 1 dans 5 cas sur 8.

Expressions booléennes

Écrire un circuit sous forme d’expression

Plutôt qu’un schéma, on peut écrire une expression booléenne : une formule qui combine des variables booléennes avec NON, ET, OU et XOR. Le circuit 1 précédent s’écrit :

$$S = (E_1 \text{ ET } E_2) \text{ XOR } (E_2 \text{ OU } E_3)$$

Schéma et expression sont deux écritures du même objet ; il faut savoir passer de l’une à l’autre :

• du schéma vers l’expression : on part de la sortie et on remonte, en remplaçant chaque porte par son opérateur et ses entrées,
• de l’expression vers le schéma : on place une porte par opérateur, en commençant par les parenthèses les plus internes.

Règles de priorité

Comme en mathématiques ($2 + 3 \times 4 = 14$ et non 20), les opérateurs booléens ont des priorités :

Pour retenir : ET se comporte comme la multiplication, OU comme l’addition — et la multiplication est prioritaire.

La table de vérité montre la différence :

Les deux colonnes sont différentes : les parenthèses comptent.

Dresser la table d’une expression

Même méthode que pour un circuit : une colonne intermédiaire par opérateur, en respectant les priorités.

Exemple : table de vérité de $S = (a \text{ ET } \overline{b}) \text{ OU } (\overline{a} \text{ ET } b)$ :

La colonne S est celle du XOR : nous venons de reconstruire un OU exclusif avec des NON, des ET et un OU.

Quelques équivalences utiles (pour info)

Elles permettent de simplifier une expression, donc de fabriquer le circuit avec moins de portes :

Application : le demi-additionneur

Le problème

Comment faire faire une addition binaire à un circuit ? Commençons par le plus simple : additionner deux bits E1 et E2. Reprenons la table d’addition binaire vue au chapitre B.1 :

• $0 + 0 = 0$
• $0 + 1 = 1$
• $1 + 0 = 1$
• $1 + 1 = 10$

Le dernier cas est la clé : le résultat ne tient pas sur un bit. Il faut donc deux sorties :

• la somme S (le chiffre des unités du résultat),
• la retenue R (le chiffre suivant, à reporter sur la colonne de gauche).

La table de vérité

Regardons chaque colonne de sortie séparément :

• R vaut 1 uniquement quand E1 et E2 valent 1 : c’est la table du ET,
• S vaut 1 quand E1 et E2 diffèrent : c’est la table du XOR.

Le schéma

E1 et E2 alimentent chacune les deux portes : les fils se divisent.

Pourquoi « demi » ?

Parce qu’il ne fait que la moitié du travail : quand on additionne deux nombres de plusieurs bits, chaque colonne doit additionner trois bits, les deux bits du rang plus la retenue de la colonne précédente.

 1 1 1 1      <- retenues
   1 0 1 1
 + 0 1 1 1
 ---------
 1 0 0 1 0

Le circuit qui additionne trois bits (deux bits + une retenue entrante) s’appelle l’additionneur complet (full adder), et se fabrique… avec deux demi-additionneurs et une porte OU. Bout à bout, 8, 32 ou 64 additionneurs complets forment l’unité de calcul d’un processeur.