digital mapa k

8/2/2019 Digital Mapa k

1/82

Apostila Mapas de Veitch-Karnaugh


2/82

lgebra de Boole e Simplificao de Circuitos Lgicos.................................................... 3Variveis e Expresses na lgebra de Boole ..................................................................... 3Postulados ........................................................................................................................... 3Postulados da Complementao ......................................................................................... 3

Postulado da Adio ........................................................................................................... 4Postulado da Multiplicao................................................................................................. 6Propriedades........................................................................................................................ 8Propriedade Comutativa...................................................................................................... 8Propriedade Associativa...................................................................................................... 8Propriedade Distributiva ..................................................................................................... 8Teoremas de De Morgan..................................................................................................... 91 Teorema de De Morgan............................................................................................... 102 Teorema de De Morgan................................................................................................ 11Identidades Auxiliares ...................................................................................................... 12Resumo ............................................................................................................................. 14

Simplifica,co de Expresses Booleanas.......................................................................... 15Exerccios Resolvidos....................................................................................................... 17Simplificao de Expresses Booleanas atravs dos Diagramas de Veitch-Karnaugh.... 21Diagrama de Veitch-Karnaugh para 2 Variveis.............................................................. 22Diagramas de Veitch-Karnaugh para 3 Variveis ............................................................ 30Diagrama de Veitch-Karnaugh para 4 Variveis.............................................................. 37Exerccios Resolvidos....................................................................................................... 45Diagrama para 5 Variveis................................................................................................ 52Exerccio Resolvido.......................................................................................................... 58Diagramas com Condies Irrelevantes............................................................................ 60Exerccios Resolvidos....................................................................................................... 63Casos que no Admitem Simplificao ............................................................................ 66Agrupamentos de Zeros .................................................................................................... 69Outra Forma de Apresenta,co do Diagrama de Veitch-Karnaugh .................................. 71Exerccios Propostos......................................................................................................... 73RESPOSTAS .................................................................................................................... 80


3/82

lgebra de Boole e Simplificao de Circuitos Lgicos

Variveis e Expresses na lgebra de Boole

Como vimos anteriormente, as variveis booleanas so representadas atravs de

letras, podendo assumir os valores 0 e 1.

Expresso booleana a sentena matemtica composta de termos cujas variveisso booleanas e os resultados podem ser 0 e 1.

Postulados

A seguir apresentaremos os postulados da complementao, da adio e damultiplicao da lgebra de boole e suas respectivas identidades resultantes.

Postulados da Complementao

Este postulado, mostra como so as regras da complementao na lgebra de

Boole. Chamaremos de o complemento de :

Atravs do postulado da complementao, podemos estabelecer a seguinteidentidade:


4/82

Assim sendo, podemos escrever: A = A.

O bloco lgico que executa o postulado da complementao o inversor.

Postulado da Adio

Este postulado, mostra como so as regras da adio dentro da lgebra de Boole.

Atravs deste postulado, podemos estabelecer as seguintes identidades:

A pode ser 0 ou 1, vejamos, ento, todas as possibilidades:


5/82

Notamos que o resultado ser sempre igual varivel A.

Vejamos as possibilidades:

Notamos que se somarmos 1 a uma varivel, O resultado ser sempre 1.


Notamos que se somarmos a mesma varivel, o resultado ser ela mesma.


6/82


Notamos que sempre que somarmos a um varivel o seu complemento, teremoscomo resultado 1.

O bloco lgico que executa o postulado da adio o OU.

Postulado da Multiplicao o postulado que determina as regras da multiplicao booleana.

Atravs deste postulado, podemos estabelecer as seguintes regras:

Podemos confirmar, verificando todas as possibilidades.


7/82

Notamos que todo numero multiplicado por 0 0.

Esta identidade a primeira vista estranha, verdadeira, como podemos confirmarpela anlise de todas as possibilidades.

Notamos que os resultados sero sempre iguais a A.

Vamos analizar todas possibilidades:

Notamos que para ambos os valores possveis que a varivel pode assumir, oresultado da expresso ser 0.

O bloco lgico que executa o postulado da multiplicao o E..


8/82

Propriedades

A seguir, descreveremos as principais propriedades algbricas, teis

principalmente, no manuseio e simplificao de expresses. tal como na matemticacomum, valem na lgebra de Boole as propriedades comutativa distributiva eassociativa.

Propriedade Comutativa

Propriedade Associativa

Propriedade Distributiva

Vamos verificar esta propriedade atraves da tabela verdade, analisando todaspossibilidades.


9/82

Notamos, pela tabela 3.1,que as expresses se equivalem.

Teoremas de De Morgan

Os teoremas de Morgan so muito empregados na prtica em simplificaes de

expresses booleanas e ainda no desenvolvimento de circuitos digitais como veremos emtpicos posteriores


10/82

1 Teorema de De Morgan

O complemento do produto c igual a soma dos complementos:

Para provar este teorema vamos montar a tabela da verdade de cada membro e

comparar os resultados.

Notamos a igualdade de ambas as colunas

O teorema pode ser estendido para mais de duas variveis:


11/82

2 Teorema de De Morgan

O complemento da soma igual ao produto dos complementos

Este teorema uma extenso do primeiro.

Podemos reescrev-lo da seguinte maneira:

Reescrevendo, em termos de A e B, temos:

Da mesma forma que no anterior, o teorema pode ser estendido para mais de duasvariveis:


12/82

Notamos, tambm, a aplicao deste teorema no item relativo equivalncia entreblocos lgicos.

Identidades Auxiliares

A seguir, vamos deduzir trs identidades teis para a simplificao de expresses.

Provamos esta identidade, utilizando a propriedade distributiva. Vamos evidenciasno 1 termo:

Do postulado da soma temos:

Logo podemos escrever:


13/82

Vamos provar esta identidade:

Vamos provar esta identidade:


14/82

Resumo


15/82

Simplifica,co de Expresses Booleanas

Utilizando o conceito da lgebra de Boole, podemos simplificar expresses econseqentemente circuitos.

Para efetuarmos estas simplificaes, existem, basicamente, do processos Oprimeiro deles a simplificao atravs da lgebra de Boole, segundo a utilizao dosmapas de Veitch-Karnaugh.

Esta expresso mostra a importncia da simplificao e a conseqenteminimizao do circuito. pois os resultados so idnticos aos valores assumidos pelavarivel A, assim sendo, todo o circuito pode ser substitudo por um nico fio ligado varivel A.


16/82

Como outro exemplo, vamos simplificar a expresso:


17/82

Exerccios Resolvidos

1- Simplifique as expresses booleanas, apresentadas a seguir


18/82


19/82

A partir da expresso , obtenha .

O primeiro passo substituir a expresso do circuito coincidncia pela suaequivalente:


20/82

Obtenha o circuito simplificado que executa a expresso:


21/82

Simplificao de Expresses Booleanas atravs dosDiagramas de Veitch-Karnaugh

Vimos at aqui a simplificao de expresses mediante a utilizao dospostulados, propriedades e identidades da lgebra de Boole. Nestes itens, vamos tratar dasimplificao de expresses por meio dos diagramas de Veitech-Karnaugh.

Estes mapas ou diagramas permitem a simplificao de maneira mais rpida dos

casos extrados de tabelas da verdade obtidas de situaes quaisquer.


22/82

Diagrama de Veitch-Karnaugh para 2 Variveis

Com 2 variveis, podemos obter 4 possibilidades:


23/82


24/82

A tabela da verdade mostra o estudo de uma funo de 2 variveis. Vamos colocarseus resultados no diagrama de Veitch-Karnaugh.


25/82

Passando para o mapa os casos da tabela da verdade, conforme o esquema de

colocao visto m figura 3.8 :

Para obtermos a expresso simplificada do diagrama, utilizamos o seguintemetodo:

Tentamos agrupar as regies onde S igual a 1, no menor nmero possvel deagrupamentos. As regies onde S 1, que no puderem ser agrupadas, sero consideradasisoladamente. Para um diagrama de 2 variveis, os agrupamentos possveis so osseguintes:

a) Quadra:

Conjunto de 4 regies, onde S igual a 1. No diagrama de 2 variveis, oagrupamento mximo, proveniente de uma tabela onde todos os casos valem 1. Assimsendo, a expresso final simplifiicada obtida S = 1. A figura 3.10 ilustra esta situao:


26/82

b) Pares:

Conjunto de 2 regies onde S 1, que tem um lado em comum, ou soa, sovizinhos. As figuras 3.11 e 3.12 mostram exemplos de 2 pares agrupados e suasrespectivas expresses, dentro os 4 possveis em 2 variveis:


27/82

c) Termos isolados:

Regies onde S 1, sem vizinhana para grupamentos. So os prprios casos deentrada, sem simplificao. A figura 3.13 exemplifica 2 termos isolados, sempossibilidade de agrupamento.

Feito isto, escrevemos a expresso de cada par, ou seja a regio que o par ocupano 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.


28/82

Notamos tambm que nenhum I ficou fora dos agrupamentos, e ainda que omesmo 1 pode pertencer a mais de um agrupamento.

Para obter a expresso simplificada. basta, agruparmos os termos obtidos nosagrupamentos:

Como podemos notar, esta a expresso de uma porta OU, pois a tabela daverdade tambm a da porta OU. Outro fato a ser notado que a expresso obtida visivelmente menor do que a extrada diretamente da tabela da verdade, acarretando umcircuito mais simples, diminuindo, conseqentemente, a dificuldade de montagem e ocusto do sistema.

2 - Vamos simplificar o circuito que executa a tabela da verdade a seguir:

Obtendo a expresso diretamente da tabela, temos:

Transportando a tabela para o diagrama.

A


29/82

Agora vamos agrupar os pares:

As expresses dos pares:

Somando as expresses dos pares, teremos a expresso simplificada:

Notamos que a tabela da verdade a de uma porta NE. Aplicando o teorema deDe Morgan expresso, aps a simplificao, encontramos a expresso de uma porta NE:


30/82

Diagramas de Veitch-Karnaugh para 3 Variveis

O diagrama de veitch-karnaugh para 3 variveis e visto na figura 3.17.

No mapa, encontramos todas as possibilidades assumidas entre as variveis A, B eC. A figura 3.18 mostra as regies deste mapa


31/82

Neste diagrama, tambm temos uma regio para cada caso da tabela da verdade.A tabele 3.7 e a figura 3.19 mostram os casos para 3 variveis e as respectivaslocalizaes no mapa.

Vamos analisar a localizao somente de uma das possibilidades, visto que asoutras so de maneira anloga. Assim sendo, vamos localizar no diagrama o caso 3:

No diagrama, ser a interseco das regies que:

Esta pode ser chamada de regio ABC. A figura 3.20 mostra esta localizao nodiagrama, para a colocao do respectivo caso de entrada da coluna S.


32/82

Para melhor compreenso, vamos, como exemplo, transpor para o diagrama assituaes de sada da tabela 3.8.

Expresso extrada da tabela da verdade:

Transpondo a tabela para o diagrama, temos:


33/82

Para efetuarmos a simplificao, seguimos o mesmo processo visto anteriormente,somente que, para 3 variaveis, os agrupamentos possiveis so os seguintes:

a) Oitava:Agrupamento maximo, onde todas as localidades valem 1, A figura 3.22 apresenta

esta situao:

b) Quadras:

Quadras so agrupamentos de 4 regies S igual a 1, adjascentes ou emseqncia. Vamos agora formar - algumas quadras possveis num diagrama de 3variveis, a titulo de exemplo:


34/82

c) Pares:

A figura 3.24 apresenta como exemplo 2 pares entre os 12 possveis em umdiagrama de 3 variveis:

d) Termos isolados:

Na figura 3.25 ,exemplos de termos isolados que so os casos de entrada semsimplificao.

Para o exemplo agrupamos primeiramente uma quadra e logo aps um parconforme mostra a figura 3.26.


35/82

Notamos que esse par no depende de C pois est localizado tanto em como

em , resultando sua expresso independente de C ou sela o termo .

O passo final somarmos as expresses referentes aos agrupamentos. A expressofinal minimizada ser:

Como outro exemplo, varrers minimizar o circuito que executa a tabela 3.9.


36/82

Transpondo para o diagrama, temos:

Efetuando os agrupamentos, notamos que obtemos apenas 3 pares:

A exprcsso minimizada ser:

Poderamos tambm ter agrupado de outra maneira, conforme mostra a figura3.29.


37/82

A expresso gerada:

Estas duas expresses, aparentemente deferentes, possuem o mesmocomportamento em cada possibilidade, fato este comprovado, levantando-se asrespectivas tabelas da verdade.

Diagrama de Veitch-Karnaugh para 4 VariveisO diagrama para 4 variveis visto na figura 3.30.


38/82

A figura 3.31 mostra as regies assumidas pelas variveis A, B, C e D


39/82

Neste tipo de diagrama, tambm temos uma regio para cada caso databela da verdade, como podemos verificar no diagrama completo, figura 3.32.

Vamos analisar a colocao de uma das possibilidades.

Como exemplo, o caso 8.

Da interseco dessas regies, obtemos a regio , que ocaso 8.


40/82

Para esclarecermos melhor a colocao do diagrama e analisarmos outros casos,vamos transpor para o mesmo a tabela 3.11.

Expresso de S, extrada da tabela da verdade:


41/82

Transpondo a tabela para o diagrama, temos:

Para efetuarmos a simplificao, seguimos o mesmo processo para os diagramasde 3 variveis, somente que neste caso, o principal agrupamento ser a oitava.

Devemos ressaltar aqui, que no diagrama, os lados extremos opostos secomunicam, ou seja, podemos formar oitavas, quadras e pares com os temos localizadosnos lados extremos apostos.

Vamos, como exemplo, verificar alguns desses casos no diagrama:

a) Exemplos de pares:


42/82


43/82

Somando as expresses, teremos a expresso final minimizada:

Como outro exemplo. vamos minimizar o circuito que executa a tabela.


44/82

Transpondo a tabela da verdade para o diagrama, temos:

No diagrama, temos: 2 quadras, 1 par e 1 termo isolado.

A expresso minimizada de S ser a soma de todos esses agrupamentos:


45/82


1- Simplifique as expresses obtidas das tabelas a seguir, utilizando os diagramas deVeitch-Kamaugh.


46/82


47/82


48/82


49/82


50/82

2 - Minimize as expresses a seguir, utilizando os diugramus de VeitchKamaugh:


51/82


52/82

Diagrama para 5 Variveis

O diagrama de Veitch-Karnaugh para simplificar expresses com 5 variaveis deentrada visto na figura 3.54.


53/82

Vamos verificar alguma.s das regies deste diagrama:


54/82

De forma anloga. o diagrama possui as regies relativas s variveis opostas s

mostradas, ou seja . Todas estas regies denominam-se hexas. Acolocao de uma condio, neste diagrama, faz-se de maneira anloga s anteriores.

Vamos verificar a regio onde:

Ento:


55/82

Para efetuarmos a simplificao num diagrama de 5 variveis, devemos tentar

primeiramente em hcxas, em seguida em oitavas, em quadras, em pares e por ltimo emtermos isolados

Para visualizarmos melhor as hexas, oitavas, quadras e pares, devemos enxergar odiagrama da esquerda sobreposto ao da direita, conforme mostra a figura 3.61.


56/82

Podemos visualizar, por exemplo, que o par, a oitava e a quadra formam-se nosdois planos.

Vamos, agora fazer a transposio e a simplificao da tabela 3.17, para melhorentendimento destes conceitos.


57/82


58/82

Exerccio Resolvido


59/82


60/82

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 pelaimpossibilidade prtica do caso de entrada acontecer, para sua utilizao em diagramasde Veitch-Karnaugh, devemos, para cada condio irrelevante, adorar 0 ou 1, dos dois,aquele que possibilitar melhor agrupamento e conseqentemente maior simplificao.

Para esclarecer este processo, vamos utilizar a tabela 3.19.

Transpondo esta tabela para o diagrama, temos


61/82

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:

Convm ressaltar que, em uma tabela da verdade, podemos ter varias condiesirrelevantes que devem ser consideradas independentemente. conforme agrupamento emque se encontram. Para exemplificar, vamos simplificar a expresso extrada da tabela3.20.


62/82

Passando para o diagrama de 4 variveis, temos:

O prximo passo agrupar as regies que valem 1, utilizando a condioirrelevante (X) para completar o agrupamento. Convm lembrar que, para maiorsimplificao, devemos ter um nmero mnimo de agrupamentos, cada um deles, porm,com o maior nmero de clulas possvel. Assim sendo, temos:


63/82

A expresso composta por 2 quadras e um par:



64/82

. 1 ^l 1


65/82

importante observar que se tivssemos agrupado precipitadamente, ao inicio do

exerccio a quadra , geraramos erradamente um termo a mais na expresso final.

Para melhor conduo do processo de agrupamento devemos iniciar sempre pelos

agrupamentos obrigatrios e bem definidos.


66/82

Casos que no Admitem Simplificao

Vamos, efetuar uma anlise das expresses representativas das funes OUExclusivo e Coincidncia.

A figura 3.72 mostra a colocao destas expresses nos diagramas, no caso de 2variveis.

Pela figura, notamos que as expresses encontram-se na forma de mximasimplificao, no havendo outra possibilidade, pois em cada diagrama temos 2 termosisolados que so as prprias expresses de entrada.

No caso de utilizarmos 3 variveis, as expresses so, respectivamente,

Para levantarmos suas tabelasda verdade, devemos tomar as variveis de 2 em 2, ou seja, efetuar primeiro as operaes

entre 2 das variveis e com o resultado obtido efetuar a operao com a terceira varivel.Esse processo se deve ao fato de as funes OU Exclusivo e Coincidncia no seremvlidas para mais de 2 variveis de entrada, podendo ser aplicado, tomandopimeiramente 2 quaisquer das 3 variveis da expresso, indiferentemente. As tabelas 3.23

e 3.24 mostram os resultados das operaes ,em todas as possibilidades.


67/82


68/82

Da mesma forma, temos apenas termos isolados, no havendo possibilidade desimplificao.

Extraindo a expresso da tabela inicial ou do diagrama, temos:

Evidenciando temos:

Substituindo-se os parnteses respectivamente por:

Como reescrevemos:

Chamando temos:

Substituindo X, temos:

Inicialmente, se tivssemos evidenciado outras variveis, teramos outras ordensno resultado, de conformidade com as tabelas levantadas. Ainda, se tivssemos

substitudo obteramos , que

analogamente, conforme as tabelas equivalente a:


69/82

Se estendermos o estudo para mais variveis, obteremos:

Para 4 variveis: S = A ~) B ^t C ^(+^) D

De posse do resultados, conclumos que para um nmero de par de variveis,temos a funo OU Exclusivo como sendo o complemento da funo Coincidncia e paraum numero impar de variveis temos a funo OU Exclusivo como sendo igual funoCoincidncia.

Agrupamentos de Zeros

Podemos, alternativamente, agrupar as clulas que valem 0 para obtermos aexpresso simplificada em diagramas de Veitch-Karnaugh, porm, com esta prtica,

obtemos o complemento da funo, ou seja, a sada Para ilustrar esta situao, vamossimplificar a expresso da tabela 3.25.


70/82

Passando para o diagrama e efetuando o agrupamento, temos:

Pela figura notamos que obtemos um par formado por zeros. Conforme o exposto,a expresso ser:

Aplicando o teorema De Morgan a esta:

Convm observar que a mesma expresso seria obtida, resultado dosagrupamentos de 2 quadras, se houvssemos utilizado o procedimento convencionalanteriormente visto.


71/82

Outra Forma de Apresenta,co do Diagrama de Veitch-Karnaugh

Ao invs de representarmos o diagrama dividindo-o em regies, como visto ataqui, podemos represent-lo de uma forma anloga, conforme a figura 3.75.

Pela figura, podemos notar que os diagramas so semelhantes, possuindo apenas aidentificao das regies pelo valor assumido pela varivel


72/82

Tanto a colocao dos casos, bem corno os agrupamentos obtidos se fazem demaneira anloga, levando aos mesmos resultados. A figura 3.76 apresenta os dois estilosdos diagramas de quatro variveis sobrepostos, onde se observam claramente os nveisassumidos pelas variveis, idnticos para ambos os mapas.


73/82

Exerccios Propostos


74/82


75/82


76/82


77/82


78/82


79/82


80/82

RESPOSTAS


81/82


82/82

digital mapa k

Documents