Unidade_5_-_Simplificacao_Booleana

Prévia do material em texto

Sistemas Digitais I – Eng. de Computação – Profa. Josiane Rodrigues 1
Unidade 5 
Simplificação Booleana 
 
Introdução 
 A álgebra Booleana é a matemática dos sistemas digitais. Um conhecimento básico 
de álgebra Booleana é indispensável para o estudo e análise de circuitos lógicos. No 
capítulo anterior, as operações Boolenas em termos de suas relações com as portas lógicas 
foram introduzidas. Assim como em outras áreas da matemática, existem certas regras bem 
desenvolvidas e leis que têm que ser seguidas para aplicar adequadamente a álgebra 
Booleana. As mais importantes são apresentadas na seção 5.2. Ao aplicarmos a álgebra 
Booleana, muitas vezes temos que reduzir uma determinada expressão para a sua forma 
mais simples. Isso significa que o circuito usará menos circuitos integrados (CI´s) para ser 
montado, reduzindo o espaço ocupado pelo mesmo e seu custo. Desta forma, seguindo as 
regras da álgebra de Boole poderemos simplificar expressões lógicas, ou seja, os circuitos 
envolvidos na implementação dessas expressões. 
 
5.1 – Identidades Booleanas Básicas 
 
 São as ferramentas algébricas para a manipulação e simplificação de expressões 
Booleanas (expressões resultantes de circuitos digitais). Nas identidades e propriedades a 
seguir, ‘A’ pode representar uma variável lógica qualquer ou mesmo uma expressão lógica. 
 
A x 0 = 0 
A + 1 = 1 
A x 1 = A 
A + 0 = A 
A x A = A 
A + A = A 
A x A = 0 
A + A = 1 
 
Essas identidades podem ser provadas substituindo-se, em caso, todos os valores 
possíveis de A, formando-se tabelas verdades. 
 
5.2 – Propriedades da Álgebra Boolena 
 
5.2.1 – Comutativa 
 
 Permite arranjar as variáveis em qualquer ordem, sem alterar o resultado. 
 
A + B = B + A e A x B = B x A 
 
 
 
 
Sistemas Digitais I – Eng. de Computação – Profa. Josiane Rodrigues 2
5.2.2 – Associativa 
 
 Define a ordem na qual as operações são executadas. Tanto na operação OR, quanto 
na operação AND, o agrupamento não afeta o resultado. 
Para a operação OR: 
A + B + C = (A + B) + C 
 = A + (B + C) 
 
Para a operação AND: 
 
 A x B x C = (A x B) x C 
= A x (B x C) 
 
Obs.: A + B x C  (A + B) x C 
 
5.2.3 – Distributiva 
 
 A distributividade em operações AND e OR obedece as leis descritas a seguir. É 
importante lembrar a regra de precedência na qual, sem agrupamento definido, a operação 
AND é sempre executada antas da operação OR. 
 
A x (B + C) = A x B + A x C 
A + (B x C) = (A + B) x (A + C) 
 
5.3 – Teorema de DeMorgan 
 
 Este teorema fornece expressões alternativas que relacionam as operações NOR e 
NAND. Elas são muito úteis nos problemas de projeto prático e fazem parte de um 
conjunto fundamental de técnicas utilizadas por projetistas lógicos. 
 A função OR, A + B, só pode ser 0 quando A e B são ambos 0, do contrário A + B 
= 1. Já a função AND, A x B, só pode ser 1 quando A e B forem ambos 1, do contrário A x 
B=0. Portanto, existe uma relação entre as funções AND e OR, e essa relação é 
estabelecida pelo teorema de DeMorgan: 
 
BABxA
BxABA


 
 
 
 
 
 
 
 
 
 
O 
A 
B AB BA  
A 
B 
BA  O 
A 
B BxA 
A 
B 
Sistemas Digitais I – Eng. de Computação – Profa. Josiane Rodrigues 3
 A primeira igualdade diz que o complemento do produto é a soma dos 
complementos. A segunda igualdade diz que o complemento da soma é o produto dos 
complementos. 
 O teorema de DeMorgan é válido para qualquer número de variáveis: 
 
Nxx...CxBxAN...CBA
N...CBAN...xxCxBxA


 
 
5.4 – Identidades Auxiliares 
 
5.4.1 – A + A x B = A 
 
 Provamos esta identidade, utilizando a propriedade distributiva. Vamos evidenciar 
A no 1o termo: 
 
 A (1 + B) = A 
 
 Do postulado da soma temos: 1 + B = 1, logo podemos escrever: 
 
 A x 1 = A A + A x B = A 
 
5.4.2 – (A + B) x (A + C) = A + B x C 
  
CxBA
CBBCA
CBBACAA
CBBACAAA




.1
...
....
 
 
5.4.3 - BABxAA  
  
 
 
BA
BA
BAAA
BAxA
BAxA
BAABAA












 
.
)(
)(
 
 
 
 
 
 
Sistemas Digitais I – Eng. de Computação – Profa. Josiane Rodrigues 4
Resumindo: 
 
POSTULADOS: 
Complementação Adição Multiplicação 
01
10


AA
AA
 
0 + 0 = 0 
0 + 1 = 1 
1 + 0 = 1 
1 + 1 = 1 
0 x 0 = 0 
0 x 1 = 0 
1 x 0 =0 
1 x 1 = 1 
IDENTIDADES: 
Complementação Adição Multiplicação 
AA  
A + 0 = A 
A + 1 = 1 
A + A = A 
A + A = 1 
A x 0 = 0 
A x 1 = A 
A x A = A 
A x A = 0 
PROPRIEDADES: 
Comutativa: A + B = B + A 
 A x B = B x A 
Associativa: A + (B + C) = (A + B) + C = A + B + C 
 A x (B x C) = (A x B) x C = A x B x C 
Distributiva: A x (B + C) = A x B + A x C 
Teorema de DeMorgan: 
BxABA
BABxA


)(
)(
 
IDENTIDADES AUXILIARES: 
A + A x B = A 
A + A x B = A + B 
(A + B) x (A + C) = A + B x C 
 
5.5 – Simplificações Algébricas 
 
Estudaremos agora como a álgebra Booleana pode ser aplicada no projeto de 
sistemas lógicos digitais. 
 Um problema comum no projeto de lógica combinacional é a simplificação de 
expressões lógicas para sua forma mais simples possível. Isto significa que queremos 
implementar a função usando o menor número possível de portas lógicas. A simplificação é 
efetuada aplicando-se as identidades básicas de forma seqüencial. Como veremos a seguir: 
 
 
 
 
 
 
 
Sistemas Digitais I – Eng. de Computação – Profa. Josiane Rodrigues 5
Exemplo 1 
 
 Vamos simplificar a equação: 
 
BABAf  . 
 
Primeiramente, utilizaremos a propriedade distributiva para agrupar os termos com 
B, de tal forma que: 
 
)( BBAf  . 
 
Como a expressão entre parênteses é igual a 1, temos que: 
 
Af
AAf

 1
 
 
Essa é a forma mais simples da função f. Observe que a função f original tem duas 
funções AND, uma operação OR e uma NOT, sendo que a álgebra mostra que todo esse 
circuito pode ser substituído apenas por A. A Fig. 5.1 mostra o circuito antes e depois da 
simplificação. 
 
 
 
Fig. 5.1 – Circuito representativo da função f antes e depois da simplificação. 
 
Exemplo 2 
 
 A função CBCBAf  necessita de uma porta AND de três entradas, uma 
AND de duas entradas e uma OR de duas entradas. Entretanto, se agruparmos o fator CB  , 
poderemos escrever: 
 
CBf
CBAf
CBCBAf



)(]1[
)()(
 
 
a segunda linha mostra que A é redundante. Com esta redução, podemos ver que f pode ser 
implementada com uma única porta AND de duas entradas. 
 
f A 
Sistemas Digitais I – Eng. de Computação – Profa. Josiane Rodrigues 6
Exemplo 3 
 
 Simplifique a expressão abaixo: 
 
BABAf  
Usando a propriedade distributiva e as identidades, teremos: 
 
Af
Af
BBAf



1
)(
 
Exemplo 4 
 
 Suponha a seguinte função: 
 
)()( cbcbag  
 
Aplicando a regra de DeMorgan para a operação NOR, obtemos: 
 
)()( cbcbag  
 
que pode ser rescrita usando outra relação de DeMorgan para: 
 
0
)()(



g
ccbbag
cbcbag
 
 
Portanto g = 0, pois 0 XX , o que se aplica tanto à variável b quanto à variável c. Isto 
significa que g é sempre igual a zero, independentemente de qualquer variável, ou seja, g é 
uma constante. 
 
5.6 - Bibliografia 
 
1 – Elementos de Eletrônica Digital – Capuano e Idoeta – Editora Érica – 19a Edição; 
2 – Sistemas Digitais – Fundamentos e Aplicações – Thomas L. Floyd - Ed.Bookman – 9a 
Edição;