Todo circuito digital — desde um somador simples até um processador moderno — começa com uma função lógica descrita em uma tabela verdade. A partir daí, o engenheiro precisa encontrar a expressão booleana que implementa essa função com o menor número possível de portas lógicas. Menos portas significa circuito menor, mais barato e mais rápido.
Este artigo é o complemento prático do artigo anterior Álgebra Booleana: fundamento matemático da computação digital: enquanto aquele artigo construiu os fundamentos teóricos — postulados, teoremas e identidades —, este os coloca em uso para simplificar funções lógicas. São apresentados três métodos: as formas canônicas (mintermos e maxtermos), que traduzem qualquer tabela verdade diretamente em expressão algébrica; a simplificação algébrica, que aplica os teoremas já estudados para reduzir termos e literais; e o mapa de Karnaugh, uma ferramenta gráfica que torna o processo visual e sistemático, sem depender de intuição algébrica.
Da tabela verdade à expressão: formas canônicas #
Mintermos e a forma SOP #
Considere o votador majoritário para três votantes A, B, C: a saída \(F\) vale 1 quando dois ou mais votantes votam 1.
| A | B | C | F |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
Por inspeção, podemos escrever uma expressão para cada linha em que \(F = 1\):
$$F = \bar{A}BC + A\bar{B}C + AB\bar{C} + ABC$$Cada um desses produtos contém todas as três variáveis (em forma direta ou complementada). Esses produtos completos têm um nome especial:
Um mintermo de \(n\) variáveis é um produto lógico que contém todas as \(n\) variáveis, cada uma aparecendo exatamente uma vez — em sua forma direta ou complementada.
Um mintermo vale 1 em exatamente uma linha da tabela verdade. A soma de mintermos (forma SOP — Sum of Products) representa a função nos pontos em que ela é 1.
Cada mintermo recebe um índice \(m_i\) igual ao valor decimal da combinação de entrada: lê-se os valores das variáveis como um número binário e converte-se para decimal. Por exemplo, a combinação A=0, B=1, C=1 forma o binário \(011_2 = 3_{10}\), logo o mintermo correspondente é \(m_3\).
Quando a tabela verdade é montada na ordem binária crescente (000, 001, 010, …, 111), o índice do mintermo coincide com o número da linha (contando do zero). Mas essa coincidência não vale se a tabela estiver em outra ordem. O índice é sempre determinado pelo valor das variáveis, não pela posição na tabela.
A expressão acima pode então ser escrita na notação compacta:
$$F = \bar{A}BC + A\bar{B}C + AB\bar{C} + ABC = m_3 + m_5 + m_6 + m_7$$$$\boxed{F(A,B,C) = \sum(3,\, 5,\, 6,\, 7)}$$Maxtermos e a forma POS #
O ponto de partida é \(\bar{F}\) — o complemento de \(F\). Como \(F = 1\) nas combinações 3, 5, 6 e 7, então \(\bar{F} = 1\) nas combinações restantes: 0, 1, 2 e 4. Ou seja:
$$\bar{F} = m_0 + m_1 + m_2 + m_4$$Agora aplicamos De Morgan a toda a expressão de \(\bar{F}\) para recuperar \(F\):
$$F = \overline{\bar{F}} = \overline{m_0 + m_1 + m_2 + m_4} = \bar{m}_0 \cdot \bar{m}_1 \cdot \bar{m}_2 \cdot \bar{m}_4$$O que é \(\bar{m}_i\)? É De Morgan aplicado a um mintermo. Por exemplo:
$$\bar{m}_0 = \overline{\bar{A}\bar{B}\bar{C}} = A + B + C$$Generalizando: a negação de um mintermo \(m_i\) é exatamente o maxtermo \(M_i\) — as variáveis que estavam complementadas ficam diretas, e vice-versa. Portanto:
$$F = \bar{m}_0 \cdot \bar{m}_1 \cdot \bar{m}_2 \cdot \bar{m}_4 = M_0 \cdot M_1 \cdot M_2 \cdot M_4$$Um maxtermo de \(n\) variáveis é uma soma lógica que contém todas as \(n\) variáveis, cada uma aparecendo exatamente uma vez.
Um maxtermo vale 0 em exatamente uma linha da tabela verdade. O produto de maxtermos (forma POS — Product of Sums) representa a função nos pontos em que ela é 0.
Na notação compacta:
$$\boxed{F(A,B,C) = \prod(0,\, 1,\, 2,\, 4)}$$Os índices de mintermos e maxtermos de uma mesma função são sempre complementares: se \(F = \sum(3,5,6,7)\), então necessariamente \(F = \prod(0,1,2,4)\). Os dois conjuntos somam todos os \(2^n\) índices possíveis.
Na prática, a escolha entre SOP e POS depende tanto do resultado da simplificação (qual forma tem menos termos e literais) quanto do hardware disponível:
- Portas NAND (as mais comuns em tecnologia CMOS) favorecem a forma SOP: dois níveis de portas NAND implementam diretamente qualquer expressão soma de produtos.
- Portas NOR favorecem a forma POS: dois níveis de portas NOR implementam diretamente qualquer expressão produto de somas.
Por isso, recomenda-se simplificar a função nas duas formas e comparar o custo em literais antes de escolher qual implementar.
Tabela geral de mintermos e maxtermos (3 variáveis) #
| Linha | x | y | z | Mintermo \(m_i\) | Maxtermo \(M_i\) |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | \(\bar{x}\bar{y}\bar{z}\) | \(x+y+z\) |
| 1 | 0 | 0 | 1 | \(\bar{x}\bar{y}z\) | \(x+y+\bar{z}\) |
| 2 | 0 | 1 | 0 | \(\bar{x}y\bar{z}\) | \(x+\bar{y}+z\) |
| 3 | 0 | 1 | 1 | \(\bar{x}yz\) | \(x+\bar{y}+\bar{z}\) |
| 4 | 1 | 0 | 0 | \(x\bar{y}\bar{z}\) | \(\bar{x}+y+z\) |
| 5 | 1 | 0 | 1 | \(x\bar{y}z\) | \(\bar{x}+y+\bar{z}\) |
| 6 | 1 | 1 | 0 | \(xy\bar{z}\) | \(\bar{x}+\bar{y}+z\) |
| 7 | 1 | 1 | 1 | \(xyz\) | \(\bar{x}+\bar{y}+\bar{z}\) |
Repare no padrão: no mintermo \(m_i\), uma variável aparece complementada se o bit correspondente em \(i\) for 0, e em forma direta se for 1. No maxtermo \(M_i\) acontece o contrário.
Por exemplo, a linha 5 tem \(x=1, y=0, z=1\), ou seja, \(i = 101_2 = 5_{10}\):
- \(m_5 = x\bar{y}z\) — x direto (bit 1), y complementado (bit 0), z direto (bit 1)
- \(M_5 = \bar{x}+y+\bar{z}\) — x complementado (bit 1), y direto (bit 0), z complementado (bit 1)
Exercícios #
Exercício 1 — \(F(A,B,C) = \sum(1,3,5,7)\): representar por produto de maxtermos
Os índices ausentes (onde \(F = 0\)) são 0, 2, 4, 6. Portanto:
$$F(A,B,C) = \prod(0,2,4,6) = M_0 \cdot M_2 \cdot M_4 \cdot M_6$$Expandindo:
$$F = (A+B+C)(A+\bar{B}+C)(\bar{A}+B+C)(\bar{A}+\bar{B}+C)$$Observe que todos os maxtermos têm \(C\) em forma direta. Isso é um indício de que \(C\) é a variável determinante: \(\sum(1,3,5,7)\) são exatamente os índices ímpares, ou seja, todas as combinações com \(C=1\). A simplificação algébrica confirma:
Simplificação algébrica
Exercício 2 — Representar a função da tabela por SOP e POS
| A | B | C | F |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 |
\(F = 1\) nos índices 1, 2, 4 (combinações \(001_2\), \(010_2\), \(100_2\)):
$$F = \sum(1,2,4) = \bar{A}\bar{B}C + \bar{A}B\bar{C} + A\bar{B}\bar{C}$$\(F = 0\) nos índices 0, 3, 5, 6, 7 (combinações \(000_2\), \(011_2\), \(101_2\), \(110_2\), \(111_2\)):
$$F = \prod(0,3,5,6,7) = (A+B+C)(A+\bar{B}+\bar{C})(\bar{A}+B+\bar{C})(\bar{A}+\bar{B}+C)(\bar{A}+\bar{B}+\bar{C})$$Cada mintermo \(m_i\) vale 1 exatamente na combinação \(i\), portanto o SOP lista os índices onde \(F = 1\). Cada maxtermo \(M_i\) vale 0 exatamente na combinação \(i\), portanto o POS lista os índices onde \(F = 0\). Como toda combinação pertence a um dos dois casos, \(\{1,2,4\} \cup \{0,3,5,6,7\} = \{0,\ldots,7\}\) — os dois conjuntos particionam o espaço de entradas.
Observe também a regra de complementação oposta: para o índice 1 (\(001_2\)), o mintermo é \(m_1 = \bar{A}\bar{B}C\) (bit 0 → complementado, bit 1 → direto), enquanto o maxtermo é \(M_1 = A+B+\bar{C}\) (bit 0 → direto, bit 1 → complementado). O mesmo padrão de bits gera literais opostos nas duas formas.
Simplificação algébrica #
Com a expressão em forma canônica em mãos, podemos aplicar os postulados e teoremas da Álgebra de Boole para reduzir o número de termos e literais. O resultado é uma expressão equivalente, mas mais simples.
Exemplo 1 — Votador majoritário: \(F(A,B,C) = \sum(3,5,6,7)\)
Exemplo 2 — \(F(A,B,C) = \sum(3,7)\)
Exemplo 3 — \(F(A,B,C) = \sum(4,5,6,7)\)
Exemplo 4 — \(F(A,B,C) = \sum(0,2,4,6)\)
O método funciona bem para funções simples, mas não é sistemático: não há um procedimento garantido que leve ao mínimo, e a sequência de passos depende de intuição e experiência. Para funções com muitos mintermos ou muitas variáveis, o mapa de Karnaugh é muito mais eficiente.
Mapa de Karnaugh #
Para superar essas limitações, o mapa de Karnaugh oferece um procedimento visual e sistemático que garante a expressão mínima sem depender de intuição algébrica.
O mapa de Karnaugh (K-map; Maurice Karnaugh, 1953, inspirado no diagrama de Veitch de 1952) é uma representação gráfica da tabela verdade onde cada célula corresponde a um mintermo. Os mintermos são organizados de modo que células vizinhas diferem em exatamente uma variável — isso permite enxergar grupos simplificáveis de forma visual.
O código Gray: por que a ordem importa #
As colunas (e linhas) do mapa de Karnaugh seguem o código Gray: cada posição adjacente difere em apenas 1 bit. Para dois bits, a sequência é:
$$00 \;\to\; 01 \;\to\; 11 \;\to\; 10$$Note que a ordem não é 00 → 01 → 10 → 11 (binária normal). Essa peculiaridade é o que garante a adjacência lógica entre células vizinhas.
Mapa de 2 variáveis #
Para \(F(A,B)\), o mapa é uma grade 2×2:
| \(A \backslash B\) | \(B=0\) | \(B=1\) |
|---|---|---|
| \(A=0\) | \(m_0\) | \(m_1\) |
| \(A=1\) | \(m_2\) | \(m_3\) |
Exemplo: \(F(A,B) = \bar{A}B + A\bar{B}\)
Mapa de 3 variáveis #
Para \(F(A,B,C)\), o mapa é uma grade 2×4, com as colunas rotuladas pelo par \(BC\) na sequência Gray:
| \(A \backslash BC\) | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | \(m_0\) | \(m_1\) | \(m_3\) | \(m_2\) |
| 1 | \(m_4\) | \(m_5\) | \(m_7\) | \(m_6\) |
Exemplo: \(F(A,B,C) = \bar{A}\bar{B}\bar{C} + \bar{A}BC + AB\bar{C} + ABC\)
| \(A \backslash BC\) | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 | 0 |
As células \(m_0, m_3, m_4, m_7\) valem 1, o que equivale a \(F(A,B,C) = \sum(0,3,4,7)\).
A seguir, veremos como esses mapas permitem simplificar funções lógicas.
Regras de simplificação com Karnaugh #
Antes de ver exemplos, vale sistematizar as regras:
| Tamanho do grupo | Variáveis eliminadas | Variáveis que restam |
|---|---|---|
| 1 célula | 0 | \(n\) |
| 2 células | 1 | \(n-1\) |
| 4 células | 2 | \(n-2\) |
| 8 células | 3 | \(n-3\) |
O algoritmo de simplificação segue esta ordem:
- Células isoladas primeiro — mintermos sem nenhum vizinho com valor 1; eles não simplificam, mas fazem parte da função.
- Única possibilidade — mintermos que só podem pertencer a um grupo; esse grupo é obrigatório (implicante primo essencial).
- Máximo de células — para os mintermos restantes, forme o maior grupo possível (potência de 2).
- Evite redundância — se todos os mintermos de um grupo já foram cobertos por grupos anteriores, esse grupo gera um termo redundante e deve ser descartado.
- Implicante de \(F\): qualquer produto de literais \(P\) tal que, sempre que \(P = 1\), também \(F = 1\). No K-map, corresponde a qualquer grupo válido de 1s.
- Implicante primo: implicante do qual não se pode remover nenhum literal sem que deixe de ser implicante — ou seja, o maior grupo possível que cobre determinados mintermos.
- Implicante primo essencial: implicante primo que é o único a cobrir pelo menos um mintermo. Deve obrigatoriamente fazer parte da cobertura mínima.
Grupos de 3, 5, 6 ou qualquer número que não seja potência de 2 são inválidos. O tamanho deve ser sempre 1, 2, 4, 8, 16…
O procedimento apresentado aqui — agrupar os 1s — produz a forma SOP (soma de produtos). Para obter a forma POS (produto de somas) diretamente pelo K-map, aplica-se o mesmo processo aos 0s do mapa: cada grupo de 0s gera um maxtermo simplificado, e o resultado final é o produto desses maxtermos.
Simplificação: mapa de 3 variáveis #
Retomando o exemplo \(F(A,B,C) = \sum(0,3,4,7)\) apresentado acima, há dois grupos de células adjacentes com valor 1. A figura a seguir os destaca:
- Grupo 1: \(m_0\) e \(m_4\) (coluna 00, ambas as linhas) → \(\bar{B}\bar{C}\)
- Grupo 2: \(m_3\) e \(m_7\) (coluna 11, ambas as linhas) → \(BC\)
Logo, a função pode ser simplificada para:
$$\boxed{F = \bar{B}\bar{C} + BC}$$Mapa de 4 variáveis #
Para \(F(A,B,C,D)\), o mapa é uma grade 4×4, com linhas rotuladas por \(AB\) e colunas por \(CD\), ambas em sequência Gray:
| \(AB \backslash CD\) | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | \(m_0\) | \(m_1\) | \(m_3\) | \(m_2\) |
| 01 | \(m_4\) | \(m_5\) | \(m_7\) | \(m_6\) |
| 11 | \(m_{12}\) | \(m_{13}\) | \(m_{15}\) | \(m_{14}\) |
| 10 | \(m_8\) | \(m_9\) | \(m_{11}\) | \(m_{10}\) |
O mapa de Karnaugh deve ser imaginado como um toroide: a primeira e a última colunas são adjacentes, e o mesmo vale para a primeira e a última linhas. Isso significa que os quatro cantos (\(m_0, m_2, m_8, m_{10}\)) também formam um grupo válido!
Para entender a geometria, pense em dobrar o retângulo duas vezes: primeiro juntando as bordas laterais (formando um cilindro), depois juntando as bordas circulares do cilindro (formando o toroide):
O resultado final, com os mintermos posicionados na superfície toroidal:
Fonte: Karnaugh map — Wikipedia
A figura abaixo mostra como a função \(F(A,B,C,D) = \bar{A}\bar{B}\bar{C}D + \bar{A}\bar{B}C\bar{D} + \bar{A}\bar{B}CD + \bar{A}BC\bar{D} + \bar{A}BCD + A\bar{B}\bar{C}D + AB\bar{C}\bar{D} \) pode ser simplificada usando o mapa de Karnaugh:
O mapa preenchido — equivalente a \(F = \sum(1,2,3,6,7,9,12)\) — é:
| \(AB \backslash CD\) | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 0 | 1 | 1 | 1 |
| 01 | 0 | 0 | 1 | 1 |
| 11 | 1 | 0 | 0 | 0 |
| 10 | 0 | 1 | 0 | 0 |
Os grupos identificados são:
- Grupo de 4: \(m_2, m_3, m_6, m_7\) — colunas \(CD = 10\) e \(CD = 11\), linhas \(AB = 00\) e \(AB = 01\); variáveis fixas \(A = 0\) e \(C = 1\) → \(\bar{A}C\)
- Grupo de 2 (toroidal): \(m_1, m_9\) — coluna \(CD = 01\), linhas \(AB = 00\) e \(AB = 10\); as bordas superior e inferior se tocam no toroide; variáveis fixas \(B = 0, C = 0, D = 1\) → \(\bar{B}\bar{C}D\)
- Célula isolada: \(m_{12}\) — todos os quatro vizinhos são 0; \(A = 1, B = 1, C = 0, D = 0\) → \(AB\bar{C}\bar{D}\)
Mapa de 5 variáveis #
Para \(F(A,B,C,D,E)\), o mapa cresce para 32 células — além do limite prático para trabalho manual, mas a estrutura segue o mesmo princípio. Usam-se dois grids 4×4 lado a lado: um para \(A=0\) e outro para \(A=1\). Em cada grid, as linhas são rotuladas por \(BC\) e as colunas por \(DE\), ambas em código Gray (00 → 01 → 11 → 10).
A adjacência funciona normalmente dentro de cada grid. Além disso, há adjacência cruzada entre os dois grids: uma célula na posição \((i,j)\) do grid \(A=0\) é adjacente à célula na mesma posição do grid \(A=1\), pois as duas diferem apenas em \(A\). Grupos podem, portanto, estender-se pelos dois grids.
Exemplo — \(F(A,B,C,D,E) = \sum(0,1,16,17,31)\)
Grid \(A=0\):
| \(BC \backslash DE\) | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 1 | 1 | 0 | 0 |
| 01 | 0 | 0 | 0 | 0 |
| 11 | 0 | 0 | 0 | 0 |
| 10 | 0 | 0 | 0 | 0 |
Grid \(A=1\):
| \(BC \backslash DE\) | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 1 | 1 | 0 | 0 |
| 01 | 0 | 0 | 0 | 0 |
| 11 | 0 | 0 | 1 | 0 |
| 10 | 0 | 0 | 0 | 0 |
Grupos identificados:
- Grupo de 4 (cruzado): \(\{m_0, m_1\}\) no grid \(A=0\) e \(\{m_{16}, m_{17}\}\) no grid \(A=1\) — mesma posição (linha \(BC=00\), colunas \(DE=00\) e \(DE=01\)). As quatro células diferem apenas em \(A\) e \(E\); o que fica fixo é \(B=0, C=0, D=0\) → \(\bar{B}\bar{C}\bar{D}\).
- Célula isolada: \(m_{31}\) no grid \(A=1\), linha \(BC=11\), coluna \(DE=11\) → \(A=1, B=1, C=1, D=1, E=1\) → \(ABCDE\).
Para funções com 6 ou mais variáveis o K-map se torna impraticável; nesse ponto, o método de Quine-McCluskey (algorítmico) é a alternativa natural.
Condições de indiferença (Don’t Care) #
Em muitos sistemas reais, algumas combinações de entrada nunca ocorrem — ou ocorrem, mas o resultado da saída não importa. Essas condições são chamadas de indiferença (don’t care) e são marcadas com X no mapa.
O exemplo clássico é o decodificador BCD (Binary-Coded Decimal): os dígitos decimais 0–9 usam apenas as combinações 0000 a 1001. As combinações 1010 a 1111 (10 a 15) são inválidas — nunca aparecem como entrada. Logo, o comportamento da saída para essas células é irrelevante e pode ser marcado como X.
- Use os X para ampliar grupos quando isso resultar em um grupo maior (potência de 2 maior) e, portanto, em um termo mais simples.
- Nunca forme um grupo composto só de X: esses mintermos não precisam ser cobertos — incluí-los desnecessariamente apenas acrescenta termos.
- Um X que não ajuda nenhum grupo pode ser simplesmente ignorado.
Exemplo com don’t care
Suponha \(F(A,B,C,D) = \sum m(1,3,5,7) + \sum d(9,11,13,15)\), onde \(d\) indica os don’t-cares.
| \(AB \backslash CD\) | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 0 | 1 | 1 | 0 |
| 01 | 0 | 1 | 1 | 0 |
| 11 | 0 | X | X | 0 |
| 10 | 0 | X | X | 0 |
Sem os X, os mintermos 1, 3, 5, 7 formam um grupo de 4 (\(A=0\), \(D=1\)) → \(\bar{A}D\).
Com os X disponíveis, os mintermos 1, 3, 5, 7 podem se juntar a 9, 11, 13 e 15 para formar um grupo de 8 (toda a coluna \(D=1\)). Resultado: simplesmente \(\boxed{F = D}\).
Dependendo das escolhas de agrupamento, um mesmo mapa de Karnaugh pode gerar duas ou mais expressões mínimas igualmente válidas. Isso ocorre quando um mintermo pode ser incluído em grupos diferentes sem alterar o número de termos ou literais do resultado final.
Por exemplo, num mapa de 3 variáveis, \(m_4\) pode ser agrupado tanto com \(\{m_0, m_4\}\) → \(\bar{B}\bar{C}\) quanto com \(\{m_4, m_6\}\) → \(A\bar{C}\); ambas as escolhas produzem expressões mínimas corretas.
Na prática, qualquer solução mínima é aceitável. Ferramentas de síntese lógica escolhem automaticamente entre as alternativas disponíveis.
Em projetos de hardware, engenheiros às vezes adicionam intencionalmente grupos redundantes no K-map — mesmo que não cubram nenhum mintermo novo — para eliminar hazards (glitches): pulsos espúrios na saída causados pelo atraso de propagação entre grupos adjacentes quando as entradas mudam. Esse refinamento vai além da minimização lógica pura e pertence à análise temporal de circuitos combinatórios.
Exercícios resolvidos #
Ex. 1 — \(F(A,B,C) = \sum(0,2,4,5,6)\) #
| \(A \backslash BC\) | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 | 1 |
- Grupo de 4 células — vermelho: \(m_0, m_2, m_4, m_6\) (colunas 00 e 10, ambas as linhas) → \(\bar{C}\)
- Grupo de 2 células — verde: \(m_4, m_5\) (linha \(A=1\), colunas 00 e 01) → \(A\bar{B}\)
Ex. 2 — \(F(A,B,C,D) = \sum(3,4,5,7,9,13,14,15)\) #
| \(AB \backslash CD\) | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 0 | 0 | 1 | 0 |
| 01 | 1 | 1 | 1 | 0 |
| 11 | 0 | 1 | 1 | 1 |
| 10 | 0 | 1 | 0 | 0 |
Identificando os implicantes primos essenciais:
| Grupo | Cor no mapa | Mintermos | Expressão | Por que essencial |
|---|---|---|---|---|
| \(\bar{A}CD\) | vermelho | \(\{3,7\}\) | \(A=0, C=1, D=1\) | único grupo cobrindo \(m_3\) |
| \(\bar{A}B\bar{C}\) | verde | \(\{4,5\}\) | \(A=0, B=1, C=0\) | único grupo cobrindo \(m_4\) |
| \(A\bar{C}D\) | amarelo | \(\{9,13\}\) | \(A=1, C=0, D=1\) | único grupo cobrindo \(m_9\) |
| \(ABC\) | ciano | \(\{14,15\}\) | \(A=1, B=1, C=1\) | único grupo cobrindo \(m_{14}\) |
Verificação: \(\{3,7\} \cup \{4,5\} \cup \{9,13\} \cup \{14,15\} = \{3,4,5,7,9,13,14,15\}\) ✓
$$\boxed{F = \bar{A}CD + \bar{A}B\bar{C} + A\bar{C}D + ABC}$$Ex. 3 — \(F(A,B,C,D) = \sum(0,2,5,7,8,10,13,15)\) #
| \(AB \backslash CD\) | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 1 | 0 | 0 | 1 |
| 01 | 0 | 1 | 1 | 0 |
| 11 | 0 | 1 | 1 | 0 |
| 10 | 1 | 0 | 0 | 1 |
- Grupo de 4 — vermelho: \(m_0, m_2, m_8, m_{10}\) (quatro cantos nas colunas 00/10, linhas 00/10) → \(\bar{B}\bar{D}\)
- Grupo de 4 — verde: \(m_5, m_7, m_{13}, m_{15}\) → \(BD\)
Esta é a função XNOR(B, D): a saída é 1 quando B e D têm o mesmo valor. O padrão xadrez no mapa de Karnaugh é sempre sinal de uma função XOR ou XNOR.
Ex. 4 — \(F(A,B,C,D) = \sum(0,2,3,4,6,9,10,11,12,14)\) #
| \(AB \backslash CD\) | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 1 | 0 | 1 | 1 |
| 01 | 1 | 0 | 0 | 1 |
| 11 | 1 | 0 | 0 | 1 |
| 10 | 0 | 1 | 1 | 1 |
| Grupo | Cor no mapa | Mintermos | Expressão | Por que essencial |
|---|---|---|---|---|
| \(\bar{A}\bar{D}\) | vermelho | \(\{0,2,4,6\}\) | \(A=0, D=0\) | único grupo cobrindo \(m_0\) |
| \(\bar{B}C\) | verde | \(\{2,3,10,11\}\) | \(B=0, C=1\) | único grupo cobrindo \(m_3\) |
| \(B\bar{D}\) | amarelo | \(\{4,6,12,14\}\) | \(B=1, D=0\) | único grupo cobrindo \(m_{12}\) |
| \(A\bar{B}D\) | ciano | \(\{9,11\}\) | \(A=1, B=0, D=1\) | único grupo cobrindo \(m_9\) |
Ex. 5 — \(F(A,B,C,D) = \sum(0,1,2,4,8,9,10,12,14)\) #
| \(AB \backslash CD\) | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 1 | 1 | 0 | 1 |
| 01 | 1 | 0 | 0 | 0 |
| 11 | 1 | 0 | 0 | 1 |
| 10 | 1 | 1 | 0 | 1 |
| Grupo | Cor no mapa | Mintermos | Expressão | Por que essencial |
|---|---|---|---|---|
| \(\bar{B}\bar{C}\) | vermelho | \(\{0,1,8,9\}\) | \(B=0, C=0\) | único grupo cobrindo \(m_1\) |
| \(\bar{B}\bar{D}\) | verde | \(\{0,2,8,10\}\) | \(B=0, D=0\) | único grupo cobrindo \(m_2\) |
| \(\bar{C}\bar{D}\) | amarelo | \(\{0,4,8,12\}\) | \(C=0, D=0\) | único grupo cobrindo \(m_4\) |
| \(A\bar{D}\) | ciano | \(\{8,10,12,14\}\) | \(A=1, D=0\) | único grupo cobrindo \(m_{14}\) |
Comparando os métodos #
Os dois métodos apresentados neste artigo — simplificação algébrica e mapa de Karnaugh — atacam o mesmo problema com abordagens bem diferentes. A tabela abaixo os compara e inclui o algoritmo de Quine-McCluskey, uma terceira alternativa de uso computacional que não foi detalhada aqui:
| Método | Vantagem | Limitação |
|---|---|---|
| Algébrico | Funciona com qualquer número de variáveis | Não sistemático; depende de intuição |
| Karnaugh | Visual e intuitivo; fácil identificar grupos | Prático apenas até 4–5 variáveis |
| Quine-McCluskey | Sistemático e algoritmicamente implementável | Prático apenas para implementação computacional |
O algoritmo de Quine-McCluskey é essencialmente o mapa de Karnaugh convertido em um procedimento tabular: ele encontra todos os implicantes primos por comparação sistemática de mintermos e depois seleciona a cobertura mínima. A ideia central é agrupar os mintermos pelo número de 1s em sua representação binária e comparar apenas grupos adjacentes — pois dois mintermos só podem se combinar se seus números decimais diferirem por exatamente uma potência de 2 (o que equivale a diferirem em exatamente um bit). Por ser determinístico e mecânico, é a base das ferramentas de síntese lógica usadas na indústria — mas a complexidade cresce exponencialmente com o número de variáveis, tornando-o impraticável à mão para funções grandes.
Conclusão #
Partindo de uma tabela verdade, aprendemos a:
- Escrever a forma canônica — soma de mintermos (SOP) ou produto de maxtermos (POS) — diretamente por inspeção.
- Simplificar algebricamente, aplicando os teoremas da Álgebra de Boole em sequência.
- Usar o mapa de Karnaugh para identificar grupos de mintermos adjacentes e obter a expressão mínima de forma visual.
O resultado de cada simplificação não é apenas uma expressão matemática mais bonita: é um circuito digital mais econômico, com menos portas e menor consumo de energia. Esse processo está na base do projeto de todo hardware digital.
Para aprofundar os teoremas e identidades utilizados ao longo deste artigo, consulte Álgebra Booleana: fundamento matemático da computação digital.
Até a próxima!
