Sistemas Digitais (Bolonha), 2007, Iouliia Skliarova
Termo mínimo de ordem i ( mi ) - produto lógico das n variáveis booleanas
independentes, em que cada uma delas aparece uma e uma só vez, não
complementada ou complementada consoante toma valores 1 ou 0,
respectivamente, na i-ésima combinação das variáveis independentes.
Termo máximo de ordem i ( Mi ) - soma lógica das n variáveis booleanas
independentes, em que cada uma delas aparece uma e uma só vez, não
complementada ou complementada consoante toma valores 0 ou 1,
respectivamente, na i-ésima combinação das variáveis independentes.
0
1
2
3
4
5
6
7
x
0
0
0
0
1
1
1
1
y
0
0
1
1
0
0
1
1
z
0
1
0
1
0
1
0
1
f(x,y,z)
0
1
0
0
1
1
1
1
m0  x  y  z
M0  x  y  z
m5  x  y  z
M5  x  y  z
mi  Mi
i  0,1,...,2n 1
Sistemas Digitais (Bolonha), 2007, Iouliia Skliarova
Qualquer função f(x0, x1,...,xn-1) pode ser representada na forma seguinte:
f ( x0 , x1,...,xn1 )  x0  f (0, x1 ,...,xn1 )  x0  f (1, x1 ,...,xn1 )
Indução perfeita:
Se x0 = 0 temos:
f (0, x1 ,...,xn1 )  1 f (0, x1,...,xn1 )  0  f (1, x1 ,...,xn1 )
Se x0 = 1 temos:
f (1, x1,...,xn1 )  0  f (0, x1 ,...,xn1 )  1 f (1, x1,...,xn1 )
Sistemas Digitais (Bolonha), 2007, Iouliia Skliarova
Estendendo para 2 variáveis:
f ( x0 , x1 ,...,xn )  x0  f (0, x1,...,xn )  x0  f (1, x1 ,...,xn ) 
 x0  x1  f (0,0, x2 ,.., xn )  x0  x1  f (0,1, x2 ,.., xn ) 
 x0  x1  f (1,0, x2 ,.., xn )  x0  x1  f (1,1, x2 ,.., xn )
Continuando a expansão até xn pode-se obter a 1ª forma canónica:
2n 1
f ( x0 , x1 ,...,xn1 )   mi  f i
fi  f ((x0 , x1 ,.., xn )  i)
i 0
Forma normal disjuntiva
DNF – disjunctive normal form
Sistemas Digitais (Bolonha), 2007, Iouliia Skliarova
2ª forma canónica:
2 n 1
2 n 1
i 0
i 0
f ( x0 , x1 ,..., xn )  f ( x0 , x1 ,..., xn )   f i  mi   ( f i  M i )
Forma normal conjuntiva
CNF – conjunctive normal form
3ª forma canónica:
2 n 1
2 n 1
i 0
i 0
f ( x0 , x1 ,..., xn )  f ( x0 , x1 ,..., xn )   f i  mi   f i  mi
4ª forma canónica:
2 n 1
2 n 1
i 0
i 0
f ( x0 , x1 ,..., xn )  f ( x0 , x1 ,..., xn )   f i i  M i   f i  M i
Sistemas Digitais (Bolonha), 2007, Iouliia Skliarova
2n 1
1ª forma canónica:
f ( x0 , x1 ,...,xn1 )   mi  f i
AND-OR
i 0
2 n 1
2ª forma canónica:
f ( x0 , x1 ,..., xn )   ( f i  M i )
OR-AND
i 0
2 n 1
3ª forma canónica:
f ( x0 , x1 ,..., xn )   f i  mi
NAND-NAND
i 0
2 n 1
4ª forma canónica:
f ( x0 , x1 ,..., xn )   f i  M i
i 0
Sistemas Digitais (Bolonha), 2007, Iouliia Skliarova
NOR-NOR
Exemplo:
Determinar as formas canónicas da função f(x,y,z)
f ( x, y, z )  x  y  z
1ª:
f ( x, y, z)  x  y  ( z  z )  z  ( x  x )  ( y  y ) 
 x y z  x y z  x y z  x y z  x  y z  x  y z 
 x y z  x y z  x y z  x  y z  x  y z
2ª:
f ( x, y, z )  ( x  z )  ( y  z ) 
 (x  y  z)  (x  y  z)  (x  y  z)  (x  y  z) 
 (x  y  z)  (x  y  z)  (x  y  z)
3ª:
f ( x, y, z)  x  y  z  x  y  z  x  y  z  x  y  z  x  y  z 
 x y z x y z  x y  z  x  y z  x  y  z
4ª:
f ( x, y, z)  ( x  y  z )  ( x  y  z )  ( x  y  z ) 
 (x  y  z)  (x  y  z)  (x  y  z)
Sistemas Digitais (Bolonha), 2007, Iouliia Skliarova
Exemplo:
Determinar as formas canónicas da função f(x,y,z)
f ( x, y, z )  x  y  z
0
1
2
3
4
5
6
7
x
0
0
0
0
1
1
1
1
y
0
0
1
1
0
0
1
1
z
0
1
0
1
0
1
0
1
f(x,y,z)
1
0
1
0
1
0
1
1
1ª:
f ( x, y, z)   m(0,2,4,6,7)
2ª:
f ( x, y, z)   M (1,3,5)
3ª:
4ª:
f ( x, y, z )   m(0,2,4,6,7)
f ( x, y, z )   M (1,3,5)
Sistemas Digitais (Bolonha), 2007, Iouliia Skliarova
Condições irrelevantes – combinações das variáveis de entrada para as
quais a saída não se conhece ou é irrelevante.
R
S
G
G
R
(verde) (vermelho)
0
0
0
1
1
0
1
1
S
(som)
0
0
1
x
x – don’t care
O circuito real para todas as condições irrelevantes vai produzir nas saídas
quaisquer valores válidos (0 ou 1).
O projectista tem a liberdade de atribuir valores 0 ou 1 às saídas respectivas.
Sistemas Digitais (Bolonha), 2007, Iouliia Skliarova
G
R
(verde) (vermelho)
0
0
0
1
1
0
1
1
1ª:
2ª:
3ª:
4ª:
S
(som)
0
0
1
x
S (G, R)   m(2)   d (3)  G  R  G  R
S (G, R)   M (0,1)   D(3)  (G  R)  (G  R )  (G  R )
S (G, R)   m(2)  d (3)  G  R  G  R
S (G, R)   M (0,1)  D(3)  (G  R)  (G  R )  (G  R )
Sistemas Digitais (Bolonha), 2007, Iouliia Skliarova
f ( x, y, z)  x  y  z  x  y  z  x  z  y  z  y  z
Aplicando o teorema de adjacência a dois primeiros termos:
f ( x, y, z)  x  y  x  z  y  z  y  z
4 termos, 8 literais
f ( x, y, z)  x  y  z  y  z  z  ( x  y  x  y ) 
(absorção, simplificação)
 y  z  z  ( y  x  y) 
(complementação, elemento
 yz  z 
absorvente)
 y  z 2 literais
(simplificação)
• Expressões irredutíveis podem não ser mínimas
• Pode existir mais que uma expressão mínima
• O processo de simplificações está sujeito a erros
Sistemas Digitais (Bolonha), 2007, Iouliia Skliarova
Para circuitos a dois níveis pode-se estabelecer seguintes critérios de
minimização:
•
Minimizar o número de termos (número de portas do 1º nível do
circuito e número de entradas no 2º nível do circuito).
•
Minimizar o número de literais (número de entradas nas portas do 1º
nível do circuito).
•
Os métodos de minimização não consideram o custo de inversão das
variáveis de entrada.
Exemplos:
f(a,b,c,d) a  c  d  b  d  a  c
3 termos, 7 literais
f (a, b, c, d )  (a  c  d )  (b  c  d )  (a  b  c )  (a  c  d ) 4 termos, 12 literais
g(a,b,c) a  b  a  c
2 termos, 4 literais
g (a, b, c)  a  (b  c )
2 termos, 3 literais
Sistemas Digitais (Bolonha), 2007, Iouliia Skliarova
A soma de produtos mínima da função f é a soma de produtos que tem o
número mínimo de produtos e o número mínimo de literais (comparando com
todas as outras somas de produtos que possam existir com o mesmo número
de produtos).
Exemplo:
f(a,b,c,d) a  b  c  b  c  d  a  c  d  a  c  d
4 termos, 12 literais
f(a,b,c,d) a  b  c  b  c  d  a  c  d
3 termos, 9 literais
f(a,b,c,d) a  c  d  b  c  d  a  b  c
3 termos, 9 literais
Todos os métodos de minimização são baseados na aplicação do teorema
de adjacência:
x,yB x  y + x y = x
(x + y)  (x +y) = x
Sistemas Digitais (Bolonha), 2007, Iouliia Skliarova
Um mapa de Karnaugh é a representação gráfica da tabela de verdade
de uma função lógica.
x
x
x
x
0
x
0
y
1
1
y
z
0
0
0
xy
1
0
2
1
3
z
1
1
00
01
11
0
2
6
4
1
3
7
5
y
x
xy
zw
00
01
11
z
10
00
01
11
10
0
4
12
8
1
5
13
9
3
7
15
11
2
6
14
10
w
y
Sistemas Digitais (Bolonha), 2007, Iouliia Skliarova
10
f ( x, y, z)  x  y  z  x  y  z  x  z  y  z  y  z
x
0
1
2
3
4
5
6
7
x
0
0
0
0
1
1
1
1
y
0
0
1
1
0
0
1
1
z f(x,y,z)
0
0
1
1
0
1
1
1
0
0
1
1
0
1
1
1
f ( x, y, z )  y  z
xy
z
z
00
01
0
00
1
1
11
1
11
10
2
16
0
3
17
1
4
5
y
2 implicantes primos
4 células distintas
2 implicantes primos essenciais
Sistemas Digitais (Bolonha), 2007, Iouliia Skliarova
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
x
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
y
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
z
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
w f(x,y,z,w)
0
0
1
1
0
0
1
1
0
0
1
0
0
0
1
0
0
0
1
1
0
0
1
1
0
1
1
1
0
1
1
0
x
zw
xy
00
01
00
00
0
01
11
0
11
13
0
10
02
0
z
11
10
4
1 12 0
8
5
1 13 1
9
7
0 15 111
6
1 14 010
w
y
4 implicantes primos
4 células distintas
2 implicantes primos essenciais
f ( x, y, z, w)  y  w  x  y  w  x  y  z
Sistemas Digitais (Bolonha), 2007, Iouliia Skliarova
b
bc
de
a=0
00
01
00
00
0
01
01
0
13
1
02
1
11
d
10
11
f (a, b, c, d , e)  a  b  d  e  a  c  d 
 a b  d e  a  d e  a  d c e
10
4
0 12 0
8
5
0 13 0
9
7
1 15 111
6
1 14 010
e
2 implicantes primos
8 células distintas
c
2 implicantes primos essenciais
b
bc
de
a=1
00
01
11
10
00
016 0 20 0 28 0 24
01
017 0 21 0 29 0 25
11
119 1 23 1 31 127
10
018 1 22 1 30 026
d
e
f (a, b, c, d , e)  d  e  c  d
c
Sistemas Digitais (Bolonha), 2007, Iouliia Skliarova
1. Preencher o mapa de Karnaugh.
2. Encontrar todos os implicantes primos.
Uma função p implica a função lógica f se em todos os casos quando p = ‘1’,
f também é igual a ‘1’.
O implicante primo da função f é um produto p que implica f, tal que se
removêssemos um literal do p o produto resultante já não vai implicar f.
Num mapa de Karnaugh, o implicante primo é um conjunto de 2n células
adjacentes que contêm valores ‘1’ e tais que se tentássemos expandir o
conjunto até 2n+1 células este passará a incluir células com ‘0’.
3. Marcar no mapa todas as células distintas – células que só são cobertas
por um único implicante primo.
4. Encontrar todos os implicantes primos essenciais – implicantes primos que
cobrem uma ou mais células distintas.
5. Incluir na soma mínima todos os implicantes primos essenciais e dos
restantes implicantes primos escolher o menor número daqueles que
contêm menos literais.
Sistemas Digitais (Bolonha), 2007, Iouliia Skliarova
O produto de somas mínimo da função f é o produto de somas que tem o
número mínimo de somas e o número mínimo de literais (comparando com
todos os outros produtos de somas que possam existir com o mesmo número
de somas).
A minimização pode ser feita aplicando o princípio da dualidade e analisando
células com ‘0’ o mapa de Karnaugh.
f ( x, y, z)  x  y  z  x  y  z  x  z  y  z  y  z
x
0
1
2
3
4
5
6
7
x
0
0
0
0
1
1
1
1
y
0
0
1
1
0
0
1
1
z f(x,y,z)
0
0
1
1
0
1
1
1
0
0
1
1
0
1
1
1
xy
z
z
00
01
0
00
1
1
11
1
f ( x, y, z )  y  z
Sistemas Digitais (Bolonha), 2007, Iouliia Skliarova
11
10
2
16
0
3
17
1
y
4
5
No mapa de Karnaugh as combinações irrelevantes deverão assumir valores
que permitem reduzir o número de literais em cada um dos implicantes primos
(i.e. permitem aumentar as dimensões de cada conjunto de 2n células).
0
1
2
3
4
5
6
7
x
0
0
0
0
1
1
1
1
y
0
0
1
1
0
0
1
1
z f(x,y,z)
0
0
1
0
0
1
1
1
0
x
1
x
0
x
1
x
x
xy
z
z
00
01
0
00
1
1
01
1
11
2
1
x6
0
x
3
1
x7
0
x
y
f ( x, y, z )  y
Sistemas Digitais (Bolonha), 2007, Iouliia Skliarova
10
4
5
Represente nas formas canónicas a função f:
f ( x, y, z )  x  y  x  z  y  z
f ( x, y, z)   m(0,2,3,6,7) x  y  z  x  y  z  x  y  z  x  y  z  x  y  z
f ( x, y, z)   M (1,4,5)  ( x  y  z )  ( x  y  z)  ( x  y  z )
f ( x, y, z )   m(0,2,3,6,7)  x  y  z  x  y  z  x  y  z  x  y  z  x  y  z
f ( x, y, z )   M (1,4,5)  ( x  y  z )  ( x  y  z )  ( x  y  z )
Obtenha a forma mínima desta função na soma de produtos e produto de somas
com o método de Karnaugh.
f ( x, y, z )  y  x  z  ( x  y)  ( y  z )
Sistemas Digitais (Bolonha), 2007, Iouliia Skliarova