2 Álgebra Booleana e Circuitos Lógicos - inf.ufsc.brj.guntzel/isd/isd2.pdf · 2 Álgebra Booleana e Circuitos Lógicos Uma álgebra Booleana pode ser definida com um conjunto de

Embed Size (px)

Citation preview

  • 2 lgebra Booleana e Circuitos Lgicos

    Uma lgebra Booleana pode ser definida com um conjunto de operadores e umconjunto de axiomas, que so assumidos verdadeiros sem necessidade de prova.

    Em 1854, George Boole introduziu o formalismo que at hoje se usa para o tratamentosistemtico da lgica, que a chamada lgebra Booleana. Em 1938, C. E. Shannon aplicouesta lgebra para mostrar que as propriedades de circuitos eltricos de chaveamento podemser representadas por uma lgebra Booleana com dois valores.

    Diferentemente da lgebra ordinria dos reais, onde as variveis podem assumirvalores no intervalo (-;+), as variveis Booleanas s podem assumir um nmero finito devalores. Em particular, na lgebra Booleana de dois valores, cada varivel pode assumir umdentre 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 qualtambm utilizada em eletrnica digital. Como o nmero de valores que cada varivel podeassumir finito (e pequeno), o nmero de estados que uma funo Booleana pode assumirtambm ser finito, o que significa que podemos descrever completamente as funesBooleanas utilizando tabelas. Devido a este fato, uma tabela que descreva uma funoBooleana recebe o nome de tabela verdade, e nela so listadas todas as combinaes devalores que as variveis de entrada podem assumir e os correspondentes valores da funo(sadas).

    2.1 Operaes Bsicas da lgebra Booleana (ou lgebra deChaveamento)

    Na lgebra Booleana, existem trs operaes ou funes bsicas. So elas, operaoOU, operao E e complementao. Todas as funes Booleanas podem ser representadasem termos destas operaes bsicas.

    2.1.1 Operao OU (Adio Lgica)

    Uma definio para a operao OU, que tambm denominada adio lgica, :

    A operao OU resulta 1 se pelo menos uma das variveis de entrada vale 1.

    Como uma varivel Booleana ou vale 1 ou vale 0, e como o resultado de uma operaoqualquer pode ser encarado como (ou atribudo a) uma varivel Booleana, basta quedefinamos quando a operao vale 1. Automaticamente, a operao resultar 0 nos demaiscasos. Assim, pode-se dizer que a operao OU resulta 0 somente quando todas as variveisde entrada valem 0.

    Um smbolo possvel para representar a operao OU +, tal como o smbolo daadio algbrica (dos reais). Porm, como estamos trabalhando com variveis Booleanas,

  • Introduo aos Sistemas Digitais (v.2001/1) Jos Lus Gntzel e Francisco Assis do Nascimento 2-2

    sabemos que no se trata da adio algbrica, mas sim da adio lgica. Outro smbolotambm encontrado na bibliografia .

    Listando as possibilidades de combinaes entre dois valores Booleanos e osrespectivos resultados para a operao OU, tem-se:

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

    Note que a operao OU s pode ser definida se houver, pelo menos, duas variveisenvolvidas. Ou seja, no possvel realizar a operao sobre somente uma varivel. Devido aisso, o operador + (OU) dito binrio.

    Nas equaes, no costuma-se escrever todas as possibilidades de valores. Apenasadotamos uma letra (ou uma letra com um ndice) para designar uma varivel Booleana. Comisso, j se sabe que aquela varivel pode assumir ou o valor 0 ou o valor 1. Ento, supondoque queiramos demonstar o comportamento da equao A+B (l-se A ou B), poderamosfaz-lo utilizando uma tabela verdade, como segue:

    A B A+B0 0 00 1 11 0 11 1 1

    Da mesma forma, podemos mostrar o comportamento da equao A+B+C (l-se A ouB ou C) por meio de uma tabela verdade. Como na equao h somente o smbolo +, trata-se da operao OU sobre trs variveis. Logo, pode-se aplicar diretamente a definio daoperao OU: o resultado ser 1 se pelo menos uma das variveis de entrada valer 1.

    A B C A+B+C0 0 0 00 0 1 10 1 0 10 1 1 11 0 0 11 0 1 11 1 0 11 1 1 1

    importante notar que, devido ao fato de haver somente um operador na equao,pode-se tambm avaliar a equao decompondo-a em pares. Por exemplo, pode-seprimeiramente achar o resultado de A+B, para depois operar os valores resultantes com osrespectivos valores de C. Esta propriedade conhecida como associativa. Tambm a ordemem que so avaliadas as variveis A, B e C irrelevante (propriedade comutativa). Estaspropriedades so ilustradas pela tabela verdade a seguir. Nela, os parntesis indicamsubexpresses j avaliadas em coluna imediatamente esquerda. Note que os valores das

  • Introduo aos Sistemas Digitais (v.2001/1) Jos Lus Gntzel e Francisco Assis do Nascimento 2-3

    colunas referentes s expresses A+B+C, (A+B)+C e (B+C)+A so os mesmos (na mesmaordem).

    A B C A+B+C A+B (A+B)+C B+C (B+C)+A0 0 0 0 0 0 0 00 0 1 1 0 1 1 10 1 0 1 1 1 1 10 1 1 1 1 1 1 11 0 0 1 1 1 0 11 0 1 1 1 1 1 11 1 0 1 1 1 1 11 1 1 1 1 1 1 1

    2.1.2 Operao E (Multiplicao Lgica)

    A operao E, ou multiplicao lgica, pode ser definida da seguinte forma:

    A operao E resulta 0 se pelo menos uma das variveis de entrada vale 0.

    Pela definio dada, pode-se deduzir que o resultado da operao E ser 1 se, esomente se, todas as entradas valerem 1.

    O smbolo usualmente utilizado na operao E , porm outra notao possvel . Podemos, tambm, listar as possibilidades de combinaes entre dois valores Booleanose os respectivos resultados, para a operao E:

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

    Assim como a operao OU, a operao E s pode ser definida entre, pelo menos duasvariveis. Ou seja, o operador (E) tambm binrio.

    Para mostrar o comportamento da equao A B (l-se A e B), escreve-se uma tabelaverdade, como segue:

    A B AB0 0 00 1 01 0 01 1 1

    De forma semelhante, pode-se determinar o resultado da equao ABC (l-se A e B eC) utilizando diretamente a definio da operao E: o resultado ser 0 se pelo menos umadas variveis de entrada valer 0.

  • Introduo aos Sistemas Digitais (v.2001/1) Jos Lus Gntzel e Francisco Assis do Nascimento 2-4

    A B C ABC0 0 0 00 0 1 00 1 0 00 1 1 01 0 0 01 0 1 01 1 0 01 1 1 1

    Tambm para a operao E valem as propriedades associativa e comutativa. Ento, aequao ABC pode ainda ser avaliada tomando-se as variveis aos pares, em qualquer ordem.Veja a tabela verdade a seguir e compare os resultados.

    A B C ABC AB (AB)C BC A(BC)0 0 0 0 0 0 0 00 0 1 0 0 0 0 00 1 0 0 0 0 0 00 1 1 0 0 0 1 01 0 0 0 0 0 0 01 0 1 0 0 0 0 11 1 0 0 1 0 0 01 1 1 1 1 1 1 1

    2.1.3 Complementao (ou Negao, ou Inverso)

    A operao complementao dispensa uma definio. a operao cujo resultado simplesmente o valor complementar ao que a varivel apresenta. Tambm devido ao fato deuma varivel Booleana poder assumir um entre somente dois valores, o valor complementarser 1 se a varivel vale 0 e ser 0 se a varivel vale 1.

    Os smbolos utilizados para representar a operao complementao sobre umavarivel Booleana A so A , ~A e A' (l-se A negado). Nesta disciplina, adotaremos oprimeiro smbolo. O resultado da operao complementao pode ser listado:

    0 = 11 = 0

    Diferentemente das operaes OU e E, a complementao s definida sobre umavarivel, ou sobre o resultado de uma expresso. Ou seja, o operador complementao dito unrio.

    E a tabela verdade para A :

    A A0 11 0

  • Introduo aos Sistemas Digitais (v.2001/1) Jos Lus Gntzel e Francisco Assis do Nascimento 2-5

    2.2 Avaliao de Expresses Booleanas

    Dada a equao que descreve uma funo Booleana qualquer, deseja-se saberdetalhadamente como esta funo se comporta para qualquer combinao das variveis deentrada. O comportamento de uma funo descrito pela sua tabela verdade e este problema conhecido como avaliao da funo ou da expresso que descreve a funo considerada. Emsuma, deseja-se achar a tabela verdade para a funo Booleana.

    Uma tabela verdade consiste basicamente de um conjunto de colunas, nas quais solistadas todas as combinaes possveis entre as variveis de entrada ( esquerda) e oresultado da funo ( direita). Tambm, pode-se criar colunas intermedirias, onde solistados os resultados de subexpresses contidas na expresso principal. Isto normalmentefacilita a avaliao, principalmente no caso de equaes muito complexas e/ou contendomuitas variveis.

    Quando numa mesma equao Booleana aparecem operaes E e OU, necessrioseguir a ordem de precedncia. Tal como na lgebra dos reais, a multiplicao (lgica) temprecedncia sobre a adio (lgica). Alm disso, expresses entre parntesis tm precednciasobre operadores E e OU que estejam no mesmo nvel. Quanto complementao, esta deveser avaliada to logo seja possvel. Caso a complementao seja aplicada sobre umasubexpresso inteira, necessrio que se avalie primeiramente a subexpresso para, s aps,inverter o seu resultado.

    O nmero de combinaes que as variveis de entrada podem assumir pode ser

    calculado por 2n, onde n o nmero de variveis de entrada.

    O procedimento para a criao da tabela verdade a partir de uma equao Booleana :

    1. Criar colunas para as variveis de entrada e listar todas as combinaes

    possveis, utilizando a frmula no de combinaes = 2n (onde n onmero de variveis de entrada);

    2. Criar uma coluna para cada varivel de entrada que apareacomplementada na equao e anotar os valores resultantes;

    3. Avaliar a equao seguindo a ordem de precedncia, a partir do nvel deparntesis mais internos:

    1o multiplicao lgica2o adio lgica

    Tomemos como exemplo a expresso W = X + Y Z . A varivel W representa afuno Booleana propriamente dita. Esta varivel depende das variveis que esto direita dosinal =, ou seja, depende de X, Y e Z. Logo, so 3 as variveis de entrada. O total decombinaes entre 3 variveis ser 23=8. Ento, a tabela verdade para W dever ter 3 colunas esquerda e 8 linhas. Seguindo o procedimento dado acima, cria-se uma coluna, na quallistam-se os valores para Z. Aps, inicia-se a avaliao propriamente dita, a partir do nvelmais interno de parntesis. Como no h parntesis na expresso, resolvem-se assubexpresses que envolvem a operao E. No caso em questo, h somente uma talsubexpresso, que X Y . Ento, cria-se uma coluna para X Y , na qual anotam-se osresultados para este produto. Finalmente, utilizam-se os resultados de X Y , listados nacoluna anterior, para operar o OU com a varivel X. Repare os passos descritos na tabelaverdade que segue. Nela, os parntesis em torno do produto X Y indicam somente que este

  • Introduo aos Sistemas Digitais (v.2001/1) Jos Lus Gntzel e Francisco Assis do Nascimento 2-6

    termo j foi avaliado e que no passo referente a esta coluna, tomaram-se apenas os valorespreviamente encontrados.

    X Y Z Z X Y W = X + Y Z0 0 0 1 0 00 0 1 0 0 00 1 0 1 1 10 1 1 0 0 01 0 0 1 0 11 0 1 0 0 11 1 0 1 1 11 1 1 0 0 1

    2.3 Portas Lgicas

    J vimos que uma funo Booleana pode ser representada por uma equao oudetalhada pela sua tabela verdade. Mas uma funo Booleana tambm pode ser representadade forma grfica, onde cada operador est associado a um smbolo especfico, permitindo oimediato reconhecimento visual. Tais smbolos so conhecidos por portas lgicas.

    Na realidade, mais do que smbolos de operadores lgicos, as portas lgicasrepresentam recursos fsicos, isto , circuitos eletrnicos, capazes de realizar as operaeslgicas. Na eletrnica que trabalha com somente dois estados, a qual denominada eletrnicadigital, o nvel lgico 0 normalmente est associado ausncia de tenso (0 volt) enquanto onvel lgico 1, presena de tenso (a qual geralmente 5 volts). Nesta disciplina, noslimitaremos ao mundo da lgebra Booleana, admitindo que as portas lgicas representamtambm circuitos eletrnicos que, de alguma maneira, realizam as funes Booleanassimbolizadas. Ento, ao conjunto de portas lgicas e respectivas conexes que simbolizamuma equao Booleana, denominaremos circuito lgico.

    2.3.1 Porta OU

    O smbolo da porta OU pode ser visto na figura 2.1. Tal como na porta E, as entradasso colocadas esquerda e a sada, direita. Deve haver no mnimo duas entradas, mas hsomente uma sada. O funcionamento da porta E segue a definio da operao E, dada naseo 2.1.1.

    B

    A A+BB

    AA+B+C

    C

    (a) (b)

    Figura 2.1 - Smbolo da porta lgica OU com 2 entradas (a) e com 3 entradas (b).

  • Introduo aos Sistemas Digitais (v.2001/1) Jos Lus Gntzel e Francisco Assis do Nascimento 2-7

    2.3.2 Porta E

    O smbolo da porta E mostrado na figura 2.2. esquerda esto dispostas as entradas(no mnimo duas, obviamente) e direita, a sada (nica). As linhas que conduzem asvariveis de entrada e sada podem ser interpretadas como fios que transportam os sinaiseltricos associados s variveis. O comportamento da porta E segue extritamente a definio(e tabela verdade) dada na seo 2.1.2.

    A

    (a)

    A.B

    B

    A

    C

    A.B.CB

    (b)

    Figura 2.2 - Smbolo da porta lgica E com 2 entradas (a) e com 3 entradas (b).

    2.3.3 Inversor (ou Porta Inversora, ou Negador)

    A porta que simboliza a operao complementao conhecida como inversor (ouporta inversora, ou negador). Como a operao complementao s pode ser realizada sobreuma varivel por vez (ou sobre o resultado de uma subexpresso), o inversor s possui umaentrada e, obviamente, uma sada. Caso se queira complementar uma expresso, necessrioobter-se primeiramente o seu resultado, para s ento aplicar a complementao. O smbolodo inversor mostrado na figura 2.3.

    AA

    Figura 2.3 - Smbolo do inversor (tambm conhecido como negador ou porta inversora).

    2.3.4 Exemplo de Circuito Lgico

    Dada uma equao Booleana qualquer, possvel desenhar-se o circuito lgico que aimplementa. O circuito lgico composto das portas lgicas relacionadas s operaes queso realizadas sobre as variveis de entrada. Os resultados das operaes so conduzidos porfios, os quais, no desenho, so representados por linhas simples.

    Os passos a serem seguidos para se realizar o desenho do circuito lgico a partir deuma equao so praticamente os mesmos usados na avaliao da expresso. Tomemos comoexemplo a equao, avaliada na seo 2.2. Inicialmente, identificamos as variveisindependentes, que no caso so X, Y e Z. Para cada uma destas, traamos uma linha (daesquerda para a direita), representando os fios que conduzem os valores. Feito isto, deve-seseguir desenhando as portas necessrias para representar cada uma das subexpresses, namesma ordem tomada para a avaliao, ou seja:

    1o parntesis (dos mais internos para os mais externos);

    2o operaes E;

  • Introduo aos Sistemas Digitais (v.2001/1) Jos Lus Gntzel e Francisco Assis do Nascimento 2-8

    3o operaes OU.

    A figura 2.4 mostra o circuito lgico para a equao W = X + Y Z .

    X

    Z

    WY

    Figura 2.4 - Um circuito lgico.

    2.4 Leis Fundamentais e Propriedades da lgebra Booleana

    As leis da lgebra Booleana dizem respeito ao espao Booleano (isto ., valores queuma varivel pode assumir) e operaes elementares deste espao. J as propriedades podemser deduzidas a partir das definies das operaes.

    Sejam A e B duas variveis Booleanas. Ento, o espao Booleano definido:

    se A0, ento A=1;

    se A1, ento A=0.

    As operaes elementares deste espao so operao OU, operao E ecomplementao, cujas definies foram dadas nas sees 2.1.1, 2.1.2 e 2.1.3,respectivamente.

    As propriedades da lgebra Booleana so as seguintes.

    Da adio lgica:

    (1) A 0 A+ =(2) A 1 1+ =(3) A A A+ =(4) A A 1+ =

    Da multiplicao lgica:

    (5) A 0 = 0(6) A 1 = A(7) A A = A(8) A A = 0

    Da complementao:

    (9) A A=

    Comutatividade:

    (10) A B B A+ = +(11) A B = B A

  • Introduo aos Sistemas Digitais (v.2001/1) Jos Lus Gntzel e Francisco Assis do Nascimento 2-9

    Associatividade:

    (12) A (B C (A B C A C B+ =+ ) + )+ = ( + )+(13) A (B C) = (A B) C = (A C) B

    Distributiva (da multiplicao em relao adio):

    (14) A (B + C) = A B + A C

    2.4.1 Teoremas de De Morgan

    O primeiro teorema de De Morgan diz que a complementao de um produto (lgico)equivale soma (lgica) das negaes de cada varivel do referido produto. Sob a forma deequao, teramos:

    A B C ... = A + B + C + ... (2.1)

    O segundo teorema o dual ( i.e., o espelho) do primeiro, ou seja, a complementaode uma soma (lgica) equivale ao produto das negaes individuais das variveis:

    A + B + C + ... = A B C ... (2.2)

    Particularizando os teoremas de De Morgan para duas variveis, temos:

    A B = A + B (2.3)

    A + B = A B (2.4)

    2.5 Derivao de Expresses Booleanas

    Dada uma funo Booleana, descrita por sua tabela verdade, derivar uma expressoBooleana para esta funo encontrar uma equao que a descreva. Logo, a derivao deexpresses Booleanas o problema inverso da avaliao de uma expresso Booleana, descritona seo 2.2

    H basicamente duas maneiras de se definir (ou descrever) uma funo Booleana:descrevendo-se todas as situaes das variveis de entrada para as quais a funo vale 1 ou,alternativamente, todas as situaes em que a funo vale 0. O primeiro mtodo conhecidopor soma de produtos (SdP), enquanto que o segundo chamado produto de somas (PdS).Qualquer funo Booleana pode ser descrita por meio de soma de produtos ou por meio deproduto de somas. Como as funes Booleanas s podem assumir um dentre dois valores (0ou 1), basta usar-se um dos dois mtodos para se encontrar uma equao para uma funo.

    A seguir, so detalhados os mtodos de derivao de expresses Booleanas.

  • Introduo aos Sistemas Digitais (v.2001/1) Jos Lus Gntzel e Francisco Assis do Nascimento 2-10

    2.5.1 Derivao de Expresses usando Soma de Produtos (SdP)

    Dada uma funo Booleana de n variveis (ou seja, n entradas), haver 2n combinaespossveis de valores. Dizemos que esse conjunto de valores que as variveis podem assumir,juntamente com os respectivos valores da funo, constituem o espao da funo. A cadacombinao de entradas podemos associar um termo produto, no qual todas as variveis dafuno esto presentes, e que construdo da seguinte forma: se a varivel correspondentevale 0, ela deve aparecer negada; se a varivel vale 1, ela deve aparecer no negada. A tabelaa seguir lista os termos produto associados a cada combinao de entradas para uma funoBooleana de trs variveis (A, B e C, por exemplo).

    A B C mintermo

    0 0 0 A B C 0 0 1 A B C0 1 0 A B C 0 1 1 A B C1 0 0 A B C 1 0 1 A B C1 1 0 A B C 1 1 1 A B C

    Cada termo produto construdo conforme a regra anteriormente descrita denominadomintermo (ou minitermo). Note que, para um dado mintermo, se substituirmos os valores dasvariveis associadas, obteremos 1. Porm, se substituirmos nesse mesmo mintermo quaisqueroutras combinaes de valores, obteremos 0. Dessa forma, se quisermos encontrar a equaopara uma funo a partir de sua tabela verdade, basta montarmos um OU entre os mintermosassociados aos 1s da funo (tambm chamados mintermos 1 ).

    Exemplo 2.1: encontrar a equao em soma de produtos (SdP) para a funo F, descrita pelaseguinte tabela verdade:

    A B C F

    0 0 0 0

    0 0 1 0

    0 1 0 1

    0 1 1 1

    1 0 0 0

    1 0 1 1

    1 1 0 1

    1 1 1 0

    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 mintermos associados a essas condies (ou seja, os mintermos1), so A B C , A B C , A B C e A B C , respectivamente. Logo, a equao em somade produtos para F ser o OU entre estes produtos, conforme segue:

    F = A B C + A B C + A B C + A B C (2.5)

  • Introduo aos Sistemas Digitais (v.2001/1) Jos Lus Gntzel e Francisco Assis do Nascimento 2-11

    A fim de simplificar a notao, o smbolo da operao E pode ser omitido. Destaforma, a equao anterior pode ser reescrita de maneira mais concisa:

    F A BC A BC A BC A BC= + + + (2.6)

    2.5.2 Derivao de Expresses usando Produto de Somas (PdS)

    O mtodo de derivao usando produto de somas o dual (isto , o oposto) do mtodode derivao em soma de produtos. A cada combinao das variveis de entrada de umafuno podemos associar um termo soma, no qual todas as variveis da funo estopresentes, e que construdo da seguinte forma: se a varivel correspondente vale 1, ela deveaparecer negada; se a varivel vale 0, ela deve aparecer no negada. A tabela a seguir lista ostermos soma associados a cada combinao de entradas para uma funo Booleana de trsvariveis (A, B e C, por exemplo).

    A B C maxtermos

    0 0 0 A B C+ +

    0 0 1 A B+ + C

    0 1 0 A C+ +B

    0 1 1 A + +B C

    1 0 0 A + +B C

    1 0 1 A C+ +B

    1 1 0 A B C+ +

    1 1 1 A B C+ +

    Cada termo soma construdo conforme a regra anteriormente descrita denominadomaxtermo (ou maxitermo). Note que, para um dado maxtermo, se substituirmos os valoresdas variveis associadas, obteremos 0. Porm, se substituirmos nesse mesmo maxtermoquaisquer outras combinaes de valores, obteremos 1. Dessa forma, se quisermos encontrar aequao para uma funo a partir de sua tabela verdade, basta montarmos um E entre osmaxtermos associados aos 0s da funo (tambm chamados maxtermos 0 ).

    Exemplo 2.2: encontrar a equao em produto de somas (PdS) para a funo F, descrita pelaseguinte tabela verdade:

    A B C F

    0 0 0 00 0 1 00 1 0 10 1 1 11 0 0 01 0 1 11 1 0 11 1 1 0

  • Introduo aos Sistemas Digitais (v.2001/1) Jos Lus Gntzel e Francisco Assis do Nascimento 2-12

    Foi escolhida a mesma funo do exemplo anterior, para que se possa estabelecercomparaes 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 essascondies (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 (2.7)

    Note que a ordem de precedncia de uma expresso em produto de somas primeirocada soma deve ser avaliada, para s ento avaliar-se o produto. Isto significa que osparntesis em torno de cada termo soma so obrigatrios! Repare tambm que os smbolosreferentes operao E (entre os termos soma) podem ser omitidos.

    2.6 Formas Cannicas, Padro e No-Padro

    As representaes em soma de produtos e em produto de somas so denominadasformas padro. A soma de produtos e o produto de somas descritos nas duas seesanteriores apresentam ainda uma caracterstica bastante particular: em cada termo soma e emcada termo produto todas as variveis da funo esto presentes. Devido a essa caracterstica,essas formas so chamadas cannicas.

    Alm das representaes descritas nas sees anteriores, h representaes alternativas(e mais concisas) para as expresses cannicas. Se associarmos cada combinao dasvariveis de entrada ao seu equivalente em decimal, cada mintermo pode ser representado pormi, onde i o decimal associado. De forma similar, cada maxtermo pode ser representado porMi, onde i o decimal associado. A tabela a seguir lista todos os mintermos e maxtermos deuma funo de trs variveis (A, B e C).

    A B C mintermo maxtermo

    0 0 0 m0 M0

    0 0 1 m1 M1

    0 1 0 m2 M2

    0 1 1 m3 M3

    1 0 0 m4 M4

    1 0 1 m5 M5

    1 1 0 m6 M6

    1 1 1 m7 M7

    Voltando funo F das sees anteriores, podemos reescrever a expresso em somade produtos, na forma cannica, como segue:

    F m m m m2 3 5 6= + + + (2.8)

    Ou ainda, de maneira mais concisa:

    F= (2,3,5,6) (2.9)

  • Introduo aos Sistemas Digitais (v.2001/1) Jos Lus Gntzel e Francisco Assis do Nascimento 2-13

    E sua expresso em produto de somas, na forma cannica, pode ser reescrita como:

    F = M0 M1 M4 M7 (2.10)

    Ou simplesmente, como:

    F= (0,1,4,7) (2.11)

    Apesar da praticidade das representaes cannicas, elas so pouco teis para aimplementao de circuitos digitais. O nmero de elementos (portas lgicas e conexes) deum circuito lgico depende diretamente do nmero de operaes Booleanas (inverso, E eOU) contidas na expresso associada. Desta forma, normal que se deseje reduzir o nmerode operaes contidas numa funo, de modo a poder-se implement-la com circuitos lgicosmais simples, e portanto, de menor custo. A reduo do nmero de operaes obtidamediante a eliminao de literais da expresso, aplicando-se as propriedades da lgebraBooleana descritas na seo 2.4. Um literal uma varivel negada ou uma varivel nonegada. O processo de reduo de literais (ou de reduo de operaes, equivalentemente) denominado simplificao.

    Para exemplificar os passos bsicos para a simplificao algbrica (literal) deexpresses Booleanas, tomemos a expresso cannica, em soma de produtos, para a funo F:

    F A BC A BC A BC A BC= + + + (2.12)

    O primeiro passo identificar pares de mintermos que se diferenciam por apenas umliteral, a fim de aplicar a propriedade (14). Os mintermos A CB e ABC , por exemplo,possuem os mesmos literais, exceto pela varivel C: no primeiro, o literal C , enquanto nosegundo, o literal C. Ento, com o uso da propriedade (14), pode-se fatorar esses doismintermos, obtendo-se:

    F A B(C C) A BC A BC= + + + (2.13)

    Pela propriedade (4), tem-se que C C=1+ . Ento, substituindo em 2.13, segue:

    F = A B 1+ AB C + ABC (2.14)

    E pela propriedade (6), A B 1 = A B. Substituindo em 2.14, obtm-se:

    F A B A BC A BC= + + (2.15)

    Assim, pela manipulao algbrica, obtivemos uma expresso em soma de produtosque simplificada em relao a sua expresso em soma de produtos na forma cannica, pois onmero de operaes e tambm de literais foram reduzidos (compare 2.15 com 2.12).

    Entretanto, na equao 2.12, o mintermo A CB tambm poderia ter sido agrupado como mintermo ABC , pois ambos possuem os mesmos literais, exceto pela varivel A (A noprimeiro e A no segundo). Naturalmente, os passos a serem seguidos seriam os mesmosdescritos anteriormente. E a equao resultante seria um pouco diferente, mas com o mesmonmero de operaes, sendo portanto, de mesma complexidade. Na verdade, o melhor seria sepudssemos agrupar o mintermo A CB com o mintermo ABC e ao mesmo tempo com omintermo ABC . Felizmente, a propriedade (3) da lgebra Booleana diz que o OU entre duasou mais variveis Booleanas iguais igual a prpria varivel Booleana em questo.Estendendo esta propriedade, pode-se dizer que o OU entre duas ou mais funes (inclusive

  • Introduo aos Sistemas Digitais (v.2001/1) Jos Lus Gntzel e Francisco Assis do Nascimento 2-14

    produtos) Booleanas iguais equivale prpria funo Booleana em questo. Desta forma,pode-se expandir o mintermo A CB para

    A C A C A CB B B= + (2.16)que uma manipulao algbrica decorrente da propriedade (3).

    Retomando a equao 2.12 e utilizando 2.16, segue que:

    F A BC A BC A BC A BC A BC= + + + + (2.17)

    Ento, a propriedade (3) garante que as expresses 2.12 e 2.17 so equivalentes,embora o mintermo A CB aparea duplicado. E pelo fato de aparecer duas vezes, pode-se usaruma cpia de A CB para simplificar com ABC e outra para simplificar com ABC . Os passosda simplificao so os mesmos j descritos: pela propriedade (14), segue:

    F A B(C C) A BC A A)BC= + + + +( (2.18)

    E pela propriedade (6), vem:

    F = A B 1+ AB C +1 BC (2.19)

    Finalmente, pela propriedade (4), tem-se:

    F A B A BC BC= + + (2.20)

    Repare que o mintermo A CB no pde ser agrupado com nenhum outro mintermo.Note tambm que foram feitas todas as simplificaes possveis, uma vez que foramagrupados e simplificados todos os pares de mintermos que se diferenciam de somente umavarivel. Logo, a expresso 2.20 representa a mxima simplificao possvel sob a forma desoma de produtos. E por esse motivo, ela dita equao mnima em soma de produtos dafuno F. Quanto a expresso 2.15, diz-se ser uma equao em soma de produtossimplificada (porm, no-mnima). Logo, toda equao mnima simplificada, porm, nemtoda equao que foi simplificada necessariamente mnima.

    Embora a equao mnima em soma de produtos apresente menor nmero deoperaes Booleanas que a representao na forma cannica, as vezes pode ser possvelreduzir-se ainda mais o nmero de operaes, fatorando-se literais. Por exemplo, na expresso2.20 pode-se fatorar o primeiro e o terceiro mintermos como segue:

    F A C) A BC= + +B( (2.21)

    A expresso 2.21, obtida pela fatorao de 2.20, no nem do tipo soma de produtos,nem produto de somas, pois h um termo que no nem produto, nem soma. Diz-se que aexpresso est na forma fatorada. No caso de 2.21, a fatorao no resultou em reduo donmero de operaes.

    No que se refere a terminologia, as formas soma de produtos e produto de somas soditas formas padro (formas standard). A forma fatorada dita no-padro. As formascannicas so, pois, casos especiais de formas padro, nas quais os termos so mintermos oumaxtermos. A fim de diferenciar somas de produtos cannicas de somas de produtossimplificadas, usaremos a expresso soma de mintermos. De maneira similar, usaremos aexpresso produto de maxtermos para diferenciar produtos de somas cannicos deprodutos de somas simplificados.

  • Introduo aos Sistemas Digitais (v.2001/1) Jos Lus Gntzel e Francisco Assis do Nascimento 2-15

    2.7 Circuitos Lgicos para Formas Padro e No-Padro

    As regras gerais para se realizar o desenho de circuitos lgicos j foram apresentadasna seo 2.3 (item 2.3.4). As regras seguintes devem ser observadas, a fim de facilitar acompreenso do desenho:

    as variveis de entrada devem ser identificadas preferencialmente esquerda, juntoaos respectivos fios;

    inversores devem ser providos para as variveis que aparecem negadas na equao;

    as portas que implementam as operaes Booleanas que aparecem na equaonormalmente so posicionadas da esquerda para a direita, seguindo a ordem de avaliao dosoperadores (descrita em 2.3.4).

    No caso de equaes na forma soma de produtos (cannica ou simplificada), h umprimeiro nvel (desconsiderando-se possveis inversores), constitudo somente por portas E,onde cada porta E implementa um dos produtos da equao. H ainda um segundo nvel,constitudo por uma porta OU, responsvel pela soma lgica dos produtos. A figura 2.5mostra um possvel circuito lgico para a equao 2.12.

    Repare que em todas as intersees de fios em que h conexo fsica, deve haver umponto (suficientemente grande), como se fora uma solda. Logo, quando no h o referidoponto na interseo de fios, significa que tais fios esto eletricamente isolados.

    A

    C

    F

    B

    1o nvel 2o nvel

    Figura 2.5 - Um circuito lgico para soma de produtos.

    O circuito da figura 2.5 pode ainda ser desenhado utilizando-se uma notaosimplificada para os inversores das entradas. Ao invs de se desenhar um inversor para cadavarivel que aparece negada na equao, coloca-se um crculo junto a cada entrada de cada

  • Introduo aos Sistemas Digitais (v.2001/1) Jos Lus Gntzel e Francisco Assis do Nascimento 2-16

    porta na qual h uma varivel negada. A aplicao desse procedimento para o circuito dafigura 2.5 resulta no seguinte desenho:

    A

    C

    F

    B

    1o nvel 2o nvel

    Figura 2.6 - Um circuito lgico para soma de produtos - outra possvel representao.

    No caso de equaes na forma produto de somas (cannica ou simplificada), oprimeiro nvel constitudo por portas OU, sendo cada uma responsvel por uma das somaslgicas da equao. O segundo nvel, por sua vez, constitudo por uma porta E, que realiza oproduto lgico das parcelas. A figura 2.7 mostra um possvel circuito lgico para a equao2.7.

    A

    C

    F

    B

    1o nvel 2o nvel

    Figura 2.7 - Um circuito lgico para produto de somas.

  • Introduo aos Sistemas Digitais (v.2001/1) Jos Lus Gntzel e Francisco Assis do Nascimento 2-17

    Pelo fato de apresentarem apenas dois nveis de portas (dois nveis lgicos), circuitospara equaes representadas nas formas padro, cannicas ou simplificadas, so ditoscircuitos em dois nveis (ou lgica a dois nveis).

    Dada a equao cannica de uma funo qualquer, o circuito para uma equaosimplificada a partir da cannica possui menos portas e/ou portas de menor complexidade. (Acomplexidade relativa de uma porta pode ser medida pelo nmero de entradas que elaapresenta). A figura 2.8 mostra o circuito lgico para a equao 2.20, que a forma mnimapara a funo da equao 2.12. Note que este circuito de menor complexidade que o circuitoda figura 2.6. A complexidade relativa de um circuito lgico pode ser calculada somando-se onmero de entradas das portas. Nos circuitos das figuras 2.6 e 2.7 h 4 portas de 3 entradas e1 porta de 4 entradas. Ento, a complexidade relativa ser 4x3+1x4=16. No circuito da figura2.8 h 2 portas de 2 entradas e 2 portas de 3 entradas. Sua complexidade relativa ser2x2+2x3=10. Claramente, o circuito da figura 2.8 de menor complexidade que os circuitosdas figuras 2.6 e 2.7. Estes dois so de mesma complexidade relativa. No clculo dacomplexidade relativa, as inverses normalmente no so levadas em conta.

    Circuitos para formas fatoradas podem ser vistos como o caso mais genrico. Emgeral, as formas fatoradas conduzem a circuitos cujo nmero de nveis lgicos maior do quedois. Por isso, circuitos lgicos para formas fatoradas so denominados circuitos multinvel(lgica multinvel). Como dito na seo 2.6, as vezes uma forma fatorada pode apresentarmenor nmero de operaes do que a respectiva forma padro. Quando isso ocorre, o circuitoassociado forma fatorada tambm ser de menor complexidade relativa. Entretanto, se noocorrer reduo no nmero de operaes, mesmo assim possvel que o circuito para a formafatorada seja de menor complexidade relativa, pois o conceito de complexidade relativatambm inclui o nmero de entradas de cada porta. Ento, a maneira mais segura de saber se ocircuito associado forma fatorada de menor complexidade ou no desenh-lo e somar onmero de entradas. A figura 2.9 mostra o circuito para a equao 2.21, obtida a partir daequao 2.20 fatorando-se o literal B. Note que o nmero de operaes Booleanas destasequaes o mesmo: 4. No entanto, a complexidade do circuito da forma fatorada 3x2+1x3=9, portanto menor do que a complexidade do circuito da figura 2.8.

    A

    C

    F

    B

    1o nvel 2o nvel

    Figura 2.8 - Circuito lgico para a equao 2.20.

  • Introduo aos Sistemas Digitais (v.2001/1) Jos Lus Gntzel e Francisco Assis do Nascimento 2-18

    A

    CF

    B

    1o nvel 2o nvel 3o nvel

    Figura 2.9 - Circuito lgico multinvel, associado equao 2.21, a qual est na formafatorada.

    2.8 Simplificao de Funes Booleanas usando Mapas deKarnaugh

    O mtodo de simplificao apresentado na seo 2.6 de aplicabilidade limitada, umavez que bastante difcil certificar-se que todos os pares de mintermos que podiam sersimplificados foram determinados. Alternativamente quele mtodo, h outro mtodo desimplificao baseado na identificao visual de grupos de mintermos passveis de seremsimplificados. No entanto, para que se possa identificar tais grupos, necessrio que osmintermos sejam dispostos de maneira mais conveniente, o que ser explicado a seguir.

    Na descrio do mtodo de simplificao literal, foi mencionado que os pares demintermos que se diferenciam de somente uma varivel so passveis de simplificao.Observando a ordem com que os mintermos de uma funo Booleana qualquer (com, porexemplo, 3 variveis) aparecem na tabela verdade, vemos que, se trocarmos o 3 mintermocom o 4 e trocarmos tambm o 7 mintermo com o 8, obteremos uma nova ordem, na qualquaisquer dois mintermos adjacentes so passveis de simplificao. interessante notartambm que o 1 mintermo pode ser simplificado com o 5, o 2 mintermo pode sersimplificado com o 6 e assim por diante.

    A B C mintermo

    0 0 0 A B C 0 0 1 A B C0 1 0 A B C 0 1 1 A B C1 0 0 A B C 1 0 1 A B C1 1 0 A B C 1 1 1 A B C

    Figura 2.10 - Mintermos para uma funo de 3 variveis.

    Ento, usando o novo ordenamento e re-arranjando os mintermos em duas linhas,temos a seguinte tabela:

  • Introduo aos Sistemas Digitais (v.2001/1) Jos Lus Gntzel e Francisco Assis do Nascimento 2-19

    A B C A B C A B C A B C

    A B C A B C A B C A B C

    Figura 2.11 - Tabela de adjacncias para uma funo de 3 variveis.

    Repare que nessa nova tabela, quaisquer dois mintermos adjacentes (na horizontal ouna vertical) so passveis de serem simplificados, pois s se diferenciam de uma varivel. importante ressaltar que esse conceito de adjacncia no est restrito aos limites da tabela,uma vez que os elementos extremos de uma mesma linha (ou de uma mesma coluna) tambmso simplificveis. Isto implica que a tabela de adjacncias de mintermos da figura 2.11 podee deve ser encarada como uma figura geomtrica tridimensional do tipo toride (ou umarosquinha). A figura a seguir explicita as relaes de adjacncia dos mintermos para umafuno de trs variveis.

    m0 m1 m3 m2

    m4 m5 m7 m6

    Figura 2.12 - Simplificaes possveis entre os mintermos de uma funo de 3 variveis.

    importante ressaltar que o conceito de adjacncia aplicvel na horizontal e navertical, mas nunca na diagonal. Por exemplo, observe que m0 e m5 no so adjacentes, poisno esto nem na mesma linha, nem na mesma coluna.

    O processo de simplificao usando a nova disposio inicia pela construo da tabelaem si: os valores da funo que se quer simplificar devem ser preenchidos conforme a novaordem. Aps, identificam-se todos os grupos de mintermos-1 adjacentes entre si. Cada grupoorigina um termo produto, no qual somente as variveis comuns a todos os mintermos-1permanecem. Desde que os grupos de mintermos-1 adjacentes tenham sido corretamenteidentificados, a simplificao se torna trivial.

    Exemplo 2.3: simplificar a funo F, cuja tabela verdade encontra-se no item 2.5.2.

    O primeiro passo construir uma tabela para F, usando a nova disposio dosmintermos.

    F C A BBC

    A 00 01 11 10

    0 0 0 1 1

    A 1 0 1 0 1

    A BC B BC

    Figura 2.13 - Grupos de mintermos-1 adjacentes e termos produto para uma funo de 3variveis.

  • Introduo aos Sistemas Digitais (v.2001/1) Jos Lus Gntzel e Francisco Assis do Nascimento 2-20

    Aps, deve-se identificar todos os grupos de mintermos-1 adjacentes entre si. Cadagrupo de mintermos-1 originar um produto, conforme indicado na figura 213. A equao emsoma de produtos simplificada ser o OU entre os produtos encontrados:

    F A B A BC BC= + + (2.22)

    2.8.1 Mapas de Karnaugh e Subcubos

    A tabela modificada usada para a identificao dos mintermos-1 adjacentes noexemplo anterior denominada mapa de Karnaugh (no caso, para 3 variveis). Na figura2.14 so mostrados os mapas de Karnaugh para funes de 2, 3 e 4 variveis.

    nome da funo B

    BA 0 1

    0 m0 m1

    A 1 m2 m3

    nome da funo

    C

    BCA 00 01 11 10

    0 m0 m1 m3 m2

    A 1 m4 m5 m7 m6

    B

    nome da funo

    D

    CDAB 00 01 11 10

    00 m0 m1 m3 m2

    01 m4 m5 m7 m6 B

    A 11 m12 m13 m15 m14

    10 m8 m9 m11 m10

    C

    Figura 2.14 - Mapas de Karnaugh para funes de 2, 3 e 4 variveis.

  • Introduo aos Sistemas Digitais (v.2001/1) Jos Lus Gntzel e Francisco Assis do Nascimento 2-21

    O primeiro passo para simplificar-se uma funo usando mapa de Karnaugh escolhero mapa conforme o nmero de variveis da funo e preencher os valores dos mintermosconforme a tabela verdade fornecida, ou conforme a equao fornecida. O segundo passo identificar grupos de mintermos adjacentes que formem grupos de 2m elementos adjacentesentre si, com 0mn, onde n o nmero de variveis da funo. Estes grupos sodenominados subcubos.

    No caso de se querer encontrar uma expresso em soma de produtos, estaremosinteressados nos subcubos de mintermos-1. Ento, cada subcubo contendo mintermos-1 iroriginar um produto, no qual uma ou mais variveis podero estar ausentes devido simplificao que obtida. Os produtos associados aos subcubos de mintermos-1,simplificados ou no, so denominados implicantes. importante ressaltar que quanto maioro nmero de elementos do subcubo, maior ser a simplificao obtida.

    Exemplo 2.4: determinar os implicantes das funes dadas a seguir.

    F0

    D

    CDAB 00 01 11 10

    00 0 0 0 0

    01 1 1 1 1 B

    A 11 0 0 0 0

    10 0 0 0 0

    C

    F1

    D

    CDAB 00 01 11 10

    00 0 0 0 0

    01 1 1 0 0 B

    A 11 1 1 0 0

    10 0 0 0 0

    C

  • Introduo aos Sistemas Digitais (v.2001/1) Jos Lus Gntzel e Francisco Assis do Nascimento 2-22

    F2

    D

    CDAB 00 01 11 10

    00 0 1 1 0

    01 0 0 0 0 B

    A 11 0 0 0 0

    10 0 1 1 0

    C

    F3

    D

    CDAB 00 01 11 10

    00 1 0 0 1

    01 0 0 0 0 B

    A 11 0 0 0 0

    10 1 0 0 1

    C

    No caso de se querer encontrar uma expresso em produtos de somas, estaremosinteressados nos subcubos de mintermos-0. Ento, cada subcubo contendo mintermos-0 iroriginar uma soma, no qual uma ou mais variveis podero estar ausentes devido simplificao que obtida. As somas associados aos subcubos de mintermos-0, simplificadasou no, so denominadas implicados. Tambm neste caso, quanto maior o nmero deelementos do subcubo, maior ser a simplificao obtida.

    Exemplo 2.5: determinar os implicados das funes dadas a seguir.

  • Introduo aos Sistemas Digitais (v.2001/1) Jos Lus Gntzel e Francisco Assis do Nascimento 2-23

    F4

    D

    CDAB 00 01 11 10

    00 1 1 1 1

    01 1 0 1 1 B

    A 11 1 0 1 1

    10 1 1 1 1

    C

    F5

    D

    CDAB 00 01 11 10

    00 0 1 1 0

    01 0 1 1 0 B

    A 11 0 1 1 0

    10 0 1 1 0

    C

    F6

    D

    CDAB 00 01 11 10

    00 0 1 1 0

    01 0 1 1 0 B

    A 11 0 1 1 0

    10 0 1 1 0

    C

  • Introduo aos Sistemas Digitais (v.2001/1) Jos Lus Gntzel e Francisco Assis do Nascimento 2-24

    F7

    D

    CDAB 00 01 11 10

    00 0 1 1 1

    01 1 1 1 1 B

    A 11 1 1 1 1

    10 1 1 0 0

    C

    2.8.2 Cobertura dos Mapas de Karnaugh

    Normalmente, possvel identificar-se numa mesma funo Booleana mais de umimplicante (ou mais de um implicado). Neste caso, necessrio determinar o conjunto deimplicantes (ou implicados) que melhor cobre a funo, onde a melhor cobertura significanecessariamente a expresso mais simplificada possvel, a qual denominada expressomnima.

    O procedimento bsico para se determinar a melhor cobertura (tambm chamadacobertura mnima) para uma expresso em soma de produtos o seguinte:

    Identificar os subcubos de mintermos-1 com maior nmero de elementos possvel,iniciando do tamanho 2n, onde n o nmero de variveis da funo. Caso algummintermo-1 fique isolado (isto , no h nenhum outro mintermo-1 adjacente aele), ento ele constituir um subcubo de um elemento;

    Identificar o menor conjunto de subcubos de modo que cada mintermo-1 pertena apelo menos um subcubo (= seja coberto pelo menos uma vez).

    Observaes:

    1. Cada mintermo-1 pode ser coberto por mais de um subcubo, caso isso resulte numasimplificao maior;

    2. Um ltimo teste para verificar se a expresso obtida realmente a mnima consisteem verificar se algum subcubo pode ser removido, sem deixar algum mintermo-1descoberto. Um subcubo que poder ser removido sem descobrir mintermos ditosubcubo no-essencial. Logo, todo o subcubo que no pode ser removido ditoessencial.;

    3. Pode haver mais de uma expresso mnima para uma mesma funo Booleana;

  • Introduo aos Sistemas Digitais (v.2001/1) Jos Lus Gntzel e Francisco Assis do Nascimento 2-25

    4. A expresso mnima aquela de menor complexidade. E a complexidade sermedida pelo nmero de literais de uma funo.

    Exemplo 2.6:. ache a equao mnima em soma de produtos para as funes Booleanas queseguem:

    S0(A,B,C,D) = (0,1,2,5,6,7,13,15)

    Cobertura 1:

    S0

    D

    CDAB 00 01 11 10

    00

    01 B

    A 11

    10

    C

    Cobertura 2:

    S0

    D

    CDAB 00 01 11 10

    00

    01 B

    A 11

    10

    C

  • Introduo aos Sistemas Digitais (v.2001/1) Jos Lus Gntzel e Francisco Assis do Nascimento 2-26

    Cobertura 3:

    S0

    D

    CDAB 00 01 11 10

    00

    01 B

    A 11

    10

    C

    S1(W,X,Y,Z) = (0,1,2,5,8.9.10)

    S1

    D

    YZWX 00 01 11 10

    00

    01 B

    A 11

    10

    C

    Conforme j mencionado anteriormente, tambm possvel obter-se uma expressomnima em produto de somas a partir do mapa de Karnaugh da funo Booleana. Para tanto,deve-se identificar os subcubos de mintermos-0, ao invs de subcubos de mintermos-1. Cadasubcubo de mintermo-0 ir originar um termo soma, possivelmente j simplificado, o qualrecebe o nome de implicado.

    Os passos para a obteno de uma cobertura mnima so os mesmos j descritos para aobteno da expresso em soma de produtos.

  • Introduo aos Sistemas Digitais (v.2001/1) Jos Lus Gntzel e Francisco Assis do Nascimento 2-27

    Exemplo 2.7: determine a equao mnima em produto de somas para a funo Booleana.

    S2(W,X,Y,Z) = (0,1,2,5,8,9,10)Observao importante: repare que a funo foi especificada pela descrio de seus

    mintermos-1. Mas como foi solicitada a expresso em produto de somas, uma vez montado omapa de Karnaugh usando a informao fornecida, passaremos a identificar os subcubos demintermos-0.

    S2

    Z

    YZWX 00 01 11 10

    00

    01 X

    W 11

    10

    Y

    Exemplo 2.8: determinar a expresso mnima em soma de produtos e a expresso mnimaem produto de somas para a funo Booleana dada a seguir. Desenhar ocircuito lgico para cada expresso obtida.

    S3(A,B,C,D) = (1,2,3,6,7,8,9,12,14)Obs: existe mais de uma cobertura mnima possvel para essa funo.

    Cobertura 1 para soma de produtos:

    S3

    D

    CDAB 00 01 11 10

    00

    01 B

    11

    A10

    C

  • Introduo aos Sistemas Digitais (v.2001/1) Jos Lus Gntzel e Francisco Assis do Nascimento 2-28

    Cobertura 2 para soma de produtos:

    S3

    D

    CDAB 00 01 11 10

    00

    01 B

    11

    A10

    C

    Cobertura 1 para produto de somas:

    S3

    D

    CDAB 00 01 11 10

    00

    01 B

    11

    A10

    C

    Cobertura 2 para produto de somas:

    S3

    D

    CDAB 00 01 11 10

    00

    01 B

    11

    A10

    C

  • Introduo aos Sistemas Digitais (v.2001/1) Jos Lus Gntzel e Francisco Assis do Nascimento 2-29

    2.9 Funes Incompletamente Especificadas

    Durante o projeto lgico, pode ocorrer que algumas condies (combinaes) deentradas de uma funo Booleana no sejam especificadas, por no afetarem a funo nocontexto do projeto. Cada condio de entrada cujo valor no especificado sinalizada comDC ou com X na tabela verdade (ou no mapa de Karnaugh) e so denominadas condiesde dont care (ou simplesmente, dont care).

    Quando da simplificao de uma funo Booleana que contenha condies de dontcare, essas condies podem e devem ser exploradas no sentido de se obter a mximasimplificao possvel. Para tanto, pode-se assumir cada condio de dont care comovalendo 0 ou 1, independente das demais condies de dont care. A escolha do valor (0 ou 1)ir depender do contexto, mas sempre dever ocorrer com o objetivo de levar a umasimplificao mxima da funo Booleana.

    Exemplo 2.9: determinar a expresso mnima em soma de produtos para a funo.

    S5(A,B,C,D) = (0,1,2,12,13) + DC(3,7,10,11,14,15)onde o conjunto de condies de dont care est especificado por DC Repare que no casode uma funo que contenha condies de dont care (ou seja, uma funo incompletamenteespecificada), no basta dizer somente onde esto os uns (ou somente os zeros) da funo: necessrio informar tambm quais condies de entrada no so especificadas, o que feitopelo conjunto DC.

    S5D

    CDAB 00 01 11 10

    00

    01 B

    11

    A10

    C

    Observaes:

    Iremos identificar cada condio de entrada no especificadas (ou dont care) pormeio de um X (xis maisculo). O valor que ser assumido para um dont care totalmente independente dos demais dont cares;

  • Introduo aos Sistemas Digitais (v.2001/1) Jos Lus Gntzel e Francisco Assis do Nascimento 2-30

    Quando da identificao dos subcubos, no aconselhvel escrever o valor que foiassumido para um determinado dont care, pois isso pode gerar confuses. O simplesfato de um dont care pertencer (ou no) a algum subcubo j identifica o valor que foiassumido para ele;

    Para uma mesma funo Booleana, deve-se identificar a soluo em soma de produtosnum mapa de Karnaugh e a soluo em produto de somas em outro mapa, a fim deevitar confuses

    Exemplo 2.10:. dada a funo que segue, determinar as equaes mnimas em SdP (soma deprodutos) e em PdS (produto de somas) para a funo dada. Desenhar osrespectivos circuitos lgicos e identificar, o circuito de menor complexidade(entre SdP e PdS).

    S6(A,B,C,D)= (0,3,5,6,7) + DC(10,11,12,13,14,15)

    Cobertura para soma de produtos:

    S6

    D

    CDAB 00 01 11 10

    00

    01 B

    11

    A10

    C

    Cobertura para produto de somas:

    S6

    D

    CDAB 00 01 11 10

    00

    01 B

    11

    A10

    C

  • Introduo aos Sistemas Digitais (v.2001/1) Jos Lus Gntzel e Francisco Assis do Nascimento 2-31

    Observao: um mesmo dont care pode assumir um valor lgico para a cobertura emSdP e outro valor lgico para a cobertura em PdS, pois as coberturas so totalmenteindependentes.

    2.10 Outras Operaes Lgicas

    At agora, tem-se visto apenas duas funes booleanas de duas variveis, OU e E.Mas, existem 2

    2 n funes Booleanas com n variveis binrias. Assim, existem 16 funesBooleanas de duas variveis e as funes E e OU so apenas duas dessas 16 funes. A tabelaa seguir lista todas as 16 funes Booleanas de duas variveis, x e y.

    Nome SmboloValores parax,y= 00 01 10 11

    Expressoalgbrica Comentrio

    Zero 0 0 0 0 0 00 =F Constante 0

    E x.y 0 0 0 1 xyF =1 x e yInibio x/y 0 0 1 0 yxF =2 x mas no yTransferncia 0 0 1 1 xF =3 x

    Inibio y/x 0 1 0 0 yxF =4 y mas no xTransferncia 0 1 0 1 xF =5 y

    XOR xy 0 1 1 0 yxyxF +=6 x ou y, mas noambos

    OU x+y 0 1 1 1 yxF +=7 x ou y

    NOR xy 1 0 0 0 F8 = (x + y)' No-OUEquivalncia 1 0 0 1 F9 = xy + x' y' x igual a yComplemento y' 1 0 1 0 '10 yF = No y

    Implicao xy 1 0 1 1 yxF +=11 Se y, ento xComplemento x' 1 1 0 0 xF =12 No xImplicao xy 1 1 0 1 yxF +=13 Se x, ento y

    NAND xy 1 1 1 0 )'(14 xyF = No EUm 1 1 1 1 1 115 =F Constante 1

    Cada linha na tabela acima representa uma funo de duas variveis e os nomes destasfunes so dados na primeira coluna. As tabelas verdades de cada uma das funes so dadasna terceira coluna. Note que cada funo foi designada por Fi onde i o decimal equivalenteao nmero binrio que obtido interpretando-se os valores das funes dados na terceiracoluna como nmeros binrios.

    Cada uma destas funes pode ser dada em termos de operaes E, OU ecomplemento. Como pode ser visto na tabela, existem duas funes constantes, 0 e 1, queretornam sempre 0 ou 1, respectivamente, independente de que valores se tem na entrada.Existem quatro funes de uma varivel, que representam o complemento e a transferncia. Eexistem 10 funes que definem oito operaes binrias: E, inibio, XOR, OU, NOR,

  • Introduo aos Sistemas Digitais (v.2001/1) Jos Lus Gntzel e Francisco Assis do Nascimento 2-32

    equivalncia, implicao e NAND. Sendo que inibio e implicao nunca so usados noprojeto de circuitos, principalmente, por poderem ser facilmente implementados usando-seoperaes E, OU e complemento. A funo NOR o complemento da operao OU e afuno NAND o complemento da operao E. Pode-se notar tambm que XOR eequivalncia so o complemento uma da outra e, por esta razo, a equivalncia normalmentechamada XNOR.

    Para implementar as funes mostradas na tabela acima, so usadas geralmente oitotipos de portas lgicas: portas E, OU, complemento ou inversora, portas de transferncia oudriver, portas NAND, XOR e XNOR. A figura 2.15 mostra os smbolos de cada uma destasportas com respectivos atrasos (em nanossegundos) e custo (em nmero de transistores).

    Figura 2.15 - Smbolos para portas lgicas com respectivos atrasos e custos

    Na figura acima, os nmeros dentro do smbolo de cada porta lgica indica o atrasoatravs da porta, ou seja, o tempo que leva para que o resultado da operao lgicacorrespondente aparea na sada da porta, quando se aplica valores na entradas. Assim, porexemplo, a porta NOR possui um atraso de propagao de 1,4 ns. O nmero ao lado dosmbolo de uma porta lgica indica a quantidade de transistores necessrios para implement-la. Assim, pode-se notar que a implementao de uma porta XOR (14 transistores) mais"cara" que a implementao de uma porta XNOR (12 transistores). Evidentemente, paraportas lgicas com mltplas entradas (mais de duas entradas) estes valores so diferentes. Afigura 2.16 mostra portas lgicas com mltiplas entradas.

    B

    A

    A+B+C

    2,8 8

    C

    B

    A

    A+B+C+D

    3,2 10

    C

    D

    A

    A.B.C

    B

    2,8

    8

    C

    A

    A.B.C.D

    B

    3,2

    10

    C

    D

    A

    (A.B.C.D) B

    2,2

    8

    C

    D

    A

    (A.B.C) B

    1,8

    6

    C

    B

    A

    A+B+C+D

    3,2 10

    C

    D

    B

    A

    A+B+C

    2,8 8

    C

    Figura 2.16 - Portas lgicas com mltiplas entradas

  • Introduo aos Sistemas Digitais (v.2001/1) Jos Lus Gntzel e Francisco Assis do Nascimento 2-33

    Obviamente, portas lgicas com mltiplas entradas so mais difceis de contruir ecomo no so muito utilizadas, o custo da manuteno de bibliotecas contendo tais portas edas ferramentas de projeto tende a ser maior que a utilidade destas portas. Por isso, em geral,se tem somente portas de trs e quatro entradas em bibliotecas de portas lgicas.

    Quando se est implementando funes booleanas usando estas portas lgicas,usualmente tenta-se encontrar uma expresso booleana que melhor satisfaa um conjunto derequisitos de projeto. Geralmente, estes requisitos envolvem restries de custo, que pode serdado em termos de nmero de transistores e/ou atraso dos sinais ao longo do circuito.

    Muitas vezes se est interessado em obter o circuito mais rpido, ou seja, o que tenha omenor atraso a partir das entradas para a sada, mas tambm existem casos em que se deseja ocircuito mais barato, ou seja, com o menor nmero de transistores. Por sua natureza, estes doisobjetivos so conflitantes, pois um circuito rpido avalia subexpresses em paralelo, o que vaiexigir mais portas do que um circuito de baixo, em que subexpresses so fatoradas eexecutadas serialmente.

    2.11 Mapeamento

    No projeto de circuitos, tem-se frequentemente o seguinte problema: dada uma funobooleana (mnima ou no), deve-se projetar um circuito lgico usando somente alguns poucostipos de portas que esto disponveis. Esta ao de adaptar-se a lgica de uma funo aoconjunto de portas que est disponvel denominada mapeamento tecnolgico (ousimplesmente mapeamento) da funo. O conjunto de portas disponvel denominadobiblioteca de portas, e depende de vrios fatores, dentre os quais, da tecnologia em que ocircuito ser implementado.

    Assim, o problema de mapeamento pode ser formulado da seguinte maneira: dada umafuno booleana simplificada, em SdP ou em PdS, ou dado um circuito para essa funo, edada uma biblioteca de portas, mapear a funo usando somente as portas (tipos de portas)que existem na biblioteca.

    Este processo envolve vrias tarefas. Primeiro ser mostrado como converter umafuno ou circuito lgico envolvendo portas E, OU e complemento em uma funo ou circuitolgico contendo apenas portas NAND (ou somente portas NOR). Esta tarefa consiste de duaspartes: converso e otimizao. Durante a converso, cada porta E e porta OU substitudapor uma porta NAND ou NOR equivalente, enquanto que durante a otimizao, soeliminados quaisquer dois inversores, um seguido do outro, que possam ter surgido durante aconverso.

    As regras para a tarefa de converso so baseadas nos Teoremas de De Morgan, comomostrado a seguir:

    Regra 1: )')'((xyxy =Regra 2: )'''()')'(( yxyxyx =+=+Regra 3: )'''()')'(( yxxyxy +==Regra 4: )')'(( yxyx +=+Regra 5: xx =)''(As regras 1 e 2 so usadas para a converso para portas NAND, enquanto as regras 3 e

    4 so usadas para a converso para portas NOR.. A regra 5 usada para a otimizao do

  • Introduo aos Sistemas Digitais (v.2001/1) Jos Lus Gntzel e Francisco Assis do Nascimento 2-34

    circuito e permite eliminar quaisquer dois inversores que aparecem um seguido do outro nocircuito. A figura 2.17 ilustra graficamente as regras dadas acima.

    Regra 1:

    Regra 2:

    Regra 3:

    Regra 4:

    Regra 5:

    Figura 2.17 - Regras de converso

    Exemplo 2.11: encontrar uma implementao usando apenas portas NAND e outraimplementao usando apenas portas NOR para a funo de carry

    iiiiiii cycxyxc ++=+1 ou ))()((1 iiiiiii cycxyxc +++=+ .

    xi

    yi

    ci

    c(i+1)

    2,4

    2,4

    2,4

    2,8

    1,4

    1,4

    1,4

    xi

    yi ci

    c(i+1)

    xi

    yi

    ci

    c(i+1)

    2,4

    2,4

    2,4

    1,4

    1,4

    1,4

    xi

    yi ci

    c(i+1)

    2,8

    1,8

    1,8

    Implementao com portas NAND

    Implementao com portas NOR

    Soma de Produtos

    Produto de Somas

    Figura 2.18 soma de produtos e produto de somas com portas NAND e portas NOR,respectivamente.

  • Introduo aos Sistemas Digitais (v.2001/1) Jos Lus Gntzel e Francisco Assis do Nascimento 2-35

    2.12 Comportamento Dinmico de Circuitos Combinacionais

    At o presente, analisamos somente o comportamento esttico dos circuitoscombinacionais. Ou seja, dada uma combinao de valores aplicados s entradas do circuitoh um tempo suficientemente longo, determinamos os valores de suas sadas. Entretanto,durante o funcionamento normal e um circuito, as entradas podem estar mudando com umadeterminada freqncia, como conseqncia da aplicao sucessiva de diferentes conjuntos dedados. Ento, desde que o circuito tenha sido projetado para funcionar nesta freqncia, osvalores das sadas tambm mudaro (com a mesma freqncia, na pior das hipteses), comoconseqncia das mudanas das entradas.

    A partir de agora, estaremos assumindo que uma varivel Booleana pode se alterar aolongo do tempo, porm sempre assumindo um valor no intervalo [0;1]. Assim, arepresentao grfica de uma varivel Booleana ao longo de um intervalo de tempo denominada forma de onda da varivel. A figura 3.13 mostra um exemplo de forma de ondaqualquer. Repare que uma forma de onda pode ser imaginada sobre o plano cartesiano, onde oeixo dos x representa o tempo (crescente da esquerda para a direita) e o eixo dos y representao valor lgico da varivel (sempre dentro do intervalo [0;1]).

    A

    tempo

    Figura 2.19 - exemplo de forma de onda.

    Quando uma varivel Booleana se modifica ao longo do tempo, ela costuma serchamada de sinal. Portanto, na anlise temporal (tambm conhecida como anlise de timing)de um circuito, pode-se associar um sinal a cada entrada do circuito e a cada sada de cadaporta do circuito (o conjunto de entradas e de sadas de portas de um circuito chamado nsou nodos do circuito.) Normalmente, os sinais referentes s entradas de um circuito sodados.

    As portas lgicas so fabricadas com material semicondutor (silcio). Apesar dasreduzidas dimenses que a tecnologia atual permite que sejam alcanadas, as portas lgicasno conseguem responder de maneira instantnea s variaes em suas entradas. Ao tempoque decorre entre alguma das entradas de uma porta se modificar e essa modificao sepropagar at a sada, d-se o nome de atraso (da porta lgica). O atraso de uma porta Pnormalmente representado por td(P) ou tdP ou tp(P) ou ainda tpP. importante ressaltar quecada porta lgica pode apresentar um atraso diferente, mesmo em se tratando de portas demesma funo e mesmo nmero de entradas. O valor do atraso de uma porta depende devrios fatores, dentre eles a tecnologia de fabricao, as dimenses dos transistores que acompem, a temperatura do local de operao etc.

  • Introduo aos Sistemas Digitais (v.2001/1) Jos Lus Gntzel e Francisco Assis do Nascimento 2-36

    Exemplo 2.11: determinar o sinal de sada S da porta que segue, a partir dos sinais A eB aplicados s suas entradas.

    A

    A

    BS

    B

    S

    Figura 2.20 - exemplo de determinao da forma de onda da sada de uma porta.

    Na anlise temporal de um circuito combinacional, prudente seguirem-se osseguintes passos:

    identificar com uma linha vertical cada mudana no valor (=transio) dos sinaisdas entradas. Note que as formas de onda das entradas sempre so fornecidas,fazendo parte dos dados do problema.

    Para cada intervalo de tempo delimitado por duas linhas verticais adjacentes,identificar o sinal resultante usando a tabela verdade da porta em questo;

    Considerar um pequeno intervalo de tempo aps cada transio de entrada,referente ao atraso de propagao da porta.

    Exemplo 2.11: determine as formas de onda e os atrasos envolvidos para S1, S2, S3e S no circuito que segue, a partir das entradas fornecidas. Considere que as portas 1 e 2 tm omesmo valor para o atraso individual. Identifique o atraso total do circuito, indicando asparcelas que o compem.

  • Introduo aos Sistemas Digitais (v.2001/1) Jos Lus Gntzel e Francisco Assis do Nascimento 2-37

    C

    S

    A

    B

    S11

    3

    2

    DS3

    4S2

    A

    B

    C

    S2

    S1

    S

    S3

    D

  • Introduo aos Sistemas Digitais (v.2001/1) Jos Lus Gntzel e Francisco Assis do Nascimento 2-38

    Exerccios

    Exerccio 2.1 - Dada a equao abaixo (que est na forma fatorada), use as propriedades dalgebra Booleana para encontrar a equao mnima em soma de produtos.

    S = Z (X + X Y )

    Exerccio 2.2 - Ache a equao em soma de mintermos e a equao em produto demaxtermos para as funes F1 e F2 descritas pela tabela verdade abaixo edesenhe os respectivos circuitos lgicos

    A B C F1 F2

    0 0 0 1 0

    0 0 1 0 1

    0 1 0 0 0

    0 1 1 1 1

    1 0 0 1 0

    1 0 1 1 0

    1 1 0 0 0

    1 1 1 0 1

    Exerccio 2.3 - Reescreva as equaes do exerccio 2, usando a notao compacta.

    Exerccio 2.4 - determinar a expresso mnima em soma de produtos e a expresso mnimaem produto de somas para a funo Booleana dada a seguir. Desenhar ocircuito lgico para cada expresso obtida.

    S4(x0 , x1, x2, x3 ) = (1,3,5,7,8,9,11,13)Cobertura para soma de produtos:

    S4

    x3

    x2x3x0x1 00 01 11 10

    00

    01 x1

    11

    x010

    x2

  • Introduo aos Sistemas Digitais (v.2001/1) Jos Lus Gntzel e Francisco Assis do Nascimento 2-39

    Cobertura para produto de Somas:

    S4

    x3

    x2x3x0x1 00 01 11 10

    00

    01 x1

    11

    x010

    x2

    Exemplo 2.11:. dada a funo que segue, determinar as equaes mnimas em SdP (soma deprodutos) e em PdS (produto de somas) para a funo dada. Desenhar osrespectivos circuitos lgicos e identificar, o circuito de menor complexidade(entre SdP e PdS).

    S7(A,B,C,D)= (4,6,8,9,12,13,14) + DC(0,2,5,10)

    Observao: neste caso, h duas coberturas mnimas para SdP. Determine cada uma nos doisprimeiros mapas.

    Cobertura 1 para soma de produtos:

    S7D

    CDAB 00 01 11 10

    00

    01 B

    11

    A10

    C

  • Introduo aos Sistemas Digitais (v.2001/1) Jos Lus Gntzel e Francisco Assis do Nascimento 2-40

    Cobertura 2 para soma de produtos:

    S7

    D

    CDAB 00 01 11 10

    00

    01 B

    11

    A10

    C

    Cobertura 1 para produto de somas:

    S7

    D

    CDAB 00 01 11 10

    00

    01 B

    11

    A10

    C

  • Introduo aos Sistemas Digitais (v.2001/1) Jos Lus Gntzel e Francisco Assis do Nascimento 2-41

    Bibliografia Suplementar

    [1] GAJSKI, Daniel D. Principles of Digital Design, New Jersey: Prentice Hall, 1997 (ISBN0-13-301144-5)

    [2] MANO, M. Morris; Computer Engineering: Hardware Design. New Jersey: PrenticeHall, 1988 (ISBN 0-13-162926-3)

    [3] TAUB, H. Circuitos Digitais e Microprocessadores. McGraw-Hill, 1982.

    [4] BROWN, Stephen; VRANESIC, Zvonko. Fundamentals of Digital Logic with VHDLDesign, McGraw-Hill Higher Education (a McGraw-Hill Company), 2000 (ISBN texto:0-07-012591-0 CD parte da coleo: 0-07-235596-4)

    [5] ERCEGOVAC, Milos; LANG, Toms; MORENO, Jaime H. Introduo aos SistemasDigitais. Porto Alegre: Bookman, 2000 (ISBN: 85-7307-698-4)

    [6] KATZ, Randy H. Contemporary Logic Design. The Benjamin/Cummings PublishingCompany, Inc. , 1994 (ISBN: 0-8053-2703-7)