Algebra Booleana

Prévia do material em texto

Prof. Eric Fagotto texto não revisado, pode conter erros 
fev./1998 - V. 1.0 
 1 
Álgebra de Boole 
 O postulado básico da álgebra de Boole é a existência de uma variável boolena tal 
que: 
x≠0 ⇔ x=1 
x≠1 ⇔ x=0 
 
 A álgebra de Boole é um sistema algébrico que consiste do conjunto {0,1}, duas 
operações binárias chamadas OR (operador: +) e AND (.) e uma operação unária NOT 
( ). 
 A operação OR é chamada de soma lógica ou união, a operação AND é conhecida 
por produto lógico ou interseção e a operação NOT é dita complementação ou ainda 
inversão (não confundir com a soma de números binários). Estas operações são definidas 
conforme as tabelas a seguir: 
 
Operação OR AND NOT 
 0 + 0 = 0 0 ⋅⋅⋅⋅ 0 = 0 0 1= 
 0 + 1 = 1 0 ⋅⋅⋅⋅1 = 0 1 0= 
 1 + 0 = 1 1 ⋅⋅⋅⋅ 0 = 0 
 1 + 1 = 1 1 ⋅⋅⋅⋅ 1 = 1 
 
 Estas operações podem ser representadas por circuitos lógicos elementares 
denominados portas ou gates: 
 
 
 
 OR AND NOT 
 
(Atenção! Ler "+” como “ou” e “.” como “AND”, ressaltando a diferença com a 
aritmética binária) 
 Um circuito de composto de gates é chamado de circuito lógico. O circuito 
mostrado abaixo realiza a expressão lógica A . B + C + D . E 
 
 
 
 
 
 
 
 
 
 
A 
B 
C 
D 
E 
AB 
DE 
AB+C AB+C + DE 
Prof. Eric Fagotto texto não revisado, pode conter erros 
fev./1998 - V. 1.0 
 2 
 
Acrescentar a simbologia para as negações de OR e de AND! 
 
Circuito Ou-Exclusivo (X-OR) 
 A tabela verdade para a função que o X-OR executa é: 
 
A B S 
0 0 0 
0 1 1 
1 0 1 
1 1 0 
 
 Uma expressão booleana para esta função seria (ela não é única!) S AB AB= + . 
Peça aos alunos para montar o circuito. 
 Utiliza-se o seguinte operador para denotar a operação de X-OR: ⊕. Logo, 
para a tabela anterior S =A⊕B 
 
 
 
 
 
 Complementando o X-OR obtemos o circuito que é conhecido como coincidência, 
nome que vem do fato de sua saída ser somente igual a “1” quando existir coincidência 
nas suas entradas, i.e.: 
A B S 
0 0 1 
0 1 0 
1 0 0 
1 1 1 
 
Símbolo: acrescentar um inversor à saída do X-OR 
Operador: , operação: S=A B. 
 
 
Propriedades Básicas 
Sendo x uma variável booleana, então: 
 
• x + 1 = 1 • x . 1 = x 
• x . 0 = 0 • x + x = x 
• x + 0 = x • x . x = x 
 
A álgebra booleana é comutativa e associativa com relação às duas operações binárias. 
Sendo x, y, z variáveis booleanas, então 
 
A
 
B 
S 
Prof. Eric Fagotto texto não revisado, pode conter erros 
fev./1998 - V. 1.0 
 3 
Comutativa 
x + y = y + x
x . y = y . x
�
�
�
 
( ) ( )
( ) ( )Associativa 
x + y + z = x + y + z
x . y . z = x . y . x
�
�
�
��
 
Complemento 
x + x = 1
x . x = 0
�
�
�
 
 
 Na álgebra booleana, a soma é distributiva sobre o produto e o produto é 
distributivo sobre a soma, 
 
( )
( ) ( ) ( )Distributiva 
x . y + z = x . y + x . z
x + y . z = x + y . x + z
�
�
�
��
 
 
 Notemos que estas propriedades apresentam-se aos pares e que em cada par, uma 
equação pode ser obtida da outra mediante a troca de 1 por 0 e 0 por 1 além de 
permutarmos os AND’s pelos OR’s . Isto é conhecido como princípio da dualidade da 
álgebra de Boole (obs: todas estas expressões podem ser provadas por indução finita, 
bastando provar uma equação e a sua dual estará provada). 
 
Expressões Booleanas 
 Define-se expressão booleana como a combinação de um número finito de 
variáveis booleanas (0,1) através das operações booleanas (+), (.) e ( ). Qualquer 
constante ou variável booleana é uma expressão booleana, e se T1 e T2 são expressões 
booleanas, o mesmo acontecerá para T T1 2, , T1+T2, T1.T2 . 
 As propriedades a seguir formam o conjunto fundamental de ferramentas básicas 
para a simplificação de expressões booleanas. 
 
( )
( )
x+xy=x
x x+y x
propriedades de absorção 
x+xy x y
x x+y xy
�
�
=�
�
= +
�
�
=
�
 
 
( )( )( ) ( )( )
xy+xz+yz=xy+xz
propriedades de consenso 
x+y x+z y+z x+y x+z
��
�
=��
 
Prof. Eric Fagotto texto não revisado, pode conter erros 
fev./1998 - V. 1.0 
 4 
Ex1: Simplifique a expressão F(x,y,z)
( )
( )
( )
=
= =
x y z + yz + xz
= z x y + y + x
= z x + y + x
= z y +1 z.1 z
 
 
Ou seja, F(x,y,z) independe dos valores de x e y, i.e., F(x,y,z) é F(x)! 
 
 É muito importante notar que na álgebra de Boole não são definidas operações 
inversas e portanto, não são permitidos cancelamentos. Por exemplo, se A+B=A+C, não 
significa que B=C. De fato, se A=B=1 e C=0 � 1+1=1+0, embora B seja diferente C. 
Analogamente, AB=AC não implica em B=C. 
 
Teorema de De Morgan 
 As regras que regem a operação de complementação para duas variáveis se 
resumem nos três teoremas seguintes: 
 
x = x
x + y = x y
xy x + y=
 
 
 De forma geral, o Teorema de De Morgan afirma que o complemento de qualquer 
expressão pode ser obtido trocando-se simultaneamente cada variável por seu 
complemento e as operações OR por AND e AND por OR, i.e. 
 
f(x1,x2,...,xn,0,1,+,.) = f(x1,x2,...,xn,1,0,.,+) 
 
Aplicações de Funções Booleanas 
Isomorfismo 
Dois sistemas algébricos (cada um consistindo de um conjunto de elementos e uma ou 
mais operações que satisfazem um conjunto de postulados) são ditos isomórficos caso 
sejam satisfeitas as seguintes condições: 
• correspondência unívoca entre elementos e operações 
• todos postulados de um sistema são válidos no outro, mediante a troca dos elementos 
e das operações. 
Conclusão: Dois sistemas isomórficos serão idênticos, à exceção dos símbolos usados 
para representar os seus elementos e operações. 
 
Prof. Eric Fagotto texto não revisado, pode conter erros 
fev./1998 - V. 1.0 
 5 
Circuitos de Chaveamento ou de Comutação ( Switching Circuits ) 
 Chave → elemento de dois estados (informação, bloqueio) 
 ↓ 
 associar variável booleana → não complementada (informação) = 1 
 ↓ 
 complementada (bloqueio) = 0 
 
A conexão paralela de duas chaves X e Y � X+Y, 
 “ série “ � X .Y 
 
Monte as T.V. para estas duas situações, observando o isomorfismo com a A.B. 
Podemos associar a cada circuito uma função de transmissão, que assumirá valor 
1 
que houver continuidade entre os terminais. Exemplificar com F=xy’+(x’+y)z, 
simplificando (F=xy’+z). 
 
Cálculo das Proposições 
 Uma proposição é uma afirmação que em função de certas condições deve ser 
verdadeira ou falsa. A cada proposição associa-se uma variável, que assume o valor 1 se a 
proposição é verdadeira, e 0 se a proposição for falsa. 
 Diremos que uma proposição será uma negação da outra quando elas implicarem 
em situações excludentes. 
Ex: “Não está chovendo” é uma negação de “está chovendo”. 
 
Duas proposições podem ser combinadas para formar uma nova proposição. 
Ex: p - temp > 30° C e u - umid > 50%. As proposições p and q sendo verdadeiras 
implicam que a temperatura está acima de 30° C e a umidade acima de 50%. 
 
Ex: 
Um sistema condicionador de ar deve ser ligado se ocorrer uma ou mais das seguintes 
condições: 
• a massa do material armazenado for menor ou igual a 100 ton., a umidade 
relativa do ar for maior do que 60%, e a temperatura estiver acima de 15 graus. 
• a massa do material armazenado for maior ou igual a 100 ton. e a temperatura 
estiver acima de quinze graus. 
 
Considere as variáveis: 
P - peso maior ou igual a 100 ton. 
U - umidade relativa do ar maior ou igual a 60% 
T - temperatura acima de 15 graus. 
 L - ar condicionado ligado 
 
L PUT PT= + , que simplificada conduz a L = T(U+P) 
 
 
Prof. Eric Fagottotexto não revisado, pode conter erros 
fev./1998 - V. 1.0 
 6 
Funções Booleanas 
 Seja F(x1, x2, ..., xn) uma expressão booleana, e visto que cada uma das n 
variáveis pode assumir independentemente o valor 0 ou 1 existirão 2
n
 combinações de 
variáveis a serem considerados na determinação de F. 
Ex: Considere F(x,y,z)= xz + xz + x y . Para a combinação x=0, y=0 e z=1 temos: 
F(x,y,z)= 01 0 1 0 0. . .+ + =1.1+0.0+1.1=1 
 
Calculando F(x,y,z) para todas as 8 combinações de variáveis, mostramos os resultados 
no quadro abaixo, que é conhecido como tabela verdade para F(x,y,z). 
 
 
x y z T 
0 0 0 1 
0 0 1 1 
0 1 0 0 
0 1 1 1 
1 0 0 1 
1 0 1 0 
1 1 0 1 
1 1 1 0 
 
Repetindo-se o procedimento para construir a tabela verdade da expressão xz xz y z+ + , 
obteremos uma tabela idêntica a anterior. Deste modo, verificamos que expressões 
booleanas diferentes podem ser representadas pela mesma tabela verdade. Contudo, 
devemos notar que cada tabela verdade define apenas uma função booleana, embora esta 
função possa ser expressa por diferentes expressões booleanas. Em outras palavras, uma função 
booleana f(x1,...,xn) é a correspondência que associa um elemento da Álgebra de Boole com cada uma das 
2n combinações das variáveis x1, ..., xn. 
 
Formas Canônicas 
Podemos derivar da tabela verdade para uma função F(x,y,z) expressões booleanas que 
representem esta função. 
 
Mintermos 
Dada uma tabela verdade qualquer podemos escrever uma função booleana 
correspondente através da soma de todos os mintermos para os quais a função assume 
valor 1. Um mintermo é qualquer produto que contenha as n variáveis de uma função 
como fatores. Contudo, na soma dos mintermos que representarão a função booleana, uma 
variável aparecerá complementada num mintermo caso ela assuma valor 0 nesta 
combinação. Retomando a tabela anterior, constatamos que para x=y=0 e z=1 F(x,y,z)=1, 
e portanto o mintermo x y z aparecerá na expressão da função. Na verdade, F(x,y,z) pode 
ser escrita como: 
 
F(x,y,z)= x y z + x y z + x y z + x y z + x y z . 
 Esta expressão obtida para F(x,y,z) é chamada de soma canônica de produtos. 
Prof. Eric Fagotto texto não revisado, pode conter erros 
fev./1998 - V. 1.0 
 7 
 As funções booleanas são normalmente expressas pelos códigos decimais 
associados aos mintermos para os quais a função vale 1. Assim, o mintermo x y z que 
está associado à linha 001, que interpretada como um número binário corresponde ao 
decimal 3. Deste modo, podemos escrever F(x,y,z) como 
 
F(x,y,z)=S(0,1,3,4,6), 
 
onde S( ) significa a soma de todos os mintermos cujos códigos decimais estão entre os 
parênteses. 
 
Maxtermos 
 Uma função booleana também pode ser expressa através do produto de todos os 
maxtermos para os quais a função assume valor 0. Um maxtermo é qualquer soma que 
contenha as n variáveis de uma função como parcelas. Contudo, no produto dos 
maxtermos que representarão a função booleana, uma variável aparecerá complementada 
num maxtermo caso ela assuma valor 1 nesta combinação. Como exemplo tomemos 
F(x,y,z), para x=z=0 e y=1; o maxtermo correspondente será ( )x y z+ + . Desta forma, 
poderemos escrever F(x,y,z) como 
 
F(x,y,z)=P(2,5,7), 
 
onde P( ) significa o produto de todos os maxtermos cujos códigos decimais estão entre 
os parênteses. Esta expressão obtida para F(x,y,z) é conhecida como produto canônico de 
somas. 
 
Estados Irrelevantes (Don’t Care States) 
 Existem algumas funções para as quais certas combinações das variáveis de entrada 
corresponderão a situações que serão irrelevantes para o funcionamento do projeto. Para estas 
combinações de entrada, o valor da função é descrito por um estado irrelevante (Don’t Care 
State-DC), denotado por X ou um traço (−). Podem ser indicadas pelos decimais contidos na 
notação D( ). Ex: Dada a tabela verdade : 
w x y z F 
0 0 0 0 0 
0 0 0 1 0 
0 0 1 0 0 
0 0 1 1 X 
0 1 0 0 1 
0 1 0 1 1 
0 1 1 0 0 
0 1 1 1 0 
1 0 0 0 1 
1 0 0 1 0 
1 0 1 0 0 
1 0 1 1 0 
1 1 0 0 1 
1 1 0 1 1 
1 1 1 0 X 
1 1 1 1 X 
 
Prof. Eric Fagotto texto não revisado, pode conter erros 
fev./1998 - V. 1.0 
 8 
 
Podemos escrever a função booleana correspondente como 
 
F(x,y,z)=S(4,5,8,12,13)+D(3,14,15) 
 
 
Mapas de Karnaugh 
 Um Mapa de Karnaugh (MK) é uma forma modificada da tabela verdade, onde as 
combinações de entrada estão arranjadas de modo a facilitar a simplificação de uma 
expressão booleana. 
 A seguir temos os MK para as situações de 2 a 6 variáveis 
 
 
 
 0 1 00 01 11 10 00 01 11 10 
 0 0 2 0 0 2 6 4 00 0 4 12 8 
 1 1 3 1 1 3 7 5 01 1 5 13 9 
 11 3 7 15 11 
 10 2 6 14 10 
 
 
 
 
 
 
 00 01 11 10 00 01 11 10 
 00 0 4 12 8 16 20 28 24 00 
 01 1 5 13 9 17 21 29 25 01 
 11 3 7 15 11 19 23 31 27 11 
 10 2 6 14 10 18 22 30 26 10 
 
 
 
 
 
 
 00 01 11 10 00 01 11 10 
 00 0 4 12 8 16 20 28 24 00 
 01 1 5 13 9 17 21 29 25 01 
 11 3 7 15 11 19 23 31 27 11 
 10 2 6 14 10 18 22 30 26 10 
 
 00 32 36 44 40 48 52 60 56 00 
 01 33 37 45 41 49 53 61 57 01 
 11 35 39 47 43 51 55 63 59 11 
 10 34 38 46 42 50 54 62 58 10 
 00 01 11 10 00 01 11 10 
 
 
2 variáveis 3 variáveis 
4 variáveis 
5 variáveis 
6 variáveis 
A 
 B 
AB 
C 
AB 
CD 
BC 
DE 
BC 
DE 
CD 
EF 
CD 
EF 
CD 
EF 
CD 
EF 
A=1 A=0 
B=1 B=0 
A=1 
A=0 
Prof. Eric Fagotto texto não revisado, pode conter erros 
fev./1998 - V. 1.0 
 9 
 Cada mapa de n variáveis consiste de 2
n
 células, representando todas as possíveis 
combinações de entrada. Para tornar os mapas mais compactos, optamos representar estas 
combinações através de códigos decimais. 
 O valor da função associado a uma combinação particular de entradas é anotado na 
célula correspondente. Como exemplo vamos montar o MK para a função 
F(w,x,y,z)=S(4,5,8,12,13)+D(3,14,15) 
 
 00 01 11 10 
00 1 1 1 
01 1 1 
11 X X 
10 X 
 
 De acordo com o método de ordenamento do MK, células adjacentes corresponderão às 
combinações que diferem unicamente por um bit. Por exemplo: 
 
células adjacências 
13 5 9 12 15 
1101 0101 1001 1100 1111 
0 1 2 4 8 
0000 0001 0010 0100 1000 
2 0 3 6 10 
0010 0000 0011 0110 1010 
 
IMPORTANTE: Compreenda bem o que significa diferir por um bit. Apesar de 1 e 2 
estarem “distanciados” por uma unidade, suas representações binárias diferem por dois 
bits! 
 
 
 
 Inspecionando-se, por exemplo, o MK para quatro variáveis, constatamos que a 
célula “4” não está colocada ao lado da célula “0” (pelo menos aparentemente). A 
explicação para este fato decorre dos MK serem versões topológicas planas de 
superfícies. 
 
 
 
 
 
wx 
yz 
Cilíndro 
Prof. Eric Fagotto texto não revisado, pode conter erros 
fev./1998 - V. 1.0 
 10 
 
 
 
 
 
 
Para um número maior do que 4 variáveis, o volume necessitará mais do que três 
dimensões para ser representado. 
 Como já devemos ter notado, existirá um número n de vizinhos adjacentes a cada 
célula de um MK escrito para n variáveis. 
 Retornando ao assunto de minimização de funções booleanas, podemos verificar 
prontamente que células adjacentes serão simplificadas de acordo com a regra do 
complemento das operações binárias (x+x’=11). Deste modo, a soma dos mintermos 
relativa à união de duas células adjacentes (para as quais a função assume valor “1”) é 
obtida ignorando-se as variáveis que assumem valor “1” numa célula e “0” na outra. 
Assim, a quadra 4-5-12-13 corresponde a xy’. 
 
 
 É dado o nome de subcubo de ordem m a um conjunto de m células de um MK, e 
nos referimos a ele dizendo que cobre estas m células. Todo subcubo cuja ocorrência 
obriga a função a ter valor “1”, é dito implicara função, ou seja, é um implicante da 
função ao qual existe associado um produto de literais. 
 Uma função pode ser expressa como a soma dos implicantes correspondentes aos 
subcubos necessários para cobrir todas as células de valor “1”. Utilizando deste 
procedimento, escreveremos a função F para o MK anterior como sendo: 
 
F=xy’+wy’z’ 
 
 Para se obter uma expressão mínima para a função deve-se cobrir todas as células 
de valor “1” com subcubos tão grandes quanto possível, pois isto diminuirá o número de 
de literais. Portanto, um subcubo totalmente contido num subcubo maior não deverá ser 
escolhido. 
 Os DCS podem e devem ser utilizados para facilitar a obtenção de expressões, 
sendo a eles atribuídos valor “0” ou “1” conforme a conveniência. 
 
1
 De agora em diante também estaremos adotando como convenções de notação : 
A’= A ; (+) ≡ XOR; (*) ≡ NXOR 
 
Toróide 
“base” 
Toróide 
“topo” 
Prof. Eric Fagotto texto não revisado, pode conter erros 
fev./1998 - V. 1.0 
 11 
 Ainda com relação a nomenclatura, um implicante correspondente a um subcubo 
não contido totalmente num subcubo maior, é chamado de implicante-primo. Além disso 
temos: 
 
• referência: é a célula de menor valor decimal do subcubo 
• redundância: é soma dos pesos binários das variáveis que não participam no 
produto das literais 
 
Implicantes Células Binários Referência Redundância 
 w x y z 
xy’ 4,5,12,13 - 1 0 - 4 9 
wy’z’ 8,12 1 - 0 0 8 4 
 
Acasos (Hazards) 
 Os circuitos digitais reais não respondem instantaneamente aos sinais nas 
entradas, o que acarreta atraso na mudança dos estados e evetualmente acasos (hazards). 
Convencionou-se definir os tempos: 
• TPLH - time for propagation of the LOW to HIGH 
• TPHL - time for propagation of the HIGH to LOW 
 
Ex: Considere a função F(x,y,z)= S(2,3,5,7) 
 
 
 
 
Portanto F(x,y,z)=x’y+xz 
 
Contudo, suponhamos: 
1. y = z = ”1 ” 
2. x esteja mudando de “0” para “1”. 
3. TPHL1<TPLH2 
 
Esta situação é descrita graficamente através do diagrama de temporização. Em cores 
vermelhas temos os sinais gerados em função do tempo, tendo o circuito somente dois 
gates (dois sub-cubos sem entrelaçamento). Conforme se pode constatar, devido ao 
TPHL1<TPHL2, durante um certo intervalo de tempo a saída do circuito, F, fica em nível 
baixo, enquanto o correto seria que esta saída F permanecesse em nível alto. A este tipo 
de ocorrência damos o nome de acaso (hazard) estático. Ao fazermos o entrelaçamento 
 
 
x’ 
y 
 
x 
z 
 00 01 11 10 
0 1 
1 1 1 1 
1 
F 
 
2 
xy 
z 
TPLH 
TPHL 
Prof. Eric Fagotto texto não revisado, pode conter erros 
fev./1998 - V. 1.0 
 12 
entre os subcubos, é adicionado mais um gate (yx) ao circuito (que descreve a transição 
x: 0 → 1, com y=z=1) o que elimina o hazard estático. 
Pergunta: O que acontecerá se duas entradas mudarem de forma simultânea e elas 
estiverem conectadas a gates com tempos diferentes de propagação? 
 
 
 
 
 
 
 
Referência p/ estas notas: Bonatti Ivani e Madureira Marcos, 
Introdução à Análise e Síntese de Circuitos Lógicos, Editora da 
UNICAMP (1990). Livro esgotado. 
yz 
Diagrama de temporização descrevendo a ação do hazard estático e o 
acréscimo do gate “redundante”, o que elimina o problema.