Apostila Logica

Introdução à Lógica Digital

Lógica é a ferramenta pela qual decidimos sobre a validade de uma proposição.

Todo o raciocínio lógico é baseado na tomada de uma decisão a partir da avaliação de determinadas condições ou proposições. Inicialmente tem-se os dados de entrada e uma condição (ou uma combinação de condições ou proposições). Aplica-se a condição aos dados de entrada para decidir quais são os dados de saída.

A lógica digital não é diferente. Mas apresenta uma peculiaridade: trabalha apenas com variáveis cujos valores alternam exclusivamente entre dois estados e não admitem valores intermediários. Estes estados podem ser representados por "um" e "zero", "sim" e "não", "verdadeiro" e "falso" ou quaisquer outras grandezas cujo valor possa assumir apenas um dentre dois estados possíveis. Assim sendo, a lógica digital é a ferramenta ideal para trabalhar com grandezas cujos valores são expressos no sistema binário.

Proposição

Toda proposição é uma frase, mas nem toda frase é uma proposição; uma frase é uma proposição apenas quando admite um dos dois valores lógicos: Falso (F)ou Verdadeiro (V), caso contrário será chamada de Termo ou Nome.

Exemplos:

1. Frases que não são proposições

• Concurso

• Seguro de Carro

• Brasil!

 Fazem referencia a objetos, sem afirmar nada sobre eles, não faz sentido, verificar sua validade.

2. Frases que são proposições

• A lua é o único satélite do planeta terra (V)

• O Concurso daquele Banco é fácil (V)

• A cidade de Salvador é a capital do estado do Amazonas (F)

• O numero 712 é ímpar (F)

• Raiz quadrada de dois é um número irracional (V)

• Ana utiliza o Plano de Saúde (V)

 Estas já fazem referencia aos objetos, afirmando algo sobre eles, faz sentido verificar sua validade, atribuindo-lhe um valor lógico.

Composição de Proposições

É possível construir proposições a partir de proposições já existentes. Este processo é conhecido por Composição de Proposições. Suponha que tenhamos duas proposições:

A = "Um triciclo carrega pessoas"

B = "Um Triciclo é um carro"

Vamos a alguns exemplos:

"Um triciclo não carrega pessoas" Negação de A (não(A))

"Um Triciclo não é um carro" Negação de B (não(B))

"Um triciclo carrega pessoas" e "Um Triciclo é um carro" Junção de A e B (A e B)

"Um triciclo carrega pessoas"" ou "Um Triciclo é um carro" Separação de A e B (A ou B)

"Um triciclo não carrega pessoas" e "Um Triciclo é um carro" Negação de A Junção com B (não (A) e B)

"Um triciclo não carrega pessoas" ou "Um Triciclo é um carro" Negação de A Separação de B (não (A) ou B)

"Um triciclo carrega pessoas" ou "Um Triciclo não é um carro" Negação de B Separação de A (A ou não(B))

"Um triciclo carrega pessoas" e "Um Triciclo não é um carro" Negação de B Junção com A (A e não(B))

Se "Um triciclo carrega pessoas" então "Um Triciclo é um carro" Se A é V então B é V (A  B)

Se "Um triciclo não carrega pessoas" então "Um Triciclo é um carro" Se (não A) é V então B é V (não (A)  B)

"Um triciclo é um ciclomotor" é equivalente a "Um Triciclo não é um carro" C é V se e somente se (não B) for V (C  não(B))

Note que, para compor proposições usou-se a expressão não (negação), e (conjunção), ou (disjunção),  (implicação) e  (equivalência). Estes são os chamados conectivos lógicos (ou Operadores Lógicos). É normal utilizarmos os conectivos padrões na língua inglesa ou seja, NOT (não), AND (e), OR (ou).

Note, também, que usou-se um símbolo para representar uma proposição: C representa a proposição Um triciclo é um ciclomotor. Assim, não(B) representa Um Triciclo não é um carro, uma vez que B representa Um Triciclo é um carro.

As proposições para serem válidas devem satisfazer a alguns princípios básicos...

Algumas Leis Fundamentais

Lei do Terceiro Excluído Uma proposição é falsa (F) ou verdadeira (V): não há meio termo.

Lei da Contradição Uma proposição não pode ser, simultaneamente, V e F.

Lei da Funcionalidade O valor lógico (V ou F) de uma proposição composta é unicamente determinado pelos valores lógicos de suas proposições constituintes.

Exercícios

E Sexo Fem. > 40 Desconto

p q p  q

Marisa V V

Laura F V

Eduardo V F

Osvaldo F F

1) Uma grande seguradora oferece descontos especiais para clientes do sexo feminino com mais de 40 anos de idade. Um corretor dessa seguradora, deu entrada em quatro propostas para 4 clientes: Marisa de 53 anos, Laura de 27, Eduardo de 49 e Osvaldo de 38 anos. Qual desses clientes obteve o desconto oferecido?

Ou > 65 Deficiente Gratuidade

p q p  q

Ari V V

Dulce V F

Ivanilda F V

Paula F F

2) Empresas de transporte coletivo da cidade oferecem passagens gratuitas para os passageiros maiores de 65 anos ou para quem tenha deficiência física de qualquer idade. Em um coletivo, entraram quatro passageiros: Ari, um cego de 68 anos, Dulce uma senhora de 72 anos sem deficiência, Ivanilda, uma jovem de 26 anos que usa muletas para andar e Paula, de 59 anos aparentemente normal. Qual desses passageiros não foi beneficiado pela gratuidade da passagem?

3) Outro dia, Isabela deixou seu currículo numa produtora de Software, para o cargo de programador. O gerente que a atendeu, impressionado com seu currículo, informou-lhe que assim que surgisse uma vaga ela seria contratada. Em quais situações o gerente terá dito a verdade?

 Surgiu uma vaga Isabela foi contratada O gerente mentiu

p q Se p então q

1ª situação V V

2ª situação V F

3ª situação F V

4ª situação F F

4) Dia desses, Jacira prometeu para o marido Hélio: "- Nessas férias, só viajarei para a capital se e somente se você alugar uma casa bem no centro da cidade". Em quais situações Jacira cumpriu a promessa?

 Alugou a casa Jacira viajou Jacira cumpriu a promessa

p q p se e somente se q

1ª situação V V

2ª situação V F

3ª situação F V

4ª situação F F

Devemos observar que:

• A conjunção (E) de duas proposições só é verdadeira, quando as duas proposições formadoras também forem verdadeiras.

• A disjunção (OU) de duas proposições só é verdadeira, quando ao menos uma das duas proposições formadoras for verdadeira.

• A implicação () só é falsa quando a primeira proposição for verdadeira e a segunda for falsa.

• A equivalência () só é falsa quando uma proposição for verdadeira e a outra for falsa.

5) Determine o valor lógico das proposições compostas abaixo, onde: A= 3, B= 5, C= 8, D=7 e X=1

a) S: ~(X > 3) ( ) b) S: (x < 1)  ~(B>D) ( )

c) S: ~(D < 0)  ~(C > 5) ( ) d) S: ~(X > 3)  (C > 7) ( )

e) S: (A > B)  (C > B) ( ) f) S: ( X >= 2 ) ( )

g) S: (X < 1 )  (B >= D) ( ) h) S: ~(D > 0)  (C > 5) ( )

i) S: ~(D > 3)  ~(B < 7) ( ) j) S: (A > B)  ~(C > B) ( )

Em um computador, todas as operações são feitas a partir de tomadas de decisões que, por mais complexas que sejam, nada mais são que combinações das três operações lógicas correspondentes às condições acima descritas: NOT, AND e OR. Para tomadas de decisões mais complexas, tudo o que é preciso é combinar estas operações, gerando as Operações Derivadas.

E para isto é necessário um conjunto de ferramentas capaz de manejar variáveis lógicas. Esse conjunto de ferramentas é a chamada "Álgebra Booleana".

Álgebra Booleana

A Álgebra Booleana recebeu seu nome em homenagem ao matemático inglês George Boole, que a concebeu e publicou suas bases em 1854, em um trabalho intitulado “ Na Investgation of the Laws of Thought on Wich to Found the Mathematics Theorie of Logic and Probabilities” . O trabalho, evidentemente, nada a ver com computadores digitais, já que foi publicado quase um século antes que eles fossem inventados.

Era meramente um tratado sobre lógica, um dos muitos exemplos em que os matemáticos se adiantam ao tempo e criam com décadas de avanço as bases abstratas para uma tecnologia de ponta. foi somente em 1937 que Claude Shannon, um pesquisador do MIT, se deu conta que a lógica booleana era a ferramenta ideal para analisar circuitos elétricos baseados em relês, os antecessores imediatos dos computadores eletrônicos digitais a válvula – que por sua vez originaram os modernos computadores que empregam a eletrônica do estado sólido.

A Álgebra Booleana é semelhante á álgebra convencional que conhecemos no curso secundário, o ramo da matemática que estuda as relações entre grandezas examinando as leis que regulam as operações e processos formais independentemente dos valores das grandezas, representadas por “letras” ou símbolos abstratos. A particularmente da álgebra Booleana é que ela estuda relações entre variáveis lógicas que podem assumir apenas um dentre dois estados opostos, “verdadeiro” “falso” não admitindo nenhum valor intermediário.

Da mesma forma que a álgebra convencional, a álgebra booleana utiliza operações lógicas, portanto são operações lógicas.

As razoes pelas quais a álgebra booleana é a ferramenta ideal para analisar problemas de lógica digital tornam-se evidentes assim que se tomam conhecimentos de suas operações..

A Variável Lógica (ou Booleana)

Considere a proposição citada anteriormente: A = " Um triciclo carrega pessoas "

A proposição é representada pelo símbolo A, dizemos que A é uma variável lógica (também chamada de variável Booleana), pois pode assumir somente um dos dois valores lógicos: F ou V.

Operações Booleanas

Operação AND, cujo operador é representado por "." (sinal gráfico do "ponto"), pode ser aplicada a duas ou mais variáveis (que podem assumir apenas os valores "verdadeiro" ou "falso"). A operação AND aplicada às variáveis A e B é expressa por:

A AND B = A.B

A operação AND resulta "verdadeiro" se e apenas se os valores de ambas as variáveis A e B assumirem o valor "verdadeiro".

Propriedades: (a) Comutatividade: A and B = B and A

(b) Associatividade: (A and B) and C = A and (B and C)

Operação OR, cujo operador é "+" (sinal gráfico da adição) e que também pode ser aplicada a duas ou mais variáveis (que podem assumir apenas os valores "verdadeiro" ou "falso"). A operação OR aplicada às variáveis A e B é expressa por:

A OR B = A+B

A operação OR resulta "verdadeira" se o valor de qualquer uma das variáveis A ou B assumir o valor "verdadeiro".

Propriedades: (a) Comutatividade: A or B = B or A

(b) Associatividade: (A or B) or C = A or (B or C)

Operação NOT, cujo operador é uma barra horizontal sobre o símbolo da variável, como em A , é unária, ou seja, aplicável a uma única variável. Ela é expressa por:

NOT A = A

A operação NOT inverte o valor da variável. Ele resulta "verdadeiro" se a variável assume o valor "falso" e resulta "falso" se a variável assume o valor "verdadeiro".

Operações Derivadas

Destas três operações fundamentais podem ser derivadas mais três operações adicionais, as operações NAND, NOR e XOR (ou OR exclusivo).

Operação NAND é obtida a partir da combinação das operações NOT e AND usando a relação:

A NAND B = NOT (A AND B)

A operação NAND resulta "falso" se e apenas se os valores de ambas as variáveis A e B assumirem o valor "verdadeiro".

Operação NOR é obtida a partir da combinação das operações NOT e OR usando a relação:

A NOR B = NOT (A OR B)

A operação NOR resulta "verdadeiro" se e apenas se os valores de ambas as variáveis A e B assumirem o valor "falso".

Operação, XOR ou "OR exclusivo" é um caso particular da função OR. Ela é expressa por:

A XOR B = (A OR B) AND NOT (A AND B)

A XOR B = (A+B) . (A.B)'

A operação XOR resulta "verdadeiro" se e apenas se exclusivamente uma das variáveis A ou B assumir o valor "verdadeiro" (uma outra forma, talvez mais simples, de exprimir a mesma idéia é: a operação XOR resulta em "verdadeiro" quando os valores das variáveis A e B forem diferentes entre si e resulta "falso" quando forem iguais).

Operação, XNOR ou "NOR exclusivo" resulta "verdadeiro" se as duas variáveis de entrada A e B tiverem valores lógicos iguais. Esta função é também chamada função EQUIVALÊNCIA.

A XNOR B = NOT (A XOR B)

Temos três formas de analisar as operações lógicas booleanas: Tabela-Verdade, Funções booleanas e Diagramas Lógicos.

Tabela-Verdade

Uma tabela verdade nada mais é que a lista de todos os possíveis resultados da operação, obtida através de todas as combinações possíveis dos valores dos operandos. Como os operandos somente podem assumir os valores "verdadeiro" e "falso", a confecção de uma tabela verdade é muito simples. Para exemplificar, vamos montar a tabela verdade da operação AND aplicada às variáveis A e B. Sabemos que para que o resultado de A AND B seja verdadeiro, AMBOS os operandos devem ser verdadeiros, todas as demais combinações de valores das variáveis resultam "falso". Ou seja:

A B A AND B Para simplificar, representemos o valor "verdadeiro" por "1" e "falso" por "0"... A B A AND B

Falso Falso Falso 0 0 0

Falso Verdadeiro Falso 0 1 0

Verdadeiro Falso Falso 1 0 0

Verdadeiro Verdadeiro Verdadeiro 1 1 1

Raciocínio idêntico pode ser feito para as demais operações. O resultado pode ser visto na tabela abaixo, que exibe a tabela verdade de todas as operações lógicas:

A B NOT A NOT B A AND B A NAND B A OR B A NOR B A XOR B A XNOR B

0 0 1 1 0 1 0 1 0 1

0 1 1 0 0 1 1 0 1 0

1 0 0 1 0 1 1 0 1 0

1 1 0 0 1 0 1 0 0 1

Semelhantemente à álgebra convencional, também na álgebra booleana é possível combinar variáveis e operadores para gerar complexas expressões algébricas que podem ser avaliadas. O valor da expressão é obtido atribuindo-se valores às variáveis e efetuando-se as operações indicadas (como na álgebra convencional, na álgebra booleana os parênteses indicam a ordem de precedência de avaliação dos termos).

Por exemplo, a expressão algébrica (da álgebra convencional), quando as variáveis assumem os valores A=9, B=3 e C=2 é:

(A / B) + C = 5

As expressões da álgebra booleana podem ser avaliadas de forma semelhante. A diferença básica é que suas operações são as operações lógicas e os valores a serem atribuídos (tanto à expressão quanto às variáveis) alternam somente entre "verdadeiro" (1) e "falso" (0).

Tomemos como exemplo uma expressão simples, como:

(A OR B) AND (NOT C)

que pode ser expressa como:

(A + B). C

e vamos determinar o valor da expressão quando as variáveis valem:

A = 0, B = 1, C = 1

Para tanto, efetuemos inicialmente a avaliação do primeiro termo entre parênteses. Trata-se de uma operação OR executada entre duas variáveis cujos valores são A = 0 e B = 1. Um exame da tabela verdade das operações lógicas indica que

0 OR 1 = 1

Em seguida executa-se a operação NOT na variável C, e ainda conforme a mesma tabela:

NOT 1 = 0

Finalmente executa-se a operação AND envolvendo os dois resultados parciais.

1 OR 0 = 1

Este é o valor da expressão para estes valores das variáveis.

Considerando que na álgebra booleana as variáveis apenas podem assumir os valores 1 e 0, dada uma expressão é relativamente simples construir uma tabela listando os valores assumidos pela expressão para todas as combinações dos valores de suas variáveis. Esta tabela denomina-se tabela verdade da expressão. Para a expressão do exemplo acima, a tabela verdade seria:

A B C (A OR B) AND (NOT 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 0

As regras básicas da álgebra booleana são simples. As operações são apenas seis (NOT, AND, OR, NAND, NOR, XOR e XNOR). Os valores possíveis, tanto para as variáveis quanto para as expressões, são apenas dois (1 ou 0). No entanto, expressões obtidas combinando operações que envolvem um grande número de variáveis podem atingir um grau de complexidade muito grande.

No entanto, sua avaliação é sempre feita decompondo-se a expressão em operações elementares respeitando-se a ordem de precedência indicada pelos parênteses, avaliando as operações elementares e combinando-se seu resultado. A avaliação pode ser trabalhosa, mas não difícil.

Assim como a álgebra convencional, a álgebra booleana também tem seus postulados (que independem de demonstração) e suas identidades (que podem ser derivadas dos anteriores). Os postulados definem a forma pela qual as expressões são interpretadas. Os principais postulados e identidades da álgebra booleana podem ser resumidos no quadro abaixo, arranjado em colunas para evidenciar a natureza complementar das operações OR e AND.

Postulados básicos

A . B = B . A A + B = B + A Lei comutativa

A . (B + C) = (A . B) + (A . C) A + (B . C) = (A + B) . (A + C) Lei distributiva

1 . A' = A 0 + A = A Elemento idêntico

A . A' = 0 A + A' = 1 Elemento inverso

Identidades derivadas

0 . A = 0 1 + A = 1

A . A = A A + A = A

A . (B . C) = (A . B) . C A + (B + C) = (A + B) + C Lei associativa

NOT (A . B) = A' + B' NOT (A + B) = A' . B' Teoremas de DeMorgan

Experimente: verifique os postulados e identidades atribuindo os mesmos valores às variáveis correspondentes das expressões de ambos os membros e compare os resultados. Repare que existe alguma analogia entre as operações AND e OR da álgebra booleana e as operações de multiplicação e adição da álgebra convencional. Mas neste caso, vale notar que esta analogia não se manifesta na lei distributiva expressa na coluna central.

Em princípio, as bases da álgebra booleana são as acima resumidas. Apenas com estes conhecimentos e utilizando-se as relações expressas nos postulados, identidades e teoremas para simplificar expressões mais complexas, é possível determinar o valor de quaisquer expressões da álgebra booleana.

Com os conhecimentos da álgebra booleana, podemos analisar todos os fenômenos relativos à lógica digital que rege as operações internas dos computadores. O que nos falta agora é um meio físico de implementar os circuitos eletrônicos baseados nessa lógica.

Equações Lógicas (Booleanas)

Dada uma variável lógica, é possível construir uma função desta variável, f(A),

Exemplo:

f(A) = A'

isto é, função da variável lógica A representa simplesmente a sua negação. Como visto acima, sua tabela-verdade é dada por (usando-se números binários 1 e 0, ao invés de V e F).

A f(A) = A'

0 1

1 0

Quando se tem apenas 1(uma) variável lógica, como acima, é possível construir 4 funções, a função f1 é a própria negação; a função f2 é a identidade; a função f3 vale sempre 0 e a função f4 vale sempre 1.

A f1(A) f2(A) f3(A) f4(A)

0 1 0 0 1

1 0 1 0 1

Veja que, para duas ou mais variáveis, o número possível de funções que podem ser construídas é de 22n, onde n é o número de variáveis. Para duas variáveis, 22.2 = 16 (apenas 16 possibilidades de construção de funções lógicas de apenas 2 variáveis).

A B f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15

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

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

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

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

0 AND ~AB A ~BA B XOR OR NOR XNOR ~B BA ~A AB NAND 1

Para 3 variáveis, 22.3 = 64 funções possíveis, e assim por diante. Na tabela cima, A e B são as variáveis independentes e fi(A,B) são as variáveis dependentes, conhecidas por funções de variáveis lógicas, funções combinatoriais ou, ainda, funções combinacionais.

A função lógica fi(A,B) pode ser representada por uma caixa preta cujo conteúdo implementa um tipo de Porta ou uma combinação das mesmas. Por exemplo, para a tabela acima, algumas funções são:

Função f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15

Porta 0 AND A'B A B'A B XOR OR NOR XNOR B' BA A' AB NAND 1



O que é aqui considerado como a Porta 0 é um circuito lógico que, independente das entradas, a saída é sempre zero. A Porta 1 segue o mesmo esquema, isto é, para quaisquer entradas, a saída é sempre 1. Os símbolos A' e B' caracterizam as negações, ou inversões, das variáveis A e B.

Qualquer circuito lógico pode ser considerado como uma caixa preta como descrita acima. Para exemplificar, veja como "encapsular" um circuito lógico em uma "caixa preta".

Observe que o modelo caixa preta é muito mais geral que o outro que já está especificado. O que se sabe do modelo caixa preta é a quantidade de circuitos que podem ser gerados a partir de 4 entradas e 1 saída. Quantos são mesmo?

Função Combinacional

Uma função combinacional é uma solução para um problema combinacional. Como exemplo de um problema combinacional, considere um sistema de segurança de uma loja em um shopping. Há um sensor de contato que, ligado, (on, V ou 1), indica que a porta está fechada; e outro sensor infravermelho que, ligado, indica que não há pessoas ou coisas se movendo no interior da loja. Há, também, um alarme que é acionado quando um dos dois sensores é desligado (off, F ou 0). Isto é, basta um único sensor ser desativado para soar o alarme. Denomine cada sensor pelos símbolos A e B,

A = "Sensor de contato"

B = "Sensor infravermelho"

Para maior realismo, suponha que a fonte de energia do sistema seja independente da rede elétrica (no-break, por exemplo). A tabela-verdade para a função alarme, f(A,B), é dada por:

A B f(A,B)

0 0 1

0 1 1

1 0 1

1 1 0

onde 0 e 1 significam desligado e ligado, respectivamente.

A equação booleana para a função alarme acima, pode ser escrita da seguinte forma:

f(A,B) = (A.B)'

A B A.B (A.B)'

0 0 0 1

0 1 0 1

1 0 0 1

1 1 1 0

onde o símbolo "'" significa a negação lógica, e o símbolo "." significa a conjunção (AND) lógica. Sua tabela-verdade é construída da mesma maneira,

A função alarme aqui tratada poderia ser especificada através do seguinte diagrama lógico,

isto é, através da Porta Lógica NAND, como veremos a seguir.

Exercícios

1. Indique para cada uma das sentenças a seguir se a mesma é uma proposição. Justifique.

a) Parece que sei lá !

b) Quem sabe esta eu acerto ?

c) Por favor responda corretamente.

d) Esta frase não é uma proposição.

e) Todas as sentenças anteriores são proposições.

f) Nenhuma das sentenças anteriores são proposições.

g) 2x > 30.

2. Apresente a negação de cada uma das proposições a seguir:

a) Todos os alunos da POLI são inteligentes.

b) A proposição do item anterior é verdadeira e esta proposição é falsa.

c) (p  ~q)  ~p

Gabarito Comentado

1. Indique para cada uma das sentenças a seguir se a mesma é uma proposição. Justifique.

a) Parece que sei lá ! Não. É impossível definir se é V ou F.

b) Quem sabe esta eu acerto ? Não. Não é uma afirmação.

c) Por favor responda corretamente. Não. Não é uma afirmação.

d) Esta frase não é uma proposição. Sim. Possui valor lógico definido (no caso é falso)

e) Todas as sentenças anteriores são proposições. Sim. Possui valor lógico definido (no caso é falso)

f) Nenhuma das sentenças anteriores são proposições. Sim. Possui valor lógico definido (no caso é falso)

g) 2x > 30. Não, porque pode assumir valores lógicos diferentes, dependendo do valor de x. (trata-se de uma

função proposicional)

2. Apresente a negação de cada uma das proposições a seguir:

a) Todos os alunos da POLI são inteligentes.

Há pelo menos um aluno na POLI que não é inteligente.

b) A proposição do item anterior é verdadeira e esta proposição é falsa.

A proposição do item anterior é falsa ou esta proposição é verdadeira

Portas Lógicas Básicas (Gates)

Porta Lógica ou Gate

São dispositivos ou circuitos lógicos que operam um ou mais sinais lógicos de entrada para produzir uma (e somente uma) saída, a qual é dependente da função implementada no circuito.

Um computador é constituído de uma infinidade de circuitos lógicos, que executam as seguintes funções básicas:

a) Realizam operações matemáticas

b) Controlam o fluxo dos sinais

c) Armazenam dados

Existem dois tipos de circuitos lógicos:

1. COMBINACIONAL - a saída é função dos valores de entrada correntes; esses circuitos não têm capacidade de armazenamento [casos a e b acima].

2. SEQUENCIAL - a saída é função dos valores de entrada correntes e dos valores de entrada no instante anterior; é usada para a construção de circuitos de memória (chamados "flip-flops" - caso c acima);

Portas Básicas

PORTA NOT (NÃO)

A Porta NOT inverte o sinal de entrada (executa a NEGAÇÃO do sinal de entrada), ou seja, se o sinal de entrada for 0 ela produz uma saída 1, se a entrada for 1 ela produz uma saída 0.

PORTA AND (E)

A Porta AND combina dois ou mais sinais de entrada de forma equivalente a um circuito em série, para produzir um único sinal de saída, ou seja, ela produz uma saída 1, se todos os sinais de

entrada forem ; caso qualquer um dos sinais de entrada for 0, a Porta AND produzirá um sinal de saída igual a zero.

PORTA OR (OU)

A Porta OR combina dois ou mais sinais de entrada de forma equivalente a um circuito em paralelo, para produzir um único sinal de saída, ou seja, ela produz uma saída 1, se qualquer um dos sinais de entrada for igual a 1; a Porta OR produzirá um sinal de saída igual a zero apenas se todos os sinais de entrada forem 0.

Portas Derivadas

PORTA NAND (NÃO E)

A porta NAND eqüivale a uma porta AND seguida por uma porta NOT, isto é, ela produz uma saída que é o inverso da saída produzida pela porta AND.

PORTA NOR (NÃO OU)

A Porta NOR eqüivale a uma Porta OR seguida por uma Porta NOT, isto é, ela produz uma saída que é o inverso da saída produzida pela Porta OR.

PORTA XOR (OU EXCLUSIVO)

A Porta XOR compara os bits; ela produz saída 0 quando todos os bits de entrada são iguais e saída 1 quando pelo menos um dos bits de entrada é diferente dos demais.

PORTA XNOR (NOU EXCLUSIVO)

A porta XNOR compara os bits; ela produz saída 1 quando todos os bits de entrada são iguais e saída 0 quando pelo menos um dos bits de entrada é diferente dos demais. É também chamada de EQUIVALÊNCIA.

Exemplo de circuitos utilizando portas lógicas

A) Uma campainha que toca (saída) se o motorista der a partida no motor do carro (entrada) sem estar com o cinto de segurança afivelado (entrada).

Se a ignição for ACIONADA (1) e o cinto estiver DESAFIVELADO (1), a campainha é ACIONADA (1). Caso contrário, a campainha não toca

B) Detetor de incêndio com vários sensores (entradas) e uma campainha para alarme (saída).

Se QUALQUER UM dos sensores for acionado (significando que um dos sensores detectou sinal de incêndio), a campainha é ACIONADA.

C) Elevador que só para no andar (Parada) se:

1) Quando estiver descendo (Elevador D) e o botão descer (Botão D) estiver acionado

2) Quando estiver subindo (Elevador S)e o botão subir (Botão S) estiver acionado

Tabela Verdade:

Botão S Botão D Elevador S Elevador D Parada

0 1 0 1 1

0 1 1 0 0

1 0 1 0 1

1 0 0 1 0

“coisa de usuário”  1 1 1 0 1

1 1 0 1 1

Representação de circuitos com as Funções NAND e NOR

Usando as propriedades apresentadas, todo e qualquer circuito pode ser representado usando exclusivamente as função NAND ou as função NOR.

Para que serviria tal artimanha, além da dor de cabeça aos alunos?

Há neste caso uma razão maior que a comodidade ou a aparente dificuldade: a razão econômica. Por diversas razões construtivas, fica mais barato construir TODOS os circuitos de um computador usando APENAS UM ÚNICO TIPO DE CIRCUITO. Aceitando essa afirmação, vamos enfrentar a tarefa de representar os nossos circuitos já conhecidos usando apenas funções NAND ou os NOR.

a) CIRCUITO INVERSOR

b) CIRCUITO AND

c) CIRCUITO OR

Exercícios

1. Faça as tabelas verdade para os seguintes diagramas:

a)

b)

2. Desenhe os diagramas lógicos para as seguintes tabelas verdade:

a) A B S b) A B S c) A B S d) A B S

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

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

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

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

3. Escreva a tabela verdade e a expressão do circuito abaixo e simplifique.

A

B X

0 0

1 0

0 1

1 1

Observação: Este circuito implementa a função XOR, usando apenas portas NAND.

B) Mostre utilizando os operadores conhecidos que :

C) A partir do Diagrama ao lado, construa a Tabela Verdade:

A B C V S

0 0 0

1 1 0

1 0 1

1 0 0

0 1 1

0 1 0

0 0 1

1 1 1

Apêndice A

Aplicação da Álgebra de Boole aos Computadores Digitais

Boole desenvolveu sua álgebra a partir desses conceitos básicos e utilizando apenas os algarismos 0 e 1.

Os primeiros computadores fabricados, como o ENIAC, trabalhavam em DECIMAL. No entanto, a utilização de circuitos eletrônicos que operassem com 10 diferentes níveis de tensão (para possibilitar detectar as 10 diferentes grandezas representadas no sistema decimal) acarretavam uma grande complexidade ao projeto e construção dos computadores, tendo por conseqüência um custo muito elevado. Surgiu então a idéia de aplicar a álgebra de Boole, simplificando extremamente o projeto e construção dos computadores, pelo fato de utilizar somente um tipo de circuito.

Nível Lógico 10

Nível Lógico 5

Nível Lógico 1

Nível Lógico 0 Nível Lógico 0

Mas como os conceitos da álgebra de chaveamentos (um ramo da álgebra do Boole) são aplicados ao projeto dos computadores digitais?

A chave de tudo é um circuito eletrônico chamado CHAVE AUTOMÁTICA.

Como funciona uma chave automática?

Vamos imaginar um circuito chaveador com as seguintes entradas:

- Uma fonte de alimentação (fornece energia para o circuito)

- Um fio de controle (comanda a operação do circuito)

- Um fio de saída (conduz o resultado)

No desenho, a chave permanece aberta enquanto o sinal C no fio de controle for 0 (ou Falso). Enquanto não houver um sinal (sinal 1 ou Verdadeiro) no fio de controle, que mude a posição da chave, o sinal no fio de saída S será 0 (ou Falso). Quando for aplicado um sinal (sinal 1 ou Verdadeiro) ao fio de controle, a chave muda de posição, tendo como resultado que o sinal na saída será então 1 (ou Verdadeiro). A posição da chave se manterá enquanto não ocorrer um novo sinal na entrada.

A chave automática foi inicialmente implementada com relés eletromecânicos e depois com válvulas eletrônicas. A partir da metade da década de 50, passaram a ser utilizados dispositivos em estado sólido - os TRANSISTORES, inventados em Stanford em 1947. Os modernos Circuitos Integrados - CI's e os microprocessadores são implementados com milhões de transistores "impressos" em minúsculas pastilhas.

Vamos agora analisar o que ocorreria se nós ligássemos em SÉRIE duas chaves automáticas como as acima, e ligássemos uma lâmpada ao circuito. O circuito resultante poderia ser representado assim:

A lâmpada acenderia SE - e somente se - as DUAS chaves estivessem na posição LIGADO (ou verdadeiro), o que seria conseguido com as duas entradas A e B em estado 1 (Verdadeiro). Substituindo CORRENTE (ou chave ligada) por 1 e AUSÊNCIA DE CORRENTE (ou chave desligada) por 0, como ficaria nossa tabela verdade para LÂMPADA LIGADA = 1 e LÂMPADA DESLIGADA = 0?

A B L

0 0 0

0 1 0

1 0 0

1 1 1

Dá para reconhecer a nossa já familiar FUNÇÃO E?

O circuito acima que implementa a função E é chamado de PORTA E (AND GATE).

Vamos agora analisar o que ocorreria se nós ligássemos em PARALELO duas chaves automáticas como as acima, e ligássemos uma lâmpada ao circuito. O circuito resultante poderia ser representado assim:

A lâmpada acenderia SE QUALQUER UMA DAS-CHAVES estivesse na posição LIGADO (ou verdadeiro), o que seria conseguido com uma das duas entradas A ou B em estado 1 (Verdadeiro). Substituindo CORRENTE (ou chave ligada) por 1 e Ausência de Corrente (ou chave desligada) por 0, como ficaria nossa tabela verdade para Lâmpada LIGADA = 1 e Lâmpada DESLIGADA = 0?

A B L

0 0 0

0 1 1

1 0 1

1 1 1

E agora, dá para reconhecer a nossa já familiar FUNÇÃO OU ?

O circuito acima, que implementa a função OU, é chamado de PORTA OU (OR Gate).

Bibliografia Auxiliar

3. QUINE, O. O Sentido da Nova Lógica. São Paulo, Editora da USP, 1942.

4. GRIES, D. The Science of Programming. New York, The MIT Press, 1986.

5. LEAL, Maria Leonor de M. S. Matemática na Computação. Rio de Janeiro, Ed. Senac Nacional, 1999