Valeurs booléennes

Vrai / faux

Principe

un ordinateur ne manipule que des 0 et des 1 (électricité ou pas)

=> vus aussi comme des valeurs de vérité

• 0 = faux = False
• 1 = vrai = True

=> une valeur booléenne (George Boole, 1815-1864)

le plus petit type de donnée possible : 1 bit

D’où ça vient ?

réponse à une question fermée (oui / non)

• l’interrupteur est-il allumé ?
• 3 est-il plus grand que 2 ?
• la porte est-elle ouverte ?

Deux notations, un seul objet

dans ce cours : surtout 0 et 1

Opérateurs booléens et portes logiques

Opérateurs et portes

Opérateurs booléens

combiner des booléens : NON, ET, OU, + OU exclusif

exemple : « la porte est-elle fermée ET la lumière allumée ? »

Portes logiques

porte logique = composant électronique qui réalise un opérateur

• 1 ou 2 signaux en entrée
• 1 signal en sortie
• un symbole pour les schémas

un processeur moderne : plusieurs milliards de portes

Lire un schéma

• entrées à gauche, sortie à droite
• les traits = les fils, ils transportent 0 ou 1
• un fil peut se diviser (alimenter plusieurs portes)
• deux fils n’arrivent jamais sur la même entrée

Table de vérité

table de vérité = sortie pour toutes les combinaisons d’entrées

nombre de lignes : $2^n$ pour n entrées

• 1 entrée => 2 lignes
• 2 entrées => 4 lignes
• 3 entrées => 8 lignes
• 4 entrées => 16 lignes

Les portes de base

NON (NOT)

unaire : une seule entrée, on l’inverse

notations : NON a, $\overline{a}$, $\lnot a$

le petit rond = « et on inverse »

a	NON a
0	1
1	0

ET (AND)

vaut 1 si et seulement si les deux entrées valent 1

« il faut le badge et le code »

notations : $a \land b$, $a \cdot b$ => comme une multiplication

a	b	a ET b
0	0	0
0	1	0
1	0	0
1	1	1

OU (OR)

vaut 1 dès qu’au moins une entrée vaut 1

attention : OU inclusif (les deux à 1 => 1 aussi)

notations : $a \lor b$, $a + b$

a	b	a OU b
0	0	0
0	1	1
1	0	1
1	1	1

OU exclusif (XOR)

vaut 1 quand les entrées sont différentes

« fromage ou dessert », mais pas les deux

symbole du OU + barre supplémentaire à l’arrière

notation : $a \oplus b$

a	b	a XOR b
0	0	0
0	1	1
1	0	1
1	1	0

XOR : deux façons de le voir

• détecteur de différence
• addition binaire sur 1 bit, dont on garde les unités
  • $0+0=0$
  • $0+1=1$
  • $1+0=1$
  • $1+1=1\underline{0}$ => on garde 0

à réutiliser plus loin (demi-additionneur)

Portes dérivées

NAND et NOR

versions niées de ET et OU (plus simples à fabriquer)

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

symbole du ET / du OU + petit rond

NAND et NOR : tables

culture : NAND est universelle (tout circuit se refait avec des NAND)

Récapitulatif des symboles

Récapitulatif des tables de vérité

toutes les entrées à gauche, un opérateur par colonne

Comment lire ce tableau

• NON a ne dépend que de a (opérateur unaire)
• NAND = colonne ET inversée, NOR = colonne OU inversée
• OU et XOR ne diffèrent que sur la dernière ligne (les deux entrées à 1)
• ET : 1 fois sur 4 ; OU : 3 fois sur 4

=> un aide-mémoire, pas quelque chose à apprendre par cœur

Simulation

Simulateur

simulateur de circuits logiques (via Capytale)

• placer entrées, portes, sortie
• basculer les entrées, observer la sortie

attention : le simulateur vérifie une table de vérité, il ne la remplace pas

Combiner des portes

Méthode

Dresser la table de vérité d’un circuit

1. compter les entrées n => $2^n$ lignes
2. écrire toutes les combinaisons (= compter en binaire de 0 à $2^n-1$)
3. une colonne intermédiaire par porte, dans l’ordre du signal
4. remplir colonne par colonne, en n’utilisant que ce qui est déjà rempli
5. la ou les dernières colonnes = la ou les sorties

=> on ne devine jamais la sortie, on avance porte par porte

Exemple

Le circuit

• ET sur E1,E2 => A
• OU sur E2,E3 => B
• XOR sur A,B => S

E2 alimente deux portes : le fil se divise

Sa table de vérité

=> sortie à 1 dans 5 cas sur 8

Exercices

Expressions booléennes

Écriture

Du schéma à l’expression

expression booléenne = formule combinant des variables avec NON, ET, OU, XOR

le circuit 1 :

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

deux écritures du même objet

• schéma => expression : partir de la sortie, remonter
• expression => schéma : une porte par opérateur, en commençant par les parenthèses internes

Exercices : schéma <=> expression

Priorités

comme en maths ($2 + 3 \times 4 = 14$)

1. parenthèses
2. NON
3. ET
4. OU (et XOR)

à priorité égale : de gauche à droite

moyen de retenir : ET = multiplication, OU = addition

Attention aux parenthèses

• a OU b ET c se lit a OU (b ET c)
• NON a ET b se lit (NON a) ET b
• … et pas NON (a ET b), qui est un NAND !

en cas de doute => parenthéser

Tables et équivalences

Table d’une expression

même méthode : une colonne par opérateur, dans l’ordre des priorités

$S = (a \text{ ET } \overline{b}) \text{ OU } (\overline{a} \text{ ET } b)$

=> c’est la table du XOR : on l’a reconstruit avec NON, ET, OU

Exercice : tables d’expressions

Équivalence

deux expressions sont équivalentes si elles ont la même table de vérité

seul critère : ni l’écriture, ni le nombre de portes ne comptent

Règles utiles (pour info)

Règles utiles : la liste

simplifier une expression = fabriquer le circuit avec moins de portes

Application : le demi-additionneur

Le problème

Additionner deux bits

table d’addition binaire (chapitre B.1) :

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

dernier cas : ça ne tient plus sur un bit

=> il faut deux sorties

• la somme S (les unités)
• la retenue R (à reporter à gauche)

La table de vérité

colonne par colonne :

• R = 1 seulement si les deux entrées sont à 1 => ET
• S = 1 si les entrées diffèrent => XOR

Le circuit

Deux portes suffisent

$$R = E_1 \text{ ET } E_2 \qquad S = E_1 \text{ XOR } E_2$$

les deux entrées alimentent les deux portes : les fils se divisent

Demi-additionneur : exercice

Pourquoi « demi » ?

sur plusieurs bits, chaque colonne additionne trois bits : les deux bits du rang + la retenue précédente

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

• 3 bits en entrée => additionneur complet (full adder)
• = 2 demi-additionneurs + 1 porte OU

L’additionneur complet

• demi-add. n° 1 : A + B
• demi-add. n° 2 : ajoute la retenue entrante => somme finale S
• porte OU : rassemble les deux retenues

Pourquoi un simple OU ?

les deux retenues ne valent jamais 1 en même temps

• si A = B = 1, la somme du n° 1 vaut 0
• donc le n° 2 ne peut plus produire de retenue

=> le cas « 1 + 1 » ne se présente jamais à l’entrée du OU

Additionner deux octets

huit additionneurs complets, un par colonne

La chaîne des retenues

• retenue sortante d’un étage => retenue entrante de l’étage de gauche
• bit 0 : pas de retenue entrante (entrée à 0)
• retenue finale r8 = 9e bit => dépassement de capacité si elle vaut 1

=> additionneur à propagation de retenue : chaque étage attend son voisin de droite

Exercice

Au final

8, 32, 64 additionneurs bout à bout => l’unité de calcul du processeur

=> l’addition est entièrement ramenée à de la logique booléenne