Unidade II Álgebra Booleana

Instituto Federal Sul-rio-grandense
Curso Tcnico em Telecomunicaes

Disciplina: Eletrnica Digital I
Prof. Gustavo Fabro de Azevedo
E-mail: gustavoazevedo@pelotas.ifsul.edu.br
Unidade II - lgebra Booleana
Introduo
Em 1854, George Boole introduziu o formalismo que at

hoje se usa para o tratamento sistemtico da lgica, que
a chamada lgebra Booleana.
Em 1938, C. E. Shannon aplicou esta lgebra para mostrar
que as propriedades de circuitos eltricos de chaveamento
podem ser representadas por uma lgebra Booleana com
dois valores.
Em particular, na lgebra Booleana de dois valores, cada
varivel pode assumir um dentre dois valores possveis, os
quais podem ser denotados por [F,V] (falso ou verdadeiro),
[H,L] (high and low) ou ainda [0,1]. Nesta disciplina,
adotaremos a notao [0,1], a qual tambm utilizada em
eletrnica digital.
gustavoazevedo@pelotas.ifsul.edu.br
Como o nmero de valores que cada

varivel pode assumir finito (e pequeno),
o nmero de estados que uma funo
Booleana pode assumir tambm ser
finito, o que significa que podemos
descrever completamente as funes
Booleanas utilizando tabelas.
Devido a este fato, uma tabela que

descreva uma funo Booleana recebe o
nome de tabela verdade, e nela so
listadas todas as combinaes de valores
que as variveis de entrada podem assumir
e os correspondentes valores da funo
(sadas).
2. Operaes Bsicas da lgebra Booleana

Na lgebra Booleana, existem trs operaes ou
funes bsicas. So elas, operao OU, operao
E e complementao.
Todas as funes Booleanas podem ser
representadas em termos destas operaes
bsicas.
Portas Lgicas
Portas lgicas so dispositivos ou circuitos
lgicos que operam um ou mais sinais lgicos
de entrada para produzir uma e somente uma
sada, a qual dependente da funo
implementada no circuito.
Naturalmente, a cada operao lgica
estudada na lgebra de Boole est associada a
respectiva porta lgica.
Smbolos Lgicos do Padro IEEE/ANSI
2.1. Funo E ou AND
2.1.1. Porta E ou AND
10
11
2.2. Funo OU ou OR
12
13
14
2.2.1. Porta OU ou OR
15
2.3. Funo
NO ou NOT
16
2.3.1. Inversor
17
2.4. Funo NO E ou NAND
18
2.4.1. Porta NO E ou NAND
19
2.5. Funo NO OU ou NOR
20
2.5.1. Porta NO OU ou NOR
21
Resumo
22
2.6. Postulados e Teoremas

2.6.1. Postulados da Complementao
23
2.6.2. Postulado da Adio
24
25
2.6.3. Postulado da Multiplicao
26
27
2.7. Propriedades
28
29
2.8. Teoremas de Morgan
30
31
2.9. Identidades Auxiliares
32
33
Resumo
34
2.10. Simplificao de Expresses Booleanas
35
36
Resumo
37
Exerccios
http://endigital.orgfree.com/goodbit/Boole.htm
38
Respostas
39
Respostas
40
Respostas
41
Circuito lgico a partir da equao Booleana

Dada uma equao Booleana qualquer,
possvel desenhar-se o circuito lgico que a
implementa.
O circuito lgico composto das portas lgicas
relacionadas s operaes que so realizadas
sobre as variveis de entrada.
Os resultados das operaes so conduzidos por
fios, os quais, no desenho, so representados
por linhas simples.
42
Tomemos como exemplo a equao W = X + Y . Z .

Inicialmente, identificamos as variveis independentes, que
no caso so X, Y e Z. Para cada uma destas, traamos uma
linha (da esquerda para a direita), representando os fios que
conduzem os valores.
Feito isto, deve-se seguir desenhando as portas necessrias
para representar cada uma das subexpresses, na mesma
ordem tomada para a avaliao, ou seja:
1 parntesis (dos mais internos para os mais externos);
2 operaes E;
3 operaes OU.
43
A figura abaixo mostra o circuito lgico para a

equao W = X + Y . Z .
44
Equao Booleana a partir do Circuito Lgico

Para a obteno da equao a partir do circuito, inicia-se a anlise
prximo s entradas e escreve-se a equao de sada de cada porta
lgica, at obter a equao de sada final do circuito.
45
Exerccio: Qual a equao para o circuito lgico

mostrado?
46
Obtendo equaes Booleanas a partir da Tabela Verdade

usando a Soma de Produtos
Dada uma funo Booleana de n
variveis (ou seja, n entradas), haver 2n
combinaes possveis de valores.
A cada combinao de entradas
podemos associar um termo produto, no
qual todas as variveis da funo esto
presentes, e que construdo da
seguinte forma: se a varivel
correspondente vale 0, ela deve
aparecer negada; se a varivel vale 1, ela
deve aparecer no negada.
A tabela a seguir lista os termos produto
associados a cada combinao de
entradas para uma funo Booleana de
trs variveis (A, B e C, por exemplo).
47
Se quisermos encontrar a equao para uma funo

a partir de sua tabela verdade, basta montarmos
um OU entre os minitermos associados aos 1s da
funo (tambm chamados minitermos 1 ).
Exemplo: encontrar a equao em soma de
produtos (SdP) para a funo F, descrita pela tabela
verdade ao lado:
F funo das variveis A, B e C. Os valores de
(A,B,C) para os quais F=1 so (0,1,0), (0,1,1), (1,0,1)
e (1,1,0). Os minitermos associados a essas
condies (ou seja, os minitermos
1), so A.B.C , A.B.C , A.B.C e A.B.C ,
respectivamente. Logo, a equao em soma de
produtos para F ser o OU entre estes produtos,
conforme segue:
F = A.B.C + A.B.C + A.B.C + A.B.C
48
Obtendo equaes Booleanas a partir da Tabela

Verdade usando o Produto de Somas
O mtodo de derivao usando produto de
somas o dual (isto , o oposto) do mtodo de
derivao em soma de produtos.
A cada combinao das variveis de entrada de
uma funo podemos associar um termo soma,
no qual todas as variveis da funo esto
presentes, e que construdo da seguinte
forma: se a varivel correspondente vale 1, ela
deve aparecer negada; se a varivel vale 0, ela
deve aparecer no negada.
A tabela a seguir lista os termos soma
associados a cada combinao de entradas
para uma funo Booleana de trs variveis (A,
B e C, por exemplo).
49
Cada termo soma construdo conforme a regra anteriormente descrita

denominado maxtermo (ou maxitermo).
Se quisermos encontrar a equao para uma funo a partir de sua tabela
verdade, basta montarmos um E entre os maxtermos associados aos 0s da
funo (tambm chamados maxtermos 0 ).
Exemplo: encontrar a equao em produto de somas (PdS) para a funo F,
descrita pela tabela verdade abaixo:
Foi escolhida a mesma funo do exemplo anterior, para
que se possa estabelecer comparaes entre os dois
mtodos de derivao. Os valores das variveis de entrada
(A,B,C) para os quais F=0 so (0,0,0), (0,0,1), (1,0,0) e
(1,1,1).
Os maxtermos associados a essas condies (ou seja, os
maxtermos 0), so A+B+C, A+B+C, A+B+C e A+B+C,
respectivamente.
Logo, a equao em produto de somas para F ser o E
entre estas somas:
F =(A + B+ C)(A + B+ C)(A + B+C)(A + B+ C)
50
A ordem de precedncia de uma expresso em

produto de somas primeiro cada soma deve
ser avaliada, para s ento avaliar-se o produto.
Isto significa que os parntesis em torno de cada
termo soma so obrigatrios!
Os smbolos referentes operao E (entre os
termos soma) podem ser omitidos.
51
Diagrama de Veitch-Karnaugh para 2 Variveis
52
53
54
55
56
S = AB + AB + AB
Passando para o mapa os casos da tabela verdade,
conforme o esquema de colocao visto abaixo:
Para obtermos a expresso simplificada do diagrama,

utilizamos o seguinte mtodo:
Tentamos agrupar as regies onde S igual a 1, no menor
nmero possvel de agrupamentos.
As regies onde S 1, que no puderem ser agrupadas,
sero consideradas isoladamente. Para um diagrama de 2
variveis, os agrupamentos possveis so os seguintes:
57
a) Quadra:
Conjunto de 4 regies, onde S igual a 1.
No diagrama de 2 variveis, o agrupamento mximo,
proveniente de uma tabela onde todos os casos valem
1.
Assim sendo, a expresso final simplificada obtida
S = 1. A figura abaixo ilustra esta situao:
58
b) Pares:
Conjunto de 2 regies onde S 1, que tem um lado em
comum, ou soa, so vizinhos. As figuras abaixo mostram
exemplos de 2 pares agrupados e suas respectivas
expresses, dentro os 4 possveis em 2 variveis:
59
c) Termos isolados:
Regies onde S 1, sem vizinhana para grupamentos. So

os prprios casos de entrada, sem simplificao.
A figura abaixo exemplifica 2 termos isolados, sem
possibilidade de agrupamento.
60
Feito isto, escrevemos a expresso de cada par, ou seja a

regio que o par ocupa no diagrama.
O par 1 ocupa a regio onde A igual a 1, ento, sua
expresso ser Par 1 = A.
O par 2 ocupa a regio onde A igual a 1, ento, sua
expresso ser Par 2 = B.
Notamos tambm que nenhum 1 ficou fora dos
agrupamentos, e ainda que o mesmo 1 pode pertencer a
mais de um agrupamento.
Para obter a expresso simplificada. basta, agruparmos os
termos obtidos nos agrupamentos:
S = Par 1 + Par 2 ... S = A + B
Como podemos notar, esta a expresso de uma porta OU,
pois a tabela da verdade tambm a da porta OU.
61
Vamos simplificar o circuito que

executa a tabela verdade a
seguir:
62
63
Diagramas de Veitch-Karnaugh para 3 Variveis
64
65
Para melhor compreenso, vamos, como exemplo, transpor

para o diagrama as situaes de sada da tabela abaixo.
66
Para efetuarmos a simplificao, seguimos o

mesmo processo visto anteriormente, somente
que, para 3 variveis, os agrupamentos possveis
so os seguintes:
a) Oitava:
Agrupamento mximo, onde todas as localidades
valem 1, A figura abaixo apresenta esta situao:
67
b) Quadras:
Quadras so agrupamentos de 4 regies S igual
a 1, adjacentes ou em sequncia. Vamos agora
formar - algumas quadras possveis num
diagrama de 3 variveis, a ttulo de exemplo:
68
c) Pares:
A figura abaixo apresenta como exemplo 2 pares
entre os 12 possveis em um diagrama de 3
variveis
69
d) Termos isolados:
Na figura abaixo, exemplos de termos isolados que so os casos
de entrada sem simplificao.
Para o exemplo agrupamos primeiramente uma quadra e logo

aps um par conforme mostra a figura abaixo.
S=AB+C
70
Notamos que esse par no depende de C pois est localizado

tanto em C como em C, resultando sua expresso
independente de C ou sela o termo.
O passo final somarmos as expresses referentes aos
agrupamentos. A expresso final minimizada ser:
S=AB+C
Exerccio: A partir da tabela abaixo obtenha a expresso
Boolena.
71
Resposta
Poderamos tambm ter agrupado de outra maneira,

conforme mostra a figura a seguir.
Estas duas expresses, aparentemente diferentes, possuem

o mesmo comportamento em cada possibilidade, fato este
comprovado, levantando-se as respectivas tabelas da
verdade.
72
Diagrama de Veitch-Karnaugh para 4 Variveis
73
Neste tipo de diagrama, tambm temos uma regio para cada

caso da tabela da verdade, como podemos verificar no
diagrama completo, figura abaixo.
74
Para esclarecermos melhor a colocao do diagrama e analisarmos

outros casos, vamos transpor para o mesmo a tabela abaixo.
75
Para efetuarmos a simplificao,

seguimos o mesmo processo para
os diagramas de 3 variveis,
somente que neste caso, o
principal agrupamento ser a
oitava.
Devemos ressaltar aqui, que no
diagrama, os lados extremos
opostos se comunicam, ou seja,
podemos formar oitavas, quadras e
pares com os temos localizados nos
lados extremos apostos.
76
Exerccio: minimizar o circuito que executa a tabela
77
Observaes Importantes:
Para no cometermos erros no momento de fazermos
os enlaces, devemos observar duas regras:
1) Fazer primeiro os enlaces com maior nmero de clulas,
pois caso contrrio corremos o risco de fazermos
agrupamentos que poderiam ser substitudos por um
maior.
2) Verificar se em cada enlace existe pelo menos uma
clula que pertena a apenas um enlace, pois corremos o
risco de fazermos enlaces redundantes, ou seja, enlaces
perfeitamente dispensveis.
78
Diagramas com Condies Irrelevantes

Chamamos de condio irrelevante (X) a
situao de entrada onde a sada pode
assumir 0 ou 1 indiferentemente.
Esta condio ocorre principalmente pela
impossibilidade prtica do caso de entrada
acontecer, para sua utilizao em diagramas
de Veitch-Karnaugh, devemos, para cada
condio irrelevante, adotar 0 ou 1, aquele
que possibilitar melhor agrupamento e
consequentemente maior simplificao.
Para esclarecer este processo, vamos utilizar
a tabela ao lado.
O smbolo (X) indica que neste caso a sada
pode assumir 0 ou 1, indiferentemente, pois,
ou a situao de entrada impossvel de
acontecer, ou, ainda, possibilita qualquer dos
2 valores na sada.
Para fins de simplificao, devemos adorar
X = 1, pois assim sendo, agrupamos uma
quadra, ao invs de 2 pares (no caso de X =
0), representando uma maior simplificao
da expresso de sada:
79
Em uma tabela da verdade, podemos ter

varias condies irrelevantes que devem
ser consideradas independentemente.
conforme agrupamento em que se
encontram.
Para exemplificar, vamos simplificar a
expresso extrada da tabela.
80
O prximo passo agrupar as regies que valem 1, utilizando

a condio irrelevante (X) para completar o agrupamento.
Convm lembrar que, para maior simplificao, devemos ter
um nmero mnimo de agrupamentos, cada um deles, porm,
com o maior nmero de clulas possvel. Assim sendo, temos:
81
Outra Forma de Apresentaco do Diagrama de

Veitch-Karnaugh
Ao invs de representarmos o diagrama dividindo-o em
regies, como visto at aqui, podemos represent-lo de uma
forma anloga, conforme a figura abaixo.
82
A figura abaixo apresenta os dois estilos dos diagramas

de quatro variveis sobrepostos, onde se observam
claramente os nveis assumidos pelas variveis, idnticos
para ambos os mapas.
83

Unidade II Álgebra Booleana

Enviado por

Direitos autorais:

Formatos disponíveis

Unidade II Álgebra Booleana

Enviado por

Dados do documento

Descrição original:

Direitos autorais

Formatos disponíveis

Compartilhar este documento

Compartilhar ou incorporar documento

Opções de compartilhamento

Você considera este documento útil?

Este conteúdo é inapropriado?

Direitos autorais:

Formatos disponíveis

Unidade II Álgebra Booleana

Enviado por

Direitos autorais:

Formatos disponíveis

Instituto Federal Sul-rio-grandense

Curso Tcnico em Telecomunicaes

Unidade II - lgebra Booleana

Em 1854, George Boole introduziu o formalismo que at

Como o nmero de valores que cada

Devido a este fato, uma tabela que

2. Operaes Bsicas da lgebra Booleana

Smbolos Lgicos do Padro IEEE/ANSI

2.1. Funo E ou AND

2.1.1. Porta E ou AND

2.4. Funo NO E ou NAND

2.4.1. Porta NO E ou NAND

2.5. Funo NO OU ou NOR

2.5.1. Porta NO OU ou NOR

2.6. Postulados e Teoremas

2.6.2. Postulado da Adio

2.6.3. Postulado da Multiplicao

2.8. Teoremas de Morgan

2.9. Identidades Auxiliares

2.10. Simplificao de Expresses Booleanas

Circuito lgico a partir da equao Booleana

Tomemos como exemplo a equao W = X + Y . Z .

A figura abaixo mostra o circuito lgico para a

Equao Booleana a partir do Circuito Lgico

Exerccio: Qual a equao para o circuito lgico

Obtendo equaes Booleanas a partir da Tabela Verdade

Se quisermos encontrar a equao para uma funo

Obtendo equaes Booleanas a partir da Tabela

Cada termo soma construdo conforme a regra anteriormente descrita

A ordem de precedncia de uma expresso em

Diagrama de Veitch-Karnaugh para 2 Variveis

Para obtermos a expresso simplificada do diagrama,

Regies onde S 1, sem vizinhana para grupamentos. So

Feito isto, escrevemos a expresso de cada par, ou seja a

Vamos simplificar o circuito que

Diagramas de Veitch-Karnaugh para 3 Variveis

Para melhor compreenso, vamos, como exemplo, transpor

Para efetuarmos a simplificao, seguimos o

Para o exemplo agrupamos primeiramente uma quadra e logo

Notamos que esse par no depende de C pois est localizado

Poderamos tambm ter agrupado de outra maneira,

Estas duas expresses, aparentemente diferentes, possuem

Diagrama de Veitch-Karnaugh para 4 Variveis

Neste tipo de diagrama, tambm temos uma regio para cada

Para esclarecermos melhor a colocao do diagrama e analisarmos

Para efetuarmos a simplificao,

Exerccio: minimizar o circuito que executa a tabela

Diagramas com Condies Irrelevantes

Em uma tabela da verdade, podemos ter

O prximo passo agrupar as regies que valem 1, utilizando

Outra Forma de Apresentaco do Diagrama de

A figura abaixo apresenta os dois estilos dos diagramas

Você também pode gostar