No tutorial anterior, todos os possíveis funções booleanas entre duas variáveis foram discutidas. No tutorial – Álgebra Booleana, foram declarados vários teoremas e postulados que são úteis para simplificar uma expressão ou função booleana. No entanto, a simplificação de uma expressão booleana utilizando teoremas e postulados é bastante complicada e sujeita a erros. Portanto, para simplificação de expressões booleanas, alguns métodos de mapas foram desenvolvidos. O método de mapa mais comumente usado é Karnaugh Map ou K-Map.
Esses métodos são baseados no fato de que cada função booleana possui uma tabela verdade única. Uma função booleana pode ser representada por diversas expressões booleanas, mas sua tabela verdade permanecerá sempre a mesma. Isto se deve ao fato de que um circuito digital sempre terá saídas fixas ou resposta correspondente às entradas. Vamos primeiro discutir o K-map.
Mapa de Karnaugh –
O mapa de Karnaugh é a técnica de simplificação mais comum para expressões booleanas. Baseia-se nos seguintes fatos –
1) Qualquer função booleana, entretanto, pode ser representada em várias formas ou expressões booleanas sempre têm uma tabela verdade única. Se duas expressões booleanas tiverem a mesma tabela verdade, elas terão a mesma função.
2) Qualquer função booleana pode ser representada por soma de produtos (Mintermos) ou produto de somas (Maxtermos).
3) A soma dos Mintermos ou produto dos Maxtermos é redutível pela aplicação de vários teoremas booleanos.
O K-map é basicamente uma representação tabular da tabela verdade. Por exemplo, uma função de duas variáveis pode ter a seguinte tabela verdade –
Figura 1: Um mapa K de duas variáveis
K-Map é útil para minimizar expressões booleanas contendo até 5 variáveis ou menos. Uma vez construído o mapa, a expressão minimizada pode ser deduzida pelo seguinte processo –
1) Insira 1s nas células correspondentes às combinações para as quais o valor da função é 1 na tabela verdade. Em seguida, preencha 0s nas células restantes do K-map. Cada célula do mapa representa um Minterm. A função booleana representada pelo mapa (o mapa é apenas uma representação gráfica da tabela verdade) é a soma dos mintermos que podem conter uma ou mais variáveis booleanas como literais.
2) Examine o mapa em busca de células de valor 1 que não podem ser combinadas com nenhuma outra célula de valor 1 ou forme grupos com outras células de valor 1. Isso significa identificar células com valor 1 que não possuem células adjacentes com valor 1. Esses grupos representam mintermos contendo todas as variáveis booleanas como literais no termo como parte da função booleana.
3) Examine o mapa para células com valor 1 que são adjacentes apenas umas às outras células com valor 1 e formem grupos contendo apenas duas células com valor 1, mas não fazem parte de nenhum grupo contendo quatro ou oito células com valor 1. Esses grupos representam mintermos contendo variáveis booleanas como literais um a menos que o número máximo de variáveis booleanas no termo como parte da função. Esses grupos são chamados de pares.
4) Examine o mapa em busca de células com valor 1 que sejam adjacentes a apenas três outras células com valor 1 e formem grupos contendo apenas quatro células com valor 1, mas não façam parte de nenhum grupo contendo oito células com valor 1. Esses grupos representam mintermos contendo variáveis booleanas como literais dois a menos que o número máximo de variáveis booleanas no termo como parte da função. Esses grupos são chamados de quads. Em uma função de 2 variáveis, a formação de quad significa que a saída da função é 1.
5) Examine o mapa em busca de células com valor 1 que sejam adjacentes a sete outras células com valor 1 e formem grupos contendo oito células com valor 1, mas que não façam parte de nenhum grupo contendo dezesseis células com valor 1 ou superior. Esses grupos representam mintermos contendo variáveis booleanas como literais três a menos que o número máximo de variáveis booleanas no termo como parte da função. Esses grupos são chamados de octetos. Em uma função de 3 variáveis, a formação do octeto significa que a saída da função é 1.
6) Forme todos os grupos de simples, pares, quádruplos e octetos de forma que haja um número mínimo de grupos. Os pares, quádruplos e octetos também podem ser formados com a combinação de células de valor 1 em bordas opostas do mapa. Como no mapa K a seguir para função booleana de 3 variáveis, m0 e m8 nos cantos estão formando um par.
Figura 2: Um mapa K de três variáveis
7) Remova quaisquer grupos redundantes.
8) Uma célula com valor 1 sem nenhuma célula adjacente com valor 1 fornece um Minterm contendo 2, 3, 4, 5 termos variáveis para função booleana de 2 variáveis, 3 variáveis, 4 variáveis e 5 variáveis ou mapa K respectivamente . Um par de células com valor 1 fornece um Minterm contendo 1, 2, 3, 4 termos variáveis para função booleana de 2 variáveis, 3 variáveis, 4 variáveis e 5 variáveis ou mapa K, respectivamente. Um quádruplo de células com valor 1 fornece um Minterm contendo 1, 2, 3 termos variáveis para função booleana de 3 variáveis, 4 variáveis e 5 variáveis ou mapa K, respectivamente. A formação de quad para uma função de 2 variáveis significa que é igual a 1. Um octeto de células com valor 1 fornece um Minterm contendo 2 ou 3 termos variáveis para função booleana de 4 e 5 variáveis ou mapa K, respectivamente. A formação do octeto para uma função de 3 variáveis significa que é igual a 1.
9) Se uma única célula com valor 1 for identificada, ela representa um Minterm tendo a variável booleana como literal no termo for correspondente ao valor 1 para a respectiva variável booleana e/ou tendo complemento da variável booleana como literal no termo for foi correspondido ao valor 0 para a respectiva variável booleana. Essa célula com valor 1 induzirá um Minterm na função contendo todas as variáveis booleanas na forma complementar ou normal. Se um par for identificado, uma variável booleana será eliminada e um Minterm contendo um número a menos de variáveis booleanas máximas será induzido na função booleana. Da mesma forma, um quad leva à eliminação de duas variáveis booleanas no Minterm e assim por diante. A variável booleana que tem uma mudança de bit dentro do par, quádruplo ou octeto é eliminada no termo.
10) A função booleana é a soma lógica dos Mintermos gerados por todos os grupos. A função booleana como produto da soma pode ser gerada de forma semelhante por grupos de 0s.
Mapa K de duas variáveis –
Um mapa K de duas variáveis possui quatro células, pois o número máximo de mintermos possíveis com duas variáveis booleanas é 4 (2 ^ 2). Pode haver no máximo 16 funções (2^2*2) geradas por duas variáveis booleanas.
Figura 3: K-Map e Mintermos de Duas Variáveis
Uma função gerada por um mapa K de duas variáveis é redutível por células ou pares únicos de valor 1. A formação de um quad no mapa K de duas variáveis significa que a função é igual a 1.
Mapa K de três variáveis –
Um mapa K de três variáveis possui oito células, pois o número máximo de mintermos possíveis com três variáveis booleanas é 8 (2 ^ 3). Pode haver no máximo 64 funções (2^2*3) geradas por três variáveis booleanas.
Figura 4: K-Map e Mintermos de três variáveis
Uma função gerada por um mapa K de três variáveis é redutível por células únicas de valor 1, pares ou quádruplos. A formação de um octeto no mapa K de três variáveis significa que a função é igual a 1.
Mapa K de quatro variáveis –
Um mapa K de quatro variáveis tem dezesseis células, pois o número máximo de mintermos possíveis com quatro variáveis booleanas é 16 (2 ^ 4). Pode haver no máximo 256 funções (2^2*4) geradas por quatro variáveis booleanas.
Figura 5: Mapa K de quatro variáveis e mintermos
Uma função gerada por um mapa K de quatro variáveis é redutível por células únicas de valor 1, pares, quádruplos ou octetos. A formação de 16 células de valor único no mapa K de quatro variáveis significa que a função é igual a 1.
Mapa K de cinco variáveis –
Um mapa K de cinco variáveis tem trinta e duas células, pois o número máximo de mintermos possíveis com cinco variáveis booleanas é 32 (2 ^ 5). Pode haver no máximo 1.024 funções (2^2*5) geradas por cinco variáveis booleanas.
Figura 6: Mapa K de cinco variáveis e mintermos
Uma função gerada por um mapa K de cinco variáveis é redutível por células únicas de valor 1, pares, quádruplos, octetos ou grupo de 16 células de valor 1. A formação de 32 células de valor único em um mapa K de cinco variáveis significa que a função é igual a 1.
Não me importo com combinações –
Não é necessário que todas as saídas de uma função booleana sejam sempre conhecidas. Em circuitos digitais, pode haver a possibilidade de, para certas combinações, a saída ser 1 ou 0. Nesse caso, d, x ou Ø é inserido no mapa K para as combinações de entrada correspondentes. Para derivar a expressão booleana, 1 ou 0 pode ser assumido em combinações indiferentes para deduzir uma soma mínima de produtos ou produto da expressão de soma.
Método Quine-McCluskey –
O K-map é útil na dedução de expressões booleanas envolvendo quatro variáveis booleanas ou menos. Além disso, fica complexo. Portanto, outro método denominado método Quine-McCluskey é usado para deduzir expressões booleanas envolvendo quatro ou mais variáveis booleanas. O método Quine-McCluskey é um método tabular para derivar a expressão booleana mínima. Na tabela verdade de uma função booleana, podem ser listadas as combinações para as quais a saída da função é 1. Essas combinações podem ser indexadas em ordem crescente como números binários. Por exemplo, suponha que exista uma função booleana envolvendo quatro variáveis booleanas (A, B, C, D) com a seguinte tabela verdade –
As combinações resultantes em 1 ao serem indexadas em ordem crescente como números binários fornecem a tabela a seguir para o caso acima
Esta função booleana pode ser escrita da seguinte forma –As combinações resultantes em 1 ao serem indexadas em ordem crescente como números binários fornecem a seguinte tabela para o caso acima –
F (A, B, C, D) = ∑ (0, 5, 8, 9, 10, 11, 14, 15)
No primeiro passo de Quine-McCluskey método, os mintermos são organizados em grupos pelo número de 1s neles como segue –
Quaisquer dois mintermos em grupos adjacentes como grupo 0 e 1, grupo 1 e 2 ou grupo 2 e 3 e assim por diante são agora comparados e examinados quanto à mudança no valor de apenas uma variável booleana. Tais mintermos são selecionados como corresponder e tabulados como pares na próxima etapa com um travessão lugar onde solteiro a variável booleana mudou para a correspondência como a seguir –
Na próxima etapa, as partidas nos grupos adjacentes de mesa na etapa 2 são comparados e examinados para traço para a mesma variável e alteração no valor de apenas uma variável booleana. Essas correspondências são selecionadas como quadras e tabuladas na tabela seguinte com um travessão lugar onde solteiro variável booleana foi alterada para a partida. Os pares na segunda tabela e os mintermos na primeiro tabelas que não foram correspondidas nas respectivas tabelas também são tabuladas na próxima tabela (terceira tabela) como segue –
Os quádruplos, pares ou simples derivados na terceira tabela (removendo os redundantes) são chamados de implementos principais. Na próxima etapa, os implementos principais são tabulados em relação aos mintermos e os mintermos incluídos no respectivo implemento principal (quádruplo, par ou único) são marcados por X em relação ao respectivo implemento principal como segue –
Na tabela final, as colunas que possuem um único X são examinadas e as linhas que contêm esse X são identificadas. Os implementos principais respectivos a essas linhas são anotados e os termos respectivos a esses implementos principais são incluídos como soma de produtos na expressão booleana por comparação de implementos principais e variáveis booleanas da terceira tabela. Na terceira tabela, a variável booleana contra o implemento principal selecionado com valor traço não é incluída, a variável booleana contra o implemento principal selecionado com valor 1 é incluída na forma normal no respectivo termo e a variável booleana contra o implemento principal selecionado com valor 0 é incluído em elogio formulário no respectivo termo. Os implementos principais selecionados de quarto tabela são chamados de implementos essenciais. Para a função booleana acima, na quarta tabela, todas as linhas são tendo um X que é único em pelo menos uma coluna. Portanto, todas as linhas são selecionadas e todos os implementos principais são implementos essenciais para a função booleana. De terceiro tabela, a expressão booleana para a função pode ser derivada da seguinte forma –
F (A, B, C, D) =AB' + AC + B'C'D' + A'BC'D
Agora, com o conhecimento do K-map e do método Quine-McCluskey, qualquer função booleana com uma determinada tabela verdade pode ser facilmente minimizada. No próximo tutorial, aprenda sobre lógica implementação de portão de uma expressão booleana minimizada.