Sistemas Digitais - Algebra Booleana

Prévia do material em texto

Sistemas Digitais 
Prof. Marcelo Grandi Mandelli 
mgmandelli@unisc.br 
Aula 2 – Álgebra Booleana 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 2 
Professor 
!  Marcelo Grandi Mandelli 
!  Engenharia de Computação – PUCRS 
!  Mestrado em Ciência da Computação – PUCRS 
"  sub-área Sistemas Digitais e Sistemas Embarcados 
!  Doutor em Ciência da Computação – PUCRS 
"  sub-área Sistemas Digitais e Sistemas Embarcados 
!  Doutor em Microeletrônica – Universidade de Montpellier, 
França 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 3 
Outras informações importantes 
!  Avaliação (previsto) 
"  Atividades de Aula – 10% 
"  Trabalho I – 30% 
"  Trabalho II – 30% 
"  Prova – 30% 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 4 
!  TRABALHOS 
"  Atividades práticas – 10% 
"  Trabalhos – 60% 
"  Prova – 30% 
!  Qualquer dúvida, sugestão, crítica: 
"  Pode marcar horário; 
"  Pode mandar email: mgmandelli@unisc.br 
"  Pode me chamar no intervalo ou durante as aulas 
Outras informações importantes 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 5 
Linguagem gráfica para representação 
de Circuitos Digitais a nível lógico 
!  Portas Lógicas, 
operações booleanas 
mais elementares: 
 
 
NXOR 
XOR 
NOR 
NAND 
NÃO, NOT ( ‘ ) 
OU ( + ) 
E ( . ) 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 6 
Propriedades da Álgebra Booleana 
#  Comutativa: 
A + B = B + A ou AB = BA 
#  Associativa: 
(A + B) + C = A + (B + C) = A + B + C 
(AB) C = A(BC) = ABC 
#  Distributiva: 
A(B + C) = (AB) + (A C) 
A + (BC) = (A + B) (A + C) 
(A + B) (C + D) = AC + AD + BC + BD 
(A + B) (C + D) = A(C + D) + B(C + D) 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 7 
Teorema de DeMorgan 
!  A + B = A . B 
 
 
 
!  AB = A + B 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 8 
Postulados da Álgebra Booleana 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 9 
Exercícios 
1. S = ABC + ABC 
2. S = (A + B) · (A + B) 
 
3. S = ABC + AC + AB 
 
4. S = (A + C) · (A + D) 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 10 
 
#  Formas padrão (canônicas) para representar expressões 
booleanas: 
"  Soma de produtos (SDP): 
!  F = ABC + AD + ABDE Mintermos 
"  Produto de somas: 
!  F = (A + B + C) . (A + B + E) Maxtermos 
FORMAS PADRONIZADAS DE EXPRESSÕES BOOLEANAS 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 11 
Soma de Produtos - Mintermos 
A B C mintermo 
0 0 0 A’B’C’ 
0 0 1 A’B’C 
0 1 0 A’BC’ 
0 1 1 A’BC 
1 0 0 AB’C’ 
1 0 1 AB’C 
1 1 0 ABC’ 
1 1 1 ABC 
$ Tabela verdade de função com n variáveis tem 2n mintermos 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 12 
Soma de Produtos - Mintermos 
A B C F 
0 0 0 0 
0 0 1 0 
0 1 0 1 
0 1 1 1 
1 0 0 0 
1 0 1 1 
1 1 0 1 
1 1 1 0 
$ Exemplo: F é função das variáveis A, B e C 
mintermo 
A’B’C’ 
A’B’C 
A’BC’ 
A’BC 
AB’C’ 
AB’C 
ABC’ 
ABC 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 13 
Soma de Produtos - Mintermos 
A B C F mintermo 
0 0 0 0 A’B’C’ 
0 0 1 0 A’B’C 
0 1 0 1 A’BC’ 
0 1 1 1 A’BC 
1 0 0 0 AB’C’ 
1 0 1 1 AB’C 
1 1 0 1 ABC’ 
1 1 1 0 ABC 
$ Selecionar os valores onde F é 1 
F = A’BC’ + A’BC + AB’C + ABC’ 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 14 
Produto de Somas - Maxtermos 
A B C mintermo MAXTERMO 
0 0 0 A’B’C’ A+B+C 
0 0 1 A’B’C A+B+C' 
0 1 0 A’BC’ A+B’+C 
0 1 1 A’BC A+B’+C' 
1 0 0 AB’C’ A’+B+C 
1 0 1 AB’C A’+B+C’ 
1 1 0 ABC’ A’+B’+C 
1 1 1 ABC A’+B’+C’ 
$ Tabela verdade de função com n variáveis tem 2n maxtermos 
$ MAXTERMO = mintermo $ DE MORGAN 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 15 
Produto de Somas - Maxtermos 
A B C F 
0 0 0 0 
0 0 1 0 
0 1 0 1 
0 1 1 1 
1 0 0 0 
1 0 1 1 
1 1 0 1 
1 1 1 0 
$ Exemplo: F é função das variáveis A, B e C 
MAXTERMO 
A+B+C 
A+B+C' 
A+B’+C 
A+B’+C' 
A’+B+C 
A’+B+C’ 
A’+B’+C 
A’+B’+C’ 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 16 
Produto de Somas - Maxtermos 
A B C F MAXTERMO 
0 0 0 0 A+B+C 
0 0 1 0 A+B+C' 
0 1 0 1 A+B’+C 
0 1 1 1 A+B’+C' 
1 0 0 0 A’+B+C 
1 0 1 1 A’+B+C’ 
1 1 0 1 A’+B’+C 
1 1 1 0 A’+B’+C’ 
$ Selecionar os valores onde F é 0 
F = (A+B+C)(A+B+C’)(A’+B+C)(A’+B’+C’) 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 17 
Exercícios 
A B C S 
0 0 0 1 
0 0 1 0 
0 1 0 1 
0 1 1 1 
1 1 1 1 
1 1 0 1 
1 0 1 0 
1 0 0 1 
1 1 1 1 
Dada a Tabela Verdade ao lado, 
ache a equação simplificada de 
saída utilizando: 
 
a) Soma de produtos 
b) Produto das somas 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 18 
Exercícios 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 19 
MAPA DE KARNAUGH 
!  O Mapa de Karnaugh é uma ferramenta de 
auxílio à minimização de funções 
booleanas. 
!  O próprio nome mapa vem do fato dele ser 
um mapeamento a partir de uma tabela-
verdade. 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 20 
MAPA DE KARNAUGH - 2 variáveis 
Ex.1 - Considere a seguinte função lógica de duas variáveis: 
 
 F(A,B) = A’B’ + AB’ 
 
A B F 
0 0 1 
0 1 0 
1 0 1 
1 1 0 
F 
A 
B 
0 1 
0 
1 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 21 
MAPA DE KARNAUGH - 2 variáveis 
Ex.1 - Considere a seguinte função lógica de duas variáveis: 
 
 F(A,B) = A’B’ + AB’ 
 
A B F 
0 0 1 
0 1 0 
1 0 1 
1 1 0 
1 
F 
A 
B 
0 1 
0 
1 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 22 
MAPA DE KARNAUGH - 2 variáveis 
Ex.1 - Considere a seguinte função lógica de duas variáveis: 
 
 F(A,B) = A’B’ + AB’ 
 
A B F 
0 0 1 
0 1 0 
1 0 1 
1 1 0 
1 
1 
F 
A 
B 
0 1 
0 
1 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 23 
MAPA DE KARNAUGH - 2 variáveis 
Ex.1 - Considere a seguinte função lógica de duas variáveis: 
 
 F(A,B) = A’B’ + AB’ 
 
A B F 
0 0 1 
0 1 0 
1 0 1 
1 1 0 
1 
1 
F 
A 
B 
0 1 
0 
1 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 24 
MAPA DE KARNAUGH - 2 variáveis 
Ex.1 - Considere a seguinte função lógica de duas variáveis: 
 
 F(A,B) = A’B’ + AB’ 
 
A B F 
0 0 1 
0 1 0 
1 0 1 
1 1 0 
1 
1 
F 
A 
B 
0 1 
0 
1 
F = B’ Função Minimizada 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 25 
MAPA DE KARNAUGH – 3 variáveis 
A B C F 
0 0 0 1 
0 0 1 0 
0 1 0 0 
0 1 1 0 
1 0 0 1 
1 0 1 1 
1 1 0 1 
1 1 1 1 
A 
BC 
00 
0 
1 
01 11 10 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 26 
MAPA DE KARNAUGH – 3 variáveis 
A B C F 
0 0 0 1 
0 0 1 0 
0 1 0 0 
0 1 1 0 
1 0 0 1 
1 0 1 1 
1 1 0 1 
1 1 1 1 
1 
A 
BC 
00 
0 
1 
01 11 10 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 27 
MAPA DE KARNAUGH – 3 variáveis 
A B C F 
0 0 0 1 
0 0 1 0 
0 1 0 0 
0 1 1 0 
1 0 0 1 
1 0 1 1 
1 1 0 1 
1 1 1 1 
1 
1 
A 
BC 
00 
0 
1 
01 11 10 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 28 
MAPA DE KARNAUGH – 3 variáveis 
A B C F 
0 0 0 1 
0 0 1 0 
0 1 0 0 
0 1 1 0 
1 0 0 1 
1 0 1 1 
1 1 0 1 
1 1 1 1 
1 
1 1 
A 
BC 
00 
0 
1 
01 11 10 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 29 
MAPA DE KARNAUGH – 3 variáveis 
A B C F 
0 0 0 1 
0 0 1 0 
0 1 0 0 
0 1 1 0 
1 0 0 1 
1 0 1 1 
1 1 0 1 
1 1 1 1 
1 
1 1 1 
A 
BC 
00 
0 
1 
01 1110 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 30 
MAPA DE KARNAUGH – 3 variáveis 
A B C F 
0 0 0 1 
0 0 1 0 
0 1 0 0 
0 1 1 0 
1 0 0 1 
1 0 1 1 
1 1 0 1 
1 1 1 1 
1 
1 1 1 1 
A 
BC 
00 
0 
1 
01 11 10 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 31 
MAPA DE KARNAUGH – 3 variáveis 
A B C F 
0 0 0 1 
0 0 1 0 
0 1 0 0 
0 1 1 0 
1 0 0 1 
1 0 1 1 
1 1 0 1 
1 1 1 1 
1 0 0 0 
1 1 1 1 
A 
BC 
00 
0 
1 
01 11 10 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 32 
MAPA DE KARNAUGH – 3 variáveis 
A B C F 
0 0 0 1 
0 0 1 0 
0 1 0 0 
0 1 1 0 
1 0 0 1 
1 0 1 1 
1 1 0 1 
1 1 1 1 
1 0 0 0 
1 1 1 1 
A 
BC 
00 
0 
1 
01 11 10 
F = A + B’C’ 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 33 
MAPA DE KARNAUGH – 4 variáveis 
0 0 0 0 
0 1 1 0 
0 1 0 0 
0 0 0 0 
AB 
CD 
00 
00 
 
01 
 
 
11 
 
10 
01 11 10 
A B C D F 
0 0 0 0 1 
0 0 0 1 0 
0 0 1 0 0 
0 0 1 1 0 
0 1 0 0 0 
0 1 0 1 1 
0 1 1 0 0 
0 1 1 1 1 
1 0 0 0 0 
1 0 0 1 0 
1 0 1 0 0 
1 0 1 1 0 
1 1 0 0 0 
1 1 0 1 1 
1 1 1 0 0 
1 1 1 1 0 
F(A,B,C, D) = A’BC’D + A’BCD + ABC’D 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 34 
MAPA DE KARNAUGH – 4 variáveis 
0 0 0 0 
0 1 1 0 
0 1 0 0 
0 0 0 0 
AB 
CD 
00 
00 
 
01 
 
 
11 
 
10 
01 11 10 
A B C D F 
0 0 0 0 1 
0 0 0 1 0 
0 0 1 0 0 
0 0 1 1 0 
0 1 0 0 0 
0 1 0 1 1 
0 1 1 0 0 
0 1 1 1 1 
1 0 0 0 0 
1 0 0 1 0 
1 0 1 0 0 
1 0 1 1 0 
1 1 0 0 0 
1 1 0 1 1 
1 1 1 0 0 
1 1 1 1 0 
F(A,B,C, D) = A’BC’D + A’BCD + ABC’D 
F(A,B,C, D) = A’BD + 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 35 
MAPA DE KARNAUGH – 4 variáveis 
0 0 0 0 
0 1 1 0 
0 1 0 0 
0 0 0 0 
AB 
CD 
00 
00 
 
01 
 
 
11 
 
10 
01 11 10 
A B C D F 
0 0 0 0 1 
0 0 0 1 0 
0 0 1 0 0 
0 0 1 1 0 
0 1 0 0 0 
0 1 0 1 1 
0 1 1 0 0 
0 1 1 1 1 
1 0 0 0 0 
1 0 0 1 0 
1 0 1 0 0 
1 0 1 1 0 
1 1 0 0 0 
1 1 0 1 1 
1 1 1 0 0 
1 1 1 1 0 
F(A,B,C, D) = A’BC’D + A’BCD + ABC’D 
F(A,B,C, D) = A’BD + BC’D 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 36 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 37 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 38 
F = A’ B C’ D’ + A’ B C’ D 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 39 
F = A’ B C’ D’ + A’ B C’ D + A’ B C D + A’ B C D’ 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 40 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 41 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 42 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 43 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 44 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 45 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 46 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 47 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 48 
Exercícios 
A B C S 
0 0 0 1 
0 0 1 0 
0 1 0 1 
0 1 1 1 
1 0 0 1 
1 0 1 0 
1 1 0 1 
1 1 1 1 
Dada a Tabela Verdade ao lado, 
ache a equação simplificada de 
saída utilizando Mapa de 
Karnaugh 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 49 
Para cada um dos seguintes mapas 
"  Indique os termos mínimos correspondentes aos ‘1’s 
do mapa; 
"  Indique o(s) termo(s) produto correspondente(s) à 
simplificação do mapa; 
Exercícios: 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 50 
Exercícios: 
1) Ache a equação em soma de mintermos, a equação em produto 
de maxtermos e o circuito para as seguintes funções: 
 
a)  F = A’ + BC 
b)  F = ABC + B’ 
c)  F = C + A’B + AC’ + ABC 
d)  F = (B C) + [(A C) . A’] 
2) Encontre a tabela verdade e expressões dos circuitos abaixo 
(para a função F) 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 51 
A B C F mintermo MAXTERMO 
0 0 0 0 A’B’C’ A+B+C 
0 0 1 0 A’B’C A+B+C' 
0 1 0 1 A’BC’ A+B’+C 
0 1 1 1 A’BC A+B’+C' 
1 0 0 0 AB’C’ A’+B+C 
1 0 1 1 AB’C A’+B+C’ 
1 1 0 1 ABC’ A’+B’+C 
1 1 1 0 ABC A’+B’+C’ 
F = A’BC’ + A’BC + AB’C + ABC’ 
F`= (A’BC’ + A’BC + AB’C + ABC’)’ 
 
De Morgan 
F` = (A+B’+C)(A+B’+C’)(A’+B+C’)(A’+B’+C) 
 
F` = ? 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 52 
Soma de Produtos - Mintermos 
•  F é função das variáveis A, B e C. Os valores de (A,B,C) para os quais F=1 são 
(0,1,0), (0,1,1), (1,0,1) e (1,1,0). 
•  Os mintermos associados a essas condições (ou seja, os mintermos 1), são A’BC’, 
A’BC, AB’C e ABC’ , respectivamente. 
•  Logo, a equação em soma de produtos para F será o OU entre estes produtos, 
conforme segue: 
Regra Exemplo 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 53 
Produto de Soma - Maxtermos 
•  Os valores das variáveis de entrada (A,B,C) para os quais F=0 são (0,0,0), (0,0,1), 
(1,0,0) e (1,1,1). 
•  Os maxtermos associados a essas condições (ou seja, os maxtermos 0), são A+ B
+C, A + B + C’, A’ + B+ C e A’+ B’+ C’, respectivamente. 
•  Logo, a equação em produto de somas para F será o E entre estas somas: 
Regra Exemplo 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 54 
Universalidade das portas NAND e NOR 
!  É possível projetar qualquer circuito utilizando unicamente 
portas NAND ou NOR 
!  A portas NAND ocupam menos transistores que portas AND 
e OR. 
 
 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 55 
Circuitos com Portas NAND 
!  Uma função representada na forma de uma soma de produtos, pode ser 
transformada numa forma diretamente realizável apenas com portas 
NAND por simples aplicação da lei de DeMorgan. 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 56 
Lei DeMorgan 
 
 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 57 
Circuitos com Portas NOR 
!  Qualquer circuito pode ser realizado apenas 
com portas NOR. 
!  No caso de a função estar representada 
como um produto de somas, a 
transformação mantém a estrutura. 
Sistemas Digitais – Marcelo Grandi Mandelli 
Slide 58 
Exercício 
!  Desenhe o circuito “XOR”, utilizando apenas 
portas “NAND”