Funções lógicas: Álgebra booleana

Estrutura algébrica consistindo em:

conjunto de elementos B
Análise e síntese de operações binárias {+, •, ‘}
circuitos combinacionais regras e identidades

Axiomas:
Técnicas Digitais I 1. B contém pelo menos dois elementos,
a, b
5. Regras distributivas:
Prof. Antônio de Pádua Braga 2. a, b encapsulados em B (i) a + (b • c) = (a + b) •
(i) a + b em B (a + c)
(ii) a • b em B (ii) a • (b + c) = a • b +
Baseado no texto de Randy H. Katz
Universidade da Califórnia, Berkeley
a•c
3. Regras comutativas: a,b em B,
(i) a + b = b + a 6. Complemento:
(ii) a • b = b • a (i) a + a' = 1
(ii) a • a' = 0
4. Identidades: 0, 1 em B
(i) a + 0 = a
(ii) a • 1 = a

Funções lógicas: Álgebra booleana Funções lógicas: Expressões e portas

B = {0,1}, + = OR, • = AND, ' = NOT => Álgebra booleana Várias maneiras de se representar expressões através de portas lógicas
Verificação dos axiomas: T2
Ex: Regra comutativa: E.g., Z = A' • B' • (C + D) = (A' • (B' • (C + D)))
0 + 1 = 1 + 0? 0 • 1 = 1 • 0? T1
1=1 0=0 uso de uma portas de 3 entradas
Teorema: qualquer função Boolena que pode ser expressa em uma A A
Z
tabela verdade também pode ser expressa em uma expressão Boolena
B Z
utilizando ', +, • B

Tabela verdade T1 C
Descrição Portas Chaves C
Se X = 0 então X' = 1
X X X X T rue
NOT T2
D
Se X = 1 então X ' = 0 D
0 1 X
1 0 False
X
Tabela verdade
Descrição Portas Chaves
Revisão do Z = 1 se X e Y X X Y Z False
Capítulo 1 ambos = 1 Y
Z
0 0 0 AND
0 1 0 X•Y
1 0 0
True
1 1 1
X Y
Descrição Portas Tabela verdade Chaves
Z = 1 se X ou Y X X Y Z False
(ou ambos) são 1 Y Z
0 0
0 1
0
1 X + Y
OR
True
1 0 1
1 1 1
X Y

Funções lógicas: NAND, NOR, XOR, XNOR Funções lógicas: Formas de onda
16 funções de duas variáveis:
X Y F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F1 1 F12 F13 F14 F15
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 X, X', Y, Y', X•Y, X+Y, 0, 1 mostram
1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 apenas a metade das funções
0 1 possíveis
X• Y X Y X+Y Y X

Descrição Portas Tabela verdade Chaves

Z = 1 se X é 0 X Y Z T rue
NAND ou Y é 0
X
Y
Z
0 0 1
0 1 1 X• Y
1 0 1
1 1 0 False
X Y

Descrição Portas Tabela verdade Chaves

NOR Z = 1 se X e Y = 0 X
Z X Y Z True
Y 0 0 1
0 1 0 X+Y
1 0 0 False
1 1 0
X Y

1
 Funções lógicas: Procedimentos de simplificação Funções lógicas: Representações alternativas
0 1 0 1 0 1
Minimização local: reduz a complexidade da implementação A B C Z
0 0 0 0 A B C
• reduz o número de elementos (entradas das portas) 0 0 1 1
0 1 0 0
• reduz o número de portas 0 1 1 1
1 0 0 0
• reduz o número de camadas do projeto 0
1 0 1 1 Representação a dois níveis
1 1 0 1 Z1 (inversores não contam)
Menos entradas significam portas mais rápidas em algumas tecnologias. 1 1 1 0

Representação multi-camadas
fan-ins (número de portas de entrada) são limitados em algumas tecnologias.
Vantagem: Portas com
0
Menos camadas no projeto implicam em menores tempos de propagação. Fan-ins reduzidos
Z2
Configuração de atraso mínimo tipicamente requer mais portas.
Porta complexa: XOR
Número de portas influenciam no custo do projeto. 0 Vantagem: Menos portas
Z3

Ex: Contadores TTL:

Z1 - 3 CIs (1x 6-inversores, 1x 3-entradas AND, 1x 3-entradas OR)
Z2 - 3 CIs (1x 6-inversores, 1x 2-entradas AND, 1x 2-entradas OR)
Z3 - 2 CIs (1x 2-entradas AND, 1x 2-entradas XOR)

Funções lógicas: Verificaçào através de formas de onda Portas Lógicas: Regras da álgebra Booleana

Dualidade: uma expressão Booleana equivalente pode ser obtida substituindo

operações AND por OR’s, operações OR por AND’s, constantes 0s por 1s, e
1s por 0s (são alterações nos elementos).
Qualquer estado que é verdadeiro em uma expressão será
falso na expressão dual.

Teoremas/Regras úteis da álgebra Booleana:

Operações com 0 e 1:
1. X + 0 = X 1D. X • 1 = X
2. X + 1 = 1 2D. X • 0 = 0
Operação sobre mesma variável:
Para uma mesma entrada, as três alternativas de implementação possuem 3. X + X = X 3D. X • X = X
essencialmente um mesmo comportamento.
Involução:
Pequenas variações são devidas ao número de camadas diferente. 4. (X')' = X
As três implementações são equivalentes. Regra da complementariedade:
5. X + X' = 1 5D. X • X' = 0

Regra comutativa:
6. X + Y = Y + X 6D. X • Y = Y • X

Portas Lógicas: Regras da álgebra Booleana (cont.) Portas Lógicas: Regras da álgebra Booleana
Regras associativas: Provando os teoremas através dos axiomas da álgebra Booleana:
7. (X + Y) + Z = X + (Y + Z) 7D. (X • Y) • Z = X • (Y • Z)
=X+Y+Z =X•Y•Z Ex: Prove o teorema X • Y + X • Y' = X
Regra distributiva: Lei distributiva (8) X • Y + X •Y' = X • (Y + Y')
8. X • (Y+ Z) = (X • Y) + (X •Z) 8D. X + (Y• Z) = (X + Y) • (X + Z)
Lei complementar (5) X • (Y + Y') = X • (1)
Teoremas de simplificação:
9. X • Y + X • Y' = X 9D. (X + Y) • (X + Y') = X Identidade (1D) X • (1) =X
10. X + X • Y = X 10D. X • (X + Y) = X
11. (X + Y') • Y = X • Y 11D. (X • Y') + Y = X + Y
Ex: Prove o teorema X + X•Y = X
Teorema de De’ Morgan:
12. (X + Y + Z + ...)' = X' • Y' • Z' • ... 12D. (X • Y • Z • ...) ' = X' + Y' + Z' + ... Identidade (1D) X + X•Y = X•1 + X•Y
13. {F(X1,X2,...,Xn,0,1,+,•)}' = {F(X1',X2',...,Xn',1,0,•,+)}
Lei distributiva (8) X • 1 + X • Y = X • (1 + Y)
Dualidade:
14. (X + Y + Z + ...) D = X • Y • Z • ... 14D. (X •FY • Z • ...)D = X + Y + Z + ... Identidade (2) X • (1 + Y) = X • (1)
15. {F(X1,X2,...,Xn,0,1,+,•)}D = {F(X1,X2,...,Xn,1,0,•,+)} Identidade (1) X • (1) = X
Teoremas para multiplicação e fatoração:
16. (X + Y) • (X' + Z) = X • Z + X' • Y 16D. X • Y + X' • Z = (X + Z) • (X' + Y)

2
 Portas Lógicas: Regras da álgebra Booleana Portas Lógicas: Regras da álgebra Booleana
Regras de DeMorgan
X Y X Y X+Y X•Y Exemplo de simplificação: Função carry out de somadores
0 0 1 1 1 1 completos
Identidade
(X + Y)' = X' • Y' 0 1 1 0 0 0
1 0 0 1 0 0 Cout = A' B Cin + A B' Cin + A B Cin' + A B Cin
NOR é equivalente a AND 1 1 0 0 0 0 = A' B Cin + A B' Cin + A B Cin' + A B Cin + A B Cin
com as entradas complementares
= A' B Cin + A B Cin + A B' Cin + A B Cin' + A B Cin
X Y X Y X•Y X +Y
(X • Y)' = X' + Y' 0 0 1 1 1 1 = (A' + A) B Cin + A B' Cin + A B Cin' + A B Cin
NAND é equivalente a OR 0 1 1 0 1 1
com as entradas complementares 1 0 0 1 1 1 = (1) B Cin + A B' Cin + A B Cin' + A B Cin
1 1 0 0 0 0
= B Cin + A B' Cin + A B Cin' + A B Cin + A B Cin
= B Cin + A B' Cin + A B Cin + A B Cin' + A B Cin
A regra de DeMorgan pode ser usada na conversão de expressões
AND/OR em expressões OR/AND. = B Cin + A (B' + B) Cin + A B Cin' + A B Cin Associação
Exemplo:
= B Cin + A (1) Cin + A B Cin' + A B Cin
Z = A' B' C + A' B C + A B' C + A B C'
= B Cin + A Cin + A B (Cin' + Cin)
Z' = (A + B + C') • (A + B' + C') • (A' + B + C') • (A' + B' + C)
= B Cin + A Cin + A B (1)
= B Cin + A Cin + A B

Portas Lógicas: Formas canônicas (2 níveis) Portas Lógicas: Formas canônicas (2 níveis)
Obtenção da expressão Booleana através da tabela verdade. Termo do produto / mintermo:
Soma de Produtos
Muitas expressões e generalizações podem ser obtidas de (AND) Produto dos elementos onde a variável
A B C Mintermos aparece apenas uma vez, sendo esta
uma mesma tabela verdade.
0 0 0 A B C = m0 1 ou 0 (mas não ambos!)
Forma canônica: forma padrão de uma expressão Booleana 0 0 1 A B C = m1
composta por uma representação algébrica. 0 1 0 A B C = m2 F na forma canônica:
0 1 1 A B C = m3
1 0 0 A B C = m4 F(A,B,C) = Σm(3,4,5,6,7)
1 0 1 A B C = m5 = m3 + m4 + m5 + m6 + m7
Soma de Produtos: = A' B C + A B' C' + A B' C
1 1 0 A B C = m6
Também conhecida como soma de mintermos 1 1 1 A B C = m7 + A B C' + A B C
011 100 101 110 111 Forma canônica / simplificada:
A B C F F
F = A' B C + A B' C' + A B' C + A B C' + A B C F = A B' (C + C') + A' B C + A B (C' + C)
0 0 0 0 1
Notação simplificada para
0 0 1 0 1 mintermos de 3 variáveis. = A B' + A' B C + A B
0 1 0 0 1
0 1 1 1 0 B = A (B' + B) + A' B C
1 0 0 1 0
1 0 1 1 0 C F = A + A' B C
1 1 0 1 0
1 1 1 1 0 A =A + BC
F' = A' B' C' + A' B' C + A' B C' F = (A + B C)' = A' (B' + C') = A' B' + A' C'

Portas Lógicas: Formas canônicas (2 níveis) Portas Lógicas: Formas canônicas (2 níveis)
Produtos de somas / Produto de maxtermos Soma de produtos, Produto de somas e Regra de DeMorgan:

Maxtermo: F' = A' B' C' + A' B' C + A' B C'

A B C Maxtermos (OR) Soma dos elementos onde a variável
0 0 0 A + B + C = M0 aparece apenas uma vez, sendo esta Aplique a regra de DeMorgan e encontre F:
0 0 1 A + B + C = M1 1 ou 0 (mas não ambos!)
0 1 0 A + B + C = M2 (F')' = (A' B' C' + A' B' C + A' B C')'
0 1 1 A + B + C = M3 Produto de maxtermos:
1 0 0 A + B + C = M4 F = (A + B + C) (A + B + C') (A + B' + C)
* Identifique na tabela as linhas onde F é 0.
1 0 1 A + B + C = M5
1 1 0 A + B + C = M6 * 0 na coluna de entrada implica um F' = (A + B' + C') (A' + B + C) (A' + B + C') (A' + B' + C) (A' + B' + C')
1 1 1 A + B + C = M7 elemento true.
Aplique a regra de DeMorgan e encontre F:
* 1 na coluna de entrada implica um
Notação simplificada para elemento complementar. (F')' = {(A + B' + C') (A' + B + C) (A' + B + C') (A' + B' + C) (A' + B' + C')}'
maxtermos de 3 variáveis.
F = A' B C + A B' C' + A B' C + A B C' + A B C
F(A,B,C) = ΠM(0,1,2)
= (A + B + C) (A + B + C') (A + B' + C)

F’(A,B,C) = ΠM(3,4,5,6,7)
= (A + B' + C') (A' + B + C) (A' + B + C') (A' + B' + C) (A' + B' + C')

3
 Portas Lógicas: Formas canônicas (2 níveis) Portas Lógicas: Formas canônicas (2 níveis)
Quatro implementações alternativas de F: Formas de onda: Verificação das três alternativas
A
100 200

A
B
B
Soma de produtos (canônica)
F1 C
C
F1

F2

F3
Soma de produtos (minimizada) F4

F2

Produto de somas (canônica) Oito combinações únicas Exceto por alguns glitches,
das três entradas as formas de ondas das três
F3 implementações são essencialmente
Produto de somas (minimizada) as mesmas.

F4

Portas Lógicas: Formas canônicas (2 níveis) Portas Lógicas: Funções especificadas incompletamente
Mapeamento entre as formas: Funções com n entradas possuem 2n configurações de entrada
1. Conversão Mintermos/Maxtermos:
Reescreva os mintermos utilizando a notação simplificada Para uma dada função, nem todas as configurações são possíveis
de maxtermos.
Substitua os índices dos mintermos pelos ainda não utilizados. Este fato pode ser explorado durante a minimização do circuito

Ex: F(A,B,C) = Σm(3,4,5,6,7) = ΠM(0,1,2) Ex: Dígito BCD (Binary Coded Decimal) incrementado de 1
2. Conversão Maxtermos/Mintermos:
Digítos BCD codificam dígitos decimais entre 0 e 9
Reescreva os maxtermos utilizando a notação simplificada em números binários 00002 à 10012
de mintermos.
Substitua os índices dos maxtermos pelos ainda não utilizados. Bits inativos de W
A B C D W X Y Z
0 0 0 0 0 0 0 1
Ex: F(A,B,C) = ΠM(0,1,2) = Σm(3,4,5,6,7) 0 0 0 1 0 0 1 0
0 0 1 0 0 0 1 1 Bits ativos de W
3. Conversão Mintermos de F / Mintermos de F': 0 0 1 1 0 1 0 0
Na notação simplificada, liste os índices não utilizados em F. 0 1 0 0 0 1 0 1
0 1 0 1 0 1 1 0 Bits DC (don’t care) de W
0 1 1 0 0 1 1 1
E.g., F(A,B,C) = Σm(3,4,5,6,7) F'(A,B,C) = Σm(0,1,2) 0 1 1 1 1 0 0 0
= ΠM(0,1,2) = ΠM(3,4,5,6,7) 1
1
0
0
0
0
0
1
1
0
0
0
0
0
1
0
1 0 1 0 X X X X
4. Conversão Mintermos de F / Maxtermos de F': 1 0 1 1 X X X X Estas entradas não são
1 1 0 0 X X X X encontradas na prática e o
Reescreva um produto de somas, com os mesmos índices em F. 1 1 0 1 X X X X valor de saída associado a
1 1 1 0 X X X X
eles é dito don’t care (não importa)
E.g., F(A,B,C) = Σm(3,4,5,6,7) F'(A,B,C) = ΠM(3,4,5,6,7)
1 1 1 1 X X X X

= ΠM(0,1,2) = Σm(0,1,2)

Portas Lógicas: Funções especificadas incompletamente Portas Lógicas: Simplificação (2 níveis)

Estados don’t care e formas canônicas:
Simplificação algébrica:
Não se trata de um procedimento sistemático ou algoritmo
Representações canônicas da função BCD incrementada de 1:
Como saber quando a expressão mais simples foi encontrada?
Z = m0 + m2 + m4 + m6 + m8 + d10 + d11 + d12 + d13 + d14 + d15

Z = Σm(0, 2, 4, 6, 8) + d(10, 11, 12 ,13, 14, 15) Ferramentas computacionais:

Soluções precisas requerem tempos computacionais elevados,
especialmente para funções com várias entradas (>10).
Z = M1 • M3 • M5 • M7 • M9 • D10 • D11 • D12 • D13 • D14 • D15 Métodos heurísticos:
Reduzem o tempo computacional, produzindo boas soluções
Z= ΠM(1, 3, 5, 7, 9) • D(10, 11, 12, 13, 14 ,15) mas não as melhores.

Ainda há relevância em se aprender métodos manuais:

Compreensão de ferramentas de CAD, suas vantagens e defeitos.
Habilidade de avaliar resultados, pelo menos em pequenos exemplos.

4
 Portas Lógicas: Simplificação (2 níveis) Portas Lógicas: Simplificação (2 níveis)
Cubos booleanos
Ferramenta chave: The Uniting Theorem — A (B' + B) = A
Técnica visual
A B F F = A B' + A B = A (B' + B) = A
0 1 XYZ
0 0 0
0 1 0 011 111
X
1 0 1 1-cube Apenas outra maneira de
1 1 1 Os valores de B mudam nas linhas ativas de F XY 010 representar tabelas verdade
110
B é eliminado, A permanece 01 11

Y 001 entradas de n variáveis =

Os valores de A não mudam nas linhas ativas de F Y Z
101
cubo de n dimensões
00 10 000 100
X
X
A B G
G = A' B' + A B' = (A' + A) B' = B' 2-cube 3-cube
0 0 1
0 1 0 1011 WXYZ
1 0 1 Os valores de B não mudam nas linhas ativas de F 0111 1111
1 1 0 0011
A é eliminado, B permanece 1010
1110
0010
Os valores de A mudam nas linhas ativas de F 0110 1001
0101 1101
Y 0001
Z
1100
W 1000
0000 0100
X
4-cube

Portas Lógicas: Simplificação (2 níveis) Portas Lógicas: Simplificação (2 níveis)

Mapeando tabelas verdade em cubos booleanos: Exemplo com 3 variáveis: Carry out de somadores completos
estado ativo = nodos cheios
(A' + A) B Cin
estado inativo = nodos vazios

estado don’t care = nodos “X” Cubo de n-1 dimensões

011 111
Expressões reduzidas A B (Cin' + Cin)
contém n-1 variáveis A B Cin Cout
F 0 0 0 0
01 11 0 0 1 0 010 Os estados ativos são
A fixo e inalterado 0 1 0 0 110 representados adição (OR)
B 0 1 1 1
1 0 0 0 001 de subcubos de dimensão
B varia em um loop B menor.
00 10 1 0 1 1 101
A 1 1 0 1 Cin
1 1 1 1 000 100
G A A (B + B') Cin
01 11
A varia em um loop B

B complementar e inalterado 00 10 Cout = B Cin + A B + A Cin

A

Portas Lógicas: Simplificação (2 níveis) Portas Lógicas: Simplificação (2 níveis)

Subcubos com mais de duas dimensões Em um cubo de três dimensões:
um 0-cubo, i.e., um simples nodo, produz um termo em 3 elementos.
F(A,B,C) = Σm(4,5,6,7)
011 111 um 1-cubo, i.e., uma linha de dois nodos, produz um termo em 2 elementos.
Estado ativos formam um retângulo,
010 isto é, um cubo de duas dimensões. um 2-cubo, i.e., um plano de quatro nodos, produz um termos em 1 elemento.
110
Representa uma expressão em uma variável um 3-cubo, i.e., um cubo de oito nodos, produz um termo constante “1”.
B 001 isto é, 3-2 dimensões.
101
C
000 100
Em geral,
A
um m-subcubo dentro de um n-cubo (m < n) produz um termo com
A é fixo e inalterado n - m elementos.
B e C variam

Este subcubo representa o

elemento A.

5
 Portas Lógicas: Simplificação (2 níveis): Portas Lógicas: Simplificação (2 níveis):
Mapas de Karnaugh: Mapas de Karnaugh:
Dificuldade no desenho de cubos de mais de quatro dimensões. Adjascências no mapa:
Método alternativo de representação da tabela verdade que ajuda
a simplificação de expressões bastante complicadas (6 variáveis). A 011 111
AB
C 00 01 11 10
Além disso, métodos computacionais são requeridos. 010
A 0 000 010 110 100 110
B 0 1 A
AB
CD 00 01 11 00 001
Mapa de duas 0
0 2 1 001 011 111 101 B
variáveis 00 101
1 0 4 12 8 C
1 3
01 B 000 100
1 5 13 9
D
A
A
AB 11
C 00 01 11 10 C
3 7 15 11 Agrupar da primeira até a última coluna
0 10
Mapa de três 0 2 6 4
2 6 14 10
Linha superiores às linhas inferiores
variáveis
1 B
1 3 7 5 Mapa de quatro
B variáveis
Esquema numérico: 00, 01, 11, 10
Código Gray — apenas um elemento varia entre um
código e outro.

Portas Lógicas: Simplificação (2 níveis): Portas Lógicas: Simplificação (2 níveis):

Exemplos de mapas de Karnaugh: Exemplos de mapas de Karnaugh com 3 variáveis:
A A
0 1 AB A
B 0 1
A fixo, inalterado B
B varia C 00 01 11 10
0 0 1 0 1 1
0 1 0 0 1 F(A,B,C) = Σm(0,4,5,7)
1 0 1 1 0 0
B complementar, inalterado F = B' C' + A C
A varia 1 0 0 1 1
F=A G = B'
No mapa, os agrupamentos são da esquerda
B
para direita e debaixo para cima.
A
AB A
AB AB A
Cin 00 01 11 10
C 00 01 11 10
C 00 01 11 10
0 0 0 1 0 F' simplesmente possui 1’s nos
0 0 0 1 1 lugares dos 0’s e vice-versa.
0 0 1 1 0
1 0 1 1 1
1 0 0 1 1 F'(A,B,C) = Σm(1,2,3,6)
1 1 1 0 0
B
F' = B C' + A' C
B
B
Cout = A B + B Cin + A Cin F(A,B,C) = A
Compare com o método usando o teorema de DeMorgan
e a álgebra Booleana para reduzir o complemento.

Portas Lógicas: Simplificação (2 níveis): Portas Lógicas: Simplificação (2 níveis):

Exemplos de mapas de Karnaugh com 4 variáveis: Mapas de Karnaugh : Circulando zeros

A
A AB
AB F(A,B,C,D) = Σm(0,2,3,5,6,7,8,10,11,14,15) CD 00 01 11 10 F = (B + C + D) (A + C + D) (B + C + D)
CD 00 01 11 10
F = C + A' B D + B' D' 00 1 0 0 1
00 1 0 0 1
01 0 1 0 0
01 0 1 0 0 D
D Encontre o menor número
11 1 1 1 1
11 1 1 1 1 de subcubos (mais largos
quanto possíveis) que cobrem C
C 10 1 1 1 1
10 1 1 1 1 os estados ativos.
B
B
1011
0111
1111 Substitua F por F, 0’s se tornam 1’s e vice-versa
0011 1010
1110
F=BCD+ACD+BCD
0010 Cubo Booleano análogo
0110
ao mapa acima. F=BCD+ACD+BCD
1001
0101 1101
C 0001 F = (B + C + D) (A + C + D) (B + C + D)
D 1100
A
1000
0000 0100
B

6
 Portas Lógicas: Simplificação (2 níveis): Portas Lógicas: Simplificação (2 níveis):
Mapas de Karnaugh : Estados don’t care (DC) Exemplo de projeto: Comparador de dois bits
Estados don’t care podem ser tratados como 1’s ou 0’s de acordo
com a conveniência para implementar o circuito.
AB A A A B C D F1 F2 F3
F(A,B,C,D) = Σm(1,3,5,7,9) + Σd(6,12,13) B N1 F1 A B = C D 0 0 0 0 1 0 0 Diagrama de blocos
CD 00 01 11 10 e
=, >, <F2 A B < C D 0 1 0 1 0
00 0 0 X 0 F = A'D + B' C' D sem don't cares C F3 A B > C D 1 0 0 1 0 Tabela verdade
D N2 1 1 0 1 0
01 1 1 X 1 0 1 0 0 0 0 1
F = C' D + A' D com don't cares 0 1 1 0 0
D
1 0 0 1 0
Um mapa de 4 variáveis
11 1 1 0 0 Representando este DC como "1", um 2-cubo 1 1 0 1 0 para cada uma das
C pode ser formado no lugar de um 0-cubo. 1 0 0 0 0 0 1 três saídas
10 0 X 0 0 0 1 0 0 1
A 1 0 1 0 0
AB
B 1 1 0 1 0
CD 00 01 11 10
1 1 0 0 0 0 1
00 0 0 X 0 0 1 0 0 1
1 0 0 0 1
1 1 1 0 0
01 1 1 X 1
Forma simplif.: F = D (A' + C') D
11 1 1 0 0
Mesma resposta acima contendo C
menos elementos. 10 0 X 0 0

Portas Lógicas: Simplificação (2 níveis): Portas Lógicas: Simplificação (2 níveis):

Exemplo de projeto: Comparador de dois bits Exemplo de projeto: Somador de dois bits
A A A
AB AB AB
CD 00 01 11 10 CD 00 01 11 10 CD 00 01 11 10 A A B C D X Y Z Diagrama de blocos
00 1 0 0 0 00 0 0 0 0 00 0 1 1 1 B N1 X 0 0 0 0 0 0 0 e
+ N3 Y 0 1 0 0 1 Tabela verdade
01 0 1 0 0 01 1 0 0 0 01 0 0 1 1 C Z 1 0 0 1 0
D D D D N2 1 1 0 1 1
11 0 0 1 0 11 1 1 0 1 11 0 0 0 0 0 1 0 0 0 0 1
C C C 0 1 0 1 0 Um mapa de 4 variáveis
10 0 0 0 1 10 1 1 0 0 10 0 0 1 0 1 0 0 1 1 para cada uma das
1 1 1 0 0 três saídas
B B B
1 0 0 0 0 1 0
Mapa para F1 Mapa para F2 Mapa para F3
0 1 0 1 1
1 0 1 0 0
F1 = A' B' C' D' + A' B C' D + A B C D + A B' C D' 1 1 1 0 1
1 1 0 0 0 1 1
F2 = A' B' D + A' C 0 1 1 0 0
1 0 1 0 1
F3 = B C' D' + A C' + A B D' 1 1 1 1 0

Portas Lógicas: Simplificação (2 níveis): Portas Lógicas: Simplificação (2 níveis):

Exemplo de projeto (continuação) Exemplo de projeto (continuação)
\A \B \C \D
A
AB
A
AB
A
AB
A Duas implementações alternativas
CD 00 01 11 10 CD 00 01 11 10 CD 00 01 11 10
B
para Y: com e sem XOR
00 0 0 0 0 00 0 0 1 1 00 0 1 1 0
C
01 0 0 1 0 01 0 1 0 1 01 1 0 0 1
D D D
11 0 1 1 1 11 1 0 1 0 11 1 0 0 1 D
C C C Y1 OBS: XOR tipicamente
10 0 0 1 1 10 1 1 0 0 10 0 1 1 0 requer 4 portas NAND
para ser implementada!
B B B
X
Mapa para X Mapa para Y Mapa para Z

X XOR Y
X=AC + BCD + ABD 1's na diagonal sugerem XOR!
Z = B D' + B' D = B xor D Y

Y = A' B' C + A B' C' + A' B C' D + A' B C D' + A B C' D' + A B C D

= B' (A xor C) + A' B (C xor D) + A B (C xnor D)

Número de portas
= B' (A xor C) + B (A xor B xor C) é reduzido se uma XOR Y2
está disponível

7
 Portas Lógicas: Simplificação (2 níveis): Portas Lógicas: Simplificação (2 níveis):
Definição dos termos: Exemplos ilustrativos:
implicant: elemento ou grupos de elementos que podem ser agrupados A
AB
no mapa de Karnaugh. 00 01 11 10 6 Prime Implicants:
CD

prime implicant: implicant simplificado 00 0 1 1 0 A' B' D, B C', A C, A' C' D, A B, B' C D
01 1 1 1 0
essential prime implicant: se um elemento ativo é coberto por um D essencial
único implicant, ele é um essential prime implicant. 11 1 0 1 1
C
10 0 0 1 1
Agrupamento mínimo = B C' + A C + A' B' D

Objetivo: B

A
AB
aumentar o número de implicants. CD 00 01 11 10

00 0 0 1 0
5 Prime Implicants:
representar os estados ativos com o menor número de prime
implicants possíveis. B D, A B C', A C D, A' B C, A' C' D
01 1 1 1 0
D
essential primes em todos os casos possíveis. 11 0 1 1 1
C
essenciais
10 0 1 0 0
Essential primes formam agrupamentos mínimos
B

Portas Lógicas: Simplificação (2 níveis): Portas Lógicas: Simplificação (2 níveis):

Mapas de Karnaugh com 5 variáveis: Mapas de Karnaugh com 6 variáveis:
CD
BC BC CD EF 00 01 11 10
DE 00 01 11 10 DE 00 01 11 10 EF 00 01 11 10 00 1
AB=00
A=0 00 00
A =0 00 1 AB=00 0 4 12 8 01
0 4 12 8 01 1 5 13 9 11
01 01 1 1
11
1 5 13 9 3 7 15 11 10 1 1
11 11 1 1 10
2 6 14 10
3 7 15 11 CD
10 2 10 1 1 CD EF 00 01 11 10
6 14 10 EF 00 01 11 10 AB=01 00 1
BC BC AB =01 00 16 20 28 24 01
DE 00 01 11 10 DE 00 01 11 10 01
17 21 29 25 11
A =1 00 A=1 00 1 11
19 23 31 27 10 1 1
16 20 28 24 ƒ(A,B,C,D,E,F) =
10
01 17 21 29 25 01 1 1 1 18 22 30 26
Σm(2,8,10,18,24, EF
CD
CD 00 01 11 10
11 11 1 1 1 EF 00 01 11 10
26,34,37,42,45,50, 00
19 23 31 27 53,58,61) AB=11
AB =11 00 48 52 60 56
10 10 01 1 1
18 22 30 26 01 = 11
49 53 61 57
11
10
ƒ(A,B,C,D,E) = Σm(2,5,7,8,10,
51 55 63 59 1 1
10
50 54 62 58
13,15,17,19,21,23,24,29 31) CD
CD EF 00 01 11 10
EF 00 01 11 10 00
= C E + A B' E + B C' D' E' 00
AB=10
AB =10 32 36 44 40 01
+ A' C' D E' 01
1 1
33 37 45 41 11
11
35 39 47 43 10 1 1
10 34 38 46 42

Portas Lógicas: Simplificação (2 níveis): Portas Lógicas: Ferramentas de CAD para simplificação:
Mapas de Karnaugh com 6 variáveis: Método de Quine-McCluskey
CD
EF 00 01 11 10
EF
CD
00 01 11 10 00 1
Método tabular para determinação sistemática de todos os prime implicants.
AB=00
00
AB=00 0 4 12 8 01 ƒ(A,B,C,D) = Σm(4,5,6,8,9,10,13) + Σd(0,7,15)
01 1 5 13 9 11
11
3 7 15 11 10
Estágio 1: Encontre todos os
10
1 1
prime implicants. Implication Table
2 6 14 10
CD
CD EF 00 01 11 10 Coluna I
EF 00 01 11 10 AB=01 00 1 Passo 1: Complete a coluna 1 com os 0000
AB =01 00 16 20 28 24 01
índices dos mintermos dos
01
17 21 29 25 11
estados ativos e don’t care. 0100
11
19 23 31 27 10
Agrupe de acordo com o 1000
1 1
10 ƒ(A,B,C,D,E,F) = número de 1's.
18 22 30 26
Σm(2,8,10,18,24, EF
CD
0101
CD 00 01 11 10
EF 00 01 11 10
26,34,37,42,45,50, 00 0110
AB=11
AB =11 00 48 52 60 56
53,58,61) 1001
01 1 1
01
49 53 61 57 = D' E F' + A D E' F 11 1010
11
51 55 63 59 + A' C D' F' 10 1 1
10
50 54 62 58 0111
CD EF
CD
00 01 11 10
1101
EF 00 01 11 10 00
AB=10
AB =10
00
32 36 44 40 01 1 1
1111
01 11
33 37 45 41
11
35 39 47 43 10 1 1
10 34 38 46 42

8
 Portas Lógicas: Ferramentas de CAD para simplificação: Portas Lógicas: Ferramentas de CAD para simplificação:
Método de Quine-McCluskey Método de Quine-McCluskey
Método tabular para determinação sistemática de todos os prime implicants. Método tabular para determinação sistemática de todos os prime implicants.
ƒ(A,B,C,D) = Σm(4,5,6,8,9,10,13) + Σd(0,7,15) ƒ(A,B,C,D) = Σm(4,5,6,8,9,10,13) + Σd(0,7,15)

Implication Table Implication Table

Passo 2: Compare elementos do grupo com Passo 2: Compare elementos do grupo com
N 1’s com aqueles com N+1 1’s. Elimine a Coluna I Coluna II N 1’s com aqueles com N+1 1’s. Elimine a Column I Column II Column III
variável que muda de estado e coloque na 0000 ¦ 0-00 variável que muda de estado e coloque na 0000 ¦ 0-00 * 01-- *
coluna seguinte. -000 coluna seguinte. -000 *
0100 ¦ 0100 ¦ -1-1 *
Exemplo, 0000 vs. 0100 resulta em 0-00 1000 ¦ 010- Exemplo, 0000 vs. 0100 resulta em 0-00 1000 ¦ 010- ¦
0000 vs. 1000 resulta em -000 01-0 0000 vs. 1000 resulta em -000 01-0 ¦
0101 ¦ 100- 0101 ¦ 100- *
Marque os termos utilizados; se um termo 0110 ¦ 10-0 Marque os termos utilizados; se um termo 0110 ¦ 10-0 *
não for utilizado, marque com um asterisco 1001 ¦ não for utilizado, marque com um asterisco 1001 ¦
(estes são prime implicants) 1010 ¦ 01-1 (estes são prime implicants) 1010 ¦ 01-1 ¦
-101 -101 ¦
0111 ¦ 011- 0111 ¦ 011- ¦
1101 ¦ 1-01 1101 ¦ 1-01 *

1111 ¦ -111 1111 ¦ -111 ¦

11-1 11-1 ¦

Repita até que nenhuma combínação possa ser feita. Repita até que nenhuma combínação possa ser feita.

Portas Lógicas: Ferramentas de CAD para simplificação: Portas Lógicas: Ferramentas de CAD para simplificação:
Prime Implicant Chart Prime Implicant Chart (Continuação):

linhas = prime implicants. Se uma coluna tem um único X,

colunas = ON-set elements. então o implicant associado com a Eliminar todas as colunas cobertas por Ache o conjunto mínimo de
coloque um "X" se elementos ativos são linha é essencial. Isto deve apare- essential primes. linhas que cobre as colunas
agrupados por prime implicants. cer no agrupamento mínimo. restantes.

ƒ = A B' D' + A C' D + A' B