Boolean algebra and Karnaugh maps · 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 |
The master's thesis that built the digital age
- In 1937 a 21-year-old student named Claude Shannon noticed that the telephone relays he was studying were doing the same thing as an algebra George Boole had invented eighty years earlier for reasoning about true and false.
- If a switch is a Boolean variable, then a circuit is an expression, and simplifying the expression removes gates from the circuit. Fewer gates is cheaper, faster and less power.
- His thesis has been called the most important of the century. Everything on this page is that one idea used as a tool.
- This lesson is Boolean algebra 布尔代数, De Morgan's laws, and the Karnaugh map 卡诺图 that does the same job by eye.
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.
The notation and the laws
+means OR,·means AND and is often left out, and an overbar means NOT. A truth table 真值表 describes the same thing exhaustively.- Identity: $A + 0 = A$ and $A \cdot 1 = A$. Null: $A + 1 = 1$ and $A \cdot 0 = 0$.
- Idempotent: $A + A = A$. Inverse: $A + \overline{A} = 1$ and $A \cdot \overline{A} = 0$.
- Absorption 吸收律: $A + A\cdot B = A$, because if $A$ is true the whole expression is true regardless of $B$.
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. · Reliez chaque loi booléenne à ce qu'elle signifie.
These laws let you simplify Boolean expressions algebraically before building the circuit. · Ces lois permettent de simplifier algébriquement les expressions booléennes avant de construire le circuit.
By the absorption law, A + A·B simplifies to ____. · Par la loi d'absorption, A + A·B se simplifie en ____.
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. · 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.
De Morgan's laws
- De Morgan's laws 德摩根定律 are the two the exam asks you to use by name:
- The recipe in words: negate the whole, swap AND and OR, negate each operand.
- They matter practically because they let any expression be rewritten using only NAND gates or only NOR gates, and a chip built from one repeated gate is cheaper to manufacture.
Two expressions, one truth table
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 · Algèbre booléenne
A·B, A+B, Ā …
Boolean algebra is just these gates written as expressions — compare the truth tables. · L'algèbre booléenne n'est que ces portes écrites sous forme d'expressions — comparez les tables de vérité.
By De Morgan's law, $\overline{A \cdot B}$ equals: · Par la loi de De Morgan, $\overline{A \cdot B}$ vaut :
Negate the whole, swap AND→OR, negate each operand: $\overline{A \cdot B} = \overline{A} + \overline{B}$. · Négation globale, inversion AND→OR, négation de chaque opérande : $\overline{A \cdot B} = \overline{A} + \overline{B}$.
Applying De Morgan's law to an expression involves which steps? Select all · tout that apply. · L'application de la loi de De Morgan à une expression implique quelles étapes ? Sélectionnez tous ceux qui s'appliquent.
Negate the whole, swap the operator, negate each part. Order is irrelevant, since AND and OR are commutative. · Négation globale, inversion de l'opérateur, négation de chaque partie. L'ordre est indifférent, car AND et OR sont commutatifs.
Worked example: simplify, and count the gates
- Simplify $Z = A\cdot B + A\cdot\overline{B}$ and say what it saves.
- Factor out $A$: $Z = A\cdot(B + \overline{B})$. By the inverse law $B + \overline{B} = 1$, so $Z = A \cdot 1 = A$.
- The original needs two AND gates, a NOT and an OR: four gates. The simplified expression needs none, just the input $A$.
- Always finish with what the simplification buys: fewer gates, so a cheaper, faster circuit that uses less power.
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}$. · Simplifier $A\cdot B + A\cdot\overline{B}$.
Factor out A: $A(B + \overline{B}) = A \cdot 1 = A$. · Factoriser 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? · 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 ?
It simplifies to just A, so the output is the input and no gate is needed at all. Four gates saved. · Elle se simplifie en A uniquement, donc la sortie est l'entrée et aucune porte n'est nécessaire. Quatre portes économisées.
The Karnaugh map
- A Karnaugh map simplifies an expression by grouping adjacent 1s taken from the truth table.
- Rows and columns are labelled in Gray code 格雷码 order,
00, 01, 11, 10, so that adjacent cells differ in exactly one variable. That is the whole trick: it makes the algebra visible as adjacency. - Place a 1 in each cell where the output is 1, then find rectangular groups of 1s whose sides are powers of two: 1, 2, 4, 8. Groups may wrap around the edges.
The bigger the rectangle, the simpler the term
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: · Une carte de Karnaugh simplifie une expression booléenne en :
You group adjacent 1s (in Gray-code order) into power-of-two rectangles; each group becomes a simplified term. · Vous regroupez les 1 adjacents (dans l'ordre Gray) en rectangles de puissances de deux ; chaque groupe devient un terme simplifié.
Why are the rows and columns of a Karnaugh map labelled 00, 01, 11, 10 rather than 00, 01, 10, 11? · 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 ?
Gray code order makes algebraic adjacency into physical adjacency. In counting order the grouping rule would simply not work. · 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.
Reading a group
- Inside a group, a variable that stays the same survives in the term; a variable that changes disappears.
- So a group of 2 drops one variable, a group of 4 drops two, and a group of 8 drops three. The larger the group, the simpler the term.
- Cover every 1 using as few and as large groups as possible, then OR the group terms together. Groups may overlap, and overlapping is often what allows a larger one.
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). · 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).
You group adjacent 1s into power-of-two rectangles in Gray-code order; the bigger the group, the simpler the term it becomes. · 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.
Put the steps of simplifying with a Karnaugh map in order. · Placez les étapes de simplification avec une carte de Karnaugh dans l'ordre.
Gray code, ones, biggest groups, drop what changes, OR the terms. Use as few and as large groups as will cover every 1. · 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.
Worked example: read a two-variable map
- A Karnaugh map for $A$ and $B$ has 1s in the cells $\overline{A}B$ and $AB$. Simplify.
- The two 1s are adjacent: they share the $B = 1$ column, so they group as a rectangle of 2.
- Inside that group $B$ stays 1 throughout, while $A$ changes from 0 to 1. The variable that changes disappears.
- So the whole expression is simply $Z = B$. Compare that with the unsimplified sum of products, $\overline{A}B + AB$, which needs a NOT, two ANDs and an OR.
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.
Which method to use
- Boolean algebra is exact and works for any number of variables, but you must spot which law applies.
- A Karnaugh map is mechanical and hard to get wrong for two to four variables, which is what the exam sets, and it shows you the largest grouping directly.
- Both give the same answer. The benefit of the K-map is that simplification becomes looking, not searching for a law.
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.
Marks that slip away
- De Morgan is negate the whole, swap the operator, negate each part. Changing only the operator is the classic half-answer.
- K-map rows must be in Gray code order,
00, 01, 11, 10. In binary counting order the adjacency is wrong and the grouping fails. - Group sizes are powers of two and may wrap the edges. A group of three is not a group.
- Say what simplifying is for: fewer gates, so cheaper, faster, lower power.
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.
You've got it
- Boolean algebra rewrites an expression into fewer terms, so the circuit needs fewer gates
- De Morgan: $\overline{A + B} = \overline{A} \cdot \overline{B}$ and $\overline{A \cdot B} = \overline{A} + \overline{B}$; absorption: $A + AB = A$; $A\cdot B + A\cdot\overline{B} = A$
- a Karnaugh map groups adjacent 1s from the truth table, with rows and columns in Gray code order so neighbours differ in one variable
- a variable that changes within a group disappears, so bigger groups give simpler terms: cover every 1 with as few, as large, groups as possible
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