ÁLGEBRA DE VARIÁVEIS LÓGICAS Variáveis e funções x …E1gina_Pastro/Notas_de... · ... de uma tabela na qual colocamos todos os possíveis valores para a variável x e os

ELETRÔNICA DIGITAl I 26

Ademar Luiz Pastro UFPR-Departamento de Engenharia Elétrica

ÁLGEBRA DE VARIÁVEIS LÓGICAS Variáveis e funções Estamos normalmente familiarizados com o conceito de variável e de função, sob o ponto de vista da matemática tradicional. Dentro deste conceito, o campo de existência de uma variável, isto é, o intervalo de variação dos valores que podem ser assumidos por uma variável x qualquer, pode ser especificado de diversas maneiras, dependendo do contexto em que a função está definida. Por exemplo:

• x é um número real, com -∞ < x < +∞ • x é um número real, com -1 ≤ x ≤ 1 • x é um inteiro, com –20 < x < 50 • x é um inteiro com 0 ≤ x ≤ 5

Uma função pode ser definida como uma regra, de acordo com a qual podemos determinar o valor de uma variável chamada variável dependente, a partir de uma ou mais variáveis chamadas variáveis independentes. Denominando y a variável dependente e x a variável independente, a relação de dependência entre as variáveis pode ser escrita como:

y = f(x). Supondo que desejamos determinar o valor da variável y a partir da variável x, de acordo com a seguinte regra:

“a variável x deve ser multiplicada por ela mesma, este produto deve ser multiplicado por 2 e o resultado destas duas operações deve ser somado à constante -3.”

A relação entre as variáveis y e x pode ser representada através da equação: y = 2x2 - 3 No exemplo acima, considerando que o domínio da variável x seja -∞ < x < +∞, determinamos o valor de y através da aplicação de operações algébricas de exponenciação, multiplicação e soma. No entanto, se considerarmos que o número de valores possíveis para a variável x seja pequeno, podemos especificar uma função através da elaboração de uma tabela na qual colocamos todos os possíveis valores para a variável x e os respectivos valores para a variável y. Supondo que na função vista acima (y = 2x2 - 3), o domínio da variável x seja -2 ≤ x ≤ 5, com x inteiro. Nesta situação, considerando que existem apenas oito valores possíveis para as variáveis x e y, é possível representar o relacionamento entre as variáveis através de uma tabela, como está mostrado abaixo:



x y = f(x) -2 5 -1 -1 0 -3 1 -1 2 5 3 15 4 29 5 47

Considerando o que foi visto acima, onde podemos representar uma função através de uma tabela, não é necessário que as variáveis envolvidas sejam numéricas, uma vez que não precisamos efetuar nenhuma operação algébrica sobre as mesmas. Esta constatação nos sugere que podemos definir uma função na qual as variáveis envolvidas não sejam numéricas. Tomemos por exemplo, uma variável independente x que pode assumir como valores, as cores de um sinal de trânsito em um cruzamento de ruas, e uma outra variável dependente y que representa a possível atitude de um motorista ao se aproximar do cruzamento (supondo que seja um motorista consciente que obedeça as leis de trânsito). O relacionamento entre as variáveis x e y está mostrado na tabela abaixo:

x y = f(x) Verde Prosseguir

Amarelo Atenção Vermelho Parar

Como podemos observar, os valores assumidos pela variável x são expressos através de condições como “o sinal está verde” ou “o sinal está amarelo” ou “o sinal está vermelho”. Da mesma forma, os valores assumidos pela variável y também representam condições, como “o motorista deve prosseguir” ou “o motorista deve prestar atenção” ou “o motorista deve parar”. Conceito de Variável Lógica Uma variável lógica é aquela que possui as seguintes características:

• Uma variável lógica pode assumir somente dois valores possíveis; • Os valores possíveis de serem assumidos pela variável, representam

condições e não valores numéricos; • Os dois valores possíveis de serem assumidos pela variável são

mutuamente exclusivos. Para efeito de análise, vamos supor que o sinal de trânsito possui somente as luzes verde e vermelha. Excluímos a possibilidade da luz estar amarela, assim como a possibilidade de ambas as luzes estarem apagadas no intervalo da mudança de uma para outra.



Neste caso, a variável x que representa o estado do sinal assume as características de uma variável lógica, visto que:

a) Temos somente dois valores possíveis: “o sinal está verde” ou “o sinal está vermelho”;

b) Os valores representam condições; c) Os valores são mutuamente exclusivos, pois se o sinal está verde não pode estar

vermelho e vice versa. Podemos representar o estado do sinal através das expressões: x = verde, significando que “o sinal está verde”, ou x = vermelho, significando que “o sinal está vermelho”. Considerando a condição de mútua exclusividade, podemos escrever: x = vermelho = não verde = verde x = verde = não vermelho = vermelho O “não” ou a barra sobre a variável, representa uma negação. A função que relaciona a atitude do motorista com a situação do sinal de trânsito neste caso, é uma função lógica, pois é uma regra que estabelece o relacionamento entre variáveis lógicas.

x y = f(x) Verde Prosseguir

Vermelho Parar VALORES PARA UMA VARIÁVEL LÓGICA Na álgebra tradicional, as variáveis de uma equação algébrica podem representar uma grandeza física qualquer. Ou seja, as variáveis podem representar valores de temperatura, pressão, distância, velocidade, tempo, corrente, tensão, potência, campo elétrico, etc. Do ponto de vista exclusivamente matemático, o que interessa é o relacionamento entre as variáveis e não o que elas representam. Assim, na equação y = 2x2 - 3, para x = 3, calculamos o valor de y = 15, independentemente do que x e y representam. Da mesma maneira, podemos associar dois nomes quaisquer aos dois valores possíveis de serem assumidos por uma variável lógica, não importando o que esta variável representa. Quaisquer nomes podem ser utilizados, porém é interessante que usemos nomes que ressaltem a condição de mútua exclusividade.



Assim, podemos usar nomes, tais como: • Frio e Quente • Entrada e Saída • Alto e Baixo • Ligado e Desligado • Verdadeiro e Falso • Verde e Vermelho • Aberto e Fechado

Num primeiro momento iremos utilizar a notação Verdadeiro (V) e Falso (F) para representar os dois valores possíveis. Além disso, ao invés de representar as variáveis lógicas pelas letras x, y, z, w, ..., será utilizada a nomenclatura A, B, C, D, ..., com objetivo de não causar nenhuma confusão com as equações algébricas tradicionais. Assim sendo, uma função lógica será representada por: Z = f(A, B, C, .....) Voltando ao exemplo do nosso sinal de trânsito, podemos estabelecer o seguinte critério: A ⇒ variável independente, que representa o estado do sinal de trânsito; Z ⇒ variável dependente, que representa a atitude do motorista. Com a seguinte nomenclatura: A = F, o sinal está vermelho; A = V, o sinal está verde; Z = F, o motorista deve parar; Z = V, o motorista deve prosseguir. Com estes critérios definidos, o relacionamento entre as variáveis lógicas Z e A pode ser representado pela tabela abaixo:

A Z = f(A)F F V V

Esta tabela, na qual são representadas todas as combinações possíveis para as variáveis lógicas, é denominada tabela verdade.



FUNÇÕES LÓGICAS DE UMA VARIÁVEL Considerando que existem somente dois valores possíveis para uma variável lógica, existem quatro resultados possíveis para uma função lógica de uma variável, o que nos dá um número de quatro possíveis funções.

A Z = f(A) F V

Quatro combinações possíveis

As quatros funções possíveis são:

A Z = f(A) F F V F

Representação: Z = f(A) = F

A Z = f(A) F V V V

Representação: Z = f(A) = V

A Z = f(A) F F V V

Representação: Z = f(A) = A

A Z = f(A) F V V F

Representação: Z = f(A) = NÃO A = A’ = A

A função Z = A é denominada: Negação ou

Inversão ou Complementação



FUNÇÕES LÓGICAS DE DUAS VARIÁVEIS Funções Básicas: E, OU e NÃO Consideremos uma função com duas variáveis lógicas independentes A e B, Z = f(A,B). Como existem quatro combinações possíveis para as variáveis lógicas A e B, significa que a tabela verdade para esta função possui 4 linhas, como pode ser observado a seguir.

A B Z = f(A,B) F F F V V F V V

Existem 16 possíveis combinações para a variável dependente Z e consequentemente, 16 possíveis funções para estas duas variáveis. Algumas destas 16 possíveis funções têm interesse especial, conforme será mostrado a seguir. Função E (AND) A função Z = f(A,B) definida pela tabela verdade mostrada abaixo é denominada operação (ou função) E (em inglês AND):

A B Z = f(A,B) F F F F V F V F F V V V

Nesta função, a variável dependente Z é igual a V somente quando A e B forem iguais a V, daí o nome, operação E. A operação E é representada por: Z = A E B, ou Z = A AND B, ou Z = A⋅B, ou simplesmente Z = AB As formas de representação da operação E mostradas acima, sugerem que a variável Z é obtida através da “multiplicação” das variáveis A e B, embora A e B não sejam variáveis numéricas. Devido à esta analogia, a operação E é normalmente chamada de multiplicação lógica.



Propriedades da operação E:

a operação E possui as mesmas propriedades da multiplicação algébrica, que são as propriedades comutativa e associativa.

Propriedade comutativa: Z = AB = BA Propriedade associativa: Z = (AB)C = A(BC) Exercício:

Provar, utilizando a tabela verdade, a validade da propriedade associativa da operação lógica E.

A B C (AB) (AB)C (BC) A(BC) F F F F F F F F F V F F F F F V F F F F F F V V F F V F V F F F F F F V F V F F F F V V F V F F F V V V V V V V

Na tabela verdade acima, podemos verificar que as colunas correspondentes às operações (AB)C e A(BC) são idênticas, o que prova a validade da propriedade associativa da operação E. Função OU (OR) A função definida pela tabela verdade mostrada abaixo é denominada operação lógica OU (em inglês, OR).

A B Z = f(A,B) F F F F V V V F V V V V

Na função OU, a variável dependente Z é igual a V sempre que as variáveis A ou B (ou ambas) forem iguais a V.



A operação OU é representada por: Z = A OU B, ou Z = A OR B, ou Z = A + B O sinal “+” sugere que a variável Z é obtida pela “soma” algébrica das variáveis A e B. Por esta razão, a operação lógica OU é também conhecida como “Soma lógica”. Propriedades: Da mesma forma que a operação lógica E, a operação OU possui as

propriedades comutativa e associativa. Comutativa: Z = A + B = B + A Associativa: Z = (A + B) + C = A + (B + C) Propriedade Distributiva:

As operações lógicas E e OU em conjunto, possuem também a propriedade distributiva:

Z = A(B + C) = AB + AC As operações lógicas E, OU e NÃO (AND, OR e NOT) são chamadas funções básicas ou funções fundamentais, pois a partir de uma combinação destas três funções, é possível representar qualquer outra função lógica, independente da complexidade.



REPRESENTAÇÃO ATRAVÉS DA NOTAÇÃO 0-1 Até aqui propositalmente foi utilizada a notação Verdadeiro(V) e Falso(F) para representar os dois possíveis valores para uma variável lógica. A escolha desta notação foi intencional, com objetivo de caracterizar o fato de não estarmos tratando com valores numéricos e sim com valores lógicos, que representam condições. A partir deste ponto passaremos a utilizar a notação 0 - 1 para representar os dois valores possíveis para as variáveis lógicas. Devemos estar cientes no entanto que, embora os valores sejam representados pelos dígitos 0 e 1, estamos tratando de condições e não de valores numéricos. Podemos estabelecer a seguinte correspondência entre os valores: F = 0 V = 1 Com esta notação, as tabelas verdades correspondentes às funções lógicas E e OU ficam assim representadas:

A B Z = AB 0 0 0 0 1 0 1 0 0 1 1 1

A B Z = A + B 0 0 0 0 1 1 1 0 1 1 1 1

Considerando a analogia com as operações algébricas de multiplicação e soma, temos as seguintes situações: 0.0 = 0 0 + 0 =0 0.1 = 0 0 + 1 =1 1.0 = 0 1 + 0 =1 1.1 = 1 1 + 1 =1 A expressão “1 + 1 = 1” é importante no sentido de lembrar que não estamos tratando com valores numéricos e sim com condições.



Outras funções de duas variáveis Como já foi visto, para duas variáveis lógicas existem 16 funções distintas, dentre as quais estão as funções básicas E e OU já analisadas. Na tabela abaixo, estão representadas todas as 16 possíveis funções. Observe que todas as funções estão representadas através de uma combinação das funções básicas E, OU e NÃO.

A B

0 0 1 1 0 1 0 1

Função

f0 0 0 0 0 f = 0

f1 0 0 0 1 ABf =

f2 0 0 1 0 BAf = f3 0 0 1 1 Af =

f4 0 1 0 0 BAf = f5 0 1 0 1 Bf =

f6 0 1 1 0 BABAf += f7 0 1 1 1 BAf +=

f8 1 0 0 0 BAf += f9 1 0 0 1 ABBAf +⋅= f10 1 0 1 0 Bf = f11 1 0 1 1 BAf += f12 1 1 0 0 Af = f13 1 1 0 1 BAf += f14 1 1 1 0 ABf = f15 1 1 1 1 f = 1

Além das funções E e OU já estudadas, existem outras funções neste conjunto, que têm interesse especial, conforme será visto a seguir. Função Ou-Exclusivo A função BABAf +=6 , cuja tabela verdade está mostrada abaixo, é denominada OU-Exclusivo (em inglês, Exclusive-OR), também conhecida como XOR..

A B Z = f(AB) 0 0 0 0 1 1 1 0 1 1 1 0



Observe que o resultado da função é “0” quando as duas variáveis forem iguais e “1” quando as duas variáveis forem diferentes. A função Ou-Exclusivo é representada pelo símbolo ⊕, assim: BABABAZ +=⊕= Função Equivalência A função ABBAf +⋅=9 , cuja tabela verdade está mostrada abaixo, é a negação da função OU-Exclusivo, sendo denominada função Equivalência.

A B Z = f(AB) 0 0 1 0 1 0 1 0 0 1 1 1

O resultado da função é “1” quando as duas variáveis forem iguais e “0” quando as duas variáveis forem diferentes. A função Equivalência é representada pela negação da expressão Ou-exclusivo. ABBABAZ +=⊕= Função NAND A função ABf =14 cuja tabela é mostrada a seguir, é a negação da função E, sendo denominada função NÃO E (em inglês, NOT AND), abreviada como NAND.

A B Z = f(AB) 0 0 1 0 1 1 1 0 1 1 1 0

De acordo com o teorema de DeMorgan: BAABZ +== Função NOR A função BAf +=8 , mostrada na tabela abaixo, é a negação da função OU, chamada NÃO OU (em inglês, NOT OR), abreviada como NOR.



A B Z = f(AB) 0 0 1 0 1 0 1 0 0 1 1 0

Pelo teorema de DeMorgan: BABAf ⋅=+= Suficiência das funções NAND e NOR De acordo com o que foi visto, as funções E, OU e NÃO, são suficientes para representar qualquer função lógica. Considerando que, xx = , podemos representar as funções E e OU da seguinte forma: BAABAB +== BABABA ⋅=+=+ Ou seja, a função E pode ser representada a partir das funções OU e NÃO, do mesmo modo que a função OU pode ser expressa a partir de funções NÃO e E. Assim, qualquer uma das combinações acima, NÃO/E ou NÃO/OU, são suficientes para representar qualquer função lógica. Continuando o raciocínio, sabemos que x + x = x e que x⋅x = x, assim: AAA ⋅= AAA += Portanto, a função NÃO pode ser realizada a partir da função NAND ou da função NOR. Para isto, basta que as duas entradas sejam iguais. Finalmente, consideremos as funções OU e E: BBAABABABA ⋅=⋅=+=+ BBAABABABA +++=+=⋅=⋅ Como observamos, repetidas aplicações da função NAND realizam uma função OU, assim como repetidas aplicações da função NOR realizam uma função E.



Concluindo o raciocínio vimos que, a partir da combinação das funções NÃO e OU é possível representar qualquer função lógica e que, a partir função NAND podemos realizar as funções NÃO e OU. Concluímos portanto que, somente a função NAND é suficiente para representar qualquer função lógica. Da mesma forma, vimos que a partir da combinação das funções NÃO e E podemos representar qualquer função lógica e que, a partir função NOR podemos realizar as funções NÃO e E. Assim, podemos concluir que a função NOR também é suficiente para representar qualquer função lógica. A suficiência das funções NAND e NOR é importante na fabricação de circuitos integrados, tendo em vista que é possível elaborar o projeto de um circuito utilizando um array de circuitos idênticos (NAND ou NOR). PORTAS LÓGICAS Uma “porta lógica” é um dispositivo físico que realiza uma operação lógica. Considerando as três operações lógicas fundamentais E, OU e NÃO, existe uma porta lógica que realiza fisicamente cada uma destas operações. Assim:

Porta lógica NÃO: é um dispositivo que realiza uma operação lógica NÃO; Porta lógica OU: é um dispositivo que realiza uma operação lógica OU; Porta lógica E: é um dispositivo que realiza uma operação lógica E.

A forma como cada uma das portas é implementada, depende da tecnologia utilizada na sua fabricação. Na figura abaixo está mostrado o circuito correspondente à uma porta inversora CMOS:

Porta inversora CMOS

Quando uma tensão alta (+VDD) é aplicada na entrada, o transistor canal p está cortado e o transistor canal n está conduzindo. Nesta situação, a saída está ligada à terra através do transistor canal n. A tensão de saída neste caso é 0V.

+VDD

p

n

Entrada Saída



Quando é aplicada uma tensão baixa (0V) na entrada, o transistor canal p está conduzindo e o transistor canal n está cortado ficando a saída ligada à alimentação através do transistor canal p . A tensão de saída nesta situação é +VDD. Na tabela verdade abaixo, estão representadas estas duas condições:

Entrada Saída 0 +VDD

+VDD 0 Esta tabela verdade corresponde à uma operação NÃO, onde o valor de tensão 0V corresponde ao valor lógico 0 e o valor de tensão +VDD corresponde ao valor lógico 1. Consequentemente, o circuito mostrado acima realiza uma operação lógica NÃO, caracterizando portanto uma porta lógica NÃO. Simbologia para as portas lógicas E, OU e NÃO Na eletrônica digital cada porta lógica possui uma simbologia, utilizada para desenhar os circuitos, que pode ser a simbologia padrão ANSI/IEEE ou a simbologia usual utilizada no mercado. Porta lógica NÃO: Simbologia: Padrão usual Padrão ANSI/IEEE

p

n

0Vp

n

0V +VDD

+VDD +VDD

+VDD



Na porta NÃO, também chamada porta inversora, o sinal de saída representa a negação (ou inversão ou complementação) do sinal de entrada, conforme podemos observar no diagrama de tempo abaixo, que mostra os sinais de entrada e saída de uma porta lógica NÃO.

Diagrama de tempo:

Porta lógica E: Simbologia:

Padrão usual Padrão ANSI/IEEE

Diagrama de tempo:

1

A

B AB

A

B

AB

A

A

A A

&



Porta lógica OU: Simbologia: Padrão usual Padrão ANSI/IEEE

Diagrama de tempo:

Porta Ou-Exclusivo

Simbologia: Padrão usual Padrão ANSI/IEEE

Diagrama de tempo:

=1

A B

A+B

A

B

AB

≥1

A

B

A

B

AB



Porta NAND O circuito CMOS que implementa a porta lógica NAND está mostrado na figura abaixo:

Quando A = 0V e B = 0V, os transistores p1 e p2 estão conduzindo, n1 e n2 estão cortados. A saída está ligada à alimentação através de p1 e p2 , sendo portanto +VDD. Quando A = 0V e B = +VDD, o transistor p1 está conduzindo e p2 está cortado. n1 está cortado e n2 conduzindo. A saída está ligada à alimentação através de p1, sendo portanto +VDD. Quando A = +VDD e B = 0V, o transistor p1 está cortado e p2 está conduzido. n1 está conduzindo e n2 cortado. A saída está ligada à alimentação através de p2, sendo portanto +VDD. Quando A = +VDD e B = +VDD, os transistores p1 e p2 estão cortados. n1 e n2 estão conduzindo. A saída está ligada à terra através de n1 e n2, sendo portanto 0V.

Simbologia para a porta lógica NAND: Padrão usual Padrão ANSI/IEEE

Diagrama de tempo:

A

B

A

B

AB

AB

&

p1 p2

n1

n2

A

B

Z

+VDD



Porta NOR O circuito CMOS que implementa a porta lógica NOR está mostrado na figura abaixo:

Quando A = 0V e B = 0V, os transistores p1 e p2 estão conduzindo, n1 e n2 estão cortados. A saída está ligada à alimentação através de p1 e p2 , sendo portanto +VDD. Quando A = 0V e B = +VDD, o transistor p1 está conduzindo e p2 está cortado. n1 está cortado e n2 conduzindo. A saída está ligada à terra através de n2, sendo portanto 0V. Quando A = +VDD e B = 0V, o transistor p1 está cortado e p2 está conduzido. n1 está conduzindo e n2 cortado. A saída está ligada à terra através de n2, sendo portanto 0V. Quando A = +VDD e B = +VDD, os transistores p1 e p2 estão cortados. n1 e n2 estão conduzindo. A saída está ligada à terra através de n1 e n2, sendo portanto 0V.

Simbologia para a porta lógica NOR: Padrão usual Padrão ANSI/IEEE

Diagrama de tempo:

A

B

A

B

AB

A+B

p1

p2

n2 n1

A

B Z

+VDD

≥1



EXPRESSÕES LÓGICAS E CIRCUITOS LÓGICOS A partir de uma expressão lógica qualquer, é possível representar, utilizando a simbologia específica para as portas lógicas, o circuito que realiza esta expressão. Da mesma forma, a partir do desenho de um circuito lógico, é possível determinar qual é a expressão lógica realizada pelo circuito. Exemplos:

a) Determinar qual a expressão lógica realizada pelos circuitos abaixo:

A

B

C

f(A,B,C)

A expressão lógica é: =)C,B,A(f

A

B

C f(A,B,C)

Expressão lógica: =)C,B,A(f

Uma representação alternativa para o circuito acima é:

A

B

Cf(A,B,C)

Expressão lógica: =)C,B,A(f

A pequena “bolha” colocada na entrada ou na saída de uma porta lógica, indica uma operação lógica NÃO na entrada ou na saída.



b) Representar o circuito lógico que realiza a expressão BACBACBAf ++= )(),,(

Exercícios:

a) Determinar a função lógica realizada em cada um dos circuitos mostrados abaixo.

A

B

C

D =)D,C,B,A(f

A

B

C

D

=)D,C,B,A(f



b) Desenhar o circuito que realiza cada uma das funções abaixo:

b.1) )(),,,( DCBADCBAf ++=

b.2) )()()(),,,( DCADCBADCABDCBADCBAf ++++⋅++++=



DIAGRAMAS DE VENN O estudo da álgebra lógica pode ser feito utilizando conceitos da teoria dos conjuntos. Neste aspecto os Diagramas de Venn representam uma ferramenta muito útil para se entender os princípios da álgebra booleana. Na figura abaixo, temos a representação do diagrama de Venn para uma variável lógica (x). Neste diagrama, o círculo representa o conjunto correspondente à variável x, enquanto o retângulo vazado representa o conjunto correspondente à negação da variável x ou seja x .

x

x No contexto do Diagrama de Venn, o valor “0” representa um conjunto vazio, enquanto o valor “1” representa todo o universo de interesse. O diagrama de Venn para duas variáveis está mostrado na figura abaixo:

A operação lógica “OU” (x+y) corresponde, no diagrama de Venn, à união dos conjuntos x e y, enquanto a operação lógica “E” corresponde à intersecção dos conjuntos, conforme está mostrado na figura abaixo.

x + y ⇒ x ∪ y x.y ⇒ x ∩ y



PRINCÍPIOS DA ÁLGEBRA LÓGICA Neste tópico são apresentados alguns princípios, propriedades, postulados e teoremas envolvendo as operações lógicas E, OU e NÃO, os quais serão aplicados no processo de simplificação das expressões lógicas. Princípio da Dualidade:

O princípio da dualidade diz que, “se uma expressão lógica é válida, a sua expressão dual também é válida”. A expressão dual é obtida trocando operações “E” por “OU”, operações “OU” por “E”, os valores “0” por “1” e “1” por “0”.

Deve-se tomar um certo cuidado ao aplicar o princípio da dualidade, pois o mesmo diz que as duas expressões são “válidas” porém, não diz que as duas expressões são “equivalentes”. Propriedades: Como foi visto anteriormente, as operações lógicas “E” e “OU” possuem as propriedades comutativa, associativa e distributiva. Estas propriedades estão mostradas abaixo, na forma de pares duais: Propriedade comutativa: x + y = y + x ⇒ x.y = y.x Propriedade associativa: x + (y + z) = (x + y) + z ⇒ x.(y.z) = (x.y).z Propriedade distributiva: x.(y + z) = x.y + x.z ⇒ x + y.z = (x + y).(x + z) Postulados: xx =+ 0 1=+ xx Aplicando o princípio da dualidade, temos as respectivas expressões duais dos dois postulados: xx =+ 0 ⇒ xx =⋅1 1=+ xx ⇒ 0=⋅ xx



Teoremas Alguns teoremas estão mostrados abaixo, também na forma de pares duais: a) xx = (involução) b) xxx =+ ⇒ xxx =⋅ (idempotência)

Verificação:

xx

xxx

xxxx

xxxx

=+=

⋅+=

+⋅+=

⋅+=+

0

)()(

1)(

c) x + 1 = 1 ⇒ x.0 = 0

Verificação:

1

1

)1()(

)1(1 1)1(1

=+=

⋅+=

+⋅+=

+⋅=⋅+=+

xx

xx

xxx

xxx

d) x + x.y = x ⇒ x.( x + y) = x (absorção)

Verificação:

xx

yxyx

yxxyxx

=⋅=

+⋅=+⋅=

⋅+⋅=⋅+

1

)1( )1(

1

e) yxyxx +=⋅+ ⇒ yxyxx ⋅=+⋅ )(

Verificação:

)(1 )()(

yxyx

yxxxyxx

+=+⋅=

+⋅+=⋅+



f) xyxyx =⋅+⋅ ⇒ xyxyx =+⋅+ )()(

Verificação:

1 )(

xx

yyxyxyx

=⋅=

+⋅=⋅+⋅

g) zxyxzyzxyx ⋅+⋅=⋅+⋅+⋅ ⇒ )()()()()( zxyxzyzxyx +⋅+=+⋅+⋅+

Verificação:

zxyx

zyzxzyyx

zyxzyxzxyx

zyxxzxyx

zyzxyxzyzxyx

⋅+⋅=

⋅+⋅+⋅+⋅=

⋅⋅+⋅⋅+⋅+⋅=

⋅⋅++⋅+⋅=

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

)()(

)(

1

h) )()( yxzxzxyx +⋅+=⋅+⋅ ⇒ yxzxzxyx ⋅+⋅=+⋅+ )()(

Verificação:

zxyx

zyzxyx

zyzxyx

zyzxyxxxyxzx

⋅+⋅=

⋅+⋅+⋅=

⋅+⋅+⋅+=

⋅+⋅+⋅+⋅=+⋅+

0

)()(

TEOREMAS DE DeMORGAN zyxzyx ⋅⋅=++ ⇒ zyxzyx ++=⋅⋅ Resumo: x + y = y + x ⇒ x.y = y.x x + (y + z) = (x + y) + z ⇒ x.(y.z) = (x.y).z x.(y + z) = x.y + x.z ⇒ x + (y.z) = (x + y).(x + z) xx =+ 0 ⇒ xx =⋅1 11 =+x ⇒ 00 =⋅x xxx =+ ⇒ xxx =⋅ 1=+ xx ⇒ 0=⋅ xx



xxyx =+ ⇒ xyxx =+ )( xyxxy =+ ⇒ xyxyx =++ ))(( yxyxx +=+ ⇒ xyyxx =+ )( ))(( zxyxyzx ++=+ ⇒ xzxyzyx +=+ )( zxxyyzzxxy +=++ ⇒ ))(())()(( zxyxzyzxyx ++=+++ ))(( yxzxzxxy ++=+ ⇒ yxxzzxyx +=++ ))(( zyxzyx ⋅⋅=++ ⇒ zyxzyx ++=⋅⋅ UTILIZAÇÃO DO DIAGRAMA DE VENN Através do Diagrama de Venn, é possível a verificação dos princípios vistos acima. A seguir estão apresentados alguns exemplos. a) Verificar o teorema: yxyxx +=+

x x.y

x + x.y Exercício: Verificar o teorema de DeMorgan. (negação da soma e negação do produto)



b) Verificar o teorema ))(())()(( zxyxzyzxyx ++=+++

x + y y + z x + y

( )( )x + y x + z

x + z x + z

( )( )x + y x + z Exercício: Verificar o teorema zxxyyzzxxy +=++



Exemplos de simplificação de funções: Simplificar as expressões lógicas abaixo:

a) CACBCBACBAf ⋅+⋅+⋅⋅=),,( b) CBCBAACBAf +++= )(),,(

c) ))()((),,( CBCABACBAf +++= c.1) ))((),,( CBCBBACAAACBAf +⋅+⋅+⋅+⋅=

c.2) CBCAABCBAf ⋅+⋅+=),,(



d) DBCDCBABDCBAf ⋅++⋅+=),,,( e) ))()(())((),,,( BABABACABADCBAf ++++++= f) CDBADCBADCBADCBADCABDCBAf ⋅+⋅++⋅⋅+⋅=),,,( f.1) )()(),,,( DDCBADCBABBDCADCBAf +⋅+++⋅= f.2) )()(),,,( DDCBACCDBADCABDCBAf +⋅++⋅+⋅=

A função possui duas expressões mínimas!



Exercícios Simplificar as funções: a) DCBACBABAADCBAf )()(),,,( ++++++= b) ))(()()(),,,( CBDACABCDBCADCBAf ++⋅+++= c) )()()(),,,( DCADCBADCABDCBADCBAf ++++⋅++++= d) )CAB()CACD)(BA()CDB(A)D,C,B,A(f +⋅++++=

e) DCBACDBAABCDDCBA

DCBADCABDCBADCBA)D,C,B,A(f

+++

++++=



FORMAS DE REPRESENTAÇÃO DE UMA FUNÇÃO Uma função lógica qualquer pode ser expressa através de duas formas:

Soma de produtos Produto de somas

Seja por exemplo dada a função: )(),,( CBACBACBAf +⋅⋅⋅= . É possível expressar a mesma como uma soma de produtos:

ACABCBA

CBACBA

CBACBACBAf

++⋅⋅=

⋅+++=

+⋅⋅⋅=

))((

)(),,(

Como observamos, a função f(A,B,C) foi expressa como uma soma de parcelas, onde cada uma das parcelas é um produto de variáveis individuais (literais), negadas ou não. Da mesma forma, esta função pode ser representada como um produto de somas.

))((

)(),,(

CBACBA

CBACBACBAf

⋅+++=

+⋅⋅⋅=

Aplicando o teorema ))(( zxyxyzx ++=+ temos: ))()((),,( CABACBACBAf ++++= Neste caso, a função foi expressa como um produto de termos, onde cada termo é representado por uma soma de variáveis individualizadas, negadas ou não. Assim, a mesma função foi representada como uma soma de produtos e como um produto de somas. Exemplo: Expressar a função abaixo na forma de soma de produtos e produto de somas.

CABDCADCBAf ⋅⋅+⊕⋅=),,,(

a) soma de produtos:

BCBACDADCA

CABCDDCADCBAf

+++⋅⋅=

+++⋅=

)()(),,,(



b) Produto de somas:

[ ] [ ]

))()()((

))()()()()((

))()()((

))()()((

))((

))(( )()(

)()(),,,(

CADCBDCBBA

CADCBDBADCBCBABA

CABCADBDACBA

CABCDADBCDACBA

CABCDADCA

zxyxyzxCACDDCABCDDCA

CABCDDCADCBAf

++++++=

++++++++++=

++++++=

++++++=

+++⋅⋅=

++=+⇒+++⋅⋅++⋅=

+++⋅=

Portanto:

))()()((

),,,(

CADCBDCBBA

BCBACDADCA

CABDCADCBAf

++++++=

+++⋅⋅=

⋅⋅+⊕⋅=

É importante observar que, as duas expressões estão representando a mesma função, de formas diferentes.

Exercício: Representar a função abaixo como uma soma de produtos e como um produto de

somas.:

))(()(),,,( DBCACBADCBAf ++++=



ESTRUTURAS DE DOIS NÍVEIS DE PORTAS Conforme vimos anteriormente, qualquer função pode ser expressa tanto na forma de soma de produtos como na forma de produto de somas. Se representarmos o circuito correspondente a qualquer uma das duas formas, a estrutura de portas correspondentes é denominada “estrutura de dois níveis de portas”. Tomemos como exemplo, a função vista anteriormente:

ACABCBA

CBACBACBAf

++⋅⋅=

+⋅⋅⋅=

)(),,(

O circuito correspondente é:

A

A'

B

B'

C

C'

A

A'B'C'+AB+AC

Estrutura AND-OR

Cada um dos produtos componentes da função é gerado por uma porta E, sendo que as saídas das portas E são concentradas numa porta OU para produzir a saída final do circuito. Observe que não foi considerada a negação das variáveis de entrada como parte da estrutura de dois níveis. Genericamente, se uma função for representada como uma soma de n produtos, a estrutura de portas que realiza esta função é composta de n portas E e uma porta OU. Esta estrutura é denominada estrutura AND-OR. O mesmo raciocínio é válido quando a função é representada na forma de um produto de somas. Neste caso a função pode ser realizada por uma estrutura de dois níveis composta por n portas OU seguidas de uma porta E. Tomando como exemplo a mesma função vista anteriormente:

))()((

))((

)(),,(

CABACBA

CBACBA

CBACBACBAf

++++=

⋅+++=

+⋅⋅⋅=



O circuito que realiza esta função está representado abaixo, numa estrutura de dois níveis, onde podemos observar o conjunto de 3 portas OU seguida de uma porta E. Esta estrutura é denominada estrutura OR-AND.

A'BC

AB'

AC'

(A'+B+C)(A+B')(A+C')

Estrutura OR-AND

As estruturas vistas acima são chamadas estruturas de dois níveis de portas, porque qualquer sinal de entrada deve passar por somente duas portas lógicas para produzir o sinal de saída do circuito.Esta característica é importante, quando consideramos que o tempo de resposta de uma porta não é imediato, ou seja, quando ocorre alteração em um sinal de entrada, o efeito desta mudança não é observado imediatamente na saída do circuito. Na prática, existe um tempo decorrido entre a mudança no sinal de entrada e a respectiva alteração na saída do circuito. Este tempo é denominado “tempo de propagação” ou “tempo de retardo”. Normalmente, na documentação de especificação do fabricante (data sheet) das portas lógicas, estão indicados dois tempos de propagação:

tPHL: tempo necessário para que o sinal de saída de uma porta passe do nível alto para o nível baixo.

tPLH: tempo necessário para que o sinal de saída de uma porta passe

do nível baixo para o nível alto.



Na figura abaixo está mostrado o tempo de propagação para uma porta NÃO.

Tempo de propagação

Nas estruturas de portas aqui mostradas, o tempo decorrido entre uma alteração no sinal de entrada e a respectiva alteração no sinal de saída do circuito, corresponde ao tempo de propagação de duas portas somente, daí o nome “estruturas de dois níveis”. Como vimos, qualquer função pode ser representada como uma soma de produtos ou um produto de somas, podendo assim ser realizada através de uma estrutura de dois níveis do tipo AND-OR ou do tipo OR-AND. Nada impede no entanto, que uma função seja realizada por circuitos que contenham mais de dois níveis de portas Por exemplo, a função )(),,( CBACBACBAf +⋅⋅⋅= vista anteriormente, pode ser realizada de diversas maneiras: a) )(),,( CBACBACBAf ++⋅⋅=

A'B'C'

A

BC

A'B'C'+A(B+C)

Entrada Saída

Entrada

Saída

50%

50%

tPHL tPLH



b) )()(),,( CBACBACBAf +++=

A'

BC

A

A'(B+C)'+A(B+C)

c) ACABCBA)C,B,A(f ++⋅⋅=

A

A'

B

B'

C

C'

A

A'B'C'+AB+AC

Em resumo, dada uma função lógica, a mesma pode ser realizada através de um circuito envolvendo um número qualquer de níveis de portas lógicas. O tempo de propagação total do sinal, depende do número de níveis de portas existentes no circuito. A estrutura de dois níveis é a que proporciona o menor tempo de propagação total para a realização da função.



ESTRUTURAS DE DOIS NÍVEIS UTILIZANDO UM SÓ TIPO DE PORTA Anteriormente vimos que as funções NAND e NOR são auto-suficientes, ou seja, a partir de qualquer uma delas, podemos representar qualquer função lógica. Veremos a seguir, como projetar um circuito utilizando uma estrutura de dois níveis com somente um tipo de porta, que pode ser a porta NAND ou a porta NOR. Tomemos como exemplo, a função vista anteriormente: ACABCBACBAf ++⋅⋅=),,( considerando que, xx = , podemos negar duas vezes a expressão.

Assim, ⋅++⋅⋅= ACABCBACBAf ),,( Aplicando o teorema de DeMorgan:

ACABCBACBAf ⋅⋅⋅⋅=),,( Observamos que, na expressão acima, existem somente operações NAND envolvidas. Assim, a função ACABCBACBAf ++⋅⋅=),,( pode ser realizada pelo circuito mostrado abaixo, onde são utilizadas somente portas NAND, em uma estrutura de dois níveis.

A'B'C'

AB

CA

A'B'C' + AB + AC

Estrutura NAND

É importante observar, que esta estrutura é idêntica à estrutura de dois níveis AND-OR vista anteriormente, onde temos todas as portas E e OU substituídas por portas NAND. Portanto, se desejarmos representar o circuito como uma estrutura de dois níveis utilizando somente portas NAND, temos que adotar o seguinte procedimento a) Representar a função na forma de soma de produtos; b) Negar duas vezes a expressão; c) Aplicar o teorema de Morgan.



Do mesmo modo, podemos observar que uma estrutura do tipo OR-AND pode nos conduzir a um circuito onde sejam utilizadas somente portas NOR. Como exemplo, vejamos a mesma função utilizada anteriormente:

))()((

)(),,(

CABACBA

CBACBACBAf

++++=

+⋅⋅⋅=

Aplicando o mesmo procedimento que vimos para a soma de produtos, temos:

)()()(

))()((),,(

CABACBA

CABACBACBAf

++++++=

++++=

Como podemos observar, na expressão acima, temos somente operações NOR, sendo portanto a função realizada pelo circuito abaixo, onde temos somente portas NOR.

A'BC

AB'

AC'

(A"+B+C)(A+B')(A+C')

Estrutura NOR

Desta forma, se desejarmos representar o circuito como uma estrutura de dois níveis utilizando somente portas NOR, temos que adotar o seguinte procedimento a) Representar a função na forma de produto de somas; b) Negar duas vezes a expressão; c) Aplicar o teorema de Morgan. Exercício: Representar o circuito que realiza a função abaixo, como uma estrutura de dois níveis

de portas, utilizando somente portas NAND. )()()(),,( DCABDCADCABCBAf +++⋅+⋅=

Documents

ÁLGEBRA DE VARIÁVEIS LÓGICAS Variáveis e funções x …E1gina_Pastro/Notas_de... · ... de uma tabela na qual colocamos todos os possíveis valores para a variável x e os