Aula sobre Mapas de Karnaugh - Simplificação de Expressões Lógicas

Sistemas Digitais 13042023 Prof Dr Marcel Stefan Wagner Aula 08b Mapas de Karnaugh 2 Prof Dr Marcel Stefan Wagner Tópicos Abordados Mapas de Karnaugh MK Propriedades do MK MK de 2 3 e 4 variáveis MK e agrupamentos Temas para a Próxima Aula Referências Bibliográficas 1 2 3 4 5 6 3 Prof Dr Marcel Stefan Wagner Mapas de Karnaugh Simplificação por Mapas de Karnaugh O Mapa de Karnaugh MK ou Diagrama de VeitchKarnaugh é um método gráfico para simplificar expressões lógicas ou para converter uma Tabela da Verdade tabelaverdade em um circuito lógico Tratase de uma maneira de mostrar a relação entre as entradas e as saídas assim como ocorre na tabelaverdade Serão implementados MK com até 4 variáveis de entrada Ainda com 5 ou 6 variáveis é possível obter a simplificação por este método porém com o aumento na quantidade de variáveis de entrada tornase muito complexa a resolução por este método A partir de 7 variáveis recomendase a utilização de recursos computacionais ou seja simplificação pelo Método de Quine McCluskey método por tabulação baseado em tabelas ou uso de Álgebra de Boole 4 Prof Dr Marcel Stefan Wagner a Obter a Tabela da Verdade da expressão caso não possua b Criar o Mapa de Karnaugh com Linhas e Colunas conforme a quantidade de Variáveis de Entrada da Tabela da Verdade de preferência com a variável MSB Most Significant Bit na linha e a LSB Least Significant Bit na coluna o que determina o tamanho do MK c Preencher o Mapa de Karnaugh com os valores presentes na coluna de Saída da Tabela da Verdade dentro da área útil d Agrupar as regiões vizinhas que possuem lados em comum onde a Saída é 12 no menor número possível de agrupamentos e Os agrupamentos devem ser feitos na Vertical eou Horizontal podendo ser um bloco de 1s mas nunca na diagonal f Cada agrupamento deve conter 2n regiões 20 1 21 2 22 4 23 8 24 16 25 32 portanto não existe agrupamento com 3 elementos ou 6 elementos por exemplo Mapas de Karnaugh Regras de Simplificação por Mapas de Karnaugh 5 Prof Dr Marcel Stefan Wagner g O Mapa de Karnaugh deve apresentar sempre a solução mais simples h Caso exista a variável X esta indica que a situação correspondente na linha de Saída da Tabela da Verdade é Indiferente ou seja Tanto Faz i A variável X pode ser usada como ferramenta no processo de simplificação pois pode ser interpretada como 02 ou 12 de forma a otimizar o circuito lógico de saída do MK j A saída do Mapa de Karnaugh deve ser tão simplificada quanto a da Álgebra de Boole k Os agrupamentos devem ser sempre o mais abrangente possível ou seja se for possível fazer um agrupamento maior então devese fazer este agrupamento maior isso corresponde à geração de menos grupos e ainda termos agrupamentos maiores na Saída do MK e dessa forma um resultado mais simplificado l Dentro dos agrupamentos entre as linhas e também entre as colunas realizase a multiplicação porta AND m Entre os agrupamentos devese somar porta OR Mapas de Karnaugh Regras de Simplificação por Mapas de Karnaugh 6 Prof Dr Marcel Stefan Wagner n É possível obter mais do que uma resposta no Mapa de Karnaugh porém todas devem ter o mesmo peso para que sejam válidas e estejam corretas o Devese agrupar todos os 1s é possível agrupar os 0s porém as operações descritas nas letras l e m se invertem e devese considerar a coleta das variáveis também de forma invertida ou seja não pode sobrar qualquer 12 sem agrupamento p Todos os grupos devem ser identificados no Mapa de Karnaugh q O mesmo 12 pode ser utilizado em mais do que um agrupamento r Cada grupo formado corresponderá a um termo na expressão booleana simplificada A cada agrupamento de 2n elementos 1s n variáveis de entrada são eliminadas do termo Dessa forma melhor será a simplificação pois a expressão simplificada terá menos termos e também menos variáveis a cada termo Mapas de Karnaugh Regras de Simplificação por Mapas de Karnaugh 7 Prof Dr Marcel Stefan Wagner Mapas de Karnaugh Construção de Mapas de Karnaugh a b a b c a b c d e b a a b c d 8 Prof Dr Marcel Stefan Wagner Mapas de Karnaugh a b a b c a b c d e b a a b c d a b 0 0 0 1 1 0 1 1 Célula MSB LSB MSB LSB Mapas de Karnaugh Representação com 2 Variáveis MSB Most Significant Bit Bit mais significativo LSB Least Significant Bit Bit menos significativo 9 Prof Dr Marcel Stefan Wagner a b a b c a b c d e b a a b c d Mapas de Karnaugh MSB LSB a b c 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 MSB LSB 12 Variável Normal 02 Variável está Invertida 𝑎 ത𝑎 ത𝑏 ҧ𝑐 ത𝑏𝑐 𝑏 ҧ𝑐 𝑏𝑐 Para que exista conexão no Mapa de Karnaugh é necessário que exista no máximo a inversão de apenas 1 bit entre as linhas eou colunas Mapas de Karnaugh Representação com 3 Variáveis 10 Prof Dr Marcel Stefan Wagner Mapas de Karnaugh Mapas de Karnaugh Representação com 4 Variáveis a b a b c a b c d e b a a b c d a b c d 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 MSB LSB Para que exista conexão no Mapa de Karnaugh é necessário que exista no máximo a inversão de apenas 1 bit entre as linhas eou colunas MSB LSB 11 Prof Dr Marcel Stefan Wagner Mapas de Karnaugh Mapas de Karnaugh Representação com 5 Variáveis Plana 12 Prof Dr Marcel Stefan Wagner Mapas de Karnaugh Mapa de Karnaugh de 2 variáveis Tabela da Verdade Mapa K 13 Prof Dr Marcel Stefan Wagner Tabela da Verdade Mapa K 1 Saída MSB LSB MSB LSB 0 0 1 Mapas de Karnaugh Mapa de Karnaugh de 2 variáveis 14 Prof Dr Marcel Stefan Wagner Tabela da Verdade Mapa de Karnaugh Mapas de Karnaugh Mapa de Karnaugh de 3 variáveis 15 Prof Dr Marcel Stefan Wagner Tabela verdade Mapa K 1 1 1 0 0 0 1 0 Mapas de Karnaugh Mapa de Karnaugh de 3 variáveis MSB 02 MSB 12 16 Prof Dr Marcel Stefan Wagner Tabela verdade Mapa K Mapas de Karnaugh Mapa de Karnaugh de 4 variáveis 17 Prof Dr Marcel Stefan Wagner Tabela verdade Mapa K 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 1 Mapas de Karnaugh Mapa de Karnaugh de 4 variáveis 18 Prof Dr Marcel Stefan Wagner Processo de simplificação da expressão de saída Consiste na combinação das células do Mapa K que contém 1 Agrupamento de 1 célula Agrupamento de 2 células Agrupamento de 4 células Agrupamento de 8 células 2n Mapas de Karnaugh Agrupamento de Células 19 Prof Dr Marcel Stefan Wagner É necessário identificar pares adjacentes no Mapa K Em cada par apenas 1 variável aparece na forma normal e na forma invertida O par pode ser agrupado e então a variável que aparece na forma normal e invertida pode ser eliminada O princípio é válido para pares adjacentes na horizontal e vertical Mapas de Karnaugh Agrupamento de 2 Células 20 Prof Dr Marcel Stefan Wagner Exercício 1 Encontre a expressão booleana que descreve o circuito lógico representado pelo seguinte Mapa de Karnaugh Mapas de Karnaugh Agrupamento de 2 Células 21 Prof Dr Marcel Stefan Wagner Exercício 1 Encontre a expressão booleana que descreve o circuito lógico representado pelo seguinte Mapa de Karnaugh Mapas de Karnaugh Agrupamento de 2 Células 22 Prof Dr Marcel Stefan Wagner Exercício 2 Encontre a expressão booleana que descreve o circuito lógico representado pelo seguinte Mapa de Karnaugh Mapas de Karnaugh Agrupamento de 2 Células 23 Prof Dr Marcel Stefan Wagner Exercício 2 Encontre a expressão booleana que descreve o circuito lógico representado pelo seguinte Mapa de Karnaugh Mapas de Karnaugh Agrupamento de 2 Células 𝑆 ҧ𝐴𝐵 ҧ𝐶 ҧ𝐴𝐵𝐶 Por Álgebra de Boole 𝑆 ҧ𝐴𝐵 1 𝑆 ҧ𝐴𝐵 ҧ𝐶 𝐶 𝑆 ҧ𝐴𝐵 24 Prof Dr Marcel Stefan Wagner Exercício 3 Encontre a expressão booleana que descreve o circuito lógico representado pelo seguinte Mapa de Karnaugh Mapas de Karnaugh Agrupamento de 2 Células 25 Prof Dr Marcel Stefan Wagner Exercício 3 Encontre a expressão booleana que descreve o circuito lógico representado pelo seguinte Mapa de Karnaugh Mapas de Karnaugh Agrupamento de 2 Células 26 Prof Dr Marcel Stefan Wagner Exercício 4 Encontre a expressão booleana que descreve o circuito lógico representado pelo seguinte Mapa de Karnaugh Mapas de Karnaugh Agrupamento de 2 Células 27 Prof Dr Marcel Stefan Wagner Exercício 4 Encontre a expressão booleana que descreve o circuito lógico representado pelo seguinte Mapa de Karnaugh Mapas de Karnaugh Agrupamento de 2 Células 28 Prof Dr Marcel Stefan Wagner É necessário identificar os quartetos no Mapa K Quando um quarteto é agrupado o termo resultante contém apenas as variáveis que não mudam de forma para todas as células do quarteto Agrupar um quarteto de 1s elimina as duas variáveis que aparecem nas formas invertida e não invertida Mapas de Karnaugh Agrupamento de 4 Células 29 Prof Dr Marcel Stefan Wagner Exercício 5 Encontre a expressão booleana que descreve o circuito lógico representado pelo seguinte Mapa de Karnaugh Mapas de Karnaugh Agrupamento de 4 Células 30 Prof Dr Marcel Stefan Wagner Exercício 5 Encontre a expressão booleana que descreve o circuito lógico representado pelo seguinte Mapa de Karnaugh Mapas de Karnaugh Agrupamento de 4 Células 31 Prof Dr Marcel Stefan Wagner Exercício 6 Encontre a expressão booleana que descreve o circuito lógico representado pelo seguinte Mapa de Karnaugh Mapas de Karnaugh Agrupamento de 4 Células 32 Prof Dr Marcel Stefan Wagner Exercício 6 Encontre a expressão booleana que descreve o circuito lógico representado pelo seguinte Mapa de Karnaugh Mapas de Karnaugh Agrupamento de 4 Células 33 Prof Dr Marcel Stefan Wagner Exercício 7 Encontre a expressão booleana que descreve o circuito lógico representado pelo seguinte Mapa de Karnaugh Mapas de Karnaugh Agrupamento de 4 Células 34 Prof Dr Marcel Stefan Wagner Exercício 7 Encontre a expressão booleana que descreve o circuito lógico representado pelo seguinte Mapa de Karnaugh Mapas de Karnaugh Agrupamento de 4 Células 35 Prof Dr Marcel Stefan Wagner Exercício 8 Encontre a expressão booleana que descreve o circuito lógico representado pelo seguinte Mapa de Karnaugh Mapas de Karnaugh Agrupamento de 4 Células 36 Prof Dr Marcel Stefan Wagner Exercício 8 Encontre a expressão booleana que descreve o circuito lógico representado pelo seguinte Mapa de Karnaugh Mapas de Karnaugh Agrupamento de 4 Células 37 Prof Dr Marcel Stefan Wagner Exercício 9 Encontre a expressão booleana que descreve o circuito lógico representado pelo seguinte Mapa de Karnaugh Mapas de Karnaugh Agrupamento de 4 Células 38 Prof Dr Marcel Stefan Wagner Exercício 9 Encontre a expressão booleana que descreve o circuito lógico representado pelo seguinte Mapa de Karnaugh Mapas de Karnaugh Agrupamento de 4 Células 39 Prof Dr Marcel Stefan Wagner É necessário identificar os octetos no Mapa K Quando um octeto é agrupado o termo resultante contém apenas a variável que não mudam de forma para todas as células do octeto Agrupar um octeto de 1s elimina as três variáveis que aparecem nas formas invertida e não invertida Mapas de Karnaugh Agrupamento de 8 Células 40 Prof Dr Marcel Stefan Wagner Exercício 10 Encontre a expressão booleana que descreve o circuito lógico representado pelo seguinte Mapa de Karnaugh Mapas de Karnaugh Agrupamento de 8 Células 41 Prof Dr Marcel Stefan Wagner Exercício 10 Encontre a expressão booleana que descreve o circuito lógico representado pelo seguinte Mapa de Karnaugh Mapas de Karnaugh Agrupamento de 8 Células 42 Prof Dr Marcel Stefan Wagner Exercício 11 Encontre a expressão booleana que descreve o circuito lógico representado pelo seguinte Mapa de Karnaugh Mapas de Karnaugh Agrupamento de 8 Células 43 Prof Dr Marcel Stefan Wagner Exercício 11 Encontre a expressão booleana que descreve o circuito lógico representado pelo seguinte Mapa de Karnaugh Mapas de Karnaugh Agrupamento de 8 Células 44 Prof Dr Marcel Stefan Wagner Exercício 12 Encontre a expressão booleana que descreve o circuito lógico representado pelo seguinte Mapa de Karnaugh Mapas de Karnaugh Agrupamento de 8 Células 45 Prof Dr Marcel Stefan Wagner Exercício 12 Encontre a expressão booleana que descreve o circuito lógico representado pelo seguinte Mapa de Karnaugh Mapas de Karnaugh Agrupamento de 8 Células 46 Prof Dr Marcel Stefan Wagner Exercício 13 Encontre a expressão booleana que descreve o circuito lógico representado pelo seguinte Mapa de Karnaugh Mapas de Karnaugh Agrupamento de 8 Células 47 Prof Dr Marcel Stefan Wagner Exercício 13 Encontre a expressão booleana que descreve o circuito lógico representado pelo seguinte Mapa de Karnaugh Mapas de Karnaugh Agrupamento de 8 Células 48 Prof Dr Marcel Stefan Wagner Quando uma variável aparece nas formas invertida e não invertida dentro de um grupo esta variável é eliminada da expressão Variáveis que não mudam para todas as células do grupo devem aparecer na expressão final Um grupo de dois 1s elimina uma variável Um grupo de quatro 1s elimina duas variáveis Um grupo de oito 1s elimina três variáveis Mapas de Karnaugh Procedimento Completo de Simplificação 49 Prof Dr Marcel Stefan Wagner 1 Construa o Mapa K e coloque 1s nas células que correspondem aos 1s na tabela verdade Coloque 0s nas demais células 2 Examine o mapa para detectar 1s que não são adjacentes a quaisquer outros 1s Estes são chamados de 1s isolados 3 Procure por octetos e os agrupe 4 Procure por quartetos e os agrupe 5 Procure por pares e os agrupe 6 Agrupe quaisquer pares necessários para incluir quaisquer 1s que ainda não tenham sido combinados 7 Construa a soma de produtos formada por cada agrupamento Mapas de Karnaugh Procedimento Completo de Simplificação 50 Prof Dr Marcel Stefan Wagner Exercício 14 Encontre a expressão booleana que descreve o circuito lógico representado pelo seguinte Mapa de Karnaugh Mapas de Karnaugh Procedimento Completo de Simplificação 51 Prof Dr Marcel Stefan Wagner Exercício 14 Encontre a expressão booleana que descreve o circuito lógico representado pelo seguinte Mapa de Karnaugh Mapas de Karnaugh Procedimento Completo de Simplificação 52 Prof Dr Marcel Stefan Wagner Referências para a Apresentação Referências TOCCI Ronald J WIDMER Neal S MOSS Gregory L Sistemas Digitais Princípios e Aplicações recurso eletrônico Biblioteca Virtual 30 Prentice Hall Brasil 2007 TOKHEIM Roger Fundamentos de Eletrônica Digital Circuitos Combinacionais Porto Alegre AMGH 2013 VAHID Frank LASCHUK Anatólio Sistemas Digitais Projeto otimização e HDLs recurso eletrônico Minha Biblioteca Porto Alegre Grupo A 2011 IDOETA Ivan V CAPUANO Francisco G Elementos de eletrônica digital Livros Érica Editora Ltda 2007 FLOYD Thomas Sistemas Digitais Fundamentos e Aplicações recurso eletrônico Minha Biblioteca 9a ed Porto Alegre Grupo A 2011 53 Contato marcelwagnerulifecombr Departamentos de Engenharia Elétrica ENEL Engenharia da Computação ENCP Ciências da Computação CCOM Ciência dos Dados CDAD Sistemas de Informação SINF Tecnologia em Análise e Desenvolvimento de Sistemas TADS e Tecnologia em Gestão da Tecnologia da Informação TGTI Obrigado Agradecimento ao Prof Dr Maurício Caldora Costa pela parceria na elaboração dos materiais