Solucionador de Mapa de Karnaugh (K-Map)

O Solucionador de Mapa de Karnaugh K-Map minimiza qualquer função lógica booleana de 2 a 5 variáveis e visualiza a simplificação como um Mapa K clássico com agrupamentos codificados por cores. Insira seus mintermos, maxtermos ou use a tabela verdade interativa — o solucionador executa o algoritmo de Quine-McCluskey internamente, encontra todos os implicantes primos, marca os essenciais e produz a expressão mínima de Soma de Produtos (SOP) ou Produto de Somas (POS) com uma explicação passo a passo. Clique em qualquer chip de implicante primo para pulsar e brilhar as células que ele cobre e veja como o agrupamento simplifica a lógica.

O que é um Mapa de Karnaugh?

Um mapa de Karnaugh (inventado por Maurice Karnaugh em 1953) é uma representação gráfica de uma tabela verdade, organizada de modo que as células que diferem por apenas uma variável de entrada sejam fisicamente adjacentes. O truque principal é a ordenação por código Gray de linhas e colunas: rótulos consecutivos como 00, 01, 11, 10 diferem por exatamente um bit. Essa adjacência permite identificar visualmente grupos de 1s (ou 0s) que podem ser combinados em um único termo simplificado.

Para n variáveis de entrada, o Mapa K possui 2^n células. Um mapa de 4 variáveis é uma grade 4×4 de 16 células; um mapa de 5 variáveis é desenhado como duas grades 4×4 adjacentes.

SOP vs POS: Qual Forma Escolher

Soma de Produtos (SOP)

SOP agrupa as células 1. Cada grupo torna-se um produto (AND) de literais, e todos os grupos são unidos por uma operação OR. Exemplo: AB'C + BD. SOP geralmente é o padrão porque mapeia diretamente para redes de portas lógicas AND–OR.

Produto de Somas (POS)

POS agrupa as células 0. Cada grupo torna-se uma soma (OR) dos literais complementados, e todas as somas são unidas por uma operação AND. Exemplo: (A + B')(C + D'). POS costuma ser menor quando a função possui mais 1s do que 0s.

A ferramenta calcula ambas as formas de forma independente — alterne o modo de saída para comparar as contagens de literais e escolha a que for mais simples para a sua implementação.

Regras de Agrupamento para Mapas de Karnaugh

• Apenas grupos de potência de dois: os grupos devem conter 1, 2, 4, 8 ou 16 células. Grupos de 3 ou 5 não são permitidos.
• Formato retangular: as células em um grupo formam um retângulo (horizontalmente, verticalmente ou envolvendo as bordas).
• Adjacência circular: a linha superior é adjacente à linha inferior; a coluna mais à esquerda é adjacente à mais à direita. É por isso que a ordenação por código Gray é importante.
• Grupos maiores primeiro: grupos maiores eliminam mais variáveis, produzindo termos de produto mais curtos. Um grupo de 8 células elimina 3 variáveis; um de 4 células elimina 2; um de 2 células elimina 1.
• Todo 1 deve ser coberto: pelo menos um grupo deve cobrir cada célula 1 (para SOP) ou célula 0 (para POS).
• Sobreposição é permitida: o mesmo 1 pode ser coberto por vários grupos se isso levar a grupos maiores.
• Don't-cares são flexíveis: eles podem ser agrupados se isso produzir grupos maiores, mas não precisam ser obrigatoriamente cobertos.

Implicantes Primos e Implicantes Primos Essenciais

Um implicante primo é um grupo que não pode ser mais expandido — aumentá-lo incluiria uma célula 0 (para SOP). O solucionador lista todos os implicantes primos que encontra. Em seguida, ele escolhe uma cobertura mínima: o menor conjunto de implicantes primos que cobre todos os mintermos necessários.

Um implicante primo essencial é marcado como ESSENCIAL quando é o único implicante primo que cobre pelo menos um mintermo específico. Toda expressão mínima deve incluir todos os implicantes primos essenciais. Após selecioná-los, os mintermos restantes não cobertos são cobertos pelos implicantes primos adicionais mais "baratos" (com menos literais).

Condições Don't-Care

Um don't-care (mostrado como X no Mapa K) é uma combinação de entrada cuja saída é irrelevante — ou ela nunca ocorre no circuito real ou seu valor não importa. O algoritmo é livre para tratar cada X como 0 ou 1, escolhendo o que resultar em uma expressão mais simples. Na prática, don't-cares geralmente reduzem a contagem de literais em 30–60%. Uma fonte comum no mundo real: decodificadores de dígitos decimais que usam apenas 10 das 16 combinações de entrada de quatro bits, deixando as combinações 10–15 como don't-cares.

O Algoritmo de Quine-McCluskey

O Mapa K é um método visual, mas para mais de 4–5 variáveis ele se torna impraticável. O algoritmo de Quine-McCluskey (QM) é o equivalente tabular — matematicamente rigoroso e escalável. Este solucionador usa o QM internamente:

1. Lista os mintermos em binário, agrupando-os pelo número de bits 1.
2. Combina pares de grupos adjacentes (que diferem em um bit), substituindo o bit divergente por um traço. Exemplo: 0011 + 0111 → 0-11.
3. Repete até que não sejam mais possíveis combinações. Termos que não podem ser combinados são implicantes primos.
4. Constrói uma tabela de implicantes primos — as linhas são os primos, as colunas são os mintermos necessários. Identifica os primos essenciais (colunas com uma única marcação).
5. Método de Petrick / busca exaustiva: para os mintermos restantes, encontra o menor conjunto de primos adicionais que os cobre.

Como Usar Esta Calculadora

1. Selecione o número de variáveis: 2, 3, 4 ou 5. A grade do Mapa K se adapta automaticamente.
2. Escolha um método de entrada:
   • Mintermos: insira os índices onde F = 1 (ex: 1, 3, 5, 7) e quaisquer don't-cares.
   • Maxtermos: insira os índices onde F = 0. O solucionador calcula o restante como 1s automaticamente.
   • Tabela Verdade: clique em cada linha para alternar a saída entre 0, 1 e X. Perfeito para lógica projetada à mão.
3. Escolha a saída SOP ou POS. Compare ambas as formas alternando — uma costuma ser mais curta que a outra.
4. Clique em Resolver. O Mapa K aparece com cada implicante primo em uma cor distinta. Clique em qualquer chip para fazer pulsar as células que ele cobre.
5. Inspecione as etapas: o detalhamento de Quine-McCluskey mostra como cada implicante primo foi derivado e quais são essenciais.

Exemplo Prático: Função de 4 Variáveis com Don't-Cares

Considere F(A,B,C,D) = Σm(1, 3, 7, 11, 15) + d(0, 2, 5).

Sem don't-cares, o SOP mínimo precisaria de vários termos. Tratar {0, 2} como 1s permite ao solucionador construir o grupo de 4 células A'B' (cobrindo 0, 1, 2, 3). Tratar 5 como um 1 permite estender a cobertura de CD. A simplificação resultante é:

Apenas 4 literais — contra mais de 10 sem o truque do don't-care. Você pode carregar exatamente este exemplo com o exemplo rápido "4 var com Don't-Cares" acima.

Por que Minimizar Funções Booleanas?

• Menos portas lógicas = menor custo de hardware, menor área de chip, menor consumo de energia.
• Circuitos mais rápidos: menos atrasos de porta no caminho crítico.
• Documentação mais limpa: uma expressão concisa é mais fácil de verificar e manter.
• Base do design digital: toda ferramenta de síntese de FPGA executa um descendente de Quine-McCluskey (como Espresso-II e posteriores).

Limitações e Quando Usar Outras Ferramentas

• 5+ variáveis: Mapas K tornam-se visualmente poluídos. Esta ferramenta suporta até 5 dividindo em dois mapas 4×4. Além disso, confie nas etapas de Quine-McCluskey ou use ferramentas de síntese como ABC / Espresso.
• Riscos (Hazards) e falhas: uma cobertura mínima pode conter riscos estáticos. Para projetos livres de riscos, inclua implicantes primos redundantes — esta ferramenta os marca, mas não adiciona coberturas de risco automaticamente.
• Minimização de múltiplas saídas: se várias funções compartilham variáveis, a minimização conjunta (compartilhando portas) resulta em hardware menor. Esta ferramenta minimiza uma função por vez.

Perguntas Frequentes

O que é um Mapa de Karnaugh?

Um Mapa de Karnaugh (K-map) é um método visual para minimizar expressões booleanas. As células são organizadas de modo que células adjacentes difiram por apenas uma variável (ordenação de código Gray). Agrupar 1s em retângulos de tamanho 1, 2, 4, 8 ou 16 revela a expressão mínima de Soma de Produtos.

Qual é a diferença entre SOP e POS?

SOP (Soma de Produtos) agrupa as células 1 e une seus termos de produto com OR, ex: A'B + CD. POS (Produto de Somas) agrupa as células 0 e une seus termos de soma com AND, ex: (A + B')(C' + D). Ambos descrevem a mesma função, mas uma forma geralmente é mais compacta.

O que são don't-cares e por que usá-los?

Termos don't-care (marcados com X) são combinações de entrada cujo valor de saída é irrelevante — eles nunca ocorrem ou seu valor não importa. O solucionador pode tratá-los como 0 ou 1, o que resultar em uma expressão mais simples. Don't-cares costumam reduzir drasticamente a contagem de literais.

O que é um implicante primo?

Um implicante primo é o maior grupo possível de células 1 adjacentes (tamanho potência de dois) que não pode ser mais expandido. Um implicante primo essencial é aquele que cobre de forma única pelo menos um mintermo e deve ser incluído em toda expressão mínima.

Como funciona o algoritmo de Quine-McCluskey?

Quine-McCluskey é o equivalente tabular de um Mapa K, adequado para muitas variáveis. Ele lista todos os mintermos em binário, agrupa-os pelo número de 1s e combina iterativamente pares que diferem em exatamente um bit. Termos que não podem ser mais combinados são implicantes primos. Uma tabela de implicantes primos seleciona então a cobertura mínima.

Quantas variáveis este solucionador de Mapa K suporta?

Esta ferramenta suporta de 2 a 5 variáveis. Um Mapa K de 5 variáveis é exibido como dois mapas 4×4 adjacentes (um para A=0, outro para A=1). Além de 5 variáveis, os Mapas K tornam-se impraticáveis; use as etapas de Quine-McCluskey para funções maiores.

Leitura Adicional

• Mapa de Karnaugh — Wikipedia
• Algoritmo de Quine-McCluskey — Wikipedia
• Método de Petrick — Wikipedia