Boolean algebra and Karnaugh maps · Álgebra booleana e mapas de Karnaugh
| English | Português |
|---|---|
| Boolean algebra/ˈbuːlɪən ˈældʒɪbrə/ | Álgebra booleana |
| De Morgan's laws/də ˈmɔːɡənz lɔːz/ | leis de De Morgan |
| Karnaugh map/ˈkɑːnɔː mæp/ | mapa de Karnaugh |
| truth table/truːθ ˈteɪbl/ | tabela-verdade |
| absorption/əbˈsɔːpʃn/ | absorção |
| 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.
A tese de mestrado que construiu a era digital
- Em 1937, um estudante de 21 anos chamado Claude Shannon notou que os relevadores telefônicos que estava estudando faziam a mesma coisa que uma álgebra que George Boole havia inventado oitenta anos antes para raciocinar sobre verdadeiro e falso.
- Se um interruptor é uma variável booleana, então um circuito é uma expressão, e simplificar a expressão remove portas do circuito. Menos portas significa mais barato, mais rápido e menor consumo de energia.
- Sua tese tem sido chamada de a mais importante do século. Tudo nesta página é essa única ideia usada como ferramenta.
- Esta aula é álgebra booleana 布尔代数, leis de De Morgan e o mapa de Karnaugh 卡诺图 que faz o mesmo trabalho 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$.
A notação e as leis
+significa OR,·significa AND e frequentemente é omitido, e uma barra superior significa NOT. Uma tabela-verdade 真值表 descreve a mesma coisa exaustivamente.- Identidade: $A + 0 = A$ e $A \cdot 1 = A$. Nula: $A + 1 = 1$ e $A \cdot 0 = 0$.
- Idempotente: $A + A = A$. Inversa: $A + \overline{A} = 1$ e $A \cdot \overline{A} = 0$.
- Absorção 吸收律: $A + A\cdot B = A$, porque se $A$ for verdadeiro toda a expressão será verdadeira independentemente de $B$.
Match each Boolean law to what it says. · Associe cada lei booleana ao que ela afirma.
These laws let you simplify Boolean expressions algebraically before building the circuit. · Essas leis permitem simplificar expressões booleanas algebricamente antes de construir o circuito.
By the absorption law, A + A·B simplifies to ____. · Pela lei da absorção, A + A·B simplifica para ____.
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. · Se A for verdadeiro, toda a expressão será verdadeira independentemente de B, e se A for falso, ambos os termos são falsos. B não pode afetar o 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
Leis de De Morgan
- Leis de De Morgan 德摩根定律 são as duas que o exame pede para usar pelo nome:
- A receita em palavras: negue todo, troque AND por OR, negue cada operando.
- Elas importam na prática porque permitem reescrever qualquer expressão usando apenas portas NAND ou apenas portas NOR, e um chip construído a partir de uma porta repetida é mais barato de fabricar.
*Duas expressões, uma tabela-verdade
Boolean algebra · Álgebra booleana
A·B, A+B, Ā …
Boolean algebra is just these gates written as expressions — compare the truth tables. · A álgebra booleana são apenas essas portas escritas como expressões — compare as tabelas-verdade.
By De Morgan's law, $\overline{A \cdot B}$ equals: · Pela lei de De Morgan, $\overline{A \cdot B}$ é igual a:
Negate the whole, swap AND→OR, negate each operand: $\overline{A \cdot B} = \overline{A} + \overline{B}$. · Negue o todo, troque AND→OR, negue 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 a lei de De Morgan a uma expressão envolve quais etapas? Selecione todas as opções aplicáveis.
Negate the whole, swap the operator, negate each part. Order is irrelevant, since AND and OR are commutative. · Negue o todo, troque o operador, negue cada parte. A ordem é irrelevante, pois AND e OR são comutativos.
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.
Exemplo resolvido: simplifique e conte as portas
- Simplifique $Z = A\cdot B + A\cdot\overline{B}$ e diga o que economiza.
- Fatore $A$: $Z = A\cdot(B + \overline{B})$. Pela lei inversa $B + \overline{B} = 1$, então $Z = A \cdot 1 = A$.
- A original precisa de duas portas AND, uma NOT e uma OR: quatro portas. A expressão simplificada precisa de nenhuma, apenas a entrada $A$.
- Sempre termine com o que a simplificação propicia: menos portas, resultando em um circuito mais barato, mais rápido que consome menos energia.
Simplify $A\cdot B + A\cdot\overline{B}$. · Simplifique $A\cdot B + A\cdot\overline{B}$.
Factor out A: $A(B + \overline{B}) = A \cdot 1 = A$. · Fatore 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 precisa de duas ANDs, uma NOT e uma OR. Quantas portas sua forma simplificada precisa?
It simplifies to just A, so the output is the input and no gate is needed at all. Four gates saved. · Ela simplifica para apenas A, então a saída é a entrada e nenhuma porta é necessária. Quatro portas economizadas.
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
O mapa de Karnaugh
- Um mapa de Karnaugh simplifica uma expressão agrupando 1s adjacentes retirados da tabela-verdade.
- Linhas e colunas são rotuladas em ordem de código Gray 格雷码,
00, 01, 11, 10, para que células adjacentes difiram em exatamente uma variável. Essa é toda a trapaça: torna a álgebra visível como adjacência. - Coloque um 1 em cada célula onde a saída é 1, depois encontre grupos retangulares de 1s cujos lados sejam potências de dois: 1, 2, 4, 8. Grupos podem envolver as bordas.
*Quanto maior o retângulo, mais simples é o termo
A Karnaugh map simplifies a Boolean expression by: · Um mapa de Karnaugh simplifica uma expressão booleana:
You group adjacent 1s (in Gray-code order) into power-of-two rectangles; each group becomes a simplified term. · Você agrupa 1s adjacentes (em ordem Gray) em retângulos de potência de dois; cada grupo se torna um termo simplificado.
Why are the rows and columns of a Karnaugh map labelled 00, 01, 11, 10 rather than 00, 01, 10, 11? · Por que as linhas e colunas de um mapa de Karnaugh são rotuladas 00, 01, 11, 10 em vez de 00, 01, 10, 11?
Gray code order makes algebraic adjacency into physical adjacency. In counting order the grouping rule would simply not work. · A ordem do código Gray transforma adjacência algébrica em adjacência física. Na ordem de contagem, a regra de agrupamento simplesmente não funcionaria.
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.
Lendo um grupo
- Dentro de um grupo, uma variável que permanece igual sobrevive no termo; uma variável que muda desaparece.
- Então um grupo de 2 elimina uma variável, um grupo de 4 elimina duas, e um grupo de 8 elimina três. Quanto maior o grupo, mais simples é o termo.
- Cubra todos os 1s usando o menor número possível de grupos maiores, então some os termos dos grupos. Os grupos podem se sobrepor, e a sobreposição frequentemente permite um grupo maior.
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). · Em um mapa de Karnaugh, um grupo maior de 1s adjacentes elimina mais variáveis, resultando em um termo mais simples (um grupo de 2 remove uma variável, um grupo de 4 remove duas).
You group adjacent 1s into power-of-two rectangles in Gray-code order; the bigger the group, the simpler the term it becomes. · Você agrupa 1s adjacentes em retângulos de potência de dois na ordem do código Gray; quanto maior o grupo, mais simples se torna o termo.
Put the steps of simplifying with a Karnaugh map in order. · Coloque as etapas de simplificação com um mapa de Karnaugh na ordem correta.
Gray code, ones, biggest groups, drop what changes, OR the terms. Use as few and as large groups as will cover every 1. · Código Gray, uns, maiores grupos, elimine o que muda, OR os termos. Use quantos e grandes grupos forem necessários para cobrir todos os 1s.
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.
Exemplo resolvido: leia um mapa de duas variáveis
- Um mapa de Karnaugh para $A$ e $B$ tem 1s nas células $\overline{A}B$ e $AB$. Simplifique.
- Os dois 1s são adjacentes: compartilham a coluna $B = 1$, então formam um grupo retangular de 2.
- Dentro desse grupo $B$ permanece 1 durante todo o tempo, enquanto $A$ muda de 0 para 1. A variável que muda desaparece.
- Então toda a expressão é simplesmente $Z = B$. Compare isso com a soma de produtos não simplificada, $\overline{A}B + AB$, que precisa de uma NOT, duas ANDs e uma 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.
Qual método usar
- Álgebra booleana é exata e funciona para qualquer número de variáveis, mas você deve identificar qual lei se aplica.
- Um mapa de Karnaugh é mecânico e difícil de errar para duas a quatro variáveis, que é o que o exame propõe, e mostra diretamente o maior agrupamento possível.
- Ambas dão a mesma resposta. O benefício do K-map é que a simplificação se torna olhar, não procurar uma lei.
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.
Marcas que escapam
- De Morgan é negue todo, troque o operador, negue cada parte. Mudar apenas o operador é a meia-resposta clássica.
- As linhas do K-map devem estar em ordem de código Gray 格雷码,
00, 01, 11, 10. Em ordem de contagem binária a adjacência está errada e o agrupamento falha. - Os tamanhos dos grupos são potências de dois e podem envolver as bordas. Um grupo de três não é um grupo válido.
- Diga para que serve a simplificação: menos portas, resultando em algo mais barato, mais rápido e com menor consumo de energia.
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
Entendeu?
- A álgebra booleana reescreve uma expressão em menos termos, então o circuito precisa de menos portas
- De Morgan: $\overline{A + B} = \overline{A} \cdot \overline{B}$ e $\overline{A \cdot B} = \overline{A} + \overline{B}$; absorção: $A + AB = A$; $A\cdot B + A\cdot\overline{B} = A$
- um mapa de Karnaugh agrupa 1s adjacentes da tabela-verdade, com linhas e colunas em ordem de código Gray 格雷码 para que vizinhos difiram em uma variável
- uma variável que muda dentro de um grupo desaparece, então grupos maiores proporcionam termos mais simples: cubra todos os 1s com o menor número possível de grupos maiores