001 AlgebraBooleanaCircuitosLogicos

Prévia do material em texto

NOTAS DE AULA 
 
Álgebra Booleana e Circuitos Lógicos 
 
Prof. Dr. Antonio Carlos Schneider Beck Filho (UFSM) 
Prof. Dr. Júlio Carlos Balzano de Mattos (UFPel) 
 
 
 
Álgebra Booleana 
 
 
Desenvolvido pelo matemático George Boole, em 1854, é usada como teoria 
geral dos circuitos chaveados (álgebra de chaveamento). 
 
Diferentemente da álgebra ordinária dos reais, onde as variáveis podem assumir 
valores no intervalo (  ,  ), as variáveis boolenas podem assumir um número finito 
de valores. 
 
A álgebra booleana trabalha apenas com duas grandezas. 
 
 0 ou 1 
 
Que também podem ser representadas como: 
 
 falso (F) ou verdadeiro (V) 
 low ou high 
 
O computador trabalha com operações lógicas e aritméticas simples sobre bits. 
Estas operações são realizadas por circuitos eletrônicos chamados circuitos lógicos. Os 
circuitos lógicos são circuitos chaveados que, normalmente, são compostos de portas 
lógicas (implementadas com transistores). 
 
Por que o uso da Álgebra Boolena ? 
 
Porque fornece uma ferramenta matemática para entender o funcionamento dos 
circuitos chaveados e, por conseguinte, para entender e projetar circuitos lógicos. 
 
 
 
 2
OPERAÇÕES BÁSICAS DA ÁLGEBRA BOOLEANA 
 
 
Tabela verdade - são tabelas que representam todas as possíveis combinações 
das variáveis de entrada de uma função e seus respectivos valores de saída. 
 
 
Operação OU (OR) → ADIÇÃO LÓGICA 
 
“Uma sentença resulta verdadeira se QUALQUER UM dos termos for 
verdadeiro.” 
 
“A operação OU resulta 1 se pelo menos uma das varáveis de entrada vale 1.” 
 
O operador lógico OU é um operador binário, e é representado por: 
 
+ ou v 
 
Utilizando a tabela verdade para demonstrar o comportamento da equação: 
 
A + B (lê-se A ou B) 
 
 
TABELA VERDADE 
 
A B A + B 
0 0 0 
0 1 1 
1 0 1 
1 1 1 
 
 
 
 3
Operação E (AND) → MULTIPLICAÇÃO LÓGICA 
 
“Uma sentença resulta verdadeira se e somente se todos os termos forem 
verdadeiros.” 
 
“A operação E resulta 0 (zero) se pelo menos uma das variáveis de entrada vale 
0 (zero).” 
 
O operador lógico E é representado por: 
 
. ou  
 
Como a operação OU, também é um operador binário. 
 
Utilizando-se a tabela verdade para demonstrar o comportamento da equação: 
 
A . B (lê-se A e B) 
 
 
TABELA VERDADE 
 
A B A . B 
0 0 0 
0 1 0 
1 0 0 
1 1 1 
 
 
 
 4
Operação NÃO (NOT) 
 
“Este operador inverte um termo.” 
 
A operação complementação (ou negação, inversão) é a operação cujo resultado 
é simplesmente o valor complementar (inverso, negado) que a variável apresenta. 
 
O operador lógico NOT é representado por: 
 
A ou A~ ou 'A 
 
O operador NOT é um operador unário. 
 
Utilizando a tabela verdade para representar a variável A é: 
 
TABELA VERDADE 
 
A A
0 1 
1 0 
 
Ex: 
 1 = 00 
 0 = 11 
 
 
 
 5
Exemplo: 
 
Criar as tabelas verdades para representar o comportamento das seguintes 
equações: 
 
A + B + C 
 
A . B . C 
 
 
 
 
A B C A + B + C 
0 0 0 0 
0 0 1 1 
0 1 0 1 
0 1 1 1 
1 0 0 1 
1 0 1 1 
1 1 0 1 
1 1 1 1 
 
 
 
A B C A . B . C 
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 
 
 
 
 
 
 
 
 
 
 
 
 6
Avaliação de Expressões Booleanas 
 
 
Uma expressão booleana é uma expressão formada por sinais de entrada 
(chamadas variáveis de entrada) ligados por conectivos lógicos, produzindo como 
resultado um único sinal de saída. 
 
Dada a equação que descreve uma função booleana qualquer, deseja-se saber 
detalhadamente como esta função se comporta para qualquer combinação das 
variáveis de entrada. 
 
O comportamento de uma função é descrito pela sua tabela verdade e este 
problema é conhecido como avaliação da função ou da expressão que descreve a 
função considerada. 
 
Na avaliação de uma expressão booleana, deverá ser seguida uma ordem de 
precedência (respeitando os parênteses). 
 
1. avaliar a negação (NOT) 
2. avaliar a multiplicação lógica (AND) 
3. avaliar a adição lógica (OR) 
 
 
Exemplo 1: avaliar a expressão CBAx  
 
A B C C BA  CBAx 
0 0 0 1 0 1 
0 0 1 0 0 0 
0 1 0 1 0 1 
0 1 1 0 0 0 
1 0 0 1 0 1 
1 0 1 0 0 0 
1 1 0 1 1 1 
1 1 1 0 1 1 
 
 
 
 
 
 
 7
Portas Lógicas 
 
Uma função booleana também pode ser representada de forma gráfica, usando 
uma simbologia específica para portas lógicas. 
 
Estes símbolos de operadores lógicos (portas lógicas) representam recursos 
físicos, isto é, recursos eletrônicos capazes de realizar as operações lógicas. 
 
Na eletrônica binária, que trabalha com somente dois estados (denominada 
eletrônica digital), o nível lógico zero normalmente está associado à ausência de tensão 
(0 volts) e o nível lógico 1, à presença de tensão (por exemplo, 5 volts). 
 
O conjunto de portas lógicas e respectivas conexões que simbolizam uma 
equação booleana é denominada de circuito lógico. As portas lógicas implementam 
operadores da álgebra booleana. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 8
Porta OR (OU) 
 
Representação gráfica: 
 
A
B S 
 
 
S = A + B 
 
A B S 
0 0 0 
0 1 1 
1 0 1 
1 1 1 
 
 
A porta OR combina dois ou mais sinais de entrada de forma equivalente a um 
circuito em paralelo: 
 
 
Porta AND (E) 
 
Representação gráfica: 
 
A
B S 
 
 
S = A . B 
 
 
A B S 
0 0 0 
0 1 0 
1 0 0 
1 1 1 
 
 
A porta AND combina dois ou mais sinais de entrada de forma equivalente a um 
circuito em série: 
 
 
 
 
 
 
 9
Porta NOT (NÃO) 
 
Representação gráfica: 
 
A S
 
 
 
S = A 
 
 
A S 
0 1 
1 0 
 
 
A porta not inverte o sinal de entrada (executa a negação do sinal de entrada). 
 
 
 
Outros Circuitos Fundamentais 
 
Porta NOR (NÃO OU) 
 
Representação gráfica: 
 
A
B S 
 
 
S = BA 
 
 
A B S 
0 0 1 
0 1 0 
1 0 0 
1 1 0 
 
 
A porta NOR equivale a uma porta OR seguida por uma porta NOT, isto é, ela 
produz uma saída que é o inverso da saída produzida pela porta OR. 
 
 
 10
Porta NAND (NÃO E) 
 
Representação gráfica: 
 
A
B S 
 
 
S = BA  
 
 
A B S 
0 0 1 
0 1 1 
1 0 1 
1 1 0 
 
 
A porta NAND equivale a uma porta AND seguida de uma porta NOT, isto é, ela 
produz uma saída que é o inverso da saída produzida pela porta AND. 
 
 
 
 
Porta XOR (OU EXCLUSIVO) 
 
Representação gráfica: 
 
A
B S 
 
 
S = BA 
 
 
A B S 
0 0 0 
0 1 1 
1 0 1 
1 1 0 
 
 
 11
A porta XOR compara os bits: ela produz a saída 1 quando somente um bit de 
entrada for igual a 1. 
 
B .A B . A B A  
 
S
A
B
 
 
 
Porta XNOR (NOR EXCLUSIVO) 
 
Representação gráfica: 
 
A
B
S
 
 
 
S = B A  
 
 
A B S 
0 0 1 
0 1 0 
1 0 0 
1 1 1 
 
 
A porta XNOR compara os bits: ela produz a saída 0 quando somente um bit de 
entrada for igual a 1. 
 
B . A B .A B A  
 
S
A
B
 
 
 12
 
Implementação de Funções Booleanas com Portas Lógicas 
 
 
Para implementar uma função lógica qualquer usando portas lógicas, devemos 
decompor a expressão em seus componentes atômicos e implementá-los com suas 
portas lógicas equivalentes. 
 
Exemplo: 
 
ABCS . 
 
Representação gráfica: 
 
A
B
C
S
 
 
 
 
Determinando a função booleana de um circuito lógico: 
 
 
X
Y
Z
S
 
 
S = 
 
 
 
Exercício: implementar a função booleana )(. BCABCS  com portas 
lógicas. 
 
 
 
 
 
 
 
 
 13
Comportamento de um Circuito Complexo 
 
 
Baseado nas tabelas dadas, pode-se determinar o comportamento de um circuito 
formado pela interligação dediversas portas lógicas. 
 
Exemplo: 
 
A
B
C
S
 
 
A B C S 
0 0 0 
0 0 1 
0 1 0 
0 1 1 
1 0 0 
1 0 1 
1 1 0 
1 1 1 
 
Exercício: determinar o comportamento do circuito abaixo. 
 
A
B
C
S
 
 
 
A B C S 
0 0 0 
0 0 1 
0 1 0 
0 1 1 
1 0 0 
1 0 1 
1 1 0 
1 1 1 
 
 
 14
 
Exercícios 
 
Dada as expressões boolenas abaixo, desenhe os circuitos lógicos e determine o 
comportamento dos circuitos (obter a tabela verdade). 
 
(a) ACBAS  . 
 
(b) CBAS  . 
 
(c) )).(( CABAS  
 
(d) )).(( CABAS  
 
(e) ).).().(( CAAABAS  
 
(f) CACBACAS ....  
 
(g) )..(. ACAABCS  
 15
Equivalência de Funções Lógicas 
 
 
Duas funções lógicas booleanas são equivalentes se e somente se, para a 
mesmo entrada, produzirem iguais valores de saída. 
 
Portanto, duas funções lógicas equivalentes possuem a mesma tabela verdade. 
 
Exercícios: verifique se as funções lógicas a seguir representam funções 
equivalentes. 
 
 
a) ).()( zxyx  e zyxzyx ....  
b) ).()( yxzx  e zyxzyx ....  
c) zyx . e ).( zyx  
 
 
Resolução do exemplo a: 
 
x y z yx  zx. yx  zx. ).()( zxyx  ).()( zxyx  
0 0 0 0 0 1 1 1 0 
0 0 1 0 0 1 1 1 0 
0 1 0 1 0 0 1 1 0 
0 1 1 1 0 0 1 1 0 
1 0 0 1 0 0 1 1 0 
1 0 1 1 1 0 0 0 1 
1 1 0 1 0 0 1 1 0 
1 1 1 1 1 0 0 0 1 
 
 
x y z z yx. zyx .. zyx .. zyxzyx .... 
0 0 0 1 0 0 0 0 
0 0 1 0 0 0 0 0 
0 1 0 1 0 0 0 0 
0 1 1 0 0 0 0 0 
1 0 0 1 0 0 0 0 
1 0 1 0 0 0 0 0 
1 1 0 1 1 1 0 1 
1 1 1 0 1 0 1 1 
 
 
NÃO SÃO EQUIVALENTES !!!! 
 
 
 16
Propriedades ou axiomas da Álgebra Booleana 
 
 
Adição lógica 
 
(1) xx  0 
(2) 11x 
(3) xxx  
(4) 1 xx 
 
 
Multiplicação lógica 
 
(5) xx 1 
(6) 00 x 
(7) xxx  
(8) 0 xx 
 
 
Complementação 
 
(9) xx  
 
Comutatividade 
 
(10) xyyx  
(11) xyyx  
 
 
Associatividade 
 
(12) zyxzyx  )()( 
(13) zyxzyx  )()( 
 
 
Distributividade 
 
(14) zxyxzyx  )( 
(15) )()( zxyxzyx  
 
 
Leis da absorção 
 
(16) xyxx  )( 
(17) xyxx  )( 
 
 
Teoremas de De Morgan 
 
(18) yxyx  
(19) yxyx  
 
 
 
 
Propriedades da função exclusiva OR (XOR) 
 
A B BA BA 
0 0 0 1 
0 1 1 0 
1 0 1 0 
1 1 0 1 
 
 B . A B .A B A 
B .A B . A B A 


 
 
Outras propriedades 
 1 A A 
0 A A 


 
 17
 
Simplificação de Expressões Booleanas 
 
 
A simplificação das expressões booleanas é feita por manipulação algébrica, 
usando-se as propriedades da álgebra booleana. 
 
Exemplos: 
 
a) CACBACBA .....  
 
 
 
 
 
 
 
 
 
 
 
b) BACAABC )...(.  
 
 
 
 
 
 
 
 
 
 
 
c) AACBABA  ..)(. 
 
 
 
 
 
 
 
 
 
 
 
 18
 
Portas Universais 
 
 
Revisão 
 
Porta NOR Porta NAND 
 
 
Porta NOR Porta NAND 
A B S A B S 
0 0 0 0 
0 1 0 1 
1 0 1 0 
1 1 1 1 
 
 
 
Circuito NAND 
 
A porta NAND é dita “porta universal” porque qualquer sistema digital pode ser 
implementado somente com portas NAND. 
 
NOT 
 
 
 
 
AND 
 
 
 
 
 19
OR 
 
 
 
 
 
Circuito NOR 
 
A porta NOR é também outra “porta universal” que pode ser utilizada para 
implementar qualquer função booleana. 
 
NOT 
 
 
 
 
OR 
 
 
 
 
AND 
 
 
 
 20
Exercícios 
 
Implemente os circuitos das expressões abaixo somente com as portas 
universais NOR e NAND. 
 
(a) CBAS  . 
 
(b) ACBAS  . 
 
(c) )).(( CABAS  
 
(d) )(.).( BACBAS 