Boolean algebra and Karnaugh maps
Introduit| English | Sens |
|---|---|
| Boolean algebra/ˈbuːlɪən ˈældʒɪbrə/ | algèbre de Boole |
| 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 de 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$.
Match each Boolean law to what it says.
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
These laws let you simplify Boolean expressions algebraically before building the circuit.
By the absorption law, A + A·B simplifies to ____.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
If A is true the whole expression is true whatever B is, and if A is false both terms are false. B cannot affect the result.
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é
Boolean algebra
A·B, A+B, Ā …
Boolean algebra is just these gates written as expressions — compare the truth tables.
By De Morgan's law, $\overline{A \cdot B}$ equals:
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Negate the whole, swap AND→OR, negate each operand: $\overline{A \cdot B} = \overline{A} + \overline{B}$.
Applying De Morgan's law to an expression involves which steps? Select tout that apply.
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
Negate the whole, swap the operator, negate each part. Order is irrelevant, since AND and OR are commutative.
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.
Simplify $A\cdot B + A\cdot\overline{B}$.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Factor out A: $A(B + \overline{B}) = A \cdot 1 = A$.
A·B + A·NOT B needs two ANDs, one NOT and one OR. How many gates does its simplified form need?
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
It simplifies to just A, so the output is the input and no gate is needed at all. Four gates saved.
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
A Karnaugh map simplifies a Boolean expression by:
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
You group adjacent 1s (in Gray-code order) into power-of-two rectangles; each group becomes a simplified term.
Why are the rows and columns of a Karnaugh map labelled 00, 01, 11, 10 rather than 00, 01, 10, 11?
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Gray code order makes algebraic adjacency into physical adjacency. In counting order the grouping rule would simply not work.
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.
In a Karnaugh map, a larger group of adjacent 1s eliminates more variables, giving a simpler term (a group of 2 drops one variable, a group of 4 drops two).
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
You group adjacent 1s into power-of-two rectangles in Gray-code order; the bigger the group, the simpler the term it becomes.
Put the steps of simplifying with a Karnaugh map in order.
Difficulté 3/5 · 200 pièces + un petit bonus lors de la première réussite aujourd'hui
Gray code, ones, biggest groups, drop what changes, OR the terms. Use as few and as large groups as will cover every 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