Boolean algebra and Karnaugh maps
Introduzido| English | Significado |
|---|---|
| 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 |
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.
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.
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
These laws let you simplify Boolean expressions algebraically before building the circuit.
By the absorption law, A + A·B simplifies to ____.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
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.
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
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:
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
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 todos that apply.
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
Negate the whole, swap the operator, negate each part. Order is irrelevant, since AND and OR are commutative.
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}$.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
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?
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
It simplifies to just A, so the output is the input and no gate is needed at all. Four gates saved.
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:
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
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?
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Gray code order makes algebraic adjacency into physical adjacency. In counting order the grouping rule would simply not work.
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).
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
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.
Dificuldade 3/5 · Moedas 200 + pequeno bônus na primeira conclusão hoje
Gray code, ones, biggest groups, drop what changes, OR the terms. Use as few and as large groups as will cover every 1.
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.
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.
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.
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