Algèbre booléenne et cartes de Karnaugh
| English | Français |
|---|---|
| Boolean algebra/ˈbuːlɪən ˈældʒɪbrə/ | Algèbre booléenne |
| De Morgan's laws/də ˈmɔːɡənz lɔːz/ | lois de De Morgan |
| Karnaugh map/ˈkɑːnɔː mæp/ | carte de Karnaugh |
| truth table/truːθ ˈteɪbl/ | table de vérité |
| absorption/əbˈsɔːpʃn/ | absorption |
| Gray code/ɡreɪ kəʊd/ | code Gray |
La thèse de master qui a construit l'ère numérique
- En 1937, un étudiant de 21 ans nommé Claude Shannon remarqua que les relais téléphoniques qu'il étudiaient faisaient la même chose qu'une algèbre inventée par George Boole quatre-vingts ans plus tôt pour raisonner sur le vrai et le faux.
- Si un interrupteur est une variable booléenne, alors un circuit est une expression, et simplifier l'expression retire des portes du circuit. Moins de portes signifie moins cher, plus rapide et moins d'énergie.
- Sa thèse a été qualifiée de la plus importante du siècle. Tout ce qui se trouve sur cette page est cette idée utilisée comme outil.
- Cette leçon porte sur l'algèbre booléenne (布尔代数), les lois de De Morgan, et la carte de Karnaugh (卡诺图) qui effectue la même tâche par l'œil.
La notation et les lois
+signifie OU,·signifie ET et est souvent omis, et une barre supérieure signifie NON. Une table de vérité (真值表) décrit exhaustivement la même chose.- Identité : $A + 0 = A$ et $A \cdot 1 = A$. Null : $A + 1 = 1$ et $A \cdot 0 = 0$.
- Idempotent : $A + A = A$. Inverse : $A + \overline{A} = 1$ et $A \cdot \overline{A} = 0$.
- Absorption (吸收律) : $A + A\cdot B = A$, car si $A$ est vrai, toute l'expression est vraie peu importe $B$.
Reliez chaque loi booléenne à ce qu'elle signifie.
Ces lois permettent de simplifier algébriquement les expressions booléennes avant de construire le circuit.
Par la loi d'absorption, A + A·B se simplifie en ____.
Si A est vrai, l'expression entière est vraie peu importe B, et si A est faux, les deux termes sont faux. B ne peut pas affecter le résultat.
Lois de De Morgan
- Les lois de De Morgan (德摩根定律) sont les deux que l'examen vous demande d'utiliser par nom :
- La recette en mots : négatif l'ensemble, échangez ET et OU, négatif chaque opérande.
- Elles ont une importance pratique car elles permettent de réécrire n'importe quelle expression en utilisant uniquement des portes NAND ou uniquement des portes NOR, et une puce construite à partir d'une porte répétée est moins chère à fabriquer.
Deux expressions, une seule table de vérité
Algèbre booléenne
A·B, A+B, Ā …
L'algèbre booléenne n'est que ces portes écrites sous forme d'expressions — comparez les tables de vérité.
Par la loi de De Morgan, $\overline{A \cdot B}$ vaut :
Négation globale, inversion AND→OR, négation de chaque opérande : $\overline{A \cdot B} = \overline{A} + \overline{B}$.
L'application de la loi de De Morgan à une expression implique quelles étapes ? Sélectionnez tous ceux qui s'appliquent.
Négation globale, inversion de l'opérateur, négation de chaque partie. L'ordre est indifférent, car AND et OR sont commutatifs.
Exemple résolu : simplifier et compter les portes
- Simplifiez $Z = A\cdot B + A\cdot\overline{B}$ et dites ce que cela économise.
- Factorisez $A$ : $Z = A\cdot(B + \overline{B})$. Par la loi inverse $B + \overline{B} = 1$, donc $Z = A \cdot 1 = A$.
- L'original nécessite deux portes ET, une porte NON et une porte OU : quatre portes. L'expression simplifiée n'en a besoin de aucune, seulement l'entrée $A$.
- Terminez toujours par ce que la simplification apporte : moins de portes, donc un circuit moins cher, plus rapide et consommant moins d'énergie.
Simplifier $A\cdot B + A\cdot\overline{B}$.
Factoriser A : $A(B + \overline{B}) = A \cdot 1 = A$.
A·B + A·NON B nécessite deux portes AND, une porte NOT et une porte OR. Combien de portes sa forme simplifiée nécessite-t-elle ?
Elle se simplifie en A uniquement, donc la sortie est l'entrée et aucune porte n'est nécessaire. Quatre portes économisées.
La carte de Karnaugh
- Une carte de Karnaugh simplifie une expression en regroupant des 1 adjacents extraits de la table de vérité.
- Les lignes et colonnes sont étiquetées selon l'ordre du code Gray (格雷码),
00, 01, 11, 10, afin que les cellules adjacentes diffèrent par exactement une variable. C'est toute l'astuce : cela rend l'algèbre visible par adjacence. - Placez un 1 dans chaque cellule où la sortie est 1, puis trouvez des groupes rectangulaires de 1s dont les côtés sont des puissances de deux : 1, 2, 4, 8. Les groupes peuvent tourner autour des bords.
Plus le rectangle est grand, plus le terme est simple
Une carte de Karnaugh simplifie une expression booléenne en :
Vous regroupez les 1 adjacents (dans l'ordre Gray) en rectangles de puissances de deux ; chaque groupe devient un terme simplifié.
Pourquoi les lignes et colonnes d'une carte de Karnaugh sont-elles étiquetées 00, 01, 11, 10 plutôt que 00, 01, 10, 11 ?
L'ordre Gray transforme l'adjacence algébrique en adjacence physique. Dans l'ordre de comptage, la règle de regroupement ne fonctionnerait simplement pas.
Lire un groupe
- À l'intérieur d'un groupe, une variable qui reste constante subsiste dans le terme ; une variable qui change disparaît.
- Ainsi, un groupe de 2 retire une variable, un groupe de 4 en retire deux, et un groupe de 8 en retire trois. Plus le groupe est grand, plus le terme est simple.
- Couvrez tous les 1s en utilisant le moins de groupes possibles et les plus grands, puis additionnez (OR) les termes des groupes. Les groupes peuvent se chevaucher, et le chevauchement permet souvent de former un groupe plus grand.
Dans une carte de Karnaugh, un plus grand groupe de 1 adjacents élimine plus de variables, donnant un terme plus simple (un groupe de 2 retire une variable, un groupe de 4 en retire deux).
Vous regroupez les 1 adjacents en rectangles de puissances de deux dans l'ordre Gray ; plus le groupe est grand, plus le terme résultant est simple.
Placez les étapes de simplification avec une carte de Karnaugh dans l'ordre.
Ordre Gray, uns, plus grands groupes, retirez ce qui change, OR les termes. Utilisez le moins de groupes et aussi grands que possible pour couvrir tous les 1.
Exemple résolu : lire une carte à deux variables
- Une carte de Karnaugh pour $A$ et $B$ a des 1s dans les cellules $\overline{A}B$ et $AB$. Simplifiez.
- Les deux 1s sont adjacents : ils partagent la colonne $B = 1$, donc ils forment un groupe rectangulaire de 2.
- À l'intérieur de ce groupe, $B$ reste 1 tout au long, tandis que $A$ passe de 0 à 1. La variable qui change disparaît.
- Donc toute l'expression est simplement $Z = B$. Comparez cela avec la somme de produits non simplifiée, $\overline{A}B + AB$, qui nécessite une porte NON, deux portes ET et une porte OU.
Quelle méthode utiliser
- L'algèbre booléenne est exacte et fonctionne pour n'importe quel nombre de variables, mais vous devez repérer quelle loi s'applique.
- Une carte de Karnaugh est mécanique et difficile à mal faire pour deux à quatre variables, ce qui correspond à ce que l'examen propose, et elle montre directement le regroupement le plus large.
- Les deux donnent la même réponse. L'avantage de la carte-K est que la simplification devient un acte de visionnement, pas une recherche de loi.
Pièges qui font perdre des points
- De Morgan est négatif l'ensemble, échangez l'opérateur, négatif chaque partie. Ne changer que l'opérateur constitue la réponse classique à moitié correcte.
- Les lignes de la carte-K doivent être dans l'ordre du code Gray,
00, 01, 11, 10. Dans l'ordre de comptage binaire, l'adjacence est incorrecte et le groupement échoue. - Les tailles de groupe sont des puissances de deux et peuvent tourner autour des bords. Un groupe de trois n'est pas un groupe valide.
- Dites pourquoi on simplifie : moins de portes, donc moins cher, plus rapide, faible consommation.
Vous avez compris
- L'algèbre booléenne réécrit une expression en moins de termes, donc le circuit a besoin de moins de portes
- De Morgan : $\overline{A + B} = \overline{A} \cdot \overline{B}$ et $\overline{A \cdot B} = \overline{A} + \overline{B}$ ; absorption : $A + AB = A$ ; $A\cdot B + A\cdot\overline{B} = A$
- une carte de Karnaugh regroupe des 1s adjacents de la table de vérité, avec lignes et colonnes dans l'ordre du code Gray afin que les voisins diffèrent d'une variable
- une variable qui change au sein d'un groupe disparaît, donc les grands groupes donnent des termes plus simples : couvrez tous les 1s avec le moins de groupes, les plus grands, possible