Opérateurs booléens et portes logiques
Programme
| Notions | Compétences | Remarques |
|---|---|---|
| Valeurs booléennes : 0, 1. Opérateurs booléens : and, or, not. Expressions booléennes |
Dresser la table d'une expression booléenne. | Le ou exclusif (xor) est évoqué. Quelques applications directes comme l'addition binaire sont présentées. L'attention des élèves est attirée sur le caractère séquentiel de certains opérateurs booléens. |
Le langage binaire
Le langage binaire
Avec le développement des premiers calculateurs fonctionnant à l'électricité, à base de relais électromécaniques, puis de tubes électroniques, de transistors, et enfin de circuits intégrés au sein de microprocesseurs, l'informatique s'est orienté vers un langage binaire :
-
0 : le courant ne passe pas
-
1 : le courant passe
Mathématiquement, on dira que les ordinateurs effectuent des opérations en base 2 (binaire), et non dans la base 10 (décimale) que nous avons l'habitude d'utiliser.
Nous verrons dans la partie sur l'encodage comment se passe la numération en base 2.
Représentation binaire de l'information
Logique booléenne
Logique booléenne
Un peu d'histoire
En 1847, le britannique George BOOLE inventait un formalisme permettant d'écrire des raisonnements logiques : l'algèbre de Boole. La notion même d'informatique n'existait pas à l'époque, même si les calculs étaient déjà automatisés (penser à la Pascaline de 1642).
Bien plus tard, en 1938, les travaux de l'américain Claude SHANNON prouvèrent que des circuits électriques pouvaient résoudre tous les problèmes de l'algèbre booléenne. Pendant la deuxième guerre mondiale, les travaux d'Alan TURING puis de John VON NEUMANN poseront définitivement les bases de l'informatique moderne.
L'algèbre de Boole définit des opérations dans un ensemble qui ne contient que deux éléments notés 0 et 1, ou FAUX et VRAI, ou encore False et True en Python.
Les opérations fondamentales sont :
- la conjonction : A ET B
- la disjonction : A OU B
- la négation : NON A
De nombreuses autres peuvent être obtenues en combinant les opérations fondamentales, on notera en particulier :
- la disjonction exclusive : OU EXCLUSIF = (A ET non B) OU (non A ET B)
Portes et circuits logiques
Portes et circuits logiques
En électronique, les transistors effectuent des opérations booléennes directement liées à l'algèbre de Boole. Ainsi, un circuit logique prend en entrée un ou plusieurs signaux électriques. Chaque entrée est dans un état "haut" 1 ou un état "bas" 0 et donne en sortie un ou plusieurs signaux électriques. Chaque sortie est alors également dans un état "haut" ou "bas".
Remarque
Il existe deux catégories de circuit logique :
-
les circuits combinatoires : les états en sortie dépendent uniquement des états en entrée.
-
les circuits séquentiels : les états en sortie dépendent des états en entrée ainsi que du temps et des états antérieurs.
Dans la suite nous nous intéresserons principalement aux circuits combinatoires.
Fonctionnement des principales portes logiques
Il est nécessaire de connaître le fonctionnement des principales portes logiques, et de savoir en établir les tables de vérités.
- symbole usuel : ~
- français : NON
- anglais (et Python) :
not - notation logique : \(\neg\)
- notation mathématique : \(\overline{x}\)
Le plus simple des circuits combinatoires est la porte "NON" ("NOT" en anglais) qui inverse l'état en entrée : si l'entrée de la porte est dans un état "bas" alors la sortie sera dans un état "haut" et vice versa.
Table de vérité de NON
Si on symbolise l'état "haut" par un "1" et l'état "bas" pour un "0", on peut obtenir ce que l'on appelle la table de vérité de la porte "NON" :
| E (Entrée) | S (Sortie) |
|---|---|
| 1 | 0 |
| 0 | 1 |
- symbole usuel : | appelé pipe en anglais
- français : OU
- anglais (et Python) :
or - notation logique : \(\vee\)
- notation mathématique : \(+\)
La porte "OU" a deux entrées (E1 et E2) et une sortie S
Table de vérité de OU
| E1 | E2 | S |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
- symbole usuel : & (appelé esperluette en français et ampersand en anglais)
- français : ET
- anglais (et Python) :
and - notation logique : \(\wedge\)
- notation mathématique :
.
La porte "ET" ("AND") a deux entrées (E1 et E2) et une sortie S
Table de vérité de ET
| E1 | E2 | S |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
- symbole usuel : ⊕
- français : OU exclusif
- anglais (et Python) :
XOR - Python :
^ - notation logique : ⊕
- notation mathématique : ↮
Table de vérité de OU EXCLUSIF
| E1 | E2 | S |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Activités
Activité 1 - Combinaison de portes logiques
Des portes logique peuvent s'obtenir en combinant 2 autres.
Constituer les portes NON OU et NON ET et en établir le tableau de vérité.
NON ET
Table de vérité
| E1 | E2 | S |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
NON OU
```{.logic style="height: 200px;" mode="tryout"} { // JSON5 v: 6, opts: {showGateTypes: true, animateWires: true, zoom: 200}, components: { or0: {type: 'or', pos: [135, 60], in: [0, 1], out: 2}, in0: {type: 'in', pos: [50, 45], id: 3}, in1: {type: 'in', pos: [50, 85], id: 4}, not0: {type: 'not', pos: [230, 60], in: 5, out: 6}, out0: {type: 'out', pos: [315, 60], id: 7}, }, wires: [[3, 0], [4, 1], [2, 5], [6, 7]] }
Table de vérité
| E1 | E2 | S |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
Activité 2 - Table de vérité d'un additionneur
En combinant les portes logiques, on obtient des circuits plus complexes. Par exemple en combinant 2 portes "OU EXCLUSIF", 2 portes "ET" et une porte "OU" on obtient un additionneur, qui permet d'additionner 2 bits (E1 et E2) en tenant compte de la retenue entrante (C0). En sortie on obtient le résultat de l'addition (S) et la retenue sortante ("C1").
Question : Constituer la table de vérité de S1 et C1 en fonction de E1, E2 et C0.
RĂ©ponse
Table de vérité :
| E1 | E2 | C0 | C1 | S1 |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 |
Remarque
En combinant plusieurs fois le type de circuit décrit ci-dessus, on obtient des additionneurs capables d'additionner des nombres sur X bits.
Activité 3 - Réalisation d'opérations logiques sur les bits
1 - Effectue à la main les opérations suivantes, en les réalisant bit à bit.
Rappel : & est le symbole de ET, | de OU, ^ de OU EXCLUSIF.
1011011
& 1010101
----------
1011011
| 1010101
----------
1011011
^ 1010101
----------
2 - Vérifie tes résultats avec python.
La logique booléenne en Python
Les opérateurs and, or et not sont utilisables pour tester des conditions, et renvoient False ou True.
>>> n = 20
>>> (n > 1) and (n < 10)
False
>>> (n > 1) and (n < 30)
True
>>> (n > 1) or (n < 10)
True
>>> not(n == 5)
True
Les opérateurs &, | et ^ sont utilisables directement avec des nombres, et renvoient des nombres.
# calcul A
>>> 12 & 7
4
# calcul B
>>> 12 | 7
15
# calcul C
>>> 12 ^ 5
9
Explication
Pour comprendre ces résultats, il faut travailler en binaire (voir le chapitre sur l'encodage) :
- Les nombre binaires sont précédés de
0b. - La fonction
bin(n)convertit un nombre entier en binaire.
Voici les mĂŞmes calculs, qui peuvent mieux s'analyser en prenant les bits un Ă un :
# calcul A
>>> bin(0b1100 & 0b111)
'0b100'
# calcul B
>>> bin(0b1100 | 0b111)
'0b1111'
# calcul C
>>> bin(0b1100 ^ 0b111)
'0b1011'
1011011
&1010101
----------
1010001
1011011
|1010101
----------
1011111
1011011
^1010101
----------
0001110
Conclusion : Du transistor aux microprocesseurs
A la base de l'informatique nous avons le transistor, composant muni de 2 entrées et une sortie. Une combinaison de transistors (sous forme de circuit intégré) permet d'obtenir des circuits logiques, la combinaison de circuits logiques permet d'obtenir des circuits plus complexes (exemple : l'additionneur).
Nous verrons dans la partie suivante que ces circuits forment l'unité arithmétique et logique des microprocesseurs.