ET35N_04_Simplificacao e Karnaugh

Prévia do material em texto

4. Técnicas de Simplificação e Projeto de Circuitos Combinacionais
4.1. Teoremas da Álgebra Booleana
Onde x é uma variável lógica que pode ser 0 ou 1 1/23
Teoremas com mais de uma variável:
2/23
Princípio da Dualidade:
Qualquer teorema ou identidade permanece válido quando se troca 0 por 1, AND por
OR e vice-versa.
3/23
x y xy x + xy = x
0 0 0 0 0 + 1.0 = 0 0 + 0 = 0 1 + 0.0 = 1 1 + 0 = 1
0 1 0 0 0 + 1.1 = 1 0 + 1 = 1 1 + 0.1 = 1 1 + 1 = 1
1 0 0 1 1 + 0.0 = 1 1 + 0 = 1 0 + 1.0 = 0 0 + 0 = 0
1 1 1 1 1 + 0.1 = 1 1 + 1 = 1 0 + 1.1 = 1 0 + 1 = 1
Exemplos:
4/23
teorema 15a
teorema 13
teorema 8
teorema 2
teorema 13
teorema 3
teorema 4
teorema 13
Teoremas 2 e 6
Teoremas de DeMorgan:
1° Teorema: O complemento da soma é igual ao produto dos complementos
2° Teorema: O complemento do produto é igual à soma dos complementos
Consenso (18) xy yz xz xy xz   
5/23
Exemplos:
6/23
Qualquer expressão booleana pode ser decomposta nas três operações
básicas: AND, OR ou NOT. Além disso, é possível implementar qualquer
expressão usando somente portas NANDs. O mesmo vale para portas NORs.
7/23
Uma simbologia alternativa para as portas lógicas é apresentada abaixo.
8/23
4.2. Formas Canônicas de Expressões Lógicas
 Soma de produtos (SOP): consiste em dois ou mais termos AND conectados
por uma operação OR. As variáveis podem estar complementadas, porém nunca
com barras sobre mais de uma variável.
Exemplo:
 Produto de somas (POS): consiste em dois ou mais termos OR conectados
por operações AND. As variáveis podem estar complementadas, porém nunca
com barras sobre mais de uma variável.
Exemplo:
X ABC ABC ABC  
( )( )( )X A B C A B C A B C      
9/23
Para cada linha da tabela verdade de um circuito lógico, pode ser
associado um mintermo e um maxtermo correspondente.
 Mintermo: produto de variáveis não repetidas. Para n variáveis, tem-se 2n
mintermos. Obtido pelo produto das entradas que resultam em nível alto.
 Maxtermo: soma de variáveis não repetidas. Para n variáveis, tem-se 2n
maxtermos. Obtido pela soma das entradas que resultam em nível baixo.
10/23
 Soma canônica: soma dos mintermos de uma função lógica das linhas de sua
tabela verdade que resultam em nível alto.
 Produto canônico: produto dos maxtermos de uma função lógica das linhas
de sua tabela verdade que resultam em nível baixo.
Exemplo. Obtenha a função lógica da tabela verdade abaixo usando a soma
canônica e o produto canônico.
 Mintermos:
 Maxtermos:
, ,
(0, 3, 4, 6, 7)
A B C
S ABC ABC ABC ABC ABC     
, ,
(1, 2,5) ( )( )( )
A B C
S A B C A B C A B C       
11/23
Exemplo. Projetar um circuito com três entradas A, B e C, cuja saída seja nível
alto quando a maioria das entradas for nível alto.
Passo 1: escrever a tabela verdade do circuito.
Passo 2: escrever a soma canônica.
Passo 3: simplificar a expressão algébrica encontrada.
12/23
Exemplo. Projetar um circuito com três entradas A, B e C, cuja saída seja nível
alto quando a maioria das entradas for nível alto.
Passo 4: implementar o circuito.
13/23
Exemplo. Encontre a função simplificada F, utilizando a soma canônica.
14/23
Exemplo. Encontre a função simplificada F.
Apesar de se atingir os resultados esperados, corre-se o risco de não simplificar a
função adequadamente, ou pior ainda, pode-se cometer erros nas simplificações. O
método de leitura por “Mapas de Karnaugh” elimina esses problemas, visto que a
leitura já é dada na forma mais simplificada possível.
15/23
4.3. Mapa de Karnaugh (Mapa K)
 Método gráfico para simplificação (e projeto) de circuitos combinacionais.
Encontra-se a expressão lógica mais simplificada possível.
 Uma função com N variáveis é representada como um mapa de 2N células,
uma para cada possível combinação das entradas.
 Cada célula difere da adjacente por um bit somente (código Gray).
Exemplo. Monte o mapa K da lista de mintermos:
, ,
(0,1, 2, 6)
A B C
S  
16/23
 Pode-se simplificar as funções pela combinação de conjuntos de 2i células '1'
adjacentes.
 A função simplificada é a soma dos termos
produtos que foram combinados.
 O mapa K é duplamente cilíndrico, ou seja, as
células também são adjacentes nos cantos.
17/23
 Para funções com quatro variáveis, tem-se um mapa K da seguinte forma:
18/23
Exemplos. Possíveis combinações de células '1' adjacentes.
19/23
Exercício:
20/23
Exercício:
21/23
Exercício:
22/23
Exercício:
23/23
Teorema 15b