Mapa de karnaugh

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 ısico Maurice Karnaugh1 em 1953, enquanto trabalhava no grupo de pesquisas da empresa Bell. Este m´todo ´ uma poderosa ferramenta para circuitos l´gicos, e e o pois permite simplificar equa¸˜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 equa¸˜es. co

1

De diagramas de Venn a Mapas de Karnaugh

Utilizar os teoremas e postulados da ´lgebra de Boole para simplificar equa¸˜es a co ´ bastante tedioso, o que faz com que seja bem prov´vel que hajam erros e a no processo. Mas j´ vimos que as equa¸˜es da ´lgebra de Boole podem ser a co a visualizadas atrav´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

c abc abc abc abc

a

b

abc

abc abc

abc

(a) Regi˜es das vari´veis o a

(b) Sub-regi˜es dos mintermos o

Figura 1: Diagrama Venn com 3 vari´veis. a Utilizando os diagramas, ´ f´cil obter a equa¸˜o simplificada da fun¸˜o. Por e a ca ca exemplo, considere-se a fun¸˜o f1 = abc + abc + abc. Desenhando esta fun¸˜o ca ca num diagrama de Venn (figura 2), fica ´bvio que podemos simplific´-la para o a f1 = (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 ca e ele atualmente (entre outras coisas), escreve o blog unclej0.blogspot.com. Esta informa¸˜o depende em se acreditar ou n˜o na wikipedia. ca a
1 Aparentemente

1

f1

Figura 2: Diagrama Venn definindo a regi˜o dada por f1 = abc + abc + abc = a (a + c)b. as regi˜es como quadrados, e n˜o como c´ o a ırculos, assim como foi feito na figura 3. No lado direito desta figura temos at´ a representa¸˜o do lado de fora do e ca