Codage des booléens
Ce cours fournit une introduction à la logique booléenne et à la manière dont elle s'applique à l'informatique. Vous apprendrez non seulement les bases des opérations booléennes, mais vous comprendrez également comment ces opérations peuvent être utilisées pour créer des structures plus complexes, telles que des additions binaires, des multiplexeurs, des décodeurs et, finalement, un ordinateur entier.
Le programme
Définition
De nombreux dispositifs électroniques, électromécaniques, (mécaniques, électriques, pneumatiques, etc....) fonctionnement en TOUT ou RIEN.
Ceci sous-entend qu'ils peuvent prendre 2 états.
Exemples :
- Arrêt / Marche
- Enclenché / Déclenché
- Vrai / Faux
- Ouvert / Fermé
- Avant / Arrière
- Conduction / Blocage
Un système présentera un fonctionnement logique combinatoire si l'état à un instant t des variables de sortie ne dépend que de l'état des variables d'entrée au même instant t.
Variable logique
Une variable logique est un type de variable qui peut prendre uniquement l'une de deux valeurs, généralement désignées comme 0 (faux) et 1 (vrai). Ces deux valeurs sont souvent utilisées pour représenter deux états opposés. Par exemple :
| État Vrai | État Faux |
|---|---|
| Oui | Non |
| True | False |
| 1 | 0 |
| Haut | Bas |
Par exemple, la variable "IsLightOn" peut avoir deux états : 1 (la lumière est allumée) ou 0 (la lumière est éteinte).
Fonction logique
Une fonction logique est une expression qui produit une valeur de vérité à partir d'autres valeurs de vérité. Par exemple, une fonction logique peut comporter des variables logiques n. Pour chacune de ces combinaisons, la fonction peut prendre une valeur 0 ou 1. Nous obtenons donc 2^n combinaisons pour ces n variables.
Table de vérité
On représente l'ensemble valeurs d'entrées et sorties par une table de vérité :
- À chaque variable d'entrée correspond une colonne,
- À chaque ligne, une valeur d'état possible,
- Une colonne de sortie contient la valeur de l'état de l'opération.
Exemple :
\begin{aligned}
S = 1 \text{ si} \left\{
\begin{array}{l}
a = 0 \text{ et } b = 1 \\
a = 0 \text{ et } b = 0 \\
a = 1 \text{ et } b = 0
\end{array}
\right.
\end{aligned}
a |
b |
S |
|---|---|---|
| 0 | 1 | 1 |
| 0 | 0 | 1 |
| 1 | 1 | 0 |
| 1 | 0 | 1 |
Opérateurs logiques
Opérateur NON
On associe à une variable binaire quelconque a son complément, noté \overline{a}
\begin{aligned}
S = 1 \text{ si } a = 0
\end{aligned}
La table de vérité de l'opérateur NON :
a |
S = \overline{a} |
|---|---|
| 0 | 1 |
| 1 | 0 |
Opérateur ET
L'état 1 est obtenu lors de l’action simultanée sur les 2 variables a et b. L'opérateur est noté \land
\begin{aligned}
S & = 1 \text{ ssi } a = 1 \text{ et } b = 1 \\
& = a \land b
\end{aligned}
La table de vérité de l'opérateur ET :
a |
b |
S = a \land b |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Propriétés
\begin{aligned}
a \land a & = a \\
a \land 1 & = a \\
a \land \overline{a} & = 0 \\
a \land 0 & = 0
\end{aligned}
Opérateur OU
L'état 1 est obtenu lors de l’action simultanée sur l'une des 2 variables ou les 2. L'opérateur est noté \lor
\begin{aligned}
S = 1 \text{ ssi} \left\{
\begin{array}{l}
a = 0 \text{ ou } b = 1 \\
a = 1 \text{ ou } b = 0 \\
a = 1 \text{ ou } b = 1
\end{array}
\right.
\end{aligned}
La table de vérité de l'opérateur OU :
a |
b |
S = a \lor b |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Propriétés
\begin{aligned}
a \lor a & = a \\
a \lor 1 & = 1 \\
a \lor \overline{a} & = 1 \\
a \lor 0 & = a
\end{aligned}
Portes Logiques de Base
Une porte logique est un dispositif qui effectue une opération logique sur un ou plusieurs signaux logiques produisant une sortie. Les portes logiques de base sont :
-
Porte AND : Cette porte a deux ou plusieurs entrées et une sortie. La sortie est vraie (1) si toutes les entrées sont vraies.
-
Porte OR : Cette porte a deux ou plusieurs entrées et une sortie. La sortie est vraie (1) si au moins une des entrées est vraie.
-
Porte NOT : Cette porte a une seule entrée et une sortie. La sortie est l'inverse de l'entrée. Si l'entrée est vraie (1), la sortie est fausse (0) et vice versa.
-
Porte XOR (OU exclusif) : Cette porte a deux entrées et une sortie. La sortie est vraie (1) si une, et seulement une, des entrées est vraie.
-
Porte NAND (NON-ET) : Cette porte a deux ou plusieurs entrées et une sortie. La sortie est fausse (0) uniquement si toutes les entrées sont vraies. C'est l'inverse de la porte AND.
-
Porte NOR (NON-OU) : Cette porte a deux ou plusieurs entrées et une sortie. La sortie est vraie (1) uniquement si toutes les entrées sont fausses. C'est l'inverse de la porte OR.
Algèbre de Boole
Définition
Système algébrique constitué de l'ensemble \{0, 1\}, muni des 3 opérateurs de base NON, ET, OU.
Propriétés
- Associativité : Comme avec les opérations habituelles, certaines parenthèses sont inutiles. Exemple :
( a \land b ) \land c = a \land (b \land c) = a \land b \land c - Commutativité : L'ordre est sans importance. Exemple :
a \land b = b \land a - Distributivité : Exemple :
a \lor ( b \land c ) = ( a \lor b ) \land ( a \lor c ) - Idempotence : Exemple :
a \land a \land a \land \dots \land a = a
Forme canonique
Combinaison des variables de la fonction via les opérateurs de base de l’algèbre de Boole.
La fonction S définie par :
\begin{aligned}
S = 1 \text{ si} \left\{
\begin{array}{l}
a = 0 \text{ et } b = 1 \\
a = 0 \text{ et } b = 0 \\
a = 1 \text{ et } b = 0
\end{array}
\right.
\end{aligned}
S s'écrit sous sa forme canonique : S= (\overline{a} \land b) \lor (\overline{a} \land \overline{b}) \lor (a \land \overline{b})
Exercices
Établir des tables de vérité
Travail à effectuer : Écrire les tables de vérité des expressions booléennes suivantes.
Conseil : essayez d'imaginer comment la lumière d'une maison pourrait être contrôlée par deux interrupteurs (a et b).
S(a, b) = \overline{a} \land bS(a, b) = b \lor (a \land b)S(a, b) = a \land (a \lor b)S(a, b, c) = (\overline{a} \land b) \lor (a \land c)- Communication = Émetteur ET Récepteur
- Décrocher = (Sonnerie ET Décision de répondre) OU décision d'appeler
- Bac = Avoir la moyenne OU (NON Avoir la moyenne ET rattrapage)
Équivalence d'expressions booléennes
- Montrer que
(a \land b) = \overline{\overline{a} \lor \overline{b}} - Montrer que
(a \lor b) = \overline{\overline{a} \land \overline{b}}
N.B : Deux expressions booléennes sont équivalentes si leurs tables de vérité le sont.
Autrement dit, si pour toutes les entrées des tables de vérité, l'ensemble des valeurs de sorties de ces mêmes tables sont équivalentes alors les expressions booléennes sont équivalentes.
Déterminer une expression booléenne
| a | b | ssi(a, b) |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Travail à effectuer : Trouver l'expression booléenne, notée ssi(a, b) à partir de la table de vérité ci-dessus.
Loi de De Morgan
Les lois de De Morgan sont des identités entre propositions logiques. Elles ont été formulées par le mathématicien britannique Augustus De Morgan (1806-1871).
\overline{(a \lor b)} = \overline{a} \land \overline{b}\overline{(a \land b)} = \overline{a} \lor \overline{b}
Travail à effectuer : Démontrer ces 2 lois.
Ressources supplémentaires
NANDGAME
NANDGAME est un jeu en ligne gratuit où vous pouvez construire un ordinateur à partir de zéro en utilisant uniquement la porte logique NAND.
Auteurs : Florian Mathieu - Philippe Boddaert
Licence CC BY NC
Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.