Arquitetura e Organização de Computadores

Arquitetura e Organização de Computadores

Nome: Thaís Cristina Turma: ADS – B

Mapas de Karnaugh

Os mapas são diagramas constituídos por quadrados cada um correspondendo a um minterm da função booleana representada. Nos diagramas dois minterms adjacentes diferem apenas no valor de um dos literais.

Vamos supor que a expressão mais simples, como soma de produtos, é a que tem um número mínimo de produtos e o menor número de literais em cada produto. Para isso usam-se propriedades booleanas, como [pic 1]B + AB = ([pic 2] + A)B = B.

Duas variáveis

Existem 4 minterms para uma função booleana de duas variáveis. Então o mapa é constituído 4 quadrados.

m0 m1 m2 m3

A[pic 3] B 0 1 0 [pic 4][pic 5] [pic 6]B 1 A[pic 7] AB

Uma função é representada escrevendo um 1 nos quadrados correspondentes a cada um dos minterms da sua representação como soma de minterms.

Para as funções f (A, B) = A + B e g(A, B) = AB temos os mapas:

f(A,B)=A+B			g(A,B)=AB
A[pic 8] B 0   1 0     1 1 1   1			A[pic 9] B 0   1 0       1     1

Na realidade a soma de minterms para A + B é [pic 10]B + A[pic 11] + AB. Agora o facto de estarem 1's adjacentes na coluna do B e na linha do A permitem que a expressão seja simplificada para a forma A + B, isto é,

[pic 12]B + A[pic 13] + AB = ([pic 14]B + AB) + (A[pic 15] + AB) = ([pic 16] + A)B + A([pic 17] + B) = B + A 

Três variáveis

Como vimos, existem 8 minterms para funções booleanas de 3 variáveis. Os mapas vão ter 8 quadrados. Note que a disposição dos mi não segue a ordem numérica, a regra é que dois quadrados adjacentes só diferem no valor de um literal.

m0 m1 m3 m2 m4 m5 m7 m6

A [pic 18]BC 00 01 11 10 0 [pic 19][pic 20][pic 21] [pic 22][pic 23]C [pic 24]BC [pic 25]B[pic 26] 1 A[pic 27][pic 28] A[pic 29]C ABC AB[pic 30]

A representação de f (A, B, C) = m0 + m2 + m4 + m7 fica o 1 para ABC está isolado portanto tem de aparecer no final. Supondo que os mapas são circulares, o 1 de [pic 31]B[pic 32] está a adjacente ao de [pic 33][pic 34][pic 35]fazendo com que [pic 36][pic 37](B + [pic 38])= [pic 39][pic 40]. De igual modo, os 1's na primeira coluna levam a que [pic 41][pic 42](A + [pic 43]) = [pic 44][pic 45], e portanto a função pode simplificar para [pic 46][pic 47]+ [pic 48][pic 49]+ ABC.

A [pic 50]BC	00	01	11	10
0	1			1
1	1		1