Baixe o app para aproveitar ainda mais
Prévia do material em texto
Mapa de Karnaugh Joa˜o Paulo Cerquinho Cajueiro 24 de agosto de 2009 O chamado mapa de Karnaugh foi desenvolvido pelo matema´tico e f´ısico Maurice Karnaugh1 em 1953, enquanto trabalhava no grupo de pesquisas da empresa Bell. Este me´todo e´ uma poderosa ferramenta para circuitos lo´gicos, pois permite simplificar equac¸o˜es booleanas apenas agrupando a´reas comuns, o que nosso ce´rebro consegue fazer bem mais rapidamente do que aplicando postulados e teoremas a equac¸o˜es. 1 De diagramas de Venn a Mapas de Karnaugh Utilizar os teoremas e postulados da a´lgebra de Boole para simplificar equac¸o˜es e´ bastante tedioso, o que faz com que seja bem prova´vel que hajam erros no processo. Mas ja´ vimos que as equac¸o˜es da a´lgebra de Boole podem ser visualizadas atrave´s de um diagrama de Venn. Isto e´ exemplificado na figura 1, que apresenta um diagrama de Venn de 3 varia´veis com os respectivos mintermos associados a cada uma das regio˜es. a b c (a) Regio˜es das varia´veis abc abc abc abc abc abc abc abc (b) Sub-regio˜es dos mintermos Figura 1: Diagrama Venn com 3 varia´veis. Utilizando os diagramas, e´ fa´cil obter a equac¸a˜o simplificada da func¸a˜o. Por exemplo, considere-se a func¸a˜o f1 = abc + abc + abc. Desenhando esta func¸a˜o num diagrama de Venn (figura 2), fica o´bvio que podemos simplifica´-la para f1 = (a + c)b. O problema aparece quando acrescentamos mais 1 varia´vel. Como fazer um diagrama definindo todas as 16 possibilidades? A soluc¸a˜o para isto e´ desenhar 1Aparentemente ele atualmente (entre outras coisas), escreve o blog unclej0.blogspot.com. Esta informac¸a˜o depende em se acreditar ou na˜o na wikipedia. 1 f1 Figura 2: Diagrama Venn definindo a regia˜o dada por f1 = abc + abc + abc = (a + c)b. as regio˜es como quadrados, e na˜o como c´ırculos, assim como foi feito na figura 3. No lado direito desta figura temos ate´ a representac¸a˜o do lado de fora do diagrama propriamente dito de que regio˜es correspondem a que varia´veis. abcd abcd abcdabcd abcd abcd abcdabcd abcd abcd abcdabcd abcd abcd abcdabcd a b c d abcd abcd abcdabcd abcd abcd abcdabcd abcd abcd abcdabcd abcd abcd abcdabcd Figura 3: Diagrama Venn de 4 varia´veis desenhado com regio˜es quadradas. Este diagrama de Venn modificado ja´ e´ o pro´prio mapa de Karnaugh, onde no mapa as regio˜es em que a func¸a˜o e´ verdadeira sa˜o marcadas com 1, e em que a func¸a˜o e´ falsa sa˜o marcadas com 0. 2 Mapas de Karnaugh Cada regia˜o (quadrado) em um mapa de Karnaugh corresponde a uma linha na tabela verdade. Ou seja, cada regia˜o corresponde a um mintermo e a um maxtermo. A figura 4 mostra os mintermos correspondentes a cada uma das regio˜es. Nela tambe´m esta´ presente o nu´mero correspondente a cada mintermo 2 ou maxtermo. a b c d 0 1 3 2 4 5 7 6 12 13 15 14 8 9 11 10 abcd abcd abcdabcd abcd abcd abcdabcd abcd abcd abcdabcd abcd abcd abcdabcd Figura 4: Regio˜es correspondentes a mintermos de um mapa de Karnaugh Note na figura 4 que os vizinhos de cada casa em um mapa de Karnaugh sa˜o tais que apenas muda uma varia´vel de cada vez. Por exemplo, da casa 5 para a casa 1 (acima) so´ muda o b, da 5 para a 7 (direita) so´ muda o c, da 5 para a 4 (esquerda) so´ muda o d e da 5 para a 13 (abaixo) so´ muda o a. Isto e´ va´lido para todas as casas. E´ poss´ıvel aplicar isto inclusive para as casas nas bordas e nas quinas, pois podemos considerar que o mapa da´ a volta em si mesmo. Deste modo considera- se a casa 6 como vizinha da 4 e so´ muda a varia´vel c, e a casa 10 vizinha da 2 e so´ muda a varia´vel a. Isto nos permite agrupar termos visualmente. Por exemplo, considere a func¸a˜o f2 = ∑ m(3, 7, 12, 13) e seu respectivo mapa de karnaugh na figura 5. f2 = ∑ m(3, 7, 12, 13) a b c d 0 1 3 2 4 5 7 6 12 13 15 14 8 9 11 10 0 0 01 0 0 01 0 0 00 1 1 00 abc acd Figura 5: Func¸a˜o f2 e simplificac¸a˜o por agrupamento de casas vizinhas. Analisando a func¸a˜o f2 por a´lgebra de Boole, vemos que podemos simplifica´- la aplicando o teorema T6. E observando no mapa de Karnaugh, os termos que sa˜o unidos e simplificados sa˜o justamente os vizinhos. f2 = abcd + abcd︸ ︷︷ ︸ T6 + abcd + abcd︸ ︷︷ ︸ T6 f2 = acd + abc 3 Ou seja, o agrupamento de 2 casas vizinhas corresponde a` simplificac¸a˜o de uma varia´vel atrave´s da aplicac¸a˜o to teorema T6. Basta ver no pro´prio mapa quais sa˜o as varia´veis que na˜o mudam dentro do agrupamento. Para simplificar 2 ou mais varia´veis basta aplicar o teorema repetidas vezes. Simplifiquemos a func¸a˜o f3 (vide figura 6), por exemplo. Basta agruparmos a func¸a˜o de duas em duas casas e 2 grupos vizinhos de duas casas viram um u´nico grupo de 4 casas, retirando mais uma varia´vel da func¸a˜o. f3 = abcd + abcd︸ ︷︷ ︸+ abcd + abcd︸ ︷︷ ︸ = abc + abc︸ ︷︷ ︸ f3 = ac f3 a b c d 0 1 3 2 4 5 7 6 12 13 15 14 8 9 11 10 0 0 00 0 0 00 1 1 00 1 1 00 ⇒ f3 a b c d 0 1 3 2 4 5 7 6 12 13 15 14 8 9 11 10 0 0 00 0 0 00 1 1 00 1 1 00 Figura 6: Agrupamento das casas da func¸a˜o f3. Este mesmo procedimento pode ser mostrado para agrupamentos de 8 casas (simplificando enta˜o 3 varia´veis) ou 16 casas (simplificando 4 varia´veis. A figura 7 mostra algumas possibilidades de agrupamentos de 2, 4 e 8 casas2, junto com o produto respectivo. Claro que num mapa de Karnaugh de 4 varia´veis um agrupamento de 16 casas seria todo o mapa e corresponderia a func¸a˜o 1. 2Exemplos utilizados tambe´m no artigo original de Karnaugh: “The map method for synthesis of combinational logic circuits”, de 1953. 4 bcd a b c d 0 0 00 0 1 00 0 0 00 0 1 00 abd a b c d 0 1 01 0 0 00 0 0 00 0 0 00 abd a b c d 1 0 10 0 0 00 0 0 00 0 0 00 bcd a b c d 1 0 00 0 0 00 1 0 00 0 0 00 (a) agrupamentos de 2 casas cd a b c d 0 1 00 0 1 00 0 1 00 0 1 00 ab a b c d 0 0 00 0 0 00 1 1 11 0 0 00 a d a b c d 1 0 10 1 0 10 0 0 00 0 0 00 b d a b c d 1 0 10 0 0 00 1 0 10 0 0 00 (b) Agrupamentos de 4 casas b a b c d 0 0 00 1 1 11 0 0 00 1 1 11 d a b c d 1 0 10 1 0 10 1 0 10 1 0 10 c a b c d 0 0 11 0 0 11 0 0 11 0 0 11 b a b c d 1 1 11 0 0 00 1 1 11 0 0 00 (c) Agrupamentos de 8 casas Figura 7: Exemplos de mapas de karnaugh com os correspondentes produtos alge´bricos. 5 2.1 Mapas de n varia´veis Claro que um mapa de Karnaugh pode ser feito com um nu´mero menor de varia´veis. Para tanto basta simplesmente sair dividindo o mapa. Tem-se apenas que lembrar que uma casa deve ter n vizinhas, ja´ que a simplificac¸a˜o de uma varia´vel corresponde a unir uma casa com a vizinha. Isto e´ mostrado na figura 8 para mapas de 2, 3 e 4 varia´veis. a b 0 1 2 3 (a) Mapa de 2 varia´veis a b c 0 1 3 2 4 5 7 6 (b) Mapa de 3 varia´veis a b c d 0 1 3 2 4 5 7 6 12 13 15 14 8 9 11 10 (c) Mapa de 4 varia´veis Figura 8: Mapas de Karnaugh de 2, 3 e 4 varia´veis, mostrando que cada casa tem n vizinhas. Mas como aplicar este princ´ıpio para func¸o˜es com mais de 4 varia´veis? E´ imposs´ıvel fazer um mapa no plano onde cada uma das regio˜es tem 5 (ou mais) vizinhos. Uma maneira (na˜o muito pra´tica) e´ trabalhar com um mapa tridimensional como exemplifica a figura 9 que mostra um mapa de Karnaugh de 6 varia´veis, note que cada casa tem 6 vizinhos: 4 no plano (como no mapa de 4 varia´veis) e 2 verticais. Na pra´tica, um mapa de 5 varia´veis e´ desenhado como 2 de 4 varia´veis, sendo um com uma varia´vel (em geral a mais significativa) sendo 0 e o outro com a mesma varia´vel sendo1. Usa-se este mesmo princ´ıpio para mapas de 6 varia´veis ou mais varia´veis, como pode ser visto na figura 10. 6 c d e f 32 33 35 34 36 37 39 38 44 45 47 46 40 41 43 42 c d e f 48 49 51 50 52 53 55 54 60 61 63 62 56 57 59 58 c d e f 16 17 19 18 20 21 23 22 28 29 31 30 24 25 27 26 c d e f 0 1 3 2 4 5 7 6 12 13 15 14 8 9 11 10 a b Figura 9: Mapa de Karnaugh tridimensional de 6 varia´veis. b c d e 0 1 3 2 4 5 7 6 12 13 15 14 8 9 11 10 b c d e 16 17 19 18 20 21 23 22 28 29 31 30 24 25 27 26 a (a) 5 varia´veis c d e f 32 33 35 34 36 37 39 38 44 45 47 46 40 41 43 42 c d e f 48 49 51 50 52 53 55 54 60 61 63 62 56 57 59 58 c d e f 16 17 19 18 20 21 23 22 28 29 31 30 24 25 27 26 c d e f 0 1 3 2 4 5 7 6 12 13 15 14 8 9 11 10 a b (b) 6 varia´veis Figura 10: Mapas de Karnaugh de 5 e 6 varia´veis. 7 3 Soma de produtos e produto de somas Ate´ o momento trabalhamos com o mapa de Karnaugh agrupando os 1’s para gerar func¸o˜es na forma soma de produtos, mas podemos agrupar os zeros tam- be´m, gerando equac¸o˜es na forma produto de somas, como mostra a figura 11 para a func¸a˜of4 = ac + a(b + cd). f4(a, b, c, d) a b c d 0 1 3 2 4 5 7 6 12 13 15 14 8 9 11 10 0 0 01 1 1 11 1 1 00 1 1 00 a + c b + c + da + b + c Figura 11: Mapa de Karnaugh com agrupamento de 0’s. Da mesma forma que na tabela verdade, um 0 no mapa de Karnaugh cor- responde a um maxtermo. Logo o agrupamento de 2 casas com 0 corresponde a uma soma com n − 1 termos (onde n e´ o nu´mero de varia´veis da func¸a˜o), o agrupamento de 4 casas equivale a uma soma de n − 2 varia´veis e assim por diante. No caso de agrupamento de zeros, deve-se tomar cuidado com a relac¸a˜o entre uma regia˜o marcada e como a varia´vel aparece na equac¸a˜o. Por exemplo, na figura 11 a regia˜o a + c ocorre onde esta´ marcado a no mapa, e na˜o onde esta´ marcado a. A explicac¸a˜o para este fenoˆmeno e´ a mesma dos maxtermos na tabela verdade terem as varia´veis barradas em relac¸a˜o aos mintermos corres- pondentes. Isto torna a ana´lise do mapa por agrupamento de 0’s bem menos intuitiva. f5 a b c d 0 1 3 2 4 5 7 6 12 13 15 14 8 9 11 10 1 0 00 1 1 10 1 1 11 1 0 11 Figura 12: Exemplo de equac¸a˜o minimizada por agrupamento de 1’s e de 0’s. A partir do mapa de Karnaugh, podemos obter a equac¸a˜o na forma produto de somas, juntando os zeros; ou na forma soma de produtos, juntando os uns. 8 As duas formas obtidas da func¸a˜o f5 da figura 12 sa˜o mostradas abaixo e apesar de aparentarem ser diferentes, elas sa˜o, de fato, equivalentes. f5 = (a + b + c) ( a + b + d ) ( a + c + d ) ( a + b + c + d ) (1) f5 = a b + a c + b d + c d + a b c (2) Comec¸ando da equac¸a˜o na forma produto de somas, multiplicamos os dois primeiros pareˆnteses e os dois u´ltimos e obtemos: f5 = ( a + a b + a d + b + b d + b c + a d + c d ) · · (a b + a c + a d + a c + b c + c d + a d + b d + c d + d) (3) Retirando os va´rios termos redundantes, chega-se a: f5 = ( a + b + c d ) ( a b + a c + d + a c + b c ) (4) Multiplicando novamente, obteˆm-se: f5 = a b + a c + a d + a b c + a b c + b d + a b c + a b c d + c d + a c d + b c d (5) Onde novamente temos va´rios termos redundantes que simplificam em: f5 = a b + a c + a d + b d + a b c + c d (6) Note que podemos usar o teorema do consenso nos segundo, terceiro e u´ltimo termo, retirando enta˜o o terceiro termo. Com isso, obte´m-se a equac¸a˜o (2) obtida por soma de produtos. Mostra-se enta˜o que a equac¸a˜o (1) e´ equivalente a` (2), q.e.d.. 4 Equac¸o˜es e circuitos na˜o-completamente espe- cificados. E´ bastante comum a situac¸a˜o de que determinadas entradas de um circuito lo´gico nunca ocorram. Como exemplo imagine-se uma esteira carregando uma caixa de um lado para o outro, com sensores de fim de curso em ambas extremidades: se do lado esquerdo e sd do lado direito. No funcionamento normal do sistema estes dois sinais nunca sera˜o acionados ao mesmo tempo; nesta situac¸a˜o na˜o importa qual e´ o resultado do circuito para se = sd = 1, ja´ que esta situac¸a˜o nunca vai existir, portanto na˜o e´ necessa´rio especificar um valor de sa´ıda para esta situac¸a˜o. Diz-se enta˜o que este circuito e´ na˜o-completamente especificado. A tabela 1 mostra o exemplo de um sinal imagina´rio z determinado em func¸a˜o de a, se e sd. Neste exemplo, sempre que se = sd = 1 a sa´ıda z e´ na˜o- especificada, ou seja, z na˜o-importa nestas situac¸o˜es. Neste texto utilizaremos a notac¸a˜o ×3 para identificar as situac¸o˜es que um sinal na˜o importa. Pode-se descrever uma func¸a˜o lo´gica na˜o-completamente especificada na forma soma de mintermos ou produto de maxtermos utilizando a notac¸a˜o d(· · · ), que vem do ingleˆs don’t care. Desta forma o sinal z pode ser descrito por: z = ∑ m (2, 4, 6) + d(3, 7) = ∏ M (0, 1, 5) + d(3, 7) (7) 3“dontchiquer, bicho.” 9 a se sd z 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 × 1 0 0 1 1 0 1 0 1 1 0 1 1 1 1 × Tabela 1: Exemplo de uma func¸a˜o na˜o completamente especificada. As sa´ıdas na˜o especificadas sa˜o identificadas por ×. Outras notac¸o˜es comumente usadas sa˜o *, - ou d. Um × na sa´ıda pode ser implementado como um 1 ou um 0, e na˜o se sabe a princ´ıpio qual destes dois valores gerara´ uma soluc¸a˜o mais minimizada, logo para obter o menor circuito poss´ıvel o engenheiro deveria obter as equac¸o˜es considerando que cada × pode ser 1 ou 0 e checar qual e´ o menor circuito final. Obviamente para problemas com muitos ×’s isto se torna impratica´vel, pois seria necessa´rio implementar 2k circuitos, onde k e´ o nu´mero de ×’s presentes. Felizmente o mapa de Karnaugh facilita bastante a implementac¸a˜o de circui- tos na˜o-completamente especificados, pois podemos considerar se determinado × e´ 1 ou 0 visualmente, na hora da implementac¸a˜o. z a se sd 0 1 3 2 4 5 7 6 1 0 1× 0 0 1× Figura 13: Mapa de Karnaugh da func¸a˜o z. Ao minizarmos a func¸a˜o z pelo mapa de Karnaugh (figura 13) obtemos 2 func¸o˜es: z′ = se + sda (pelos 1’s) (8) z′′ = sd (se + a) (pelos 0’s) (9) Note que, neste caso, estas duas equac¸o˜es na˜o sa˜o equivalentes; ou seja, na˜o e´ poss´ıvel sair de uma delas e chegar na outra por a´lgebra de Boole, como ja´ foi feito na sec¸a˜o 3 para f5. Isto porque na minimizac¸a˜o por soma de produtos foi considerado que os ×’s eram 1, enquanto que em produto de somas eles foram considerados como sendo 0. Esta situac¸a˜o e´ bastante comum ao minimizar func¸o˜es na˜o completamente especificadas, pore´m, apesar de estranho, na˜o causa nenhum problema, ja´ que as diferenc¸as nas sa´ıdas ocorrem justamente quando na˜o importa o valor da sa´ıda, seja por que aquela entrada nunca ocorre ou por outra raza˜o qualquer. 10
Compartilhar