Introdução à Álgebra Booleana

Prévia do material em texto

UUnniivveerrssiiddaaddee FFeeddeerraall ddee JJuuiizz ddee FFoorraa 
FFaaccuullddaaddee ddee EEnnggeennhhaarriiaa 
DDeeppaarrttaammeennttoo ddee CCiirrccuuiittooss EEllééttrriiccooss 
 
 
CCIIRRCCUUIITTOOSS LLÓÓGGIICCOOSS 
 
Página 1 de 5 
CCaappííttuulloo 22 
IInnttrroodduuççããoo àà ÁÁllggeebbrraa BBoooolleeaannaa 
 
1. Introdução 
 A manipulação de variáveis que podem assumir apenas dois valores distintos foi sistematizada por 
Shannon, usando idéias do matemático inglês George Boole. Este ramo da Matemática recebe o nome de 
Álgebra Booleana, sendo que as variáveis booleanas (VB), ao contrário das variáveis algébricas usuais, 
podem assumir apenas dois valores. Assim, se A é uma variável booleana ela pode valer apenas 
verdadeiro/falso, quente/frio, macho/fêmea etc. Os símbolos 1 e 0 são usados para representar, de uma 
maneira geral, os dois possíveis valores que qualquer variável booleana pode assumir. 
 As VB não assumem valores quantitativos, mas podem ser usadas para representar informações 
quantitativas. Por exemplo, um número de 4 bits pode ser representado por quatro VB, onde cada uma 
delas está relacionada com cada um dos quatro coeficientes do número. Assim, há 16 maneiras distintas de 
usarmos essas quatro variáveis, sendo possível representar desde 0000 (decimal 0) até 1111 (decimal 15). 
 É possível manipularmos as VB usando-se operadores similares aos operadores algébricos usuais. 
Esses operadores são comumente denominados operadores lógicos ou conectivos lógicos e os mais 
importantes serão analisados a seguir. 
 
2. O conectivo E (AND) 
 Este conectivo é muito semelhante à multiplicação, embora não se deva levar essa comparação muito 
adiante. Os símbolos mais comuns para a operação E são (A e B são VB): 
f(A,B) = A . B = AB = A  B = A  B Operação E 
 Formalmente, dizemos que o E de várias VB é verdadeiro se todas as variáveis são verdadeiras. Uma 
maneira muitas vezes mais prática de representar a função de um conectivo lógico é construindo uma 
tabela da verdade (ou tabela verdade), que mostra todas os possíveis arranjos de valores lógicos que as 
variáveis podem assumir e o resultado da operação considerada para cada um desses arranjos. 
 A tabela da verdade para o E de duas variáveis seria: 
 
A B A . B 
0 0 0 
0 1 0 
1 0 0 
1 1 1 
Tabela da verdade (ou tabela verdade) para a operação E 
 
 A operação E pode ser relacionada com a operação elétrica de duas chaves ligadas em série. Apenas 
quando ambas as chaves estão fechadas há passagem de corrente elétrica que permite que o LED do 
circuito abaixo acenda. 
 
Apenas quando A e B estiverem fechadas o LED acenderá 
 
 Há muitas representações simbólicas diferentes para a operação 
E. Entretanto, o Institute of Electrical and Electronics Engineers e a 
American Standards Association propuseram um conjunto de símbolos 
distintivos para cada operação lógica de interesse. Cada símbolo é 
comumente denominado PORTA. As formas das portas E com duas e 
três entradas estão mostradas ao lado. 
 
Portas E com 2 e 3 entradas 
 
 
UUnniivveerrssiiddaaddee FFeeddeerraall ddee JJuuiizz ddee FFoorraa 
FFaaccuullddaaddee ddee EEnnggeennhhaarriiaa 
DDeeppaarrttaammeennttoo ddee CCiirrccuuiittooss EEllééttrriiccooss 
 
 
CCIIRRCCUUIITTOOSS LLÓÓGGIICCOOSS 
 
Página 2 de 5 
3. O conectivo OU (OR) 
 Este conectivo seria correspondente à adição na Álgebra usual. Os símbolos que podemos usar são: 
f(A,B) = A + B = A  B = A  B Operação OU 
 Para que o OU de VB seja verdadeiro, basta que uma delas seja verdadeira, não importando os 
valores lógicos assumidos pelas outras. A tabela da verdade correspondente está mostrada abaixo. 
 
A B A + B 
0 0 0 
0 1 1 
1 0 1 
1 1 1 
 
Tabela da verdade para a operação OU 
 
 Esta operação está eletricamente relacionada com chaves ligadas em paralelo, como esquematizado a 
seguir. 
 
 
Basta que a chave A ou a chave B esteja fechada para que o LED acenda 
 
 Os símbolos lógicos de portas OU com duas ou três entradas são os mostrados abaixo. 
 
 
Portas OU com 2 e 3 entradas 
 
4. O conectivo NÃO (NOT) 
 Este operador é definido para apenas um argumento e a operação NÃO, também chamada 
complementação ou inversão, tem como símbolos: 
 
f(A) = 
A
 = A’ = A* Operação NÃO 
 
 Este operador “troca” (complementa, inverte) o valor da variável, como mostra a tabela da verdade 
abaixo. 
A 
A
 
0 1 
1 0 
 
Tabela da verdade para a operação NÃO 
 
 O símbolo lógico da porta NÃO (porta inversora ou inversor) é o seguinte: 
 
 
Porta inversora (NÃO) 
 
 
UUnniivveerrssiiddaaddee FFeeddeerraall ddee JJuuiizz ddee FFoorraa 
FFaaccuullddaaddee ddee EEnnggeennhhaarriiaa 
DDeeppaarrttaammeennttoo ddee CCiirrccuuiittooss EEllééttrriiccooss 
 
 
CCIIRRCCUUIITTOOSS LLÓÓGGIICCOOSS 
 
Página 3 de 5 
 Uma simplificação comumente adotada nos esquemas elétricos digitais é representar uma inversão 
apenas por um círculo colocado à frente da variável, como mostra o exemplo a seguir. 
 
 
Simplificação ao se representar uma inversão de variável 
 
 
5. As portas NE, NOU e OU-EXCLUSIVO 
 Qualquer função de VB pode ser implementada usando-se apenas as portas E, OU e NÃO. Entretanto, 
outras portas existem que podem facilitar o projeto de circuitos lógicos. 
a) Porta NE (NAND) 
Uma porta E seguida por um inversor corresponde a uma porta Não-E ou NE. O resultado da operação 
NE entre duas variáveis é conseguido fazendo-se a inversão (complementação) do E das variáveis. O 
símbolo e a tabela da verdade para a porta NE de duas entradas estão mostrados abaixo. 
 
f(A,B) = 
A.B
 = (A.B)’ Função NE (NAND) 
 
A B 
A.B
 
 
A porta NE (NAND) 
 
0 0 1 
0 1 1 
1 0 1 
1 1 0 
 
b) Porta NOU (NOR) 
Uma porta NOU consiste de uma porta OU seguida de um inversor. O resultado da operação é o 
complemento do OU das variáveis. Ilustra-se a seguir. 
 
f(A,B) = 
A +B
 Função NOU (NOR) 
 
A B 
A + B
 
 
A porta NOU (NOR) 
 
0 0 1 
0 1 0 
1 0 0 
1 1 0 
 
c) A porta OU-EXCLUSIVO (EXCLUSIVE-OR; XOR) 
Uma porta especial é a OU-EXCLUSIVO: sua saída é 1 apenas quando as entradas são diferentes. 
Veja a seguir. 
 
f(A,B) = 
A B
 Função OU-EXCLUSIVO (XOR) 
 
A B A B 
 
A porta OU-
EXCLUSIVO (XOR) 
 
0 0 0 
0 1 1 
1 0 1 
1 1 0 
 
UUnniivveerrssiiddaaddee FFeeddeerraall ddee JJuuiizz ddee FFoorraa 
FFaaccuullddaaddee ddee EEnnggeennhhaarriiaa 
DDeeppaarrttaammeennttoo ddee CCiirrccuuiittooss EEllééttrriiccooss 
 
 
CCIIRRCCUUIITTOOSS LLÓÓGGIICCOOSS 
 
Página 4 de 5 
6. Proposições Elementares 
 Consideremos a tabela abaixo, que mostra diversas operações efetuadas sobre apenas uma variável 
booleana A. 
A A . A A + A A . 0 A . 1 A + 0 A + 1 A . 
A
 A + 
A
 
A
 
0 0 0 0 0 0 1 0 1 0 
1 1 1 0 1 1 1 0 1 1 
 
 Os resultados expressos na tabela mostram as proposições elementares da Álgebra Booleana que 
estão resumidas abaixo: 
A . A = A A . 0 = 0 A + 0 = A A . 
A
 = 0 
A
 = A 
A + A = A A . 1 = A A + 1 = 1 A + 
A
 = 1 
 
As nove proposições elementares da Álgebra Booleana 
7. Leis Fundamentais 
 Três são as leis fundamentais que regem as operações entre variáveis booleanas. São elas: 
 
Comutativa A + B = B + A 
A . B = B . A 
Associativa (A + B) + C = A + (B + C) 
(A . B) . C = A . (B . C) 
Distributiva A . (B + C) = A . B + A . C 
A + B . C = (A + B) . (A + C) 
8. Teoremas de De Morgan 
 São dois os teoremas de De Morgan, importantíssimos na simplificação de funções booleanas. 
Inicialmente, completemos a tabela abaixo. 
 
A B 
 
A +B
 
A
.
B
 
A.B
 
A+ 
B
 
0 0 
0 1 
1 0 
1 1 
 
 Notamos, pela tabela da verdade acima, que: 
 
A +B
 = 
A
.
B
 
 A . B
 = 
A
+
B
 
 
 Esses são os dois teoremas de De Morgan. Sua importância reside no fato de podermos implementar 
uma função OU com portas E e inversores e uma função E com portas OU e inversores. Veja o exemplo: 
A B A B A.B   
 
 
 
Um dos teoremas de De Morgan “em ação” 
 
UUnniivveerrssiiddaaddee FFeeddeerraall ddee JJuuiizz ddee FFoorraa 
FFaaccuullddaaddee ddee EEnnggeennhhaarriiaa 
DDeeppaarrttaammeennttoo ddee CCiirrccuuiittooss EEllééttrriiccooss 
 
 
CCIIRRCCUUIITTOOSS LLÓÓGGIICCOOSS 
 
Página 5 de 5 
 
Exercícios 
 
1. Mostre como podemos implementar as operações E, OU e NÃO usando apenas portas NAND (para 
simplificar, considere apenas duas entradas). 
 
2. Prove que: 
a) A + AB = A 
b) A . (A + B) = A 
c) A + 
A
B = A + B 
d) A . (
A
 + B) = AB 
 
3. Prove, usando tabelas da verdade, que se f(A,B) é uma função booleana das variáveis A e B, então 
 
f(A,B) = A . f(1,B) + 
A
 . f(0, B) 
 
 
4. Desenhe um diagrama lógico para um somador completo de dois bits, que considera o “vem-um” da 
soma anterior (carry in, bit D) e gera o “vai-um” para a soma posterior (carry out, bit C). 
 
 
A B D S C 
0 0 0 
0 0 1 
0 1 0 
0 1 1 
1 0 0 
1 0 1 
1 1 0 
1 1 1