FUNÇÕES LÓGICAS Formas de representação de uma função …cricte2004.eletrica.ufpr.br/pastro/P%E1gina_Pastro/Notas_de_Aula... · ELETRÔNICA DIGITAl I 4 Ademar Luiz Pastro UFPR-Departamento

ELETRÔNICA DIGITAl I 1

Ademar Luiz Pastro UFPR-Departamento de Engenharia Elétrica

FUNÇÕES LÓGICAS Formas de representação de uma função lógica Como foi visto no tópico anterior, existem duas formas básicas para representar uma função lógica qualquer:

• Soma de Produtos

CDDCBADBCBADCBAf +++=),,,(

• Produtos de Somas.

))()()((),,,( CADCBADCDCADCBAf +++++++= Com objetivo de desenvolver um procedimento para encontrar a expressão mínima de uma função lógica(minimizar a função), serão analisadas duas formas padrões, também denominadas Formas Canônicas, utilizadas para representar as funções lógicas, que são: a) Forma canônica de Soma de Produtos ABCDDCABCDBADCBADBCADCBADCBAf +++++=),,,( b) Forma canônica de Produto de Somas ))()()((),,,( DCBADCBADCBADCBADCBAf ++++++++++++= Como pode ser observado nos exemplos mostrados acima, cada componente da soma de produtos ou do produto de somas, contém todas as variáveis da função, negadas ou não. Observa-se também que as negações existentes abrangem somente variáveis individuais. Forma canônica de Soma de Produtos Qualquer função lógica pode ser representada na forma canônica de Soma Produtos. Tomemos como exemplo, a mesma função vista anteriormente: )(),,( CBACBACBAf +⋅⋅⋅= Como já foi visto, podemos representar a função como uma soma de produtos: ACABCBACBAf ++⋅⋅=),,( É importante observar que, embora a função esteja representada como uma soma de produtos, ela não está na forma canônica, pois nem todas as parcelas componentes da soma possuem as três



variáveis da função (A, B e C). Para se chegar à forma canônica de soma de produtos, é necessário que as três variáveis estejam presentes em todas as parcelas da soma. É possível observar que na segunda parcela não aparece a variável C enquanto na terceira parcela não aparece a variável B. Nosso objetivo é reescrever a função de modo que as três variáveis apareçam em todas as parcelas. Para isto, vamos lançar mão de dois teoremas vistos anteriormente: 1=+ xx e xx =⋅1 Como na segunda parcela da soma, não aparece a variável C, deve-se multiplicar (operação lógica E) esta parcela por CC + . O valor da expressão não é alterado, considerando que 1=+CC e AB.1 = AB. Do mesmo modo, na terceira parcela não aparece a variável B. Assim, multiplicamos esta parcela por BB + . Assim, CBBACCABCBACBAf )()(),,( ++++⋅⋅= Desenvolvendo temos,

ABCCBAABCCABCBACBAf ++++⋅⋅=),,( Como o produto ABC está em duplicidade, podemos eliminar um deles, pois x + x = x. Portanto, CBAABCCABCBACBAf +++⋅⋅=),,( A função ),,( CBAf está representada agora na sua “forma canônica” de Soma de Produtos, onde as três variáveis, negadas ou não, aparecem em todas as parcelas da soma. Cada um dos produtos componentes da forma canônica da soma de produtos recebe a denominação de “Minterm”. Portanto, podemos dizer que a função está representada na forma de “Soma de Minterms”. Exemplo: Representar como uma soma de minterms, a função: CABDCADCBAf ⋅⋅+⊕⋅=),,,(



Inicialmente deve-se representar a função como uma soma de produtos, aplicando os teoremas e princípios já vistos:

BCBACDADCA

CABCDDCADCBAf

+++⋅⋅=

+++⋅=

)()(),,,(

Seguindo o procedimento visto acima, temos,

)()( ))(()()(),,,( DDBCAADDCCBACDBBADCBBADCBAf ++++++++⋅+= Aplicando a propriedade distributiva,

ABCDDABCBCDADBCABCDA

DBCADCBADCBABCDACDBADCBADCBADCBAf

++++

+++⋅++⋅+⋅+⋅⋅⋅=

),,,(

Eliminando os produtos duplicados, temos a soma de minterms abaixo:

ABCDDABCBCDADBCADCBADCBACDBADCBADCBAf +++++⋅+⋅+⋅⋅⋅=),,,( Forma canônica de Produto de Somas Considerando a mesma função analisada anteriormente:

)(),,( CBACBACBAf +⋅⋅⋅= a qual, como já foi visto, pode ser expressa através do seguinte Produto de Somas: ))()((),,( CABACBACBAf ++++= Como podemos observar, temos um produto de somas que não está na forma canônica, tendo em vista que as três variáveis da função não aparecem em todas as somas. Na segunda soma não aparece a variável C e na terceira soma não aparece a variável B. É possível reescrever a expressão, de modo que as três variáveis, negadas ou não, apareçam em todas as somas. Para isto, serão utilizados os teoremas: xx =+ 0 e 0=⋅ xx



Como na segunda soma não aparece a variável C, é possível somar o produto CC , o que não altera seu valor, uma vez que 0=CC . Do mesmo modo, adicionaremos o produto BB na terceira soma. Assim: ))()((),,( CBBACCBACBACBAf ++++++= Aplicando a propriedade distributiva: x + y⋅z = (x + y)⋅(x + z), ))()()()((),,( CBACBACBACBACBACBAf ++++++++++= Eliminando somas repetidas, temos: ))()()((),,( CBACBACBACBACBAf ++++++++= Chegamos portanto, à forma canônica de produto de somas, onde as três variáveis da função aparecem, negadas ou não, em todas as somas. Cada uma das somas componentes do produto é denominada “Maxterm”. A forma canônica de produto de somas é portanto um Produto de Maxterms. Exemplo: Representar como um produto de maxterms a função: CABDCADCBAf ⋅⋅+⊕⋅=),,,( Representando a função como um produto de somas:

[ ] [ ]

))()()((

))()()((

))()()((

))()((

)()(

)()(),,,(

CADCBDCBBA

CABCDBDCBA

CABCDDBCDCBA

CABCDDCBA

CACDDCABCDDCA

CABCDDCADCBAf

++++++=

++++++=

++++++=

+++⋅+=

+++⋅⋅++⋅=

+++⋅=

Inserindo as variáveis faltantes em cada soma:

))()()((

))()()((

))()()((),,,(

DCBBADCBBADCBADCBA

DCBADCBADCCBADCCBA

DDCBBADCBAADCBAADDCCBADCBAf

++++++++++++

++++++++++++=

++++++++++++=



))()()((

))()()((

))()()((),,,(

DCBADCBADCBADCBA

DCBADCBADCBADCBA

DCBADCBADCBADCBADCBAf

++++++++++++

++++++++++++

++++++++++++=

Eliminando somas duplicadas:

))()()((

))()()((),,,(

DCBADCBADCBADCBA


++++++++++++

++++++++++++=

Identificação dos Minterms Com objetivo de facilitar a representação de uma função lógica através da soma de minterms, veremos a seguir uma forma de identificar cada um dos minterms componentes da função. Seja por exemplo a função abaixo, representada pela soma de minterms:

ABCCABCBACBACBACBAf ++++⋅=),,( Para identificar um minterm, transformamos o produto de variáveis em um número binário, associando o bit “0” à variável negada e o bit “1” à variável não negada. Para o minterm CBA , temos a seguinte associação: CBA 0 1 0 O número binário 010 corresponde a 2 no sistema decimal. Assim, o minterm CBA é denominado minterm 2 e representado por m2. Para a função especificada acima, temos então: ABCCABCBACBACBACBAf ++++⋅=),,( 0 0 1 0 1 0 1 0 1 1 1 0 1 1 1 1 2 5 6 7 Portanto, CBA ⋅ = m1, CBA = m2, CBA = m5, CAB = m6, ABC = m7,



Podemos escrever a função como: 76521),,( mmmmmCBAf ++++= , ou de forma mais resumida:

f(A,B,C) = Σm(1,2,5,6,7) , ou simplesmente f(A,B,C) = Σ(1,2,5,6,7) Identificação dos Maxterms Para o caso da função representada através de um produto de maxterms, adotamos um procedimento similar, com a diferença que, associamos o bit 1 à variável negada e o bit 0 à variável não negada. Seja por exemplo a função: ))()()((),,( CBACBACBACBACBAf ++++++++= Se tomarmos por exemplo, o maxterm )( CBA ++ e fizermos as associações especificadas, temos: CBA ++ 0 1 1 O número binário 011 é equivalente a 3 no sistema decimal, portanto, CBA ++ corresponde ao maxterm 3, sendo representado por M3. Desta forma, para a função especificada acima temos: ))()()((),,( CBACBACBACBACBAf ++++++++= 0 0 1 0 1 1 1 0 0 1 1 1 1 3 4 7 Então: CBA ++ = M1, CBA ++ = M3, CBA ++ = M4, CBA ++ = M7 Podemos escrever a função como:



7431),,( MMMMCBAf ⋅⋅⋅= , ou ainda: f(A,B,C) = ΠM(1,2,4,7) , Ou, de forma mais resumida: f(A,B,C) = Π(1,2,4,7) Exemplos:

a) Representar a soma de produtos correspondente à função abaixo: f(A,B,C,D) = Σ(0,1,4,8,10,12,13,15) m0 = m1 = m4 = m8 = m10 = m12 = m13 = m13 =

Portanto,

=),,,( DCBAf

b) Representar o produto de somas correspondente à função abaixo: f(A,B,C,D) = Π(2,3,5,6,7,9,11,14) M2 = M3 = M5 = M6 = M7 = M9 = M11 = M14 =

Portanto, =),,,( DCBAf





Exercícios: Considere a função lógica: )()()(),,,( DCABDCADCABDCBAf +++⋅+=

a) Representar o circuito que realiza a função acima, como uma estrutura de dois níveis de portas, utilizando:

a.1) Somente portas NAND; a.2) Somente portas NOR.

b) Representar a função acima como:

b.1) Soma de Minterms; b.2) Produto de Maxterms.



Caracterização de uma função lógica Nos tópicos anteriores, as funções lógicas foram apresentadas, na forma de soma de minterms ou produto de maxterms, sem qualquer preocupação no sentido de saber de onde as mesmas foram obtidas. Será visto a seguir, o processo de caracterização de uma função lógica, ou seja, de que maneira determinamos os minterms ou maxterms de uma função. Consideremos como exemplo, um sistema de alarme no qual existam quatro sensores, identificados por: A, B, C e D. O diagrama em blocos do nosso sistema de alarme está mostrado na figura abaixo:

Nosso objetivo é determinar qual é a lógica necessária para disparar o alarme, em função dos sinais gerados pelos sensores. O alarme deverá ser disparado caso qualquer uma das seguintes condições seja satisfeita:

a) Se os sensores A e B forem ativados, desde que o sensor D não seja ativado; b) Se somente o sensor C for ativado; c) Se os sensores A, C e D forem ativados; d) Se somente o sensor B for ativado e) Se os sensores B e C forem ativados.

Determinar a função lógica f(A,B,C,D) que aciona o alarme, considerando os seguintes valores lógicos: x = 0 ⇒ sensor “x” não ativado x = 1 ⇒ sensor “x” ativado f(A,B,C,D) = 0 ⇒ Não disparar o alarme f(A,B,C,D) = 1 ⇒ Disparar o alarme

A

f(A,B,C,D)

Sensor A

Sensor B

Sensor D

Sensor C

B

C

D

Alarme



O primeiro passo para a caracterização da função, é a construção da tabela verdade, na qual são representadas todas as possíveis combinações das variáveis de entrada(sensores) e, a partir das condições estabelecidas, qual é a saída correspondente à cada uma das combinações. A tabela verdade para o sistema de alarme, está mostrada abaixo:

A B C D f(A,B,C,D)0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 1 1 0 0 1 0 0 1 0 1 0 1 0 0 1 1 0 1 0 1 1 1 1 1 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 1 1 1 1 0 0 1 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1

Uma vez obtida a tabela verdade, temos que decidir se a função será representada na forma de soma de minterms ou produto de maxterms. No nosso exemplo, vamos analisar ambas as formas. a) Função na forma de soma de minterms: Nesta forma de representação, como já vimos, a função é representada como uma soma de produtos, onde cada produto contém as quatro variáveis da função, complementadas ou não. Analisando a tabela verdade, vemos que na linha 3, quando A = 0, B = 0, C = 1 e D = 0, o valor da função deve ser f(A,B,C,D) = 1. Devemos então, incluir na nossa soma, o produto DCBA ⋅⋅⋅ , cujo resultado será 1 para a combinação especificada. Como o resultado deste produto é 1, e considerando que 11 =+ x , teremos f(A,B,C,D) = 1, independente do valor assumido pelos demais produtos componentes da função. Da mesma forma, para a linha 5 da tabela verdade, quando A = 0, B = 1, C = 0 e D = 0, devemos incluir na soma, o produto DCBA ⋅⋅⋅ , de modo a termos f(A,B,C,D) = 1 para a combinação especificada. Generalizando, devemos incluir na soma, um produto para cada linha da tabela verdade onde o valor da função deve ser 1. Desta forma, garantimos que, para cada uma destas combinações temos um produto que garante o valor 1 para a função nestas linhas.



Assim, para a tabela verdade acima, temos a seguinte soma de minterms:

ABCDDABCDCABCDBABCDADBCADCBADCBADCBAf ++⋅++++⋅+⋅=),,,( Portanto, para determinar a função como uma soma de minterms, devemos incluir na função um minterm para cada linha da tabela verdade onde o valor da função deve ser 1. b) Função na forma de produto de maxterms Nesta forma de representação, a função é representada como um produto de somas, onde cada soma contém as quatro variáveis da função, complementadas ou não. Analisando a tabela verdade, vemos que na linha 1, quando A = 0, B = 0, C = 0 e D = 0, o valor da função deve ser f(A,B,C,D) = 0. Incluímos então no nosso produto, a soma DCBA +++ , cujo resultado será 0 para a combinação especificada. Como o resultado desta soma é 0, e considerando que 00 =⋅ x , teremos f(A,B,C,D) = 0, independente do valor assumido pelas demais somas componentes da função. Da mesma forma, para a linha 2 da tabela verdade, quando A = 0, B = 0, C = 0 e D = 1, devemos incluir no produto, a soma DCBA +++ , de modo a termos f(A,B,C,D) = 0 para a combinação especificada. Generalizando, devemos incluir no produto, uma soma para cada linha da tabela verdade onde o valor da função deve ser 0. Desta forma, garantimos que, para cada uma destas combinações temos uma soma que garante o valor 0 para a função nestas linhas. Assim, para a nossa função temos o seguinte produto de maxterms:

))()()((

))()()((),,,(

DCBADCBADCBADCBA


++++++++++++=

++++++++++++=

Portanto, a função lógica a ser implementada para acionar o nosso alarme, pode ser escrita como: f(A,B,C,D) = Σ(2,4,6,7,11,12,14,15), ou então, f(A,B,C,D) = Π(0,1,3,5,8,9,10,13) Exercício: Simplificar a função lógica encontrada para acionamento do alarme.



MAPA DE KARNAUGH O mapa de Karnaugh é uma ferramenta de grande utilidade no processo de simplificação de funções lógicas. O mapa de Karnaugh é representado por uma figura geométrica, na qual existe um quadro correspondente à cada linha da tabela verdade que define a função. Como foi visto no exemplo do alarme, existe uma correspondência entre as linhas da tabela verdade e os minterms e maxterms da função. Da mesma forma, existe uma correspondência entre os minterms e maxterms com os quadros do mapa de Karnaugh. Mapa de Karnaugh para uma função de 2 variáveis Consideremos, por exemplo, a função de duas variáveis, cuja tabela verdade está representada abaixo:

A B f(A,B) 0 0 0 0 1 1 1 0 0 1 1 1

O mapa de karnaugh para uma função de duas variáveis, é composto de quatro quadros, conforme podemos ver na figura abaixo:

Primeiramente, é necessário identificar cada um dos quadros componentes do mapa, ou seja, qual quadro corresponde à qual minterm. Para isto, deve-se associar à cada coluna um dos valores da variável A e à cada linha os valores da variável B, ficando portanto com a seguinte representação:

Portanto, o mapa correspondente à tabela verdade mostrada acima é:

BA

0 1

0

1



Outras formas de representar a identificação dos quadros no mapa, estão mostrados na figura abaixo:

Nos exemplos acima, estão representados tanto os minterms como os maxterms da função no mapa de Karnaugh. Na prática, considerando que os valores são mutuamente exclusivos, basta representar um deles, ou seja, representamos somente os 1’s ou somente os 0’s da função. Assim, a função acima pode ser representada pelos mapas:

f(A,B) = Σ(1,3)

ou,

f(A,B) = Π(0,2)

Portanto, se a função for representada como uma soma de minterms, colocamos 1’s nos quadros correspondentes aos minterms e se for representada como um produto de maxterms, colocamos 0’s nos quadros correspondentes aos maxterms.

B

A

0 0

B

A

1 1

A

B

0 0

1 1 B

A

0 0

1 1

A B

B A

0 1

0

1

0 0

1 1



Mapa de Karnaugh para 3 variáveis Consideremos agora, uma função de 3 variáveis, cuja tabela verdade está mostrada abaixo:

A B C f(A,B,C)0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 1 1 1 1 1

A função é:

f(A,B,C) = Σ(2,4,6,7) ou,

f(A,B,C) = Π(0,1,3,5) O mapa de karnaugh para uma função de três variáveis é formado por oito quadros, conforme mostrado abaixo:

Como podemos observar, nas colunas colocamos os valores para as variáveis A e B e nas linhas os valores para a variável C. Observe que os valores para as variáveis A e B seguem a seqüência do código Gray, o qual já foi visto anteriormente. No caso da função representada pela tabela verdade acima, temos os seguintes minterms representados no mapa:

1 1 1

1

A

C

B

A A

B B

1 1 1

1 C

C

A A

B B

0

C AB

1

110100 10



Caso seja utilizada a representação dos maxterms da função temos o seguinte mapa:

Mapa de Karnaugh para 4 variáveis O mapa para quatro variáveis possui 16 quadros, que podem ser identificados colocando nas colunas os valores das variáveis A e B e nas linhas os valores das variáveis C e D, utilizando a seqüência do código Gray, como foi visto acima. Na figura abaixo está mostrada a representação de um mapa para quatro variáveis:

Seja por exemplo, a função:

f(A,B,C,D) = Σ(0,1,2,4,6,7,10,12) ou, f(A,B,C,D) = Π(3,5,8,9,11,13,14,15)

A representação do mapa para esta função, utilizando os minterms é:

1 1 1

1

A

C

B

A A

B B

1 1 1

1

C

C

A A

B B

1

1 1 1

D 1

1 1 1

C

C

D

D

D

D

CDAB

110100 10

00

01

11

10

0

0 0 0

A

C

B

A A

B B

0

0 0 0 C

C

A A

B B



É importante salientar que, a disposição dos minterms/maxterms no mapa de Karnaugh depende da forma como as variáveis da função são dispostas. Se alterarmos a disposição das variáveis, alteraremos também a disposição dos minterms/maxterms. Nos exemplos que serão vistos, utilizaremos sempre a disposição apresentada acima. Minimização de funções utilizando o mapa de Karnaugh A característica fundamental do mapa de Karnaugh é resultado da utilização da seqüência do código Gray para representar os valores das variáveis no mapa. Como já foi visto no capítulo que trata de códigos binários, o código Gray possui a característica de ter somente um bit diferente entre dois valores consecutivos. Assim dois quadros adjacentes do mapa, na horizontal ou na vertical (na diagonal esta característica não é observada), possuem somente uma variável com valor diferente entre os dois. Esta característica se observa também em quadros que estão na extremidade do mapa, seja na horizontal ou na vertical. Portanto, se existirem dois minterms em quadros adjacentes no mapa (na horizontal ou na vertical), estes dois minterms terão todas as variáveis iguais, com exceção de uma, que será negada em um minterm e não negada em outro. Seja por exemplo, a função f(A,B,C,D) = Σ(2,4,7,10,12,15) O mapa para esta função, utilizando os minterms, está mostrado abaixo.

Conforme é possível observar no mapa de Karnaugh da função, os minterms m4 e m12 são adjacentes(na horizontal). Estes dois minterms diferem somente pela variável A, que aparece negada no minterm m4 e não negada no minterm m12. Desta forma,

DCB

AADCB

DCABDCBAmm

⋅=

+⋅=

⋅+⋅=+

)( 124

1 1

1 1

1 1

A

B

C

Dm4 m12



Observa-se portanto, que os dois minterms podem ser combinados, resultando em um único produto composto de três variáveis. Observe que a variável A que aparece negada em um minterm e não negada em outro, foi eliminada. O grande mérito do mapa de Karnaugh, é que o mesmo permite um reconhecimento visual rápido dos minterms que podem ser combinados Assim, qualquer par de minterms adjacentes (na horizontal ou na vertical) podem ser combinados, resultando em um produto, onde é eliminada a variável que aparece negada em um minterm e não negada em outro. As chaves que indicam os valores das variáveis nos diversos quadros do mapa, nos permitem identificar rapidamente qual é a variável que muda de um quadro para outro. No caso da função vista acima, podemos identificar no mapa, três pares de minterms adjacentes, conforme mostrado no mapa abaixo:

Para extrair do mapa os produtos correspondentes a cada combinação, analisamos a posição dos minterms em relação às chaves. Se todos os minterms da combinação estão cobertos pela chave, a variável correspondente aparece não negada e se os minterms estão fora da abrangência da chave, a variável correspondente aparece negada. Assim: DCBmm ⋅=+ 124 BCDmm =+ 157

DCBmm =+ 102 A expressão mínima para a função é a soma dos produtos obtidos: DCBBCDDCBDCBAf ++⋅=),,,(

1 1

1 1

1 1

A

B

C

D



Exemplo: Encontrar a expressão mínima da função: f(A,B,C,D) = Σ(0,1,11,14,15).

O mapa de Karnaugh para a função está mostrado abaixo: Como já foi visto, é possível combinar os minterms 0 e 1, assim como os minterms 14 e 15, combinações estas que estão indicadas no mapa.

Analisando o mapa, podemos observar que o minterm 11 também pode ser combinado com o minterm 15. Porém, o minterm 15 já foi combinado com o minterm 14. A questão é, um minterm pode ser combinado mais de uma vez? A resposta é afirmativa, sendo a explicação apresentada a seguir. Analisando somente os minterms 11, 14 e 15 temos: ABCDDABCCDBAmmm ++=++ 151411 Observamos na expressão acima, que o produto ABCD pode ser combinado tanto com produto

CDBA como com produto DABC . Considerando que, x + x = x, fica claro que podemos duplicar o produto ABCD na expressão acima, sem alterar seu valor. Assim, ABCDABCDDABCCDBAmmm +++=++ 151411 Podemos agora combinar uma das ocorrências do minterm 15 com o minterm 11 e a outra com o minterm 14. Portanto:

ABCACD

DDABCACDBBmmm+=

+++=++

)()(151411

Seguindo a mesma linha de raciocínio, podemos notar que um produto qualquer pode ser replicado quantas vezes for necessário, de forma a ser combinado com outros produtos. Isto

1

1

1

1 1

A

B

C

D



significa que, qualquer minterm no mapa de Karnaugh pode ser combinado quantas vezes for necessário. Na figura abaixo está mostrado o mapa com todas as combinações possíveis.

A expressão mínima da função é portanto:

ACDABCCBADCBAf ++⋅⋅=),,,( Consideremos agora a função f(A,B,C,D) = Σ(2,3,8,10,12), mapeada na figura abaixo, onde estão indicadas todas as possíveis combinações

A partir das combinações possíveis, mostradas no mapa, é extraída a expressão mínima da função, que é: DCADBADCBCBADCBAf ⋅+⋅++⋅=),,,( Uma das características do mapa de Karnaugh é que, se utilizarmos corretamente o mesmo, a expressão extraída é mínima, ou seja, não pode mais ser simplificada. Analisando a expressão acima, vemos que podemos fatorar B nos três primeiros produtos.

1 1

1 1

1

A

B

C

D

1

1

1

1 1

A

B

C

D



Portanto, DCABDADCCADCBAf ⋅+++= )(),,,( Na expressão acima, podemos identificar, entre parênteses, o teorema zxxyyzzxxy +=++ . Então, o produto DC (correspondente a yz) pode ser eliminado, ficando portanto a expressão:

DCADBACBA

DCABDACADCBAf

⋅+⋅+⋅=

⋅++=

)(),,,(

Podemos ainda, simplificar a expressão de forma diferente: DCABACBCBADCBAf )(),,,( +++⋅= Utilizando o mesmo teorema, verificamos que o produto BA pode ser eliminado da expressão. Temos então: DCADCBCBADCBAf ⋅++⋅=),,,( Do exemplo acima, é possível concluir que:

a) A função possui duas expressões mínimas: DCADBACBADCBAf ⋅+⋅+⋅=),,,( DCADCBCBADCBAf ⋅++⋅=),,,(

b) O mapa não foi utilizado corretamente, pois foi possível simplificar a expressão. Verificamos então, através das expressões mínimas obtidas para a função acima, que temos uma combinação desnecessária no mapa. Analisando as combinações m2+m10 e m8+ m10, verificamos que uma das duas é desnecessária. A opção por uma ou outra combinação nos leva à uma das duas expressões mínimas da função vistas anteriormente. A pergunta a ser respondida é, como identificar uma combinação desnecessária? Como regra geral, para que uma combinação seja necessária, pelo menos um minterm desta combinação não pode pertencer a nenhuma outra combinação, situação esta que não ocorre no exemplo acima.



Na figura abaixo estão mostradas as duas configurações possíveis para o mapa do nosso exemplo

DCADCBCBA ⋅++⋅ DCADBACBA ⋅+⋅+⋅ Combinações envolvendo mais de dois minterms Nos exemplos vistos até aqui, foram analisadas as combinações envolvendo dois minterms adjacentes no mapa, onde cada combinação resulta em um produto onde uma das variáveis é eliminada. De modo geral, é possível efetuar combinações com 2n minterms, desde que as condições necessárias sejam satisfeitas. Uma combinação com 2n minterms, resulta em um produto onde são eliminadas n variáveis. Combinações típicas com 4 minterms estão mostradas abaixo: Consideremos por exemplo, a função f(A,B,C,D) = Σ(10,11,14,15), cujo mapa está mostrado a seguir. No mapa estão também indicadas duas alternativas para as combinações com os pares de minterms.

Na alternativa indicada pela linha cheia, combinamos os minterms m10+m14 e m11+ m15. Temos portanto:

1 1

1 1

A

B

C

D

1 1

1 1

1

A

B

C

D

1 1

1 1

1

A

B

C

D



DACmm =+ 1410 e ACDmm =+ 1511 Assim, ACDDACDCBAf +=),,,( Como podemos observar, esta expressão pode ser simplificada.

AC

DDACDCBAf=

+=

)(),,,(

Isto significa, que podemos efetuar na realidade, uma única combinação com os quatro minterms, combinação esta que está indicada no mapa abaixo:

Para extrair do mapa o produto correspondente à combinação com os quatro minterms, observamos o seguinte:

• Como as combinações são de 22 = 4 minterms, duas variáveis serão eliminadas; • Duas variáveis têm valores diferentes entre os quatro minterms (A e B). Estas variáveis

serão eliminadas; • Duas variáveis têm o mesmo valor para os quatro minterms (C e D). Estas variáveis são as

que formarão o produto a ser extraído do mapa; • Como os quatro minterms estão na região do mapa onde A = 1, esta variável aparece não

negada. Do mesmo modo, como os quatro minterms estão na região do mapa onde C = 1, esta variável também aparece não negada

Assim, temos diretamente do mapa: ACDCBAf =),,,(

1 1

1 1

A

B

C

D



Nos mapas de Karnaugh abaixo, estão mostradas outras situações onde é possível combinar os quatro minterms:

DCABDCBAf +=),,,( DBDBDCBAf +=),,,(

DBDCBAf ⋅=),,,( Da mesma forma, podem ser feitas combinações com 23 = 8 minterms, desde que satisfeitas as condições necessárias. Numa combinação com 8 minterms são eliminadas 3 variáveis. Observe que, para que a combinação seja possível, uma das variáveis deve ter o mesmo valor nos oito minterms e três variáveis têm valor diferente.

CBDCBAf +=),,,( DBDCBAf +=),,,(

1 1 1 1

1 1 1 1

1 1

1 1

A

B

C

D1 1

1 1 1 1

1 1 1 1

1 1

A

B

C

D

1 1

1 1

A

B

C

D

1 1 1 1

1

1

1

A

B

C

D1 1

1 1

1 1

1 1

A

B

C

D



Utilização do Mapa de Karnaugh Até este ponto, foram analisadas as diferentes possibilidades de efetuar as combinações com os minterms no mapa de Karnaugh. Veremos agora como efetivamente utilizar o mapa de Karnaugh para se obter a expressão mínima de uma função. De início, é necessário estabelecer os seguintes conceitos:

a) As combinações devem ser efetuadas de modo que cada minterm seja incluído em pelo menos uma combinação, se possível. Como será visto adiante, existem situações em que um minterm não pode ser combinado com nenhum outro.

b) Considerando que numa combinação de 2n minterms são eliminadas n variáveis

de um produto, devem ser selecionadas aquelas combinações que abrangem o maior número possível de minterms.

Um certo cuidado deve ser observado para que não sejam selecionadas combinações que são desnecessárias, conforme foi visto anteriormente. Exemplo: obter a expressão mínima da função f(A,B,C,D) = Σ(3,6,8,10,11,13,14,15).

Como se observa no exemplo acima, a combinação que abrange o maior número de minterms, tracejada no mapa, mostrou ser desnecessária, e não pode ser incluída na expressão mínima da função. Portanto, a expressão mínima da função é: DBAABDDBCCDBDCBAf ⋅+++=),,,( De modo a evitar combinações desnecessárias, pode-se seguir a seqüência de etapas relacionadas abaixo:

1) Identificar os minterms que não podem ser combinados com nenhum outro;

1

1

1 1 1

1 1 1

A

B

C

D



2) Identificar os minterms que só podem fazer parte de uma única combinação com dois minterms. Aqueles minterms que podem ser combinados mais de uma vez, são temporariamente ignorados;

3) Identificar os minterms que só podem fazer parte de uma única combinação com quatro

minterms. Aqueles minterms que podem ser combinados mais de uma vez, são temporariamente ignorados;

4) Repetir o procedimento para grupos de oito minterms, dezesseis, etc; 5) Se após seguir o procedimento acima, ainda restar algum minterm que não foi

combinado, o mesmo pode ser combinado de forma arbitrária, sempre levando em consideração que devemos ter o menor número possível de combinações.

Exemplos: a) Minimizar a função lógica: f(A,B,C,D) = Σ(0,1,3,5,6,9,11,12,13,15).

De acordo com a sequência de etapas proposta, observamos que:

1) O minterm 6 não pode ser combinado com nenhum outro. Indicamos isto através de um circulo em torno do minterm.

2) O minterm 0 pode ser combinado somente com o minterm 1. Da mesma forma, o minterm 12 pode ser combinado somente com o minterm 13.

3) Os minterms 3, 5 e 15 somente podem ser combinados uma vez, numa combinação com quatro minterms.

A expressão mínima da função é portanto: =),,,( DCBAf

1 1 1 1

1 1

1

1 1 1

A

B

C

D



b) Minimizar a função lógica: f(A,B,C,D) = Σ(0,2,3,4,5,7,8,9,13,15).

=),,,( DCBAf c) Minimizar a função lógica: f(A,B,C,D) = Σ(1,3,4,5,6,7,11,12,14,15).

=),,,( DCBAf d) Minimizar a função lógica: f(A,B,C,D) = Σ(0,2,4,6,7,8,9,10,13,15).

=),,,( DCBAf

A

B

C

D

A

B

C

D

A

B

C

D



Utilização do mapa quando a função é representada pela soma de maxterms Até aqui, foi vista a utilização do mapa de Karnaugh quando a função é representada pela soma de minterms. Quando a função é representada pelo produto de maxterms, as regras para as combinações são exatamente as mesmas já vistas para os minterms. Deve-se apenas tomar cuidado no mapeamento da função e na extração da expressão mínima, lembrando que, no caso dos maxterms a variável negada é associada ao bit 1 e variável não negada é associada ao bit 0. Exemplos: a) Obter a expressão mínima da função: f(A,B,C,D) = Π(0,1,2,4,5,6,8,11,15) O mapeamento dos maxterms está mostrado abaixo:

)DCA)(DCB)(CA)(DA()D,C,B,A(f ++++++=

b) Obter a expressão mínima da função: f(A,B,C,D) = Π(0,3,4,5,6,7,11,13,14,15)

=),,,( DCBAf

0 0

0 0

0 0

0 0 0 0

A

B

C

D

0 0

0 0 0

0 0

0 0

A

B

C

D



Exercícios: Minimizar as funções abaixo:

a) f(A,B,C,D) = Σ(0,3,4,5,7,11,12,14,15)

b) f(A,B,C,D) = Σ(0,1,2,5,6,8,9,10,13)

c) f(A,B,C,D) = Σ(0,2,3,4,5,6,7,8,10,11,15)

d) f(A,B,C,D) = Σ(0,1,2,3,5,8,9,10,11,12,14,15)

e) f(A,B,C,D) = Σ(1,2,3,5,7,10,11,12,13,14,15)

f) f(A,B,C,D) = Σ(0,2,4,5,7,8,10,12,14,15)

g) f(A,B,C,D) = Σ(0,1,5,8,10,11,13,14,15)

h) f(A,B,C,D) = Π(0,1,2,5,8,10,11,13,14,15)

i) f(A,B,C,D) = Π(1,2,3,4,5,7,9,10,11,15)

j) f(A,B,C,D) = Π(0,2,3,4,5,6,7,8,10,11,13,15)



Mapa de Karnaugh para funções de 5 variáveis A construção de um mapa de Karnaugh para funções de 5 variáveis segue o mesmo procedimento já visto para os mapas de 2, 3 e 4 variáveis. Considerando que o mapa é formado por 32 quadros, dispostos em uma matriz de 4 linhas por 8 colunas, colocamos nas colunas os valores de três destas variáveis (A, B e C) e nas linhas os valores das outras duas variáveis (D e E), utilizando a seqüência do código Gray, conforme podemos observar na figura abaixo.

Representando as chaves, temos o mapa abaixo:

Analisando este mapa, percebemos que a linha tracejada divide o mesmo em dois mapas de quatro variáveis. No mapa da esquerda temos A = 0 e no mapa da direita temos A = 1. Além disto, é possível notar que o mapa da direita está invertido em relação ao original. Isto significa que, todos os critérios já vistos para utilização de um mapa de quatro variáveis são válidos para cada uma das partes que compõem o mapa de cinco variáveis. Além disso, podemos observar que os minterms simétricos em relação à linha tracejada central, são logicamente adjacentes, ou seja, possuem somente uma variável diferente entre os dois (variável A). Desta forma, minterms simétricos também podem ser combinados.

B

C

D

A

C

E

DE

ABC

000

00

01

11

10

001 011 010 110 111 101 100



Seja por exemplo, a função f(A,B,C,D,E) = Σ(0,5,8,10,11,20,21,22,23,26,27), mapeada no mapa de cinco variáveis abaixo:

Os minterms 0 e 8, assim como os minterms 20, 21, 22 e 23 podem ser combinados da mesma forma que são feitas as combinações em um mapa de 4 variáveis. É possível observar também, que os minterms 5 e 21 são simétricos e podem ser combinados. Além disso, os pares de minterms (10, 11) e (26, 27) também são simétricos podendo ser combinados no quadrado mostrado no mapa. A expressão mínima da função é portanto:

EDCACBAEDCBDCBEDCBAf ⋅⋅⋅+++=),,,,( . Uma representação alternativa para o mapa de cinco variáveis está mostrada na figura abaixo, onde foi mapeada a mesma função do exemplo anterior.

Nesta representação, o mapa da direita foi girado 180 graus em torno de um eixo vertical, de modo a ficar na posição normal de um mapa de quatro variáveis. Neste caso, ao invés de trabalharmos com minterms simétricos, trabalhamos com minterms correspondentes nos dois mapas.

1

1

1 1

1 1

1

1 1

1

1

B

C

D

E

B

C

A

D

1

1 1

1

1

B

C

D

1

1

1 1

1 1

A

C

E



Exemplos: Minimizar as funções de 5 variáveis:

a) f(A,B,C,D,E) = Σ(0,2,5,8,13,15,18,21,24,29,31)

=),,,,( EDCBAf

b) f(A,B,C,D,E) = Σ(0,1,4,5,6,12,14,16,19,20,22,28,30,31)

=),,,,( EDCBAf Exercícios Minimizar as funções:

a) f(A,B,C,D,E) = Σ(0,2,4,6,9,10,13,14,15,16,18,21,24,26,28,29,30,31) b) f(A,B,C,D,E) = Σ(0,2,4,5,6,7,8,10,12,13,16,18,21,23,24,25,26,29) c) f(A,B,C,D,E) = Σ (0,1,2,5,7,8,9,10,13,15,16,17,19,21,22,24,25,26,29,30) c) f(A,B,C,D,E) = Π(1,2,4,5,8,15,18,20,21,24,29)

B

C

D

E

B

C

A

D

B

C

D

E

B

C

A

D



Mapa de Karnaugh para funções de 6 variáveis O mapa para uma função de 6 variáveis é composto por 64 quadros, dispostos em uma matriz de 8 linhas por 8 colunas. A identificação de cada um dos quadros está mostrada na figura abaixo.

Na figura abaixo temos representadas as chaves que definem o posicionamento das variáveis, bem como está mapeada a função. Podemos observar que, o mapa para 6 variáveis é formado por quatro mapas de 4 variáveis.

FEDCAEFCBAEACEDCBAFECBFEDCBAf ⋅⋅⋅+⋅⋅+++=),,,,,(

B

C

E

A

C

F 1

1

1

1 1

1 1

1 1

1

1

1 1

1 1

1 D F

DEF

ABC

000

000

001

011

010

001 011 010 110 111 101 100

110

111

101

100



Mapeamento quando a função não é expressa em minterms Até agora, vimos como mapear uma função no mapa de Karnaugh quando conhecemos os minterms ou os maxterms da mesma. Veremos a seguir, que podemos mapear a função bem como encontrar sua expressão mínima, mesmo sem ter os seus minterms. Seja por exemplo a função DCBDCBACBDBADCADCBAf ++++++= )()(),,,( Para mapear a função, é necessário representar a mesma como uma soma de produtos. Assim: DCBDBACBACBDBADACADCBAf ++++++⋅=),,,( Devemos agora efetuar um procedimento ao contrário do processo de minimização, ou seja, cada produto componente da soma, corresponde a uma combinação de minterms. Portanto, CA ⋅ corresponde à combinação: 5410 mmmm +++

DA corresponde à combinação: 7531 mmmm +++

DBA corresponde à combinação: 64 mm +

CB corresponde à combinação: 131254 mmmm +++

CBA corresponde à combinação: 1110 mm +

DBA corresponde à combinação: 119 mm +

DCB corresponde à combinação: 102 mm + Na figura abaixo temos o mapeamento completo da função, com as respectivas combinações que podemos efetuar para extrair a expressão mínima.

Assim, DCCBCBADCBAf +++=),,,( Exercício: Mapear e obter a expressão mínima da função abaixo. BCDCBABADCBADCBAf +⋅++++= )(),,,(

1 1 1 1

1 1 1

1 1 1

1 1 1

A

B

C

D



Funções não especificadas completamente De acordo com o que já foi visto, uma função lógica qualquer f é definida especificando o valor assumido (f = 0 ou f = 1), para cada combinação possível das variáveis independentes, através da tabela verdade. A partir desta especificação, determinamos os minterms ou maxterms da função e, através do mapeamento da função no mapa de Karnaugh, sua expressão mínima. No entanto, existem situações em que o valor da função f não é especificado para todas, combinações da variáveis. Neste caso, diferentes funções são possíveis, todas elas satisfazendo as especificações. Estas funções, aparecem em duas situações. Às vezes não nos interessa qual o valor que a função assume para certas combinações de variáveis. Em outros casos, sabemos de antemão que certas combinações de variáveis nunca ocorrem. Vejamos por exemplo, o circuito apresentado abaixo.

Desejamos que a saída do circuito seja S = 1 quando o valor registrado pelo contador for 0, 1, 2, 6, 7 e 8. Considerando que o contador BCD conta de 0 a 9 e considerando que existem 16 combinações possíveis com quatro bits, existem 6 combinações que nunca irão ocorrer na entrada do nosso circuito. Como temos certeza que estas combinações nunca ocorrerão, o valor da função para estas combinações é irrelevante. Podemos fazer tanto f = 0 como f = 1 nestas situações. Neste caso colocamos x na tabela verdade para estas situações de forma a indicar que o valor assumido pela função neste caso é irrelevante (don´t care). Temos então, para o nosso exemplo, a seguinte tabela verdade:

A B C D S 0 0 0 0 1 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 0 1 0 0 0

Entrada SaidaContadorBCD Lógica

B

A

C

DS



0 1 0 1 0 0 1 1 0 1 0 1 1 1 1 1 0 0 0 1 1 0 0 1 0 1 0 1 0 x 1 0 1 1 x 1 1 0 0 x 1 1 0 1 x 1 1 1 0 x 1 1 1 1 x

A função neste caso, é representada por: f(A,B,C,D) = Σ(0,1,2,6,7,8) + d(10,11,12,13,14,15) Como x pode assumir tanto o valor 0 como 1, podemos ter diversas funções diferentes, cada uma delas com sua expressão mínima. Como nosso objetivo é encontrar a expressão mais simples para a função, fazemos igual a 1 aqueles x que contribuem para simplificar a função. Os demais fazemos iguais a 0, conforme mostrado no mapa abaixo.

A expressão mínima para a função neste caso é: CBADBBCDCBAf ⋅⋅+⋅+=),,,( Exercícios: Minimizar as funções abaixo:

a) f(A,B,C,D) = Σ(1,4,5,6,8) + d(10,11,12,13,14,15)

b) f(A,B,C,D,E) = Σ(0, 2,3,16,21) + d(4,5,6,7,8,11,13,15,18,19,22,23,24, 25,26,29,30,31

1 x

1 x 1

1 1 x x

1 x x

A

B

C

D



MINIMIZAÇÃO DE FUNÇÕES POR TABULAÇÃO (Método de Quine-McCluskey) O mapa de Karnaugh é uma ferramenta útil para a minimização de funções de até 5 ou no máximo 6 variáveis. Para funções com um número maior de variáveis, o uso mapa de Karnaugh é muito complexo. Para estas situações, temos que lançar mão de algum tipo de procedimento sistemático, preferencialmente um que possa ser automatizado. O processo minimização de funções por tabulação, também conhecido como método de Quine-McCluskey, satisfaz os requisitos acima, ou seja, pode ser utilizado tanto manualmente como programável em computadores. O conceito fundamental envolvido neste procedimento está baseado em repetidas aplicações do

princípio xyxxy =+ , para se obter o conjunto de todas as combinações possíveis entre os minterms da função, a partir do qual a expressão mínima pode ser selecionada. Assim, a primeira etapa consiste em determinar, de forma sistemática, quais produtos podem ou não ser combinados e efetuar todas as combinações possíveis. Genericamente, dois produtos quaisquer com k variáveis podem ser combinados, se e somente se, ambos tiverem k-1 variáveis idênticas e diferirem em apenas uma variável. O produto resultante desta combinação é composto pelas k-1 variáveis idênticas, enquanto a variável que é negada em um produto e não negada em outro é eliminada. Como exemplo, consideremos a função de 7 variáveis abaixo: f(A,B,C,D,E,F,G) = Σ(66,74,75,79,98,99,107,111) Representando a função através da soma de produtos, temos:

DEFGCABFGEDCABFGEDCABGFEDCAB

DEFGCBAFGEDCBAGFEDCBAGFEDCBAGFEDCBAf

++⋅⋅+⋅⋅=

+⋅+⋅+⋅+⋅⋅⋅=

),,,,,,(

As combinações que podem ser efetuadas são:

GFECBADDGFECBAGFEDCBAGFEDCBAmm ⋅⋅=+⋅⋅=⋅+⋅⋅⋅=+ )(7466

GFEDCABBGFEDCAGFEDCABGFEDCBAmm ⋅⋅=+⋅⋅=⋅⋅+⋅⋅⋅=+ )(9866

FEDCBAGGFEDCBAFGEDCBAGFEDCBAmm ⋅=+⋅=⋅+⋅=+ )(7574

DFGCBAEEDFGCBADEFGCBAFGEDCBAmm ⋅=+⋅=⋅+⋅=+ )(7975 FGEDCABBFGEDCAFGEDCABFGEDCBAmm =+=+⋅=+ )(10775 DEFGCABBDEFGCADEFGCABDEFGCBAmm =+=+⋅=+ )(11179



FEDCABGGFEDCABFGEDCABGFEDCABmm ⋅⋅=+⋅⋅=⋅⋅+⋅⋅=+ )(9998

FGECABDDFGECABFGEDCABFGEDCABmm =+=+⋅⋅=+ )(10799

DFGCABEEDFGCABDEFGCABFGEDCABmm =+=+=+ )(111107

Podemos ainda efetuar uma combinação com 4 minterms: DFGCABBDFGCADFGCABDFGCBAmmmm =+=+⋅=+++ )(1111077975 Portanto:

DFGCAFGECAB

FEDCABFEDCBAGFEDCAGFECBAGFEDCBAf

+⋅+

+⋅⋅+⋅+⋅⋅+⋅⋅=

),,,,,,(

Esta ainda não é a expressão mínima da função, pois a mesma ainda pode ser simplificada, como podemos ver abaixo:

GFECBADFGCAFEDCBAGFECBADFGCA ⋅⋅+=⋅+⋅⋅+

FEDCABDFGCAFGECABFEDCABDFGCA ⋅⋅+=⋅+⋅⋅+

GFECBAFEDCABGFEDCAGFECBAFEDCAB ⋅⋅+⋅⋅=⋅⋅+⋅⋅+⋅⋅ Em todos os casos acima, foi aplicado o teorema: zxxyyzzxxy +=++ Assim, a expressão mínima da função é: DFGCAFEDCABGFECBAGFEDCBAf +⋅⋅+⋅⋅=),,,,,,( Analisando o procedimento visto acima, fica evidente a necessidade de existir um procedimento formal e sistemático para encontrar a expressão mínima de função lógica, que nos conduza de forma direta ao resultado final. Este procedimento, que veremos a seguir, é o método tabular de Quine-McCluskey.



Funções mínimas e suas propriedades No estudo das funções lógicas, existe uma distinção entre “expressão mínima” e “expressão irredutível” de uma função, sendo que nenhuma delas é necessariamente única. Convém lembrar que, toda expressão mínima é irredutível porém, nem toda expressão irredutível é mínima. Por exemplo, dada a função f(A,B,C,D) = Σ(1,2,3,4,5,6,8,12), as expressões: DCACBADCACBADCA ⋅++⋅+⋅+ e DCADCBDCADBADCA ⋅+⋅+⋅+⋅+

são expressões irredutíveis desta função, enquanto as expressões: DCACBADCADBA ⋅+++⋅ e DCADCADBACBA ⋅+⋅++⋅ são expressões mínimas da função. Vamos analisar a seguir, as propriedades destas expressões e determinar as características dos termos contidos em uma expressão representada pela soma de produtos mínima. Conceito de Implicantes Uma função lógica f(A,B,C,...) cobre outra função g(A,B,C,...) se f assume o valor 1 sempre que g o fizer. Representamos esta fato por f ⊇ g. Assim, se f cobre g, existe um “1” na sua tabela verdade em cada linha onde g também tiver “1”. No exemplo mostrado abaixo, BACBCACBAf ++=),,( CBCACBAg +=),,(

A B C BACBCA ++ CBCA + 0 0 0 0 0 0 0 1 1 1 0 1 0 1 0 0 1 1 1 0 1 0 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 0

Como podemos observar, a função f(A,B,C) cobre a função g(A,B,C).



Se f cobre g e por sua vez g cobre f, então f e g são equivalentes. Seja f(A,B,C,...) uma função lógica qualquer e h(A,B,C,...) um produto de variáveis. Se f cobre h, então h implica f, ou h é um implicante de f. A implicação é representada por h → f. Portanto, um implicante de uma função lógica é todo o produto de variáveis que é coberto pela função. Exemplo: Se f = CDAB + e h = CAB , então h é um implicante de f.

Obs.: Pelo que observamos, fica claro que todos os minterms de uma função, bem como todas as possíveis combinações com estes minterms, são implicantes da função.

Implicantes Primos Um “Implicante Primo” p de uma função f é um produto de variáveis coberto por f, de tal forma que a retirada de qualquer variável de p resulta em um novo produto não coberto pela função f. O conjunto de todos os implicantes primos de f é representado por P. Por exemplo, na função: CDAABDCBAf +=),,,( , CABh =1 é um implicante e CDAh =2 é um implicante primo. Teorema: “Uma soma de produtos irredutível equivalente à função f é a união de

implicantes primos de f”. Desta forma, para encontrar a expressão mínima de uma função f, a primeira etapa consiste em gerar o conjunto de todos os implicantes primos da função f e, deste conjunto selecionar aqueles implicantes primos cuja união produz a expressão mínima para a função. Supondo que a função f seja representada na forma de soma de produtos, a aplicação do principio

xyxxy =+ entre pares de minterms produz um implicante de f. Aplicações repetidas deste princípio entre pares de produtos que possuem somente uma variável diferente, produz um conjunto de implicantes de f. Um produto que não pode mais ser combinado com nenhum outro, é um “implicante primo” da função f. Desta forma, a primeira etapa na determinação da expressão mínima de uma função é a combinação sistemática dos produtos. A segunda etapa, que é a seleção do conjunto mínimo de implicantes primos, é em geral mais complicada, como veremos adiante.



Exemplo: Determinar o conjunto P de todos os implicantes primos da função:

f(A,B,C,D) = Σ(0,4,5,7,8,9,13,15) Soma de produtos:

ABCDDCABDBCADCBA

BCDADCBADCBADCBA)D,C,B,A(f

+++⋅⋅+

++⋅+⋅⋅⋅=

Combinações com 2 minterms: DCAmm ⋅⋅=+ 40

DCBmm ⋅⋅=+ 80

CBAmm ⋅=+ 54

BDAmm =+ 75 √

DCBmm =+ 135 √ BCDmm =+ 157 √

CBAmm ⋅=+ 98

DCAmm =+ 139 ABDmm =+ 1513 √ Combinações com 4 minterms: BDABDBDA =+ BDBCDDCB =+ O conjunto de implicantes primos é: BDDCACBACBADCBDCAP ++⋅++⋅⋅+⋅⋅= Derivando expressões mínimas de uma função Uma inspeção no conjunto de implicantes primos P do exemplo anterior nos mostra que o implicante primo BD deve estar contido em qualquer expressão irredutível equivalente à f, uma vez que é o único produto que cobre os minterms 7 e 15. Qualquer outro minterm da função é coberto por dois implicantes primos, sendo que nenhum deles é essencial para a especificação de uma expressão irredutível. Um implicante primo p de uma função f é denominado “implicante primo essencial” se ele cobre pelo menos um minterm de f que não é coberto por nenhum outro implicante primo. Considerando que todos os minterms da função devem ser cobertos, todos os implicantes primos essenciais devem estar contidos em qualquer expressão irredutível da função f. Exemplos:



f(A,B,C,D) = Σ(4,5,8,12,13,14,15)

DCAABCBP ⋅++= Todos os implicantes primos são essenciais.

f(A,B,C,D) = Σ(0,2,3,4,5,7) BABAACBCCACBP ++++⋅+⋅=

Neste caso, nenhum implicante primo é essencial. Todos os implicantes primos têm o mesmo tamanho (mesmo número de variáveis) e cada minterm é coberto por exatamente dois implicantes primos.

Como foi visto, as etapas para a obtenção da expressão mínima de uma função f são as seguintes:

• 1) Determinar todos os implicantes primos essenciais da função e incluí-los na expressão mínima;

• 2) Remover da lista de implicantes primos, aqueles que são cobertos pelos implicantes

primos essenciais;

• 3) Se o conjunto obtido na etapa 1 cobrir todos os minterms de f, então esta é a expressão mínima única. Senão, selecionar implicantes primos adicionais, de forma que todos os minterms seja cobertos, e o número de implicantes primos seja mínimo.

A execução da etapa 3 nem sempre é tão simples. Para um número pequeno de variáveis, isto pode ser feito através do mapa de Karnaugh, enquanto que para um número maior de variáveis um método tabular torna-se necessário.



Determinação dos implicantes primos por tabulação (Quine McCluskey) Através de uma análise da representação binária dos minterms, observa-se que a condição necessária e suficiente para que dois minterms possam ser combinados é que suas representações em binário difiram em somente uma posição. Para que a representação binária de dois minterms sejam diferentes em somente uma posição, é necessário que os dois minterms possuam somente um bit “1” diferente. Desta forma, para facilitar o processo de combinação, os minterms são arranjados em grupos, de acordo com o número de bits “1” existentes na sua representação em binário. Para que o processo seja sistemático, os seguintes passos devem ser seguidos:

• 1- Arranjar todos os minterms em grupos, de tal forma que todos os minterms de um mesmo grupo tenham o mesmo número de bits “1” na sua representação binária. O número de bits “1”em um produto é denominado índice do mesmo. Deve-se agrupar os produtos em ordem crescente de seu índice;

• 2- Comparar cada produto de um grupo com todos os outros do grupo sucessivo,

combinando os produtos sempre que possível. Repetir este processo, comparando cada produto de um grupo de índice i com os produtos do grupo de índice i+1, até que todas as combinações sejam efetuadas. Dois produtos de grupos adjacentes são combináveis se diferirem em somente um bit na sua representação binária. O termo resultante consiste nos bits idênticos, sendo o bit diferente substituído por um traço (-). Cada produto que foi combinado pelo menos uma vez, deve ser marcado;

• 3- Os termos gerados no passo 2 são comparados de acordo com o mesmo

procedimento. Um novo termo é gerado pela combinação de dois termos que difiram em somente um bit e que tenham o traço na mesma posição. O processo continua até que nenhuma combinação seja mais possível. Aqueles termos que não foram marcados formam o conjunto dos implicantes primos da função.

Este procedimento consiste em um processo mecanizado de comparação e redução de todos os pares de produtos adjacentes. Exemplo:

Determinar os implicantes primos da função: f(A,B,C,D) = Σ(0,1,2,5,7,8,9,10,13,15) Inicialmente os minterms arranjados em ordem crescente do seu índice, conforme mostrado na tabela abaixo :



minterm A B C D

0 0 0 0 0 √ 1 0 0 0 1 √ 2 0 0 1 0 √ 8 1 0 0 0 √ 5 0 1 0 1 √ 9 1 0 0 1 √ 10 1 0 1 0 √ 7 0 1 1 1 √ 13 1 1 0 1 √ 15 1 1 1 1 √

Obs.: a marca “√” indica que o minterm foi combinado.

Aplicando o processo descrito no passo 2 temos:

A B C D 0,1 0 0 0 - √ 0,2 0 0 - 0 √ 0,8 - 0 0 0 √ 1,5 0 - 0 1 √ 1,9 - 0 0 1 √ 2,10 - 0 1 0 √ 8,9 1 0 0 - √ 8,10 1 0 - 0 √ 5,7 0 1 - 1 √ 5,13 - 1 0 1 √ 9,13 1 - 0 1 √ 7,15 - 1 1 1 √ 13,15 1 1 - 1 √

Repetindo novamente o processo com os grupos formados na etapa anterior:

A B C D 0,1,8,9 - 0 0 - → CB ⋅

0,2,8,10 - 0 - 0 → DB ⋅ 1,5,9,13 - - 0 1 → DC

5,7,13,15 - 1 - 1 → BD O Mapa de Implicantes Primos O mapa de implicantes primos mostra o relacionamento de cobertura entre os implicantes primos e os minterms da função.



Este mapa consiste em uma tabela com m linhas e n colunas, onde n representa respectivamente o número de minterms e m o número de implicantes primos. As entradas na iésima linha do mapa consiste de x’s colocados nas intersecções das colunas correspondentes aos minterms cobertos pelo iésimo implicante primo. O mapa de implicantes primos correspondente à função vista anteriormente, está mostrado abaixo:

mintermsimplicantes 0 1 2 5 7 8 9 10 13 15

CB ⋅ × × × ×

DB ⋅ × x × × DC × × × ×

BD × x × x O problema agora consiste em selecionar um conjunto mínimo de implicantes primos tal que, cada coluna contenha pelo menos um x nas linhas correspondentes ao conjunto selecionado e que, o número total de literais (variáveis) nos implicantes primos seja o menor possível. Estes requisitos garantem que a união dos implicantes primos selecionados é equivalente à função f, e que nenhuma outra expressão contendo um número menor de literais, equivalente a f, possa ser encontrada. Linha essenciais Se uma coluna do mapa de implicantes contiver somente um ”x”, o implicante primo correspondente à linha em que este x aparece é essencial e, conseqüentemente, deve ser incluído em qualquer expressão mínima de f. no exemplo acima, os implicantes primos DB ⋅ e BD são essenciais. Este x é identificado no mapa, assim como o implicante primo correspondente ao mesmo. A linha correspondente a um implicante primo essencial é denominada linha essencial. Uma vez determinados os implicantes primos essenciais, todos os minterms cobertos pelos mesmos são marcados. No exemplo acima, o implicante primo essencial DB ⋅ cobre, além dos minterms 2 e 10, também os minterms 0 e 8. assim, os minterms 0, 2, 8 e 10 são marcados. Se, após todos os implicantes primos, bem como os minterms terem sido marcados, a função inteira estiver coberta, isto é, todos os minterms foram marcados, então a união dos implicantes primos essenciais corresponde à expressão mínima da função. Caso contrário, implicantes primos adicionais serão necessários.



Os dois implicantes primos essenciais DB ⋅ e BD do exemplo acima, cobrem todos os minterms da função, com exceção dos minterms 1 e 9. Para encontrar quais são os implicantes primos não essenciais necessários para cobrir o restante dos minterms, construímos um mapa de implicantes primos reduzido,contendo somente os implicantes primos não essenciais e os minterms que não foram cobertos pelos implicantes primos essenciais, conforme mostrado abaixo.

implicantes 1 9 CB ⋅ × ×

DC × × Através do mapa novo mapa de implicantes primos, observa-se que os minterms 1 e 9 são cobertos tanto pelo implicante primo CB ⋅ como pelo implicante primo DC . Como ambos os implicantes possuem o mesmo número de variáveis, existem duas expressões mínimas para a função, que são: CBBDDBDCBAf ⋅++⋅=),,,( e DCBDDBDCBAf ++⋅=),,,( Exemplos: Minimizar as funções abaixo, através do método de Quine McCluskey: a) f(A,B,C,D) = Σ(0,2,3,4,5,7,8,9,13,15) Determinação dos implicantes primos (tabulação):

0: 0000 2: 0010 4: 0100 8: 1000 3: 0011 5: 0101 9: 1001 7: 0111

13: 1101 15: 1111



Obs.: Todas as combinações que não estão assinaladas são implicantes primos. Mapa dos implicantes primos:

implicante 0 2 3 4 5 7 8 9 13 15 →

Como pode-se observar no mapa, BD é um implicante primo essencial e cobre os minterms 5, 7, 13 e 15.

Mapa dos implicantes primos reduzido:

implicante

Como o nosso objetivo é encontrar uma expressão mínima qualquer para a função, é possível simplificar o mapa de implicantes primos, considerando que: O implicante primo CBA é coberto por DCA ⋅⋅ O implicante primo CDA é coberto por CBA ⋅ O implicante primo DCA é coberto por CBA ⋅ Portanto, estes implicantes primos podem ser extraídos do mapa, o que resulta em:

implicante



E a expressão mínima da função é: =),,,( DCBAf b) f(A,B,C,D) = Σ(0,2,3,4,5,7,8,10,11,13,15) Determinação dos implicantes primos:

Mapa dos implicantes primos:

implicante

Mapa de implicantes primos reduzido:

implicante

Uma expressão mínima da função é: =),,,( DCBAf



c) f(A,B,C,D,E) = Σ(1,3,4,5,6,7,10,11,12,13,14,15,18,19,20,21,22,23,25,26,27) Tabulação dos implicantes primos:



Mapa de implicantes primos:

→: Implicantes primos essenciais Mapa de implicantes primos reduzido

Este mapa contém somente os implicantes primos que não são essenciais, bem como os minterms que não são cobertos pelos implicantes primos essenciais.

Como estamos interessados em obter uma expressão mínima qualquer, podemos reduzir ainda mais o mapa, eliminando os implicantes primos que cobrem minterms que são cobertos por outros implicantes primos. DEA é coberto por DEC ; DEB é coberto por DEC ; BDA é coberto por DCB ; DBA é coberto por DCA .



Eliminando estes implicantes primos, temos o mapa final, mostrado abaixo:

A expressão mínima da função é:

=),,,,( EDCBAf



Aplicação do método de Quine-McCluskey para funções não especificadas completamente: Na minimização de funções não especificadas completamente (funções que envolvem condições irrelevantes), o procedimento de tabulação para determinar os implicantes da função segue os mesmos procedimentos já vistos para as funções contendo somente minterms. Exemplo: Minimizar a função f(A,B,C,D) = Σ(0,2,5,6,8) + d(10,11,12,13,14,15) Determinação dos implicantes primos: Na etapa de tabulação e combinação, tanto os minterms e as condições irrelevantes são tratados da mesma maneira, ou seja, tratamos todas as condições irrelevantes como se fossem minterms.

0: 0000 √ (0,2): 00-0 √ (0,2,8,10): -0-0 2: 0010 √ (0,8): -000 √ (2,6,10,14): --10 8: 1000 √ (2,6): 0-10 √ (8,10,12,14): 1--0 5: 0101 √ (2,10): -010 √ (10,11,14,15): 1-1- 6: 0110 √ (8,10): 10-0 √ (12,13,14,15): 11--

10: 1010 √ (8,12): 1-00 √ 12: 1100 √ (5,13): -101 11: 1011 √ (6,14): -110 √ 13: 1101 √ (10,11): 101- √ 14: 1110 √ (10,14): 1-10 √ 15: 1111 √ (12,13): 110- √

(12,14): 11-0 √ (11,15): 1-11 √ (13,15): 11-1 √ (14,15): 111- √

Mapa de implicantes primos: Na construção do mapa de implicantes primos, são considerados somente os minterms da função. As condições irrelevantes são ignoradas. Os implicantes primos que envolvem somente condições irrelevantes são desconsiderados.

0 2 5 6 8 → DCB x → DB x × × → DC × x DA ×

Como os implicantes primos AC e AB cobrem somente condições irrelevantes, eles não são necessários, podendo ser eliminados. No mapa de implicantes primos podemos observar que os



implicantes primos essenciais cobrem todos os minterms da função, sendo a expressão mínima portanto, composta somente pelos implicantes primos essenciais. DCDBDCBEDCBAf ++=),,,,( Exercício: Minimizar a função abaixo f(A,B,C,D) = Σ(1,2,3,5,6,8) + d(10,11,12,13,14,15) Determinação dos implicantes primos:

Mapa de implicantes primos: Como os implicantes primos AC e AB cobrem somente condições irrelevantes, podem ser eliminados.

Mapa de implicantes primos reduzido



Para cobrir os minterms 1, 3 e 5 são necessários os implicantes primos DCB e CB . A expressão mínima da função é portanto: =),,,,( EDCBAf Algorítmo de Petrick Nos exemplos vistos até agora, o objetivo foi o de encontrar uma expressão mínima qualquer para a função. É possível no entanto, que seja de interesse a obtenção de todas as possíveis expressões mínimas da função. Neste caso o algoritmo de Petrick é uma ferramenta que nos permite determinar todas estas expressões mínimas, através de um processo sistemático. Seja por exemplo, a função vista anteriormente: f(A,B,C,D) = Σ(0,2,3,4,5,7,8,10,11,13,15) Como já foi visto, o mapa de implicantes primos para esta função é:

implicante 0 2 3 4 5 7 8 10 11 13 15 DCA ⋅⋅ × × CBA × × → DB ⋅ × × x × CB × × × × CD × × × × → BD × × x ×

DB ⋅ e BD são implicantes primos essenciais.

Eliminando os implicantes primos essenciais, temos o seguinte mapa de implicantes primos reduzido:

implicante 3 4 11a DCA ⋅⋅ × b CBA × b CB × × d CD × ×



Para efeitos de simplificar a representação, identificamos os implicantes primos por a, b, c e d, conforme pode ser observado no mapa de implicantes acima. Para se obter os implicantes primos restantes que formam a expressão mínima da função, é necessário que os minterms 3, 4 e 11 sejam todos cobertos por alguma combinação destes implicantes primos. Assim temos a seguintes situação:

• O minterm 3 é coberto pelo implicante primo c ou pelo implicante primo d. Representamos esta situação por: c + d.

• O minterm 4 é coberto pelo implicante primo a ou pelo implicante primo b. Portanto, representamos por: a + b.

• O minterm 11 é coberto pelo implicante primo c ou pelo implicante primo d, ou seja: c + d. •

Considerando que todos os minterms devem ser cobertos, é necessário efetuar uma operação lógica E entre todas estas condições. Denominando P a união de todos os implicantes primos que cobrem estes minterms, temos: P = (c + d)(a+ b)(c + d)

= (a+ b)(c + d) Distribuindo os produtos, temos: P = ac + ad + bc + bd Cada um dos produtos da soma de produtos acima, representa uma combinação de implicantes primos necessária para cobrir todos os minterms. Como todos os implicantes primos (a, b, c, d) contém o mesmo número de variáveis, todas estas combinações são equivalentes. Assim, o conjunto de todas as expressões mínimas para a função é:

CDCBADBBD

BACBADBBD

CDDCADBBD

CBDCADBBDDCBAf

++⋅+=

++⋅+=

+⋅⋅+⋅+=

+⋅⋅+⋅+=

),,,(



Exercício: Determinar todas as expressões mínimas possíveis para a função f(A,B,C,D) = Σ(0,1,2,3,5,7,8,9,10,12,13,14,15) Seguindo as etapas vistas anteriormente, chegamos ao seguinte mapa de implicantes primos:

implicante 0 1 2 3 5 7 8 9 10 12 13 14 15 a BA ⋅ × × × × b AB × × × × c CA × × × × d DA × × × × e BD × × × × f DA × × × × g CB ⋅ × × × × h DB ⋅ × × × × i DC × × × ×

Como pode-se observar no mapa acima, não existe nenhum implicante primo essencial na função. È necessário portanto, selecionar quais implicantes primos acima são necessários para formar a expressão mínima da função. O conjunto de implicantes primos para cobrir todos os minterms é: P = (a+g+h)(a++f+g+i)(a+h)(a+f)(e+f+i)(e+f)(c+d+g+h)(c+g+i) (d+h)(b+c+d)(b+c+e+i)(b+d)(b+e) Simplificando temos: P = (a+h)(a+f)(e+f)(c+g+i)(d+h)(b+d)(b+e) Distribuindo os produtos temos: P = (a+fh)(e+bf)(c+g+i)(d+bh) = acde + abceh +adeg +abegh +adei + abehi +abcdf + abcfh + abdfg +abfgh +abdfi +abfhi + cdefh + bcefh + defgh + befgh + defhi + befhi + bcdfh + bcfh + bdfgh + bfgh + bfhi Considerando que todos os implicantes primos possuem o mesmo número de variáveis, devemos selecionar as combinações que envolvam o menor número de implicante primos.



Portanto, as expressões mínimas para a função são: acde = BDDACABA +++⋅ adeg = CBBDDABA ⋅+++⋅ adei = DCBDDABA +++⋅ bcfh = CADBDAAB +⋅++ bfgh = CBDBDAAB ⋅+⋅++ bfhi = DCDBDAAB +⋅++ Exercícios: a) Minimizar a função: f(A,B,C,D) = Σ(1,3,6,7,8) + d(10,11,12,13,14,15) b) Obter todas as expressões mínimas da função, através do Algorítmo de Petrick: f(A,B,C,D) = Σ(4,5,6,7,12,14,18,20,21,22,26,29,31)

Documents

FUNÇÕES LÓGICAS Formas de representação de uma função …cricte2004.eletrica.ufpr.br/pastro/P%E1gina_Pastro/Notas_de_Aula... · ELETRÔNICA DIGITAl I 4 Ademar Luiz Pastro UFPR-Departamento