Parte2_Sistemas Digitais_Com Exercícios

Prévia do material em texto

11/11/2013
1
Álgebra Booleana ou Álgebra de Boole
• O nome Álgebra Booleana é em homenagem
ao matemático inglês George Boole que em
1854, publicou um livro clássico.
• Uma investigação das leis do pensamento
sobre as quais são baseadas as teorias
matemáticas da lógica e das probabilidades.
• O propósito estabelecido por Boole era o de
realizar uma análise matemática da lógica.
Tipos de Sinais Postulados da Álgebra de Boole
• A Álgebra de Boole é um sistema constituído por
um conjunto S, duas operações fechadas ( + , ou,
e ., e) definidas sobre S, e por um conjunto de
postulados.
• A operação simbolizada por + é chamada
operação OU (ou OR). A operação simbolizada
por . é chamada operação E (ou AND).
• Os símbolos + e . não tem o mesmo significado
dos símbolos aritméticos usados para as
operações aritméticas de adição e multiplicação.
Postulados da Álgebra de Boole
• Uma operação é dita fechada sobre um 
conjunto se, quando aplicadas a dois ou mais 
elementos pertencentes ao conjunto, origina 
um outro elemento também pertencente ao 
conjunto.
• Por exemplo:
– Se [ a Є S ] e [b Є S] Є = pertence 
então : 
» (a + b) Є S
» (a . b) Є S
Postulados da Álgebra de Boole
• P.1 Associatividade de + e .
» (a + b) + c = a + (b + c)
» (a . b) . c = a . (b . c)
• P.2 Comutatividade de + e .
» (a + b) = b + a
» a . b = b . a
• P.3 ∃! (Existência) de um único elemento 
unitário em relação à operação +
» 0 + a = a + 0 = a 
elemento unitário
11/11/2013
2
Postulados da Álgebra de Boole
• P.4 ∃! (Existência) de um único elemento 
unitário em relação à operação .
» 1 . a = a . 1 = a
elemento unitário
• P.5 Distributividade de + sobre .
» a + (b . c) = (a + b) . (a + c)
• P.6 Distributividade de . sobre +
» a . (b + c) = (a . b) + (a . c)
• P.7 Existência de um complemento
» (∀∀∀∀ a) (∃∃∃∃ ā) tal que, ∀ = qualquer que seja
» a . ā = 0
» a + ā= 1
Postulados da Álgebra de Boole
�Aplicação: Qual o complemento de O ?
• Por P.3, 
• P.3 ∃! (Existência) de um único elemento 
unitário em relação à operação +
» 0 + a = a + 0 = a 
elemento unitário
• O + Ō = 1 ∴ Ō = 1 e O . Ō = O, donde 
• O . 1 = O ∴ Ō = 1, c.q.d
Teoremas Fundamentais
�T.1 Lei da Dualidade
• Dada uma certa igualdade, se forem
permutados entre si os símbolos + e ., os
dígitos 0 e 1, nos seus dois membros, pode-se
obter uma outra igualdade, dual da primeira.
» (a + b) + c = a + (b + c)
» (a . b) . c = a . (b . c)
Teoremas Fundamentais
• T.2 a + 1 = 1
• T.3 a . 0 = 0
• T.4 a + a = a
• T.5 a . a = a
• T. 6 Lei da Absorção: a + (a . b) = a
• T.7 Lei da Absorção: a . (a + b) = a
Teoremas Fundamentais
• T.8 Inverso do inverso:
• T. 9 ā é único
• T.10 Teorema de De Morgan
Funções Booleanas
• Chama-se função booleana a uma dada
expressão envolvendo elementos e operações da
álgebra de Boole.
�Exemplos:
– f1 (a,b,c) = a . b + ā . b . c + b . c
– f2 (A, B, C, D) = Ā . B + Ā .B . C . D + Ā
• Obs.: A notação E, simbolizada pelo . pode ser
omitida, podendo-se representar a operação a . b
simplesmente por ab.
11/11/2013
3
TABELA VERDADE (TV)
• São tabelas que representam todas as possíveis combinações das
variáveis de entrada de uma função, e os seus respectivos valores
de saída;
• A determinação da tabela verdade de uma função envolve os
seguintes procedimentos:
– Preenchimento das colunas referentes às variáveis da função, registrando-se
todas as combinações de 0’s e 1’s que as variáveis podem assumir.
– Se a função possuir N variáveis, então o número de combinações é igual a 2N.
Esse número é igual ao número de linhas da tabela verdade.
• Preenchimento de colunas envolvendo expressões intermediárias.
Aqui o número de colunas depende da complexidade da função.
• Preenchimento da coluna de saída, que é uma manipulação lógica
das colunas que envolvem expressões intermediárias e da função
em si.
Exemplo: Representar numa TV a 
função: f (a,b,c,d) = a . (a + b . d . c) 
a b c d d c b d c a + b. d . c f (a,b,c,d)
0 0 0 0 1 1 0 0 0
0 0 0 1 0 1 0 0 0
0 0 1 0 1 0 0 0 0
0 0 1 1 0 0 0 0 0
0 1 0 0 1 1 1 1 0
0 1 0 1 0 1 0 0 0
0 1 1 0 1 0 0 0 0
0 1 1 1 0 0 0 0 0
1 0 0 0 1 1 0 1 1
1 0 0 1 0 1 0 1 1
1 0 1 0 1 0 0 1 1
1 0 1 1 0 0 0 1 1
1 1 0 0 1 1 1 1 1
1 1 0 1 0 1 0 1 1
1 1 1 0 1 0 0 1 1
1 1 1 1 0 0 0 1 1
Passagem da Tabela Verdade para a 
Expressão Algébrica
Seja a Tabela Verdade:
a b f
0 0 1
0 1 0
1 0 1
1 1 1
Pode-se obter f como uma
somatória de termos onde
aparecem todas as variáveis
observando-se as regras a
seguir:
• O número de termos é igual ao número de 1’s
(huns)da função. No caso o número de termo é 3.
• Cada termo possui todas as variáveis interligadas
pele operação . (E), considerando-se a variável
barrada se, para uma dada linha onde f é igual a
1(um), a mesma for 0 (zero).
Portanto Simplificando Temos:
Formas Canônicas
• A partir da tabela verdade, é possível chegar à
expressão que representa o comportamento de
um circuito, e em seguida construir o circuito,
usando as portas lógicas já estudadas.
• O processo de elaboração da expressão usa as
chamadas formas canônicas, que consistem em
regras para representar as condições de entrada
que:
– produzirão saída 1 (e portanto as demais condições
produzirão saída 0) ou alternativamente,
– produzirão saída 0 (e portanto as demais condições
produzirão saída 1).
Formas Canônicas
• São, portanto, duas as formas canônicas:
• Forma normal disjuntiva: quando ela está
formada pela soma de MINTERMOS.
– Um mintermo é um produto de todas as variáveis
da função (barradas ou não) - representa as
condições que produzem saída 1;
• Forma normal conjuntiva: quando está
representada por produtos de MAXITERMOS.
– Um maxitermo é representado pela soma de
todas as variáveis (barradas ou não) da função -
representa as condições que produzirão saída 0.
11/11/2013
4
Exemplos:
�Mintermos: f (a,b,c,d) = a.b.c.d
�Maxitermos: f (a,b,c,d) = a + b + c + d
• Essas formas são alternativas, isto é, a
expressão poderá ser encontrada aplicando-se
alternativamente UMA ou OUTRA das formas.
Soma dos Minitermos
• É produzida construindo:
– um termo (uma sub-expressão) para cada linha da tabela verdade (que
representa uma combinação de valores de entrada) em que a saída é 1,
– cada um desses termos é formado pelo PRODUTO (FUNÇÃO AND) das
variáveis de entrada, sendo que:
• quando a variável for 1, mantenha;
• quando a variável for 0, complemente-a (função NOT).
– a função booleana será obtida unindo-se os termos PRODUTO (ou
minitermos) por uma porta OR (ou seja, "forçando-se" a saída 1 caso
qualquer minitermo resulte no valor 1).
• Dessa forma, ligando os termos-produto (também chamados
mintermos) pela porta OR, caso QUALQUER UM dos mintermos seja 1
(portanto, caso qualquer uma das condições de valores de entrada
que produz saída 1 se verifique), a saída pela porta OR será também
1.
• Ou seja, basta que se verifique qualquer uma das alternativas de
valores de entrada expressos em um dos mintermos, e a saída será
também 1, forçada pelo OR. Caso nenhuma dessas alternativas se
verifique, produz-se a saída 0.
Exemplo Mintermos PRODUTO DOS MAXITERMOS• É produzida construindo:
– um termo (uma sub-expressão) para cada linha da tabela verdade (que 
representa uma combinação de valores de entrada) em que a saída é 0,
– cada um desses termos é formado pela SOMA (FUNÇÃO OR) das 
variáveis de entrada, sendo que:
• quando a variável for 0, mantenha;
• quando a variável for 1, complemente-a (função NOT).
– a função booleana será obtida unindo-se os termos SOMA (ou 
maxitermos) por uma porta AND (ou seja, "forçando-se" a saída 0 caso 
qualquer minitermo resulte no valor 0).
• Dessa forma, ligando os termos-soma (também chamados 
maxitermos) pela porta AND, caso QUALQUER UM dos minitermos
seja 0 (portanto, caso qualquer uma das condições de valores de 
entrada que produz saída 0 se verifique), a saída pela porta AND será 
também 0. 
• Ou seja, basta que se verifique qualqueruma das alternativas de 
valores de entrada 0 expressos em um dos maxitermos, e a saída 
será também 0, forçada pelo AND. Caso nenhuma dessas alternativas 
se verifique, produz-se a saída 1.
Exemplo Maxitermos
Exemplo: 
O mesmo comportamento (a mesma tabela verdade) pode ser igualmente 
representada por qualquer das formas canônicas.
11/11/2013
5
Concluindo:
• Se ambas as formas canônicas produzem expressões
equivalentes, devemos escolher a representação que
resultar em menor número de termos, produzindo uma
expressão mais simples.
• Por esse método, pode-se encontrar a expressão que
represente qualquer tabela verdade. Após se encontrar
uma expressão que represente o comportamento
esperado, é possível que não seja uma expressão simples
que possa ser construída com poucas portas lógicas.
�Antes de projetar o circuito, é útil SIMPLIFICAR a expressão,
de forma a possibilitar construir um circuito mais simples e
portanto mais barato.
• Portanto, o fluxo de nosso procedimento será:
– DESCRIÇÃO VERBAL ---> TABELA VERDADE ---> FORMA 
CANÔNICA---> FUNÇÃO SIMPLIFICADA ---> CIRCUITO
CIRCUITOS COMBINACIONAIS
Exercícios
Ex. 1. 
Algoritmos de criptografia são muito utilizados em páginas de comércio 
eletrônico da Internet e na construção de redes VPN (Virtual Private 
Network), para garantir o sigilo na comunicação entre um cliente e o servidor.
• Normalmente esses algoritmos usam uma chave K conhecida do cliente 
(ou dinamicamente transferida de um servidor em tempo de execução) 
que é utilizada para criptografar o conteúdo de uma mensagem (que pode 
ser o número do cartão de crédito do cliente, o valor da compra, o código 
do lojista, etc.) segundo a expressão:
– Z = K ΘΘΘΘ Conteúdo
– O valor Z, criptografado, é enviado do cliente ao servidor onde é 
descriptografado com a mesma chave K segundo a expressão:
– Z ΘΘΘΘ K = Conteúdo
• Qual a sugestão que você daria para o operador ΘΘΘΘ ? Demostre.
Ex.2. Simplifique por Álgebra de Boole
e Teorema de Morgan
i)
ii)
iii) ).( CABAABCZ +=
Exercícios – Circuit Maker
III. Monte o circuito de um comparador de
palavras de 4 bits. Se iguais indicar
acendendo um LED.
IV. Monte um circuito para a transferência de
dados entre CPU e Dispositivos de E/S. Após
um sinal dado no Barramento de Controle
(R/W) é feita a transferência;
V. Monte as portas lógicas: INVERSOR / AND e
OR e XOR, utilizando somente portas NAND.
Exercícios – Circuit Maker
VI. Uma Apólice de seguros(TIPO22) pode ser 
emitida somente se o pretendente:
a) É possuidor de uma apólice do TIPO19, e é um 
homem casado;
b) É possuidor da apólice do TIPO19 e é casado e com 
idade inferior a 25 anos;
c) Não é possuidor da Apólice TIPO19, e é mulher 
casada;
d) É um homem com menos de 25 anos;
e) É casado e com 25 anos ou mais de idade.
PERGUNTA: Quando que a apólice tipo 22 será emitida?
(Monte a TV / Equações/Simplificar e Circuito)
11/11/2013
6
Exercícios - Circuit Maker
VII.Desenvolva as expressões e o circuito:
O Alarme soará se for recebido um sinal de
falha juntamente com um sinal de parada
ou um sinal de alerta.
VIII. Monte um circuito que represente pessoas
atravessando uma rua com sinal de trânsito
e sinal para os pedestres. Considere todas as
variáveis possíveis para o problema.
Exercício – Circuit Maker
• Monte um circuito DECODIFICADOR de 
MEMÒRIA RAM:
– Tamanho da memória 1MBytes (1024K Bytes)
• Quantos Bits precisamos para endereçarmos 1M endereços?
– Tamanho dos Chips de Memória 256KBytes
• Quantos bits necessitamos para endereçar 256K Bytes?
• Qual será o Tamanho do Decodificador:
– N x M, onde 
» N - definirá o valor binário para a saída
» M - definirá qual chip esta sendo endereçado
Solução Decodificador
20 bits – 2 bits = 18bits
N (2) Entradas x M(4) Saídas
CHIP DE 
MEMÓRIA 
256K BYTES
CHIP DE 
MEMÓRIA 
256K BYTES
CHIP DE 
MEMÓRIA 
256K BYTES
CHIP DE 
MEMÓRIA 
256K BYTES
DECODIFICADOR
2 X 4
E0
E17
E18
E19
00 01 10 11
Minimização de Funções
• O tamanho e a complexidade do circuito que realiza uma
dada função depende de sua complexidade algébrica.
Assim, sempre que for possível deverá ser adotada uma
simplificação na expressão algébrica, usando postulados
e teoremas, o que conduzirá a uma simplificação dos
circuitos.
• Técnicas especiais de minimização foram desenvolvidas
e a mais comum é a que emprega os Mapas de
Karnaugh.
– Esta técnica é usada para reduzir as funções a formas mais
simples. É uma técnica viável para funções de 2,3,4,5 e 6
variáveis.
• Para funções de mais de 6 variáveis, técnicas mais
avançadas, tais como os algoritmos de Quine-McClusky,
devem ser utilizadas.
Mapas de Karnaugh
• Os mapas de Karnaugh são ferramentas gráficas para simplificação de
expressões booleanas, através desta técnica e apesar de algumas limitações
a ela inerentes, pode-se obter simplificações de forma segura, rápida e bem
mais prática que a aplicação dos teoremas da álgebra de Boole.
• Um mapa K corresponde a uma grade quadriculada, onde cada quadrículo
ou célula corresponde a uma linha da tabela verdade. Desta forma, existem
mapas K oriundos de soma de mintermos ou produto de maxitermos. Aqui
optaremos por tratar com soma de mintermos.
• A forma do mapa K depende apenas do número de varáveis envolvidas, para
uma função com N variáveis o mapa terá 2N células. Cada célula
correspondendo a um mintermo (ou maxitermo).
• A construção do mapa deve garantir que as células adjacentes, ou seja,
aquelas que apresentarem faces comuns (lados comuns), devem
representar termos que diferem em apenas uma variável.
Mapa de Karnaugh para função de 2
variáveis.
• O mapa de Karnaugh é um diagrama
constituído de uma certa quantidade de
quadrados ou celas.
• O número de celas é igual a 2N onde, N é o
número de variáveis da função.
– Assim, um mapa para uma função de 4 variáveis
possui 24 = 16 celas.
• O mapa de Karnaugh para função de 2
variáveis possui, portanto, 4 celas, e tem a
configuração a seguir para uma função f (a,b):
11/11/2013
7
Mapa para 2 Variáveis Mapa para 4 Variáveis
Mapa K representado por mintermos da forma padrão:
- soma de mintermos:
f(A,B,C,D) = m0 + m1 + m2 + m3 + ... + m15 = Σm(0,1,2,3,4,...,15)
A B C D 
0 0 0 0 
0 0 0 1 
0 0 1 0 
0 0 1 1 
0 1 0 0 
0 1 0 1 
0 1 1 0 
0 1 1 1 
1 0 0 0 
1 0 0 1 
 
Simplificação através de Mapas de 
Karnaugh
• Passos para simplificação usando mapas Karnaugh e expressões 
na forma de soma de mintermos:
1. Representação da função no mapa: para tanto marcam-se 1’s 
(uns) nas células que representem algum termo da expressão da 
função;
2. Agrupamento de células:
i. O número de células de um grupo deve corresponder a uma 
potência de base 2;Ex: 1,2,4,8,16,...
ii. Quando 2N células são adjacentes (possuindo lados comuns) elas 
podem ser agrupadas e deste grupo é possível obter um termo com 
N variáveis eliminadas;Ex: dada a função f(A,B,C,D), um grupo de 4 
células vai gerar um termo simplificado com apenas 2 
variáveis. 
iii. Os grupos de células devem ter a forma quadrada, não são 
permitidos grupos em L, T ou algo que não seja quadrado ou 
retangular;
Simplificação através de Mapas de 
Karnaugh
iv. Uma célula pode fazer parte de mais de um grupo, 
mas um grupo não pode ter todas as suas células 
associadas a outros grupos, caso contrário será 
superposto pelos outros;
v. Para uma função com N variáveis, deve-se dar 
preferência a grupos com 2N-1, 2N-2,...21 células, ou 
uma célula, necessariamente nessa ordem. Se há 3 
varáveis, de início tente agrupar grupos com 23-1 = 4 
células, após esgotar as possibilidades de agrupar 
grupos deste tamanho, procure agrupar células em 
número de 23-2 = 2 e assim sucessivamente após 
esgotar as possibilidades de agrupar grupos deste 
tamanho procure isolar as células “descasadas”. 
Simplificação através de Mapas de 
Karnaugh
3. Extração das expressões dos grupos de 
células: tais expressões são formadas pela 
interseção das variáveis (com ou sem barra) 
comuns aos nomes das células do grupo:
• EX: f(A,B,C) = Σm(0,1,3,7,5)
A B C f(A,B,C)0 0 0 1
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 1
11/11/2013
8
Após a marcação de células:
1
1 1 1 1
Definindo Agrupamentos:
F(A,B,C) = G1 + G2 = A B + C 
SIMPLIFICAÇÃO: Células que não tiveram os valores alterados 
em cada um dos agrupamentos, ligadas pela função (+)
1
Exemplos de MAPAS de KARNAUGH 
PARA SOMA DE MINTERMOS: 
Mapa para duas variáveis 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 0 1 B 
A 
 
 A B 
 
A B 
 
A B 
 
 
 A B 
0 
 
 
1 
 
 B 
 
 
B 
 
 A A 
Exemplos de MAPAS de KARNAUGH 
PARA SOMA DE MINTERMOS:
Mapa para três variáveis
00 01 11 10C
AB
A B C A B C
A B C A B C
0
1
A B C A B C
A B C A B C
A A
BB B
C
C
Exemplos de MAPAS de KARNAUGH 
PARA SOMA DE MINTERMOS:
Mapa para quatro variáveis 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 A B C D 
 
A B C D 
 
A B C D 
 
A B C D 
 
 
A B C D 
 
 
 A B C D 
 
 
A B C D 
 
 
A B C D 
 
 
 
A B C D 
 
 
 
 A B C D 
 
 
 
A B C D 
 
 
A B C D 
 
 
 
A B C D 
 
 
 
 A B C D 
 
 
 
A B C D 
 
 
 
A B C D 
 
00 
 
 
01 
 
 
11 
 
 
10 
 
00 01 11 10 
AB 
CD 
 
C 
 
C 
 
D 
 
D 
 
D 
 
A 
 
A 
 
B 
B 
 
B 
Exemplos de MAPAS de KARNAUGH 
PARA SOMA DE MINTERMOS:
Mapa para cinco variáveis 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
00 
 
 
01 
 
 
11 
 
 
10 
 
000 001 011 010 110 111 101 100 DE 
ABC 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 E 
 
D 
 
 
 
E 
 
 
D 
 
 E 
 A A 
 
 
 B B B 
 
 
 
 C C C C C 
11/11/2013
9
Exemplos de MAPAS de KARNAUGH PARA SOMA DE MINTERMOS:
Mapa para 6 variáveis 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 F 
 
 E 
 
 
 D 
 F 
 
 
 
 
 
 E 
 F 
 
 
 
 
 D 
 F 
 
 
 E 
 
 F 
 
 
000 
 
 
001 
 
 
011 
 
 
010 
 
 
110 
 
111 
 
 
101 
 
100 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
000 001 011 010 110 111 101 100 DEF 
ABC 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 A A 
 
 
 B B 
 
 
 
 C C C C C 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Em qualquer mapa Karnaugh as células adjacentes sempre apresentam uma 
única variação de estado em uma única variável do termo.
Exercício A)
• Da tabela a seguir pede-se: 
– Utilize as condições em X (valor X significa que
para o arranjo de entrada considerado admite-se
tanto valor zero quanto valor um) para encontrar
a expressão simplificada ao máximo, esta deve
ser obtida diretamente por mapa de Karnaugh.
TV do Exercício A)
A B C D S 
0 0 0 0 1 
0 0 0 1 0 
0 0 1 0 1 
0 0 1 1 0 
0 1 0 0 X 
0 1 0 1 1 
0 1 1 0 1 
0 1 1 1 X 
1 0 0 0 1 
1 0 0 1 0 
1 0 1 0 X 
1 0 1 1 0 
1 1 0 0 X 
1 1 0 1 X 
1 1 1 0 X 
1 1 1 1 1 
 
Exercício B)
• Projete (construa o circuito após simplificação 
pelo mapa Karnaugh) o circuito lógico abaixo, 
que é capaz de exibir os valores de 0 a 15 em 
Hexadecimal.
Exercício C)
• Encontre as expressões simplificadas a partir 
das configurações de mapas abaixo:
 
 
 
 
 
 
 
 
 
 
 
1 1 1 1 
1 1 1 1 
 1 1 1 
 1 1 
 
AB 
CD 
 
 1 
 1 1 1 
1 1 1 
 1 
 
AB 
CD 
 
 
1 1 1 
1 1 
 1 1 
1 1 1 
 
AB 
CD 
11/11/2013
10
Exercício D)
Simplifique: 
_ _ _ _ _ _ _ _
I. S = A.B.C.D+ A.B.C.D + A.B.C.D + A.B.C.D + 
A.B.C.D
_ _ _ _ _ _ _ _
II. S = A.B.D+ A.C.D + A.B.C.D + B.C.D + 
_ _ _ _ _ _ _ _
A.B.C.D+ A.B.C.D + A.B.C + A.B.C.D