Informatique au lycée/Algèbre booléenne et circuits logiques
L'algèbre de Boole
[modifier | modifier le wikicode]
Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?L'algèbre de Boole, ou calcul booléen, est la partie des mathématiques qui s'intéresse aux opérations et aux fonctions sur les variables logiques. Elle fut inventée par le mathématicien britannique George Boole. Aujourd'hui, l'algèbre de Boole trouve de nombreuses applications en informatique et dans la conception des circuits électroniques.
On appelle B l’ensemble constitué de deux éléments appelés valeurs de vérité {FAUX, VRAI}. Cet ensemble est aussi noté B = {0, 1}, notation que l’on utilisera désormais.
Sur cet ensemble on peut définir les lois ET et OU et une transformation appelée « complémentaire » (parfois « inversion » ou « contraire »).
ET
Elle est définie de la manière suivante : a ET b est VRAI si et seulement si a est VRAI et b est VRAI.
OU
Elle est définie de la manière suivante : a OU b est VRAI si et seulement si a est VRAI ou b est VRAI, ou si a et b sont vrais.
NON
Le contraire de « a » est VRAI si et seulement si a est FAUX.
Fonctions logiques et tables de vérité
[modifier | modifier le wikicode]Une table de vérité est un tableau qui représente des entrées (en colonne) et des états binaires (0 et 1). Le résultat, exprimé lui aussi sous forme binaire, se lit dans la dernière colonne.
| Symbole de la porte logique | Opération booléenne | Table de vérité | |||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ET (AND) | TODO : image | A·B |
| ||||||||||||||||||
| OU | TODO | A+B |
| ||||||||||||||||||
| NON | TODO |
| |||||||||||||||||||
| NON-ET | TODO |
| |||||||||||||||||||
| NON-OU | TODO |
| |||||||||||||||||||
| OU exclusif | TODO |
| |||||||||||||||||||
Quelques propriétés utiles
[modifier | modifier le wikicode]Associativité
[modifier | modifier le wikicode]Comme avec les opérations habituelles, certaines parenthèses sont inutiles :
(a + b) + c = a + (b + c) = a + b + c
(a·b)·c = a·(b·c) = a·b·c
Commutativité
[modifier | modifier le wikicode]L'ordre est sans importance :
a + b = b + a
a·b = b·a
Distributivité
[modifier | modifier le wikicode]Comme avec les opérations mathématiques habituelles, il est possible de distribuer :
a·(b+c) = a·b + a·c
Idempotence
[modifier | modifier le wikicode]a + a + a + [...] + a = a
a·a·a·[...]·a = a
Élément neutre
[modifier | modifier le wikicode]a+0=a
a·1 = a
Élément nul
[modifier | modifier le wikicode]0·a = 0
1+a=1
Complémentarité
[modifier | modifier le wikicode]a = ¬(¬a)
a+ a = 1
a· a = 0
Théorème de De Morgan
[modifier | modifier le wikicode]Priorité
[modifier | modifier le wikicode]Pour faciliter leur compréhension, il a été décidé que ces opérations seraient soumises aux mêmes règles que les opérations mathématiques. La fonction ET (multiplication logique) est ainsi prioritaire par rapport à la fonction OU (somme logique) ; on peut, pour s'aider, placer des parenthèses dans les opérations.
Tables de Karnaugh
[modifier | modifier le wikicode]Une table de Karnaugh est une méthode inventée par Maurice Karnaugh en 1954 et qui sert à simplifier des équations logiques ou à trouver l'équation logique correspondant à une table de vérité. La méthode utilisée est graphique. Elle fonctionne très bien avec 3 ou 4 variables, beaucoup moins bien avec 5 ou 6 variables, et plus du tout au-delà !
Principe
[modifier | modifier le wikicode]Soit la table de vérité de S suivante avec les variables A, B, C et D :
| A | B | C | D | S |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
La table de Karnaugh correspondante se présente ainsi :
| AB\CD | 00 | 01 | 11 | 10 |
| 00 | 1 | 0 | 1 | 1 |
| 01 | 0 | 1 | 1 | 1 |
| 11 | 0 | 1 | 1 | 1 |
| 10 | 1 | 0 | 1 | 1 |
Méthode de recherche de l'équation de la table de vérité
[modifier | modifier le wikicode]- Pour trouver une équation logique, il faut regrouper les valeurs de S égales à 1 dans des rectangles ayant comme nombre de cases une puissance de 2 (16, 8, 4, 2 ou 1 cases).
- Les groupes formés doivent être les moins nombreux possibles, mais ils doivent englober tous les 1. On peut faire des chevauchements.
- On a intérêt à dessiner des rectangles les plus grands possibles.
- On peut considérer cette table comme un tore : la dernière ligne est adjacente à la première et la première colonne est adjacente à la dernière. On peut ainsi regrouper des 1 se trouvant à ces emplacements.
Pour les tables à 4 variables, il faut de préférence procéder dans l’ordre suivant :
- les rectangles 8 cases, puis
- les rectangles 4 cases, puis
- les rectangles 2 cases, et enfin
- les cases uniques.
Dans l'exemple : on peut former un rectangle de 8 cases (en bleu), puis un carré de 4 (en vert) et enfin on peut regrouper les deux 1 restants (en rouge).
| AB\CD | 00 | 01 | 11 | 10 |
| 00 | 1 | 0 | 1 | 1 |
| 01 | 0 | 1 | 11 | 1 |
| 11 | 0 | 1 | 11 | 1 |
| 10 | 1 | 0 | 1 | 1 |
