Blog

Mapa de Karnaugh Jo -o Paulo Cerquinho Cajueiro a 24 de agosto de 2009 O chamado mapa de Karnaugh foi desenvolvido pelo matem ‘ tico e f’ a Bico Maurice Karnaughl em 1953, enquanto trabalhava no grupo de pesquisas da empresa Bell. Este m’ todo ‘ uma poderosa ferramenta para circuitos I • gicos, e e o pois permite simplificar equaa -es booleanas apenas agrupando ‘ reas comuns, co a o que nosso c • rebro consegue fazer bem mais rapidamente do que aplicando e postulados e teoremas a equaa -es. o De diagramas de Ven Utilizar os teoremas simplificar equaa -es que seja bem prov•v oriá Sv. içx to view de Boole para o que faz com o processo. Mas j vimos que as equa. -es da Igebra de Boole podem ser a co a visualizadas atraW s de um diagrama de Venn. Isto exemplificado na figura 1, e e que apresenta um diagrama de Venn de 3 vari ‘ veis com os respectivos mintermos a associados a cada uma das regi -es. o abc abc abc abc b Regi -es das vari ‘veis o a (b) Sub-regi-es dos mintermos o Figura 1: Diagrama Venn com 3 vari ‘veis. Utilizando os diagramas, • f • cil obter a equas-o simplificada da fun,-o. por e a ca ca exemplo, considere-se a funa-o fl = abc abc + abc. Desenhando esta fun,-o ca ca num diagrama de Venn (figura 2), fica ‘bvio que podemos simplific’-la para o afl = (a + c)b. O problema aparece quando acrescentamos mais 1 vari ‘vel. Como fazer um a diagrama definindo todas as 16 possibilidades? A solu,-o para isto ‘ desenhar cae ele atualmente (entre outras coisas), escreve o blog unclejo. blogspot. com. Esta informa. -o depende em se acreditar ou n -o na wikipedia. a a 1 Aparentemente Figura 2: Diagrama Venn definindo a regi-o dada por fl = abc + abc + abc = a (a + c)b. as regi -es como quadrados, e n -o como c’ o a Irculos, assim como foi feito na figura 3. No lado direito desta figura temos at’ a representa. -o do lado de fora do e ca diagrama propriamente dito de que regi -es correspondem a que vari ‘veis. o a d abcd abcd abcd abcd abcd abcd abcd abcd abcd abcd abcd abcd abcd abcd b abcd abcd abcd abcd abcd abcd abcd a Karnaugh o Note na figura 4 que os vizinhos de cada casa em um mapa de Karnaugh s -o a tais que apenas muda uma vari ‘vel de cada vez.

Por exemplo, da casa 5 para a a casa 1 (acima) s’ muda o b, da 5 para a 7 (direita) s’ muda o c, da 5 para ao 0 4 (esquerda) s’ muda o d e da 5 para a 13 (abaixo) s” muda o a. Isto v’ lido o o e a para todas as casas. E poss’ aplicar isto inclusive para as casas nas bordas e nas quinas, pois Ivel podemos considerar que o mapa d’ a volta em si mesmo. Deste modo consideraa se a casa 6 como vizinha da 4 e s’ muda a vari ‘vel c, e a casa 10 vizinha da 2 eoas’ muda a vari’vel a. o a Isto nos permite agrupar termos visualmente. Por exemplo, considere a fun. o f2 = ca m (3, 7, 12, 13) e seu respectivo mapa de karnaugh na figura 5. f2 = m (3, 7, 12, 13) doo 01 05 1 13 09 13 11 c02 060 140 10 bacd abc a 0411208 Figura 5: Funs-o f2 e simplificas -o por agrupamento de casas vizinhas. ca ca Analisando a fum -o f2 por “Igebra de Boole, emos que podemos simplific ca a a la aplicando o teorema T6. E observando no mapa de Karnaugh, os termos que s-o unidos e simplificados s -o ju T6. E observando no mapa de Karnaugh, os termos que s -o unidos e simplificados s -o justamente os vizinhos. a f2 = abcd + abcd + abcd + abcd f2 = acd + abc Ou seja, o agrupamento de 2 casas vizinhas corresponde simplifica, -o de a ca uma vari’vel atrav’s da aplica, -o to teorema T6. gasta ver no pr’ prio mapa a e ca o quais s -o as vari”veis que n -o mudam dentro do agrupamento. a a a para simplificar 2 ou mais vari ‘veis basta aplicar o teorema repetidas vezes. Simplifiquemos a funs-o f3 (vide figura 6), por exemplo. Basta agruparmos a ca funa-o de duas em duas casas e 2 grupos vizinhos de duas casas viram um unico ca grupo de 4 casas, retirando mais uma vari ‘ vel da funa -o. ca f3 = abcd + abcd + abcd + abcd= abc + abc E = ac f3 00 04a 1 12 1801 051 13 015011 c02 060140 10bf30001 05 13 0411218 Figura 6: Agrupamento das casas da fun,-o E . ca Este mesmo procedimento pode ser mostrado para agrupamentos de 8 casas (simplificando ent- 0 3 vari • vels) ou 1 5 casas (simplificando 4 vari ‘veis. A figura a a a 7 mostra algumas possibilidade nt-0 3 vari ‘veis) ou 16 casas (simplificando 4 vari ‘ veis. A figura a a a 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 vari ‘veis um a agrupamento de 1 6 casas seria todo o mapa e corresponderia a fun. -0 1. ca 2 Exemplos utilizados tamb’m no artigo original de Karnaugh: “The map method for e synthesis of combinational logic circuits”, de 1953. 4 10 dOOOOc abd 0000bOaOOO d10001000c abd0100bOaOOO dOOOOOOOOC bcd1100boa001 doooooooocooboo (a) agrupamentos de 2 casas abOOOObOa001 0111001 d1001c10b01 (c) Agrupamentos de 8 casas Figura 7: Exemplos de mapas de karnaugh com os correspondentes produtos alg bricas. e 2. Mapas de n vari • veis a Claro que um mapa de Karnaugh pode ser feito com um n mero menor de u vari veis. Para tanto basta simplesmente sair dividindo o mapa. Tem-se apenas a que lembrar que uma casa deve ter n vizinhas, j’ que a simplifica, -o de uma a ca vari ‘vel corresponde a unir uma casa com a vizinha. Isto ‘ mostrado na figura a e 8 para mapas de 2, 3 e 4 vari’ veis. ad 015139371511261410 013015372 2 trabalhar com um mapa a a e tridimensional como exemplifica a figura g que mostra um mapa de Karnaugh de 5 vari’veis, note ue cada casa tem 6 vizinhos: 4 no plano (como no mapa a de 4 vari e 2 verticais. Na pr tica, um mapa de 5 vari • veis desenhado como 2 de 4 vari ‘veis, sendo a a e a um com uma vari ‘vel (em geral a mais significativa) sendo O e o outro com a a mesma vari vel sendo 1. Usa-se este mesmo princ• a Ipio para mapas de 6 vari veis a ou mais vari • veis, como pode ser visto na figura 10. a 6 04513911 15 101281714362 d 16 2021 29 25 2731 26 282417 23 19 22 30 18 50 48 52 53 61 57 59 63 58 60 56 49 55 51 54 62 PAGF 32 33 35 34 2021 23 22 2829 31 30 24 25 27 26 121315148911 36 37 39 38 4445 47 464041 43 42 061 63 62 56 57 59 58 (a) 5 vari veis a (b) 6 vari ‘veis a Figura 10: Mapas de Karnaugh de 5 e 6 vari ‘veis. 7 agrupamento de zeros, deve-se tomar cuidado com a rela, -o entre ca uma regi -o marcada e como a vari ‘vel aparece na equa. -o. Por exemplo, na a a ca figura 11 a regi-o a + c ocorre onde est• marcado a no mapa, e n -o onde est’ a a a a marcado a. A explica. -o para este fena meno ‘ a mesma dos maxtermos na ca o e tabela verdade terem as vari • veis barradas em relas -o aos mintermos corresa ca pondentes. Isto torna a an ‘ lise do mapa por agrupamento de CYs bem menos a intuitiva. f5 1 0216014010b b+c d