Unidade_2 Sistemas Digitais

7/25/2019 Unidade_2 Sistemas Digitais

1/17

Sistemas Digitais

LGEBRA BOOLEANA


2/17

Sistemas Digitais LGEBRA BOOLEANA 2

LGEBRA BOOLEANA

Introduo

A lgebra Booleana a ferramenta matemtica utilizada, tanto naanlise dos blocos construtivos bsicos, como na construo de novas

funes lgicas, fundamentais para o desenvolvimento de blocos maiselaborados. O britnico George Boole publicou em 1854 um livrodenominado Uma Investigao das Leis do Raciocnio, obra em que foi

apresentada a anlise matemtica da lgica de dois valores, ou lgicab inria, que forneceu os fundamentos para uma cincia e tecnologia que sse desenvolveria no futuro: a eletrnic a di gital.

Em 1938, Claude Elwood Shannon, do Massachusetts Institute of

Technology (MIT), apresentou uma teoria de representao das funes

lgicas a partir de chaves e rels. Estas representaes posteriormenteforam adaptadas a circuitos eletrnicos com vlvulas termoinicas esemicondutores. O estudo de Shannon, publicado como Anlise Simblicado Circuito de Chamamento e Rels,estabeleceu as bases operacionais

da eletrnica digital.

Funes Lgicas

As denominadas var iveis b inrias, lgicas ou booleanas soaquelas que podem assumir somente dois v alores (Falso ou Verdadeiro,Aberto ou Fechado, Apagado ou Aceso e 0 ou 1). Esse fato implica que, paraum determinado conjunto de nvariveis booleanas, o nmero Nde possveis

combinaes lgi cas que pode ser construdo com essas variveis sejaf in i toe calculado por:

N = 2n

Assim, como o nmero de possveis combinaes das variveis deentradade um sistema lgico f in i to, os possveis comportamentos da suasada tambm so f in i tos e, no s possveis de prever, como derepresentar em forma

tabular, denominada

Tabela da Verdade. O nmero

F

de possveis comportamentos, ou fu nes lg ic as, realizado por um sistema


3/17


dado por:F = 2

N

Para se constatar essas afirmaes, considera-se o sistema digital S1,

que possui uma entrada digital Ee uma sada d ig it al S, como mostrado aseguir:

Como este sistema possui uma entrada digital E, possvel se efetuar

duas combinaes na entrada, ou esta varivel pode assumir os valores 0 ou1. O mesmo ocorre para a sada S, onde os valores que a varivel pode

assumir so 0 e 1. No entanto, enquanto na entrada podem ser feitas duascombinaes com os valores 0 e 1, na sada S possvel se fazer quatro

combinaes ou funes.

E S E S E S E S

0 0 0 1 0 0 0 1

1 0 1 0 1 1 1 1

Nula Inversa Identidade Verdade

Como possvel se verificar nas Tabelas Verdade apresentadasacima, um sistema lgico S1, com uma entrada (E) e uma sada (S), podeefetuar quatro funes lgicas distintas. Dentre essas possveis funes

lgicas, aquela que representa um especial interesse para lgebra Booleana a funo LgicaInversa, tambm conhecida como N Oou NOT.

Exemplo:Um jogo de futebol marcado com uma condio: o jogo

somente se realizar se no chover. Determine a funo booleana associada situao.

Soluo: As variveis da situao em questo so chuva ejogo.Comojogo a varivel dependente, corresponder sada. Logo, a varivel

chuvacorresponder entrada. Definimos o sucessode um evento comoestado lgico 1 (verdadeiro) e o fracasso de um evento como estadolgico 0(falso). Como a situao possui apenas uma varivel de entrada, onmero de combinaes da Tabela Verdade ser 21= 2. Na primeira linha,

chuv a = 0, ou seja, a ch uv a no oco rreu, e ojogo f o i rea l izado, que denotado porjogo = 1. Na segunda linha, chuv a = 1, significando que a


4/17


chuva oco rreu, e, assim, ojogo no fo i real izado, denotado porjogo = 1.Essa situao correspondente Funo Lg ic a Inv ersa.

C J

0 11 0

O mesmo procedimento pode ser aplicado a um sistema S2, quepossui 2 entradasE0eE1e uma sada S.

Neste caso as 2 entradas podem ser combinadas de 4 maneiraspossveis, enquanto que as sadas podem ser combinadas de 16 maneirasdiferentes, como mostrado :

E1 E0 S E1 E0 S E1 E0 S E1 E0 S0 0 0 0 0 1 0 0 0 0 0 00 1 0 0 1 0 0 1 1 0 1 0

1 0 0 1 0 0 1 0 0 1 0 11 1 0 1 1 0 1 1 0 1 1 0

Nula No OuNo Implicao

ReversaNo Implicao

E1 E0 S E1 E0 S E1 E0 S E1 E0 S0 0 0 0 0 1 0 0 1 0 0 10 1 0 0 1 1 0 1 0 0 1 01 0 0 1 0 0 1 0 1 1 0 01 1 1 1 1 0 1 1 0 1 1 1

E No E1 No E0No Ou

Exclusivo

E1 E0 S E1 E0 S E1 E0 S E1 E0 S0 0 0 0 0 0 0 0 0 0 0 10 1 1 0 1 1 0 1 0 0 1 11 0 1 1 0 0 1 0 1 1 0 11 1 0 1 1 1 1 1 1 1 1 0

Ou Exclusivo E0 E1 No E


5/17


E1 E0 S E1 E0 S E1 E0 S E1 E0 S0 0 1 0 0 1 0 0 0 0 0 10 1 1 0 1 0 0 1 1 0 1 1

1 0 0 1 0 1 1 0 1 1 0 11 1 1 1 1 1 1 1 1 1 1 1

ImplicaoImplicao

ReversaOu Verdade

Nas Tabelas da Verdade mostradas acima, foram investigadas todasas possveis funes que um sistema S2de 2 entradasE0e E1e uma sadaS. podem executar. Dentre essas funes, algumas so de particular

interesse porque sero utilizadas na construo ou elaborao de circuitoslgicos de maior complexidade, incluindo aqueles utilizados na construo deprocessadores.

Exemplo:Os noivos Joo e Maria iro se casar. Determine a funo

booleana associada situao.

Soluo: As variveis da situao em questo so Joo, Maria e

casamento. A varivel casamentocorresponde sada, porque a varivel

dependente. Logo, as variveis Joo e Maria correspondem s entradas.Definindo-se a presenade cada noivo como estado lgico 1(verdadeiro) ea ausnc ia como estado lgico 0 (falso) conclui-se que nmero decombinaes da Tabela Verdade ser 22= 4. Nas primeiras t rslinhas dessatabela, devido ausnciade um (ou mais) dos noivos, o cas amento no foirealizado, denotado por C = 0. Na quarta linha dessa tabela, devido

presenados dois noivos, o casamento fo i realizado, denotado por C = 1.Essa situao correspondente Funo Lg ic a E.

J M C0 0 0

0 1 0

1 0 0

1 1 1

Exemplo:Os alunos Joo e Maria frequentam as aulas da disciplina

Sistemas Digitais. Determine a funo booleana associada situao.

Soluo: As variveis da situao em questo so Joo, Maria e


6/17


aula. A varivel aulacorresponde sada, porque a varivel dependente.Logo, as variveis Jooe Maria correspondem s entradas. Definindo-se a

presenado aluno como estado lgico 1(verdadeiro) e o ausnc ia comoestado lgico 0 (falso) conclui-se que nmero de combinaes da Tabela

Verdade ser 22

= 4. Na primeiralinha dessa tabela, devido ausnciadosdois alunos, a aul a no fo i realizad a, denotado por C = 0. Nas t rslinhasseguintes, devido presenade um ou mais alunos, a aula foi r ealizada, ou

C = 1. Essa situao correspondente Funo Lg ic a OU.

J M C

0 0 0

0 1 1

1 0 1

1 1 1

Postulados da lgebra Booleana

No item anterior, foi estudado como a sada de um sistema digital secomporta em funo das possveis combinaes de suas variveis deentrada. A investigao das combinaes, ou possveis funes, de sada foifeita sob a forma de Tabelas da Verdade. A partir de 3 variveis de entrada,no entanto, este mtodo se torna muito trabalhoso.

A lgebra Booleana a ferramenta matemtica capaz de tratar aspossveis funes que um sistema digital pode executar. Por se tratar de umacincia exata, a lgebra Booleana tem a justificativa de sua existncia em umconjunto de postulados. Ou seja, baseada em qu atro pr incpios, quereconhecemos, mas para os quais no existem meios matemticos dedemonstrao. So eles:

Conjunto Booleano S S = {0,1}

Operao Produto no Conjunto S

0 . 0 = 00 . 1 = 01 . 0 = 0

1 . 1 = 1


7/17


Operao Soma no Conjunto S

0 + 0 = 0

0 + 1 = 11 + 0 = 11 + 1 = 1

Operao Complemento no Conjunto S

0 = 1

1 = 0

Propriedades da lgebra Booleana

Propriedade ComutativaX. Y = Y. X

X + Y = Y + X

X Y X .Y Y X Y .X X Y X + Y Y X Y + X

0 0 0 0 0 0 0 0 0 0 0 00 1 0 1 0 0 0 1 1 1 0 1

1 0 0 0 1 0 1 0 1 0 1 1

1 1 1 1 1 1 1 1 1 1 1 1

X Y Y X X Y Y X

Propriedade AssociativaX.(Y.Z) = (X.Y).Z

X+(Y+Z) = (X+Y)+Z

X Y Z Y .Z X(Y .Z) X .Y (X .Y) Z X Y Z Y + Z X+(Y+Z) X + Y (X+Y)+Z

0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 1 0 0 0 0 0 0 1 1 1 0 1

0 1 0 0 0 0 0 0 1 0 1 1 1 1

0 1 1 1 0 0 0 0 1 1 1 1 1 1

1 0 0 0 0 0 0 1 0 0 0 1 1 1

1 0 1 0 0 0 0 1 0 1 1 1 1 1

1 1 0 0 0 1 0 1 1 0 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1

X(YZ) (XY)Z X (Y + Z) (X Y) Z


8/17


Propriedade DistributivaX (Y+Z) = X.Y+X.Z

X+Y.Z = (X+Y).(X+Z)

X Y Z Y+Z X.(Y+Z) X .Y X . Z X.Y+X.Z X Y Z Y . Z X.(Y+Z) X+Y X+Z (X+Y).(X+Z)

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 1 1 0 0 0 0 0 0 1 0 0 0 1 0

0 1 0 1 0 0 0 0 0 1 0 0 0 1 0 0

0 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1

1 0 0 0 0 0 0 0 1 0 0 0 1 1 1 1

1 0 1 1 1 0 1 1 1 0 1 0 1 1 1 1

1 1 0 1 1 1 0 1 1 1 0 0 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

X(Y + Z) XY + XZ X+Y.Z = (X+Y).(X+Z)

Teoremas da lgebra Booleana

Teorema da Multiplicao Lgica no Conjunto

Booleano S, ondeX S

Demonstraes para a Adio Lgica:

_ _

X 0 X + 0 1 X 1 + X X X X + X X X X + X

0 0 0 1 0 1 0 0 0 0 1 1

1 0 1 1 1 1 1 1 1 1 0 1

_

X + 0 = X 1 + X = 1 X + X = X X + X = 1

Teorema da Adio Lgica no Conjunto S,

onde X S


9/17


Demonstraes para a Multiplicao Lgica:

_ _

X 1 X .1 0 X 0 .X X X X .X X X X .X0 1 0 0 0 0 0 0 0 0 1 0

1 1 1 0 1 0 1 1 1 1 0 0

_

X .1 = X 0 .X = 0 X .X = X X .X = 0

Teorema do Complemento da Varivel Lgica

no Conjunto S,onde X S

Demonstraes para o Complemento Duplo:__ _

X X X

0 1 0

1 0 1__X = X

Teorema de De Morgan

O Teorema de De Morgan define as regras usadas para a conversode operaes lgicas de soma em operaes lgicas de produto e vice-versa, podendo ser aplicado a um nmero qualquer de variveis. Pode serapresentado das seguintes formas:

a) O complementode uma expresso na forma de som a lgicade um conjunto de variveis equivalente a um produto lgico do

complementodas variveis.


10/17


b) O complemento de uma expresso na forma de produto

lgico de um conjunto de variveis equivalente a uma som a lgica docomplementodas variveis.

Demonstrao do Teorema de De Morgan para duas variveis:

X+ Y X Y . e X Y X Y.

Usando-se as Tabelas da Verdade para os dois casos:_____ _ _ _ _

X Y X + Y X + Y X Y X .Y

0 0 0 1 1 1 1

0 1 1 0 1 0 0

1 0 1 0 0 1 0

1 1 1 0 0 0 0

X + Y X Y .

_____ _ _ _ _

X Y X .Y X .Y X Y X + Y

0 0 0 1 1 1 1

0 1 0 1 1 0 1

1 0 0 1 0 1 1

1 1 1 0 0 0 0

X Y X Y.

Simbologia das Portas Lgicas

As portas lgicas(ou gates) correspondem aos circuitos eletrnicos

que realizam as funes ou operaes lgicas. Possuem representaesgrficas que podem ser utilizadas na representao de funes lgicas maiselaboradas.

Porta E ou AND Smbolo lgico da porta E ou AND de 2 entradas:


11/17


Tabela da Verdade

X Y XY

0 0 0

0 1 0

1 0 0

1 1 1 Equao Booleana F(X,Y) = X . Y = XY

Smbolo lgico da porta E ou AND de 3 entradas:

Tabela da Verdade

X Y Z XYZ

0 0 0 0

0 0 1 0

0 1 0 0

0 1 1 0

1 0 0 01 0 1 0

1 1 0 0

1 1 1 1 Equao Booleana F(X,Y,Z) = X .Y. Z = XYZ

Para uma porta E ou AND de n entradas a Equao Booleanaser:

F(X0, X1, X2, ....., Xn-1) = X0. X1. X2........ Xn-1

Porta OU ou OR

Smbolo lgico da porta OU ou OR de 2 entradas:


12/17


Tabela da Verdade

X Y X + Y

0 0 0

0 1 1

1 0 1

1 1 1 Equao Booleana F(X,Y) = X + Y

Smbolo lgico da porta OU ou OR de 3 entradas:

Tabela da Verdade

X Y Z X+Y+Z

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 Equao Booleana F(X,Y,Z) = X + Y + Z

Para uma porta OU ou OR de n entradas a Equao Booleanaser:

F(X0, X1, X2, ....., Xn-1) = X0+ X1+ X2+ ..... + Xn-1

Porta OU EXCLUSIVO ou XOR

Smbolo lgico da porta OU EXCLUSIVO ou XOR de 2entradas:


13/17


Equao Booleana F(X,Y) = X Y

Smbolo lgico da porta OU EXCLUSIVO ou XOR de 3entradas:

Equao Booleana F(X,Y,Z) = X Y Z

Para uma porta OU EXCLUSIVO ou XOR de n entradas a EquaoBooleana ser:

F(X0, X1, X2, ....., Xn-1) = X0 X1X2..... Xn-1

Porta No E ou NAND Smbolo lgico da porta No E ou NAND de 2 entradas:


14/17


Tabela da Verdade

___

X Y XY

0 0 1

0 1 1

1 0 1

1 1 0

Equao Booleana F(X,Y) = X.Y

Para uma porta No E ou NAND de n entradas a EquaoBooleana ser:

F(X0, X1, X2, ....., Xn-1) = 1-n210 X....XXX

Porta No OU ou NOR Smbolo lgico da porta No OU ou NOR de 2 entradas:

Tabela da Verdade

_____X Y X + Y

0 0 1

0 1 0

1 0 0

1 1 0

Equao Booleana F(X,Y) = X + Y

Para uma porta No OU ou NOR de n entradas a EquaoBooleana ser:

F(X0, X1, X2, ....., Xn-1) =1-n210 X....XXX

Problemas Propostos

1. Apresente as expresses a seguir na sua forma expandidacompleta (ou cannica), isto , como Somas de Produtos, emque os termos contm todas as variveis:

a) E)(CDBA

b) )C(BABCA


15/17


c) BAD)C(BA

d) BC))(ZCB(A

2. Simplifique as expresses:

a)ECBDCABAE

b)CD+BDACBA

3. Apresente a expresso a seguir na sua forma expandidacompleta (ou cannica), isto , como Somas de Produtos, emque os termos contm todas as variveis:

))]CCBA((BCABC[

4. Escreva a expresso lgica, minimize e apresente o circuitolgico minimizado:

5. Projete um circuito que use somente portas NAND. A expressodada :

)D)(CB(AF

6. O cofre de uma banco possui 5 fechaduras: V, W, X, Y, Z, as


16/17


quais devem estar todas destrancadas para que a porta docofre se abra. As chaves das fechaduras so distribudas entrecinco executivos do seguinte modo:

executivo A tem duas chaves: V e X executivo B tem duas chaves: V e Y

executivo C tem duas chaves: W e Y

executivo D tem duas chaves: X e Z

executivo E tem duas chaves: V e Z

a) Determine o nmero mnimo de executivos requeridos parase abrir o cofre.

b) Descubra todas as combinaes possveis de executivos quepodem abrir o cofre.

c) Qual o executivo essencial, sem a presena do qual impossvel abrir o cofre?


17/17


BIBLIOGRAFIA BSICA

1. TOCCI, Ronald J.; WIDMER, Neal S.; MOSS, Gregory L., Sistemas

Digitais: Princpios e Aplicaes, Prentice Hall Brasil, 2007.

2. UYEMURA, John P., Sistemas Digitais: Uma Abordagem Integrada,

So Paulo, Thomson Pioneira, 2002.

3. VAHID, Frank; LASCHUK, Anatlio, Sistemas Digitais: projeto,otimizao e HDLs, Bookman, 2008.

BIBLIOGRAFIA COMPLEMENTAR

1. ERCEGOVAC, Milos D.; LANG, Tomas e MORENO, Jaime H., Introduoaos Sistemas Digitais, Porto Alegre, Bookman, 2000.

2. IDOETA, Ivan V.; CAPUANO, Francisco G., Elementos de eletrnicadigital.Livros rica Editora. Ltda, 2002.

3. TAUB, Herbert; SCHILLING, Donald, Eletrnica Digital, So Paulo.

McGraw-Hill, 1982.

Documents

Unidade_2 Sistemas Digitais