Buscar

4 - Mintermos maxtermos Karnaugh

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Unibratec – Prof. Remy Eskinazi
Soma de Produtos
Soma de produtos é uma forma de representação de funções Booleanas constituida pela aplicação da operação lógica OU sobre um conjunto de termos formados pela operação E:
Z = AB + AC + DF
Termo produto
Soma de produtos
2 níveis lógicos
Unibratec – Prof. Remy Eskinazi
Produto de Somas
O produto de somas é outra forma de representação de funções Booleanas caracterizada pela aplicação da operação E sobre um conjunto de operações OU sobre as entradas
2 níveis lógicos
Z = (A + B)(A + C)(D + F)
Termo soma
Produto de Somas
Unibratec – Prof. Remy Eskinazi
Mintermos
Um mintermo é um termo produto que vale 1 em um ponto do domínio de uma função Booleana
É definido por um produto (AND) onde cada variável aparece apenas uma vez, direta ou complementada
Mintermo ABC
Unibratec – Prof. Remy Eskinazi
Maxtermos
Um maxtermo é um termo soma que vale 0 (zero) em um ponto do domínio da função
É determinado por uma disjunção (OR) onde cada variável aparece apenas uma vez, direta ou complementada
Maxtermo (A + B + C)
Unibratec – Prof. Remy Eskinazi
Formas Canônicas
Uma tabela verdade é uma assinatura que identifica unívocamente uma função Booleana
Espressões Booleanas diferentes podem representar uma mesma função Booleana
F = A + BC
F = A B + A B + BC
F = A( B + C + B C) + B C
Tabela Verdade
Espressões Booleanas
Unibratec – Prof. Remy Eskinazi
Formas Canônicas Dois Níveis
Formas Canônicas são representações (assinaturas) únicas de funções Booleanas
Ex: uma soma padrão de produtos é uma forma canônica
F = A B C + A B C + A B C + A B C + A B C
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
F' = A B C + A B C + A B C
OR de 1’s
Unibratec – Prof. Remy Eskinazi
Formas Canônicas Dois Níveis
Formas Canônicas são representações (assinaturas) únicas de funções Booleanas
Ex: produto de somas é outra forma canônica
F = (A + B + C) (A + B + C) (A + B + C)
0 0 0
0 0 1
0 1 0
F = (A + B + C ) (A + B + C ) (A + B + C) (A + B + C ) (A + B + C)
AND de 0’s 
Unibratec – Prof. Remy Eskinazi
Formas Canônicas Dois Níveis
Notação para soma de mintermos:
F(A,B,C) = (1, 3, 5, 7) 
			= m1 + m3 + m5 + m7
			= A B C + A B C + A B C + A B C
Notação para produto de maxtermos:
F(A,B,C) = (0, 2, 4, 6)
			= M0·M2·M4·M6
			= (A + B + C) (A + B + C) ( A + B + C) (A + B + C)
Unibratec – Prof. Remy Eskinazi
Simplificação de Soma de Mintermos
Usando métodos algébricos:
F(A,B,C) = ∑(3,4,5,6,7)
			= m3 + m4 + m5 + m6 + m7
			= A' B C + A B' C' + A B' C + A B C' + A B C
			= A B' (C + C') + A' B C + A B (C' + C)
			= A B' + A' B C + A B
			= A (B' + B) + A' B C
			= A + A' B C
			= A + B C
Implementação
Unibratec – Prof. Remy Eskinazi
Mintermos x Maxtermos
É possível obter um produto de maxtermos a partir de uma soma de mintermos e vice-versa aplicando De Morgan sobre o complemento da função
F(A,B,C) = (1, 2, 3, 5, 7) = A’ B’ C + A’ B C’ + A B’ C + A B C
	 F ’ (A,B,C) =  (0, 4, 6) = A’ B’ C’ + A B’ C’ + A B C’
	 F (A,B,C) = (F ’ (A,B,C) )’ = (A’ B’ C’ + A B’ C’ + A B C’)’
			= (A + B + C’)(A + B’ + C’)(A’ + B’ + C’)
			 = (1, 3, 7)
Unibratec – Prof. Remy Eskinazi
Funções Incompletas
São funções para as quais algumas combinações de valores das entradas nunca ocorrem
Ex: acionador de display de 7 segmentos para dígitos BCD
 4 entradas -> 16 combinações
 apenas 10 utilizadas
 6 combinações nunca ocorrem
 são denominadas irrelevantes
(don’t cares)
 podem ser utilizadas para simplificar a lógica
Unibratec – Prof. Remy Eskinazi
Funções Incompletas
Funções incompletas mapeiam pontos do domínio da função em 3 valores possíveis:
F(A, B, C, D)  { 0, 1, X }
Os domínios de pontos onde F vale { 0, 1, X} são denominados, respectivamente, de:
	F1 = {m0, m2, m3, m5, m6, m7, m8, m9 }
	Fx = {i10, i11, i12, i13, i14, i15 }
	F0 = {M1, M4 }
F pode ser descrita definindo-se dois desses três conjuntos:
F (A, B, C, D) = F1  Fx ou F1  F0 ou F0  Fx 
Unibratec – Prof. Remy Eskinazi
Minimização Lógica Dois Níveis
Manipulação algébrica: 
Difícil determinar a ordem e quais transformações aplicar
Como saber se atingiu-se a melhor solução ?
Ferramentas de auxílio:
Não conseguem tratar problemas grandes de forma exata 
Baseiam-se em heurísticas e critérios de custo
Resultados bastante bons em lógica dois níveis
Métodos manuais apenas para fins didáticos ou funções muito simples
Unibratec – Prof. Remy Eskinazi
Minimização Lógica Dois Níveis
Idéia base: aplicação de distribuição e complemento
A(B + B’) = A
Dentro de F1: 
B varia enquanto
A não muda
Resultado: B é eliminado!
F = A B' + A B = A (B' + B) = A
G = A' B' + A B' = (A' + A) B' = B'
Dentro de G1: 
A varia enquanto
B não muda
Resultado: A é eliminado!
Unibratec – Prof. Remy Eskinazi
Cubos
 O espaço Booleano n-dimencional pode ser visualizado espacialmente
 Produtos de literais são chamados de cubos
Cubo 1
X
0
1
Cubo 2
Unibratec – Prof. Remy Eskinazi
Visualização de Cubos
Cubo 3
XYZ
X
011
010
000
001
111
110
100
101
Y
Z
 Pontos adjacentes diferem em 1 bit
 Todos os pontos da função estão dispostos
 sobre uma face
 Y e Z variam enquanto X permanece 
 inalterado: Y e Z podem ser eliminados da
 expressão
F(X, Y, Z) = ∑(4,5,6,7) = X
 
Unibratec – Prof. Remy Eskinazi
Mapas de Karnaugh
Visualização do domínio de uma função na forma matricial
Pontos do domínio estão dispostos seguindo o código Gray, pares adjacentes diferem em 1 bit 
B 
Unibratec – Prof. Remy Eskinazi
Adjacências no Mapa de Karnaugh
 Os elementos nas extremidades das linhas e colunas são também adjacentes
Unibratec – Prof. Remy Eskinazi
Adjacências no Mapa de Karnaugh
O cubo obtido é definido pelas variáveis que não mudam de fase ao longo de seus mintermos 
B é eliminado
A permanece
A é eliminado
B’ permanece
F = ?
F = ?
F = ?
Unibratec – Prof. Remy Eskinazi
Adjacências no Mapa de Karnaugh
O cubo obtido é definido pelas variáveis que não mudam de fase ao longo de seus mintermos 
B é eliminado
A permanece
A é eliminado
B’ permanece
F = A B’ + AB = A
F = A’ B’ + AB’ = B’
F = A B C’ + A B C + AB’C + A B’ C’
 = A(B(C + C’) + B’(C + C’)) 
 = A
Unibratec – Prof. Remy Eskinazi
Adjacências no Mapa-K
Adjacência nas extremidades das linhas
Adjacência nas extremidades das colunas
Unibratec – Prof. Remy Eskinazi
Complemento de uma Função
F = ? 
F’ = ?
Trocar 0’s por 1’s
Unibratec – Prof. Remy Eskinazi
Complemento de uma Função
F = A C + B’ C’ 
F’ = A’ C + B C’ 
Trocar 0’s por 1’s
Unibratec – Prof. Remy Eskinazi
Karnaugh de 4 variáveis
F = ?
Unibratec – Prof. Remy Eskinazi
Karnaugh de 4 variáveis
F = C + A' B D + B' D'
Unibratec – Prof. Remy Eskinazi
Minimização com Irrelevâncias
Os pontos irrelevantes podem ser considerados como 1 ou 0 no mapa de Karnaugh
São utilizados para formar cubos maiores, simplificando a função
00
C
AB
01
11
10
1
x
0
1
x
1
x
0
A
B
0
1
Os pontos irrelevantes deste cubo
estão sendo computados como 1’s
Este ponto irrelevante é considerado como 0
Unibratec – Prof. Remy Eskinazi
Exemplo: comparador de 2 bits
 3 funções de 4 variáveis
 3 mapas de Karnaugh
Unibratec – Prof. Remy Eskinazi
Exemplo: comparador de 2 bits
F1 = ?
F2 = ?
F3 = ?
Unibratec – Prof. Remy Eskinazi
Exemplo: comparador de 2 bits
F1 = A' B' C' D' + A' B C' D + A B C D + A B' C D'
F2 = A' B' D + A' C
F3 = B C' D' + A C' + A B D'
A xnor B xnor C xnor D

Teste o Premium para desbloquear

Aproveite todos os benefícios por 3 dias sem pagar! 😉
Já tem cadastro?

Outros materiais

Materiais relacionados

Perguntas relacionadas

Materiais recentes

Perguntas Recentes