Boolean algebra and Karnaugh maps · Álgebra de Boole y mapas de Karnaugh
| English | Español |
|---|---|
| Boolean algebra/ˈbuːlɪən ˈældʒɪbrə/ | Álgebra de Boole |
| De Morgan's laws/də ˈmɔːɡənz lɔːz/ | leyes de De Morgan |
| Karnaugh map/ˈkɑːnɔː mæp/ | mapa de Karnaugh |
| truth table/truːθ ˈteɪbl/ | tabla de verdad |
| absorption/əbˈsɔːpʃn/ | absorción |
| Gray code/ɡreɪ kəʊd/ | código 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 tesis del máster que construyó la era digital
- En 1937, un estudiante de 21 años llamado Claude Shannon observó que los relés telefónicos que estaba estudiando hacían lo mismo que el álgebra que George Boole había inventado ochenta años antes para razonar sobre lo verdadero y lo falso.
- Si un interruptor es una variable booleana, entonces un circuito es una expresión, y simplificar la expresión elimina puertas lógicas del circuito. Menos puertas significa menor costo, mayor velocidad y menor consumo de energía.
- Su tesis ha sido llamada la más importante del siglo. Todo en esta página es esa única idea utilizada como herramienta.
- Esta lección trata sobre álgebra booleana 布尔代数, las leyes de De Morgan y el mapa de Karnaugh 卡诺图 que realiza la misma función visualmente.
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$.
Notación y leyes
+significa OR (O),·significa AND (Y) y a menudo se omite, y una barra superior significa NOT (NO). Una tabla de verdad 真值表 describe exhaustivamente lo mismo.- Identidad: $A + 0 = A$ y $A \cdot 1 = A$. Nulo: $A + 1 = 1$ y $A \cdot 0 = 0$.
- Idempotente: $A + A = A$. Inverso: $A + \overline{A} = 1$ y $A \cdot \overline{A} = 0$.
- Absorción 吸收律: $A + A\cdot B = A$, porque si $A$ es verdadero, toda la expresión es verdadera sin importar $B$.
Match each Boolean law to what it says. · Asocia cada ley de Boole con lo que dice.
These laws let you simplify Boolean expressions algebraically before building the circuit. · Estas leyes permiten simplificar expresiones de Boole algebraicamente antes de construir el circuito.
By the absorption law, A + A·B simplifies to ____. · Por la ley de absorción, A + A·B se simplifica a ____.
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 es verdadero, toda la expresión es verdadera sin importar B; si A es falso, ambos términos son falsos. B no puede afectar el resultado.
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
Leyes de De Morgan
- Las leyes de De Morgan 德摩根定律 son las dos que el examen pide usar por nombre:
- La receta en palabras: negar todo, intercambiar AND y OR, negar cada operando.
- Son importantes en la práctica porque permiten reescribir cualquier expresión usando solo puertas NAND o solo puertas NOR, y un chip construido con una sola puerta repetida es más barato de fabricar.
Dos expresiones, una tabla de verdad
Boolean algebra · Álgebra de Boole
A·B, A+B, Ā …
Boolean algebra is just these gates written as expressions — compare the truth tables. · El álgebra de Boole son simplemente estas compuertas escritas como expresiones — compara las tablas de verdad.
By De Morgan's law, $\overline{A \cdot B}$ equals: · Por la ley de De Morgan, $\overline{A \cdot B}$ es igual a:
Negate the whole, swap AND→OR, negate each operand: $\overline{A \cdot B} = \overline{A} + \overline{B}$. · Negar todo, cambiar AND→OR, negar cada operando: $\overline{A \cdot B} = \overline{A} + \overline{B}$.
Applying De Morgan's law to an expression involves which steps? Select all · todos that apply. · Aplicar la ley de De Morgan a una expresión implica cuáles pasos? Selecciona todos los que correspondan.
Negate the whole, swap the operator, negate each part. Order is irrelevant, since AND and OR are commutative. · Negar todo, cambiar el operador, negar cada parte. El orden es irrelevante, ya que AND y OR son conmutativos.
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.
Ejemplo resuelto: simplificar y contar las puertas
- Simplifica $Z = A\cdot B + A\cdot\overline{B}$ y di qué ahorra.
- Factoriza $A$: $Z = A\cdot(B + \overline{B})$. Por la ley inversa $B + \overline{B} = 1$, así que $Z = A \cdot 1 = A$.
- El original necesita dos puertas AND, una NOT y una OR: cuatro puertas. La expresión simplificada no necesita ninguna, solo la entrada $A$.
- Siempre termina explicando qué ofrece la simplificación: menos puertas, por lo tanto un circuito más barato, rápido y con menor consumo de energía.
Simplify $A\cdot B + A\cdot\overline{B}$. · Simplifica $A\cdot B + A\cdot\overline{B}$.
Factor out A: $A(B + \overline{B}) = A \cdot 1 = A$. · Factorizar 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·NOT B necesita dos ANDs, un NOT y un OR. ¿Cuántas compuertas necesita su forma simplificada?
It simplifies to just A, so the output is the input and no gate is needed at all. Four gates saved. · Se simplifica a solo A, así que la salida es la entrada y no se necesita ninguna compuerta en absoluto. Cuatro compuertas ahorradas.
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
Mapa de Karnaugh
- Un mapa de Karnaugh simplifica una expresión agrupando unos adyacentes tomados de la tabla de verdad.
- Las filas y columnas están etiquetadas en orden de código Gray 格雷码,
00, 01, 11, 10, para que las celdas adyacentes difieran en exactamente una variable. Ese es todo el truco: hace que el álgebra sea visible mediante la adyacencia. - Coloca un 1 en cada celda donde la salida sea 1, luego busca grupos rectangulares de unos cuyos lados sean potencias de dos: 1, 2, 4, 8. Los grupos pueden envolverse alrededor de los bordes.
Cuanto más grande es el rectángulo, más simple es el término
A Karnaugh map simplifies a Boolean expression by: · Un mapa de Karnaugh simplifica una expresión de Boole mediante:
You group adjacent 1s (in Gray-code order) into power-of-two rectangles; each group becomes a simplified term. · Agrupas unos adyacentes (en orden de Gray) en rectángulos de potencias de dos; cada grupo se convierte en un término simplificado.
Why are the rows and columns of a Karnaugh map labelled 00, 01, 11, 10 rather than 00, 01, 10, 11? · ¿Por qué las filas y columnas de un mapa de Karnaugh están etiquetadas 00, 01, 11, 10 en lugar de 00, 01, 10, 11?
Gray code order makes algebraic adjacency into physical adjacency. In counting order the grouping rule would simply not work. · El orden de Gray convierte la adyacencia algebraica en adyacencia física. En orden de conteo, la regla de agrupación simplemente no funcionaría.
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.
Leer un grupo
- Dentro de un grupo, una variable que permanece igual sobrevive en el término; una variable que cambia desaparece.
- Así, un grupo de 2 elimina una variable, un grupo de 4 elimina dos, y un grupo de 8 elimina tres. Cuanto mayor es el grupo, más simple es el término.
- Cubre todos los 1s usando el menor número de grupos posibles y los más grandes, luego suma (OR) los términos de los grupos juntos. Los grupos pueden superponerse, y la superposición suele ser lo que permite uno más grande.
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). · En un mapa de Karnaugh, un grupo más grande de unos adyacentes elimina más variables, dando un término más simple (un grupo de 2 elimina una variable, un grupo de 4 elimina dos).
You group adjacent 1s into power-of-two rectangles in Gray-code order; the bigger the group, the simpler the term it becomes. · Agrupas unos adyacentes en rectángulos de potencias de dos en orden de Gray; cuanto mayor es el grupo, más simple se vuelve el término.
Put the steps of simplifying with a Karnaugh map in order. · Coloca los pasos para simplificar con un mapa de Karnaugh en orden.
Gray code, ones, biggest groups, drop what changes, OR the terms. Use as few and as large groups as will cover every 1. · Gray code, unos, grupos más grandes, eliminar lo que cambia, ORar los términos. Usa tantos y tan grandes grupos como sean necesarios para cubrir cada 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.
Ejemplo resuelto: leer un mapa de dos variables
- Un mapa de Karnaugh para $A$ y $B$ tiene 1s en las celdas $\overline{A}B$ y $AB$. Simplifica.
- Los dos 1s son adyacentes: comparten la columna $B = 1$, así que se agrupan como un rectángulo de 2.
- Dentro de ese grupo, $B$ permanece en 1 durante todo el tiempo, mientras que $A$ cambia de 0 a 1. La variable que cambia desaparece.
- Así que toda la expresión es simplemente $Z = B$. Compara esto con la suma de productos sin simplificar, $\overline{A}B + AB$, que necesita una NOT, dos AND y una OR.
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.
Qué método usar
- El álgebra booleana es exacta y funciona para cualquier número de variables, pero debes identificar qué ley aplica.
- Un mapa de Karnaugh es mecánico y difícil de equivocar para dos a cuatro variables, que es lo que establece el examen, y te muestra directamente el agrupamiento más grande.
- Ambos dan la misma respuesta. La ventaja del mapa K es que la simplificación se convierte en mirar, no en buscar una ley.
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.
Puntos que se escapan
- De Morgan es negar todo, cambiar el operador, negar cada parte. Cambiar solo el operador es la clásica respuesta incompleta.
- Las filas del mapa K deben estar en orden de código Gray,
00, 01, 11, 10. En orden de conteo binario la adyacencia es incorrecta y falla el agrupamiento. - Los tamaños de grupo son potencias de dos y pueden envolverse alrededor de los bordes. Un grupo de tres no es un grupo válido.
- Di para qué sirve simplificar: menos puertas, por lo tanto más barato, más rápido y menor consumo de energía.
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
Ya lo tienes
- El álgebra booleana reescribe una expresión en menos términos, por lo que el circuito necesita menos puertas.
- De Morgan: $\overline{A + B} = \overline{A} \cdot \overline{B}$ y $\overline{A \cdot B} = \overline{A} + \overline{B}$; absorción: $A + AB = A$; $A\cdot B + A\cdot\overline{B} = A$.
- Un mapa de Karnaugh agrupa unos adyacentes de la tabla de verdad, con filas y columnas en orden de código Gray para que los vecinos difieran en una variable.
- Una variable que cambia dentro de un grupo desaparece, por lo tanto grupos más grandes dan términos más simples: cubre cada 1 con el menor número de grupos posibles y los más grandes.