Introdução11.1
Hoje você vai ver como simplificar uma função booleana olhando a estrutura do problema no Mapa de Karnaugh. A ideia é a mesma da aula anterior, ou seja, reduzir sem alterar a tabela-verdade. A diferença é que, agora, a vizinhança entre células aparece de forma explícita e os agrupamentos ficam visíveis.
Se na aula de minimização algébrica você aprendeu a apagar o que sobra pela álgebra, aqui você vai aprender a enxergar esse excesso no espaço visual do mapa. Isso é útil porque muitas expressões parecem confusas no papel, mas ficam evidentes quando reorganizadas em células adjacentes.
O Mapa de Karnaugh reorganiza a tabela-verdade em uma grade com ordem Gray para que células que diferem por uma única variável fiquem lado a lado. Assim, você pode agrupar casos equivalentes e eliminar variáveis que mudam dentro do grupo.
Da tabela-verdade ao mapa11.2
Antes de falar em agrupamento, vale reforçar um ponto muito importante. O mapa não é uma técnica mágica separada da tabela-verdade. Ele é a própria tabela-verdade reorganizada de um jeito mais inteligente para revelar vizinhanças.
Para 3 variáveis, uma disposição muito comum é usar $A$ nas linhas e $BC$ nas colunas. As colunas ficam na ordem $00, 01, 11, 10$. Já para 4 variáveis, fazemos o mesmo com duas variáveis nas linhas e duas nas colunas.
Um mapa está completo quando contém todas as combinações possíveis da tabela-verdade. Para 3 variáveis, são 8 células. Para 4 variáveis, são 16 células.
Vamos começar com uma função simples para ver o caminho completo. Considere a tabela abaixo:
$$ \begin{array}{c|c|c||c} A & B & C & F \\ \hline 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{array} $$
Agora observe o que a tabela nos diz em duas leituras diferentes.
- Na SOP, destacamos as linhas em que $F=1$.
- Na POS, destacamos as linhas em que $F=0$.
Da tabela acima, obtemos:
$$ F = \Sigma m(1,2,5,6) $$
$$ \begin{aligned} F &= \bar{A}\bar{B}C + \bar{A}B\bar{C} + A\bar{B}C + AB\bar{C} \end{aligned} $$
$$ F = \Pi M(0,3,4,7) $$
$$ \begin{aligned} F = &(A + B + C)(A + B + \bar{C}) \\ &(A + \bar{B} + C)(A + \bar{B} + \bar{C}) \end{aligned} $$
Essas duas escritas representam exatamente a mesma função. Elas só enfatizam aspectos diferentes da tabela.
O mapa faz exatamente isso, reorganiza a tabela para aproximar combinações que diferem por uma única variável. Quando isso acontece, você consegue reunir vários termos em um grupo só e eliminar as variáveis que mudam dentro dele.
Como ler o mapa11.3
O mapa de Karnaugh usa ordem Gray, isto é, uma ordem em que apenas um bit muda de um termo para o seguinte. Isso evita o problema da ordem binária comum, em que linhas vizinhas na tabela podem estar longe no desenho.
Se você tiver um número em binário e quiser obter seu código de Gray, use a regra prática $G = B \oplus (B \gg 1)$, em que $\gg 1$ significa deslocar os bits uma posição para a direita.
Por exemplo, se $B = 101$, então $B \gg 1 = 010$ e $G = 101 \oplus 010 = 111$. Essa conversão é útil porque valores consecutivos em Gray diferem por apenas um bit.
Para 3 variáveis, uma disposição muito comum é usar $A$ nas linhas e $BC$ nas colunas. As colunas ficam na ordem $00, 01, 11, 10$. Iremos adotar um padrão nas construções para mantermos uma consistência entre nossas soluções. Quando o número de variáveis é ímpar, a linha costuma receber a menor quantidade de variáveis, e as colunas recebem o restante. Quando o número de variáveis é par, a distribuição fica equilibrada, com a mesma quantidade de variáveis em linhas e colunas. Veja um exempo de maa de Karnaugh abaixo:
O mapa vazio acima mostra apenas a estrutura. O ponto mais importante agora é entender como localizar uma combinação específica. Por exemplo, a célula $ABC = 0 1 1$ fica na linha de $A=0$ e na coluna $BC=11$. Já a célula $101$ fica na linha de $A=1$ e na coluna $BC=01$.
Repare que células vizinhas no mapa diferem por apenas uma variável. Em álgebra booleana, isso significa que dois mintermos podem ser escritos com um fator comum e uma variável complementar dentro de um parêntese, como em $ABC + AB\bar{C} = AB(C + \bar{C}) = AB$. É esse cancelamento da variável que muda que torna a simplificação possível.
Não existe agrupamento diagonal. Dois pontos na diagonal mudam duas variáveis ao mesmo tempo, então eles não são vizinhos lógicos.
Regras de agrupamento11.4
Antes de resolver exemplos maiores, guarde estas regras.
- agrupe células apenas em potências de 2, como $1, 2, 4, 8, \dots$
- prefira o maior grupo possível
- lembre que o mapa “dá a volta”, então bordas opostas podem se tocar
- em SOP, leia os grupos de $1$s
- em POS, leia os grupos de $0$s
- descarte as variáveis que mudam dentro do grupo
- permita sobreposição quando ela ajudar a cobrir melhor a função
Para ler um grupo do mapa começa perguntando o que muda e o que não muda dentro do grupo. Em SOP, os grupos de $1$s viram produtos: a variável que fica em $1$ entra direta, a que fica em $0$ entra negada e a que muda desaparece. Em POS, os grupos de $0$s viram somas: a variável que fica em $0$ entra direta, a que fica em $1$ entra negada e a que muda desaparece.
Um bom grupo não é apenas um grupo grande. É um grupo que elimina variáveis sem deixar casos importantes descobertos.
SOP: lendo os 1s11.5
Vamos começar com a leitura em SOP, porque ela costuma ser a porta de entrada mais natural. Em SOP, você agrupa os casos em que a saída vale $1$. Cada grupo gera um produto. As variáveis que permanecem fixas entram no termo final, e as variáveis que mudam desaparecem.
Considere a função abaixo.
$$ F = \Sigma m(1,3,5,7) $$
Esse grupo contém quatro células. Vamos ler o que permanece fixo.
- $A$ muda entre as linhas, então sai.
- $B$ muda entre as colunas, então sai.
- $C$ permanece em $1$ em todo o grupo, então fica.
Logo, a expressão reduzida é:
$$F = C$$
Forma canônica original
$$ F = \bar{A}\bar{B}C + \bar{A}BC + A\bar{B}C + ABC $$
Forma reduzida
O mapa mostra que quatro combinações diferentes, na verdade, carregavam a mesma informação essencial. O desenho só estava espalhando isso em linhas separadas.
Agora considere um mapa de 4 variáveis com $1$s nas quatro quinas.
$$ H = \Sigma m(0,2,8,10) $$
Esse é um caso clássico de borda. Visualmente, os cantos parecem separados, mas logicamente eles formam agrupamentos pelas quinas.
Na prática, essas quatro células pertencem a um único grupo de 4, porque as bordas opostas do mapa são adjacentes.
Para ler o termo final, observe as variáveis fixas:
- $B$ permanece em $0$
- $D$ permanece em $0$
- $A$ varia
- $C$ varia
Então o agrupamento gera o termo:
$$H = \bar{B}\bar{D}$$
Leitura algébrica
$$ H = \bar{B}\bar{D} $$
Leitura no circuito
Esse exemplo é importante porque corrige uma intuição muito comum no começo. O mapa não é uma grade plana sem continuidade. Ele tem conectividade nas bordas.
Considere a função abaixo.
$$ G = \Sigma m(0,1,2,3,4,5,6,7,8,9,10,11) $$
Agora observe o mapa correspondente.
Vamos considerar primeiro uma leitura sem sobreposição. Nesse caso, o mapa pode ser coberto com um grupo de 8 células e um grupo adicional de 4 células.
$$G_{sem} = \bar{B} + \bar{A}B$$
Essa cobertura é correta, mas ainda não é a mais econômica. Entretanto, podemos permitir agrupamentos sobrepostos. Com isso, o mesmo mapa admite dois grupos de 8 células:
O primeiro grupo gera:
$$G_1 = \bar{A}$$
O segundo grupo gera:
$$G_2 = \bar{B}$$
Juntando as duas coberturas, a expressão final fica menor:
$$G_{compartilhado} = \bar{A} + \bar{B}$$
Cobertura sem compartilhamento
Cobertura compartilhada
Esse exemplo mostra o ganho da sobreposição: a primeira leitura funciona, mas a segunda explora melhor o mapa e reduz a expressão final.
POS: lendo os 0s11.6
Na POS, o raciocínio é o mesmo, mas o alvo muda. Em vez de agrupar os $1$s, você agrupa os $0$s. Cada grupo gera uma soma.
Aqui está a regra que costuma causar confusão, então vale dizer devagar.
- Se uma variável fica em $0$ no grupo, ela aparece direta no termo soma.
- Se uma variável fica em $1$ no grupo, ela aparece negada no termo soma.
- Se uma variável muda, ela desaparece do termo.
Isso é o espelho da leitura em SOP.
Considere a função abaixo.
$$ F = \Pi M(1,3,5,7) $$
Agora veja o mapa, com os zeros centrais destacados.
Esse grupo reúne quatro células em que a variável $C$ permanece em $1$. Como estamos lendo POS, uma variável fixa em $1$ entra negada no termo soma.
Portanto, o termo reduzido é:
$$F = \bar{C}$$
Agora veja a forma canônica correspondente, escrita a partir das linhas em que $F=0$.
$$ F = \Pi M(1,3,5,7) $$
Se você quiser enxergar isso como circuito, a leitura reduzida fica muito mais curta do que a forma canônica original.
Forma canônica POS
$$ F = (A + B + \bar{C})\,(A + \bar{B} + \bar{C})\,(\bar{A} + B + \bar{C})\,(\bar{A} + \bar{B} + \bar{C}) $$
Forma reduzida
O ponto mais importante aqui é este. Em POS, você não lê “zeros virando zero”. Você lê os zeros como grupos que se transformam em somas com as variáveis apropriadas. A lógica muda na aparência, mas a mecânica continua sendo agrupar e eliminar o que varia.
Considere a função abaixo.
$$ J = \Pi M(0,1,4,5,6,7,10,11,13,14,15) $$
Agora pense no mapa de 4 variáveis abaixo, em que os zeros formam três blocos bem definidos.
Os zeros podem ser cobertos com três grupos. Cada grupo elimina uma parte diferente da tabela e ajuda a manter a POS compacta.
$$ J_1 = A + C $$
e
$$ J_2 = \bar{B} + \bar{D} $$
e
$$ J_3 = \bar{A} + \bar{C} $$
Juntando os três grupos, a expressão final é:
$$J = (A + C)(\bar{B} + \bar{D})(\bar{A} + \bar{C})$$
Forma canônica POS
$$ J = \Pi M(0,1,4,5,6,7,10,11,13,14,15) $$
Forma reduzida
Esse exemplo mostra que POS também pode se beneficiar de cobertura ampla. Mesmo quando a cobertura exige três grupos, a leitura final ainda fica bem menor do que a forma canônica.
Cobertura ótima e don't care11.7
Nem todo mapa é resolvido por uma única leitura óbvia. Em muitos casos, existem várias coberturas válidas, e o trabalho do projetista é escolher a que elimina mais variáveis, usa menos grupos ou produz uma expressão final mais simples.
O caso mais importante dessa discussão é o de don't care. Essas combinações representam entradas que não serão utilizadas na prática. Como a função nunca precisará responder corretamente nesses pontos, você pode tratá-los como $0$ ou $1$ conforme for mais útil para ampliar os agrupamentos.
Isso leva a três consequências importantes:
- um don't care pode participar de um grupo, mas não é obrigado a participar;
- um don't care não precisa ser coberto;
- um don't care só deve ser usado quando ele realmente reduz a expressão final.
Exemplo clássico: em BCD de 4 bits, só os valores de $0$ a $9$ são válidos. Logo, os estados de $10$ a $15$ podem ser tratados como irrelevantes no processo de minimização.
Vamos começar com um exemplo em SOP, isto é, agrupando os $1$s do mapa.
$$ Q = \Sigma m(8,9) + d(10,11,12,13,14,15) $$
Primeiro, observe o mapa completo, mas ignore os estados irrelevantes na hora de agrupar. Nesse cenário, os únicos $1$s obrigatórios são os mintermos $8$ e $9$, então só conseguimos formar um grupo de 2 células.
Nesse grupo, $A$ permanece em $1$, $B$ permanece em $0$, $C$ permanece em $0$ e apenas $D$ varia. Portanto, a leitura em SOP é:
$$Q_{sem} = A\bar{B}\bar{C}$$
Essa expressão está correta, mas ainda não aproveita a flexibilidade oferecida pelos estados irrelevantes. Para ver isso, permita que os don't cares participem do agrupamento. Como eles ocupam as posições vizinhas aos mintermos obrigatórios, o grupo pode crescer de 2 para 8 células.
Com esse grupo ampliado, apenas $A$ permanece fixo. As variáveis $B$, $C$ e $D$ passam a variar dentro do agrupamento e, por isso, desaparecem da expressão final. O resultado é:
$$Q = A$$
O ganho é claro. O grupo cresceu de 2 para 8 células, o número de literais caiu de 3 para 1 e o circuito final ficou muito mais simples. Esse é exatamente o papel do don't care, ele não altera a função útil, mas pode tornar a implementação significativamente menor.
O mesmo raciocínio vale em POS. A diferença é que, nesse caso, você usa os estados irrelevantes para ampliar grupos de $0$s, e não grupos de $1$s.
Neste desafio final, a função será lida em SOP. Isso significa que devemos agrupar os $1$s do mapa. Diferentemente dos exemplos anteriores, aqui a cobertura mínima não colapsa em um ou dois termos. A solução exige quatro grupos, e o objetivo é identificar com cuidado quais variáveis permanecem fixas em cada região.
Considere a função abaixo:
$$ T = \Sigma m(0,1,3,4,5,6,9,10,11,12,14,15) $$
Como a função está em forma $\Sigma m$, vamos ler cada grupo como um produto.
No primeiro grupo, $A=0$ e $C=0$ permanecem fixos, enquanto $B$ e $D$ variam. Portanto:
$$T_1 = \bar{A}\bar{C}$$
No segundo grupo, $B=0$ e $D=1$ permanecem fixos. As variáveis $A$ e $C$ variam, então o termo resultante é:
$$T_2 = \bar{B}D$$
No terceiro grupo, $A=1$ e $C=1$ permanecem fixos. Assim, obtemos:
$$T_3 = AC$$
No quarto grupo, $B=1$ e $D=0$ permanecem fixos, o que produz:
$$T_4 = B\bar{D}$$
Juntando os quatro termos, a expressão reduzida final fica:
$$T = \bar{A}\bar{C} + \bar{B}D + AC + B\bar{D}$$
Esse exemplo é um bom fechamento para a aula porque reúne várias ideias ao mesmo tempo: leitura em SOP, identificação de grupos essenciais, interpretação correta das variáveis fixas e montagem da expressão final a partir de várias regiões do mapa.
Circuito original
Circuito reduzido
O ponto principal aqui não é apenas obter a resposta final, mas perceber como a estrutura do mapa orienta a escolha dos grupos. Mesmo quando a função não se reduz a um termo muito curto, o mapa ainda organiza a simplificação de forma sistemática e segura.
Questões11.8
1. O que o Mapa de Karnaugh faz com a tabela-verdade e por que isso ajuda na minimização?
- A) Muda a função booleana para obter outro comportamento.
- B) Reorganiza os casos para tornar vizinhos os termos que diferem por uma única variável.
- C) Remove todas as variáveis da expressão final.
- D) Substitui a tabela-verdade por um circuito sem equivalência lógica.
2. Em uma leitura em SOP, qual conjunto de células deve ser agrupado primeiro e qual é a ideia por trás disso?
- A) As linhas em que a saída vale $0$.
- B) Os casos em que a saída vale $1$.
- C) Apenas os casos com três variáveis fixas.
- D) Apenas os cantos do mapa.
3. Em um grupo de SOP, se uma variável muda entre as células agrupadas, o que acontece com ela na expressão final?
- A) Ela é duplicada no termo final.
- B) Ela passa a valer sempre 1.
- C) Ela desaparece da expressão reduzida.
- D) Ela se transforma em constante.
4. Considere um grupo de zeros em POS no qual $A=0$, $B=1$ e $C$ varia. Qual é o termo resultante e por que os sinais entram assim?
- A) $\bar{A} + B$
- B) $A + \bar{B}$
- C) $A + B$
- D) $\bar{A} + \bar{B}$
5. Por que as quinas de um mapa de 4 variáveis podem pertencer ao mesmo grupo, mesmo parecendo distantes no desenho?
6. Simplifique visualmente a função abaixo usando SOP e diga quais células formam o grupo principal.
$$F = \Sigma m(0,1,2,3,8,9,10,11)$$
7. Simplifique visualmente a função abaixo usando POS e indique quais zeros estão sendo agrupados.
$$F = \Pi M(1,3,5,7)$$
8. Explique com suas palavras a diferença entre a leitura de SOP e a leitura de POS no mapa, mencionando o que acontece com as variáveis fixas.
9. O que o recurso de don't care permite fazer no mapa de Karnaugh e quando ele deve ser usado?
1. B. O mapa reorganiza a tabela-verdade para aproximar termos vizinhos e tornar visíveis os agrupamentos que permitem eliminar variáveis.
2. B. Em SOP, você agrupa os casos em que a saída vale 1, porque eles formam os termos do produto final.
3. C. A variável que muda dentro do grupo desaparece, pois ela não é necessária na expressão reduzida.
4. B. Em POS, uma variável fixa em 1 entra negada no termo soma, e uma variável fixa em 0 entra direta.
5. Porque o mapa “dá a volta”, então bordas opostas são vizinhas logicamente e podem entrar no mesmo agrupamento.
6. $F = \bar{B}$. Os oito mintermos formam um único grupo em que apenas $B=0$ permanece fixo.
7. $F = \bar{C}$. Os zeros se agrupam em uma faixa em que $C=1$ permanece constante, então o termo soma é negado.
8. Em SOP, você agrupa os $1$s e lê um produto; em POS, você agrupa os $0$s e lê uma soma. Em ambos os casos, as variáveis que mudam desaparecem.
9. Permite tratar estados irrelevantes como $0$ ou $1$ para aumentar o agrupamento e reduzir a expressão, mas só vale usar quando isso realmente simplifica a função.
Próximos passos11.9
No próximo capítulo, Aritmética Digital I, vamos projetar do zero um somador completo de 1 bit e um subtrator de 1 bit, construir suas tabelas-verdade, minimizar suas expressões e mostrar como esses blocos podem ser encadeados para formar circuitos de uma quantidade arbitrária de bits.