Baixe Portas Logicas e outras Notas de estudo em PDF para Informática, somente na Docsity! FACULDADE ESTÁCIO DE SÁ DE BELO HORIZONTE Curso Superior de Tecnologia em Redes de Computadores Disc: Arquitetura de Computadores Prof: José Eustáquio do Amaral Pereira. Unidade III Conceitos de Lógica Digital RESUMO de proposições e conectivos Proposição: sentença que pode assumir o valor FALSO ou VERDADEIRO. Através de três conectivos é possível fazer a associação de duas ou mais sub-proposições de forma que a proposição resultante só possa assumir um dos valores FALSO ou VERDADEIRO. O conectivo E Na hipótese das duas sub-proposições serem verdadeiras a proposição resultante também será verdadeira.. Caso uma das proposições, ou ambas, assuma o valor FALSO, a proposição resultante será FALSA. É a chamada Conjunção de proposições. Representação da Conjunção: . (ponto, símbolo usado na multiplicação) entre as sub-proposições. Ex: A.B significando A E B As diversas possibilidades de combinação entre proposições ligadas pelo conectivo E podem ser expressas na chamada “Tabela verdade”. Para duas proposições quaisquer A e B, a Tabela verdade será: Onde: V: Verdadeiro F: Falso Conclusão: proposições ligadas com o conectivo E têm que ser todas verdadeiras para que a proposição resultante seja verdadeira. O conectivo OU Na hipótese de uma das duas sub-proposições ser verdadeira ou de ambas serem verdadeiras, a proposição resultante também será verdadeira.. Caso as duas proposições assumam o valor FALSO, a proposição resultante será FALSA. É a chamada Disjunção de proposições. Forma de representação da Disjunção: + (sinal de mais) entre as sub-proposições. Ex: A+B significando A OU B As diversas possibilidades de combinação entre proposições ligadas pelo conectivo OU podem, também, ser expressas na chamada “Tabela verdade”. Para duas proposições quaisquer A e B, a Tabela verdade para a Disjunção será: Onde: V: Verdadeiro F: Falso Prof. José Eustáquio do Amaral Pereira – 11/08/09 1 A B A.B V V V V F F F V F F F F A B A+B V V V V F V F V V F F F FACULDADE ESTÁCIO DE SÁ DE BELO HORIZONTE Curso Superior de Tecnologia em Redes de Computadores Disc: Arquitetura de Computadores Prof: José Eustáquio do Amaral Pereira. Conclusão: basta que uma das proposições ligadas com o conectivo OU seja verdadeira para que a proposição resultante seja verdadeira. O conectivo NÃO O conectivo NÃO faz a Negação de uma dada proposição. Dada uma proposição A o conectivo aplicado a ela cria uma nova proposição que pode ser lida como “É falso que A”. Se a proposição original for verdadeira a Negação (conectivo NÃO) a torna falsa.. A tabela verdade do conectivo NÃO é bem simples. Onde: V: Verdadeiro F: Falso Conclusão: proposição verdadeira negada, resulta em proposição falsa, e vice-versa. Na construção das tabelas verdade podem ser usados outros símbolos. É comum, por exemplo, usar- se o 1(hum) para as proposições verdadeiras e o 0(zero) para as falsas. O conceito de tabela verdade se aplica, também, para a análise de um número de proposições ligadas por diferentes conectivos. Ela é um importante instrumento de análise e interpretação que nos permitirá, no estudo de circuitos lógicos, verificar os resultados (proposições de saída) ou sinais resultantes a partir das possíveis combinações de sinais de entrada. Leis da Álgebra das Proposições As leis da álgebra das proposições são como propriedades que permitem a análise e simplificação de proposições. Em outras palavras, com um número menor de conectivos ligando proposições, pode-se obter o mesmo resultado. Exemplo: “É falso que (o Atlético perdeu para o Santos E o Rubinho Barrichelo ganhou o campeonato de pilotos de 2004)” tem o mesmo valor (Falso ou Verdadeiro) que a proposição “É falso que o Atlético perdeu para o Santos OU É falso que o Rubinho Barrichelo ganhou o campeonato de pilotos de 2004” Esse exemplo pode ser “testado” usando-se as tabelas verdades. Para tanto vamos chamar de A a proposição “o Atlético perdeu para o Santos” e de B a proposição “o Rubinho Barrichelo ganhou o campeonato de pilotos de 2004” A representação dessas proposições com seus conectivos, nas duas formas propostas, fica nas formas abaixo: (A . B)’ para o primeiro caso e A’ + B’ para o segundo Na construção das tabelas verdade usaremos 1(hum) para as proposições verdadeiras e 0(zero) para as falsas Tabela verdade de (A . B)’ Tabela verdade de A' . B' A B A . B (A . B)’ A B A' B' A' + B' 1 1 1 0 1 1 0 0 0 Prof. José Eustáquio do Amaral Pereira – 11/08/09 2 A A’ V F F V FACULDADE ESTÁCIO DE SÁ DE BELO HORIZONTE Curso Superior de Tecnologia em Redes de Computadores Disc: Arquitetura de Computadores Prof: José Eustáquio do Amaral Pereira. 0 1 0 Leis Complementares A + A’ = 1 0’ = 1 A . A’ = 0 1’ = 0 A’’ = A Demonstração pelas Tabelas verdade A A’ A + A’ 1 0 1 0 1 1 A A’ A’’ 1 0 1 0 1 0 Leis de De Morgan (A + B)’ = A’. B’ (A . B)’ = A’ + B’ Tabela verdade de (A + B)’ Tabela verdade de A' . B' A B A + B (A + B)’ A B A' B' A' . B' 1 1 1 0 1 1 0 0 0 1 0 1 0 1 0 0 1 0 0 1 1 0 0 1 1 0 0 0 0 0 1 0 0 1 1 1 A tabela verdade da segunda Lei de De Morgan já foi feita anteriormente. Analogia entre a Álgebra das Proposições e Circuitos elétricos Circuito em série (com chaves em série) Supondo que os dois fios à esquerda sejam colocados na tomada e que as setas representam chaves ou interruptores (X e Y), em que situação a lâmpada se acenderá? Prof. José Eustáquio do Amaral Pereira – 11/08/09 5 A 1 A + 1 1 1 1 0 1 1 A A’ A . A’ 1 0 0 0 1 0 X Atenção: isto é uma lâmpada X Y FACULDADE ESTÁCIO DE SÁ DE BELO HORIZONTE Curso Superior de Tecnologia em Redes de Computadores Disc: Arquitetura de Computadores Prof: José Eustáquio do Amaral Pereira. Parece intuitivo que isso só ocorrerá se ambas as chaves estiverem acionadas/ligadas/fechadas. Se só a chave X estiver acionada a corrente não fluirá pela lâmpada porque não há como ela passar pela chave Y que está aberta. Com qual conectivo visto na Álgebra das proposições se parece esse circuito? Com o conectivo E. Ambas as chaves (proposições) devem estar ligadas para que o circuito funcione (a lâmpada acenda). Caso tivéssemos três chaves em série a situação não seria diferente. Bastaria que uma delas estivesse aberta para que o circuito não funcionasse. Circuito em paralelo (com chaves em paralelo) Supondo que os dois fios à esquerda sejam colocados na tomada e que as setas representam chaves ou interruptores (X e Y), em que situação a lâmpada se acenderá? Acionando/ligando qualquer das chaves individualmente ou ambas, a lâmpada se acenderá. A única situação em que não haverá fluxo de corrente para acender a lâmpada será aquela em que ambas as chaves estiverem abertas. Com qual conectivo visto na Álgebra das proposições se parece esse circuito? Com o conectivo OU. Basta que uma das chaves (proposições) esteja ligada para que o circuito funcione (a lâmpada acenda). Caso tivéssemos três chaves a situação não seria diferente. Bastaria que uma delas estivesse fechada para que o circuito funcionasse. Circuito com propriedade de representar o conectivo NÃO Há circuitos menos simples que os anteriores que podem representar o conectivo NÃO. A propriedade de um circuito NÃO é que quando a chave está desligada a lâmpada estará acesa; quando a chave está ligada, a lâmpada estará apagada. Nesse circuito, quando a chave X está aberta a lâmpada estará acesa, uma vez que a corrente pode fluir pelo circuito mais externo. Quando a chave X estiver fechada o eletroímã será ativado e “atrairá” a chave que se conecta a um dos pólos da lâmpada, abrindo o circuito externo. Nessa situação a lâmpada NÃO se acende. Representação de circuitos elétricos com chaves representando conectivos. Para facilidade e simplificação do desenho que representa o circuito, a chave NÃO será representada pelo símbolo ‘ aplicado à uma proposição que se quer negar. As chaves que Prof. José Eustáquio do Amaral Pereira – 11/08/09 6 X Atenção: isto é uma lâmpada X Y X Lembra da lâmpada? Este é um novo componente – um eletroímã FACULDADE ESTÁCIO DE SÁ DE BELO HORIZONTE Curso Superior de Tecnologia em Redes de Computadores Disc: Arquitetura de Computadores Prof: José Eustáquio do Amaral Pereira. representam o conectivo E e OU serão mostradas como proposições em circuitos série e em paralelo. Ex: A equação da álgebra das proposições que equivale ao circuito acima é: A . (B + A’) A chave ou proposição A está ligada em série a um circuito em paralelo que tem B como uma das chaves ou proposição e a negação de A como outra chave ou proposição. Também para esse tipo de circuito é possível fazer a tabela verdade. A B A' B + A' A . (B + A') 1 1 0 1 1 1 0 0 0 0 0 1 1 1 0 0 0 1 1 0 Ex 2: O circuito equivalente é: (A . B’) + (A’ + C) . B A tabela verdade é: A B C A' B' A . B' A' + C (A' + C) . B (A . B') + (A' + C) . B 1 1 1 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 1 0 1 0 1 1 1 0 1 1 0 0 0 1 1 0 0 1 0 1 1 1 0 0 1 1 1 0 1 0 1 0 0 1 1 1 0 0 1 1 1 0 1 0 0 0 0 0 1 1 0 1 0 0 Ex3: Dada a expressão (A’ . B) + (A’ . (B’ + A + B)), construir o circuito correspondente Prof. José Eustáquio do Amaral Pereira – 11/08/09 7 A B A ’ A B’ B C A ’ BA ’ A ’ A B’ FACULDADE ESTÁCIO DE SÁ DE BELO HORIZONTE Curso Superior de Tecnologia em Redes de Computadores Disc: Arquitetura de Computadores Prof: José Eustáquio do Amaral Pereira. 1o passo: Construir a expressão equivalente A . B + A . B’ + A’ . B’ 2o passo: Lei distributiva nas duas primeiras parcelas da soma A . (B + B’) + A’ . B’ 3o passo: Lei complementar - B + B’ = 1 A . 1 + A’ . B’ 4o passo – Lei de identidade - A . 1 = A A + A’ . B’ 5o passo: Lei da absorção A + B’ Redes e Portas eletrônicas Um circuito digital admite a presença de dois valores lógicos que, em geral, são representados por sinais elétricos: entre 0 e 1 volt, representa um desses valores (o binário 0) e entre 2 e 5 volts, o outro valor (o binário 1). As portas lógicas “trabalham” com valores lógicos desse tipo e realizam diversas funções e são a base do hardware dos computadores digitais. Toda a lógica digital baseia-se no fato de que os transistores podem operar como uma chave binária (aberta – fechado) cujo tempo de comutação é extremamente pequeno. Os transistores, isoladamente ou em conjunto, são capazes de implementar os conectivos lógicos. Esse grupo específico de transistores que implementam os conectivos é chamado de portas lógicas. As portas lógicas elementares são: As portas E e OU podem ser vistas em outras publicações em um formato um pouco diferente. Aqui, por questões de simplicidade, foram usadas Autoformas padrão do MSWord. Prof. José Eustáquio do Amaral Pereira – 11/08/09 1 A + B OU A . B E A’ NÃO A B A B A FACULDADE ESTÁCIO DE SÁ DE BELO HORIZONTE Curso Superior de Tecnologia em Redes de Computadores Disc: Arquitetura de Computadores Prof: José Eustáquio do Amaral Pereira. As portas E e OU admitem mais de 2 entradas e uma única saída. Cada uma das entradas assim como a saída pode assumir o valor 0 (falso) ou 1 (verdadeiro). Reflita sobre a relação entre a Álgebra Booleana e as portas lógicas. Cada uma das portas implementa um conectivo da Álgebra Booleana. A saída da porta E será igual a 1 (verdadeira) se e somente se todas as entradas forem iguais a 1 (verdadeiras). A porta OU será igual a 0 (falsa) se e somente se todas as entradas forem iguais a 0 (falsas). Em outras palavras, para que a porta E seja igual a 0 (falsa) basta que uma das entradas seja igual a 0; para que a porta OU seja igual a 1, basta que uma das entradas seja igual a 1. Entendidas as portas lógicas, podemos fazer entender a função das expressões lógicas e dos circuitos elétricos vistos anteriormente. Como será o circuito lógico (formado por Portas Lógicas) representado pela expressão: (A’ . B) + (A’. (B’+ A + B)) Lembrando da simplificação feita nessa expressão usando as Leis da Álgebra das proposições, o circuito lógico acima tem a mesma função que o circuito abaixo: Exercício 1- Dado o circuito lógico abaixo, aplicando as Leis da Álgebra das Proposições, determinar um outro circuito equivalente com o menor número possível de portas. 1o passo: determinar a Expressão equivalente ao primeiro circuito e efetuar as possíveis simplificações. A expressão correspondente ao circuito é (A + B.C)’ + B 1o passo: Lei de De Morgan – (A’ . (B.C)’) + B 2o passo: Lei distributiva – (B + A’) . (B + (B.C)’) 3o passo: Lei de De Morgan - (B + A’) . (B + (B’ +C’)) 4o passo: Lei complementar – (B + A’) . (1 + C’) 5o passo: Lei identidade – (B + A’) . 1 Prof. José Eustáquio do Amaral Pereira – 11/08/09 1 A A’ A B C A B FACULDADE ESTÁCIO DE SÁ DE BELO HORIZONTE Curso Superior de Tecnologia em Redes de Computadores Disc: Arquitetura de Computadores Prof: José Eustáquio do Amaral Pereira. 6o passo: Lei identidade – (B + A’) O circuito correspondente é: Com a simplificação do circuito, de 2(duas) portas OU, 1(uma) E e 1(uma) NÃO, o novo circuito tem 1(uma) porta OU e 1(uma) NÃO. Outra conclusão importante é que o sinal de saída independe do valor (verdadeiro ou falso – 0 ou 1) de C. Exercício 2. Dado o circuito lógico abaixo, determinar um outro circuito lógico capaz de produzir os mesmos resultados (sinais de saída) em função dos valores das entradas (sinais de entrada). Para resolução deste problema, determinar primeiro a expressão lógica correspondente ao circuito, simplificar o mesmo, usando as Leis da Álgebra das proposições e, finalmente, representar o circuito lógico reduzido (simplificado)., Resolução: A expressão lógica que representa o circuito é: A . B’ . C’ + A . B . C’ + A . B’ . C + A’ . B . C’ Aplicando a propriedade comutativa a expressão fica sendo: A . B’ . C’ + A . B’ . C + A . B . C’ + A’ . B . C’ Aplicando a propriedade distributiva a expressão passa a ser: A . B’ . (C’ + C) + B . C’ . (A + A’) Aplicando a propriedade da complementação teremos: A . B’ . 1 + B . C’ . 1 Finalmente, com a aplicação da propriedade da idem-potência a expressão fica reduzida a: A . B’ + B . C’ A representação dessa expressão fica sendo: Prof. José Eustáquio do Amaral Pereira – 11/08/09 1 A B A B C A B C FACULDADE ESTÁCIO DE SÁ DE BELO HORIZONTE Curso Superior de Tecnologia em Redes de Computadores Disc: Arquitetura de Computadores Prof: José Eustáquio do Amaral Pereira. Transformação em outro circuito lógico de mais fácil análise. Análise do circuito considerando as possíveis combinações dos sinais de A e B. Solução pela Tabela verdade A B C B' A . B F1 = (A . B)' F2 = B' . C F3 = A + F2) R = F1 . F3 1 1 1 0 1 0 0 1 0 1 1 0 0 1 0 0 1 0 1 0 1 1 0 1 1 1 1 1 0 0 1 0 1 0 1 1 0 1 1 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 1 0 1 1 1 1 0 0 0 1 0 1 0 0 0 Observemos as colunas C e R, esta com a resposta final do circuito. Nas linhas ímpares da tabela o sinal de C é igual a 1 e nas linhas pares é igual a 0. Na coluna R observamos que nas seis primeiras linhas as saídas são aos pares, dois 0(zeros), dois 1(um) e dois 0(zeros). O sinal de saída se repete independente se o sinal de C é zero ou um. Já nas duas últimas linhas, com os mesmos sinais de A e B, a saída acompanha o sinal de C. Logo, para A igual a 0 (zero) e B igual a 0(zero) é o sinal de C que determina a saída do circuito. c.q.d (?) Circuito não-equivalente NEQ ou XOR Tabela verdade O que a tabela nos sugere? R1 – a saída será verdadeira apenas quando uma das entradas for verdadeira. 2 - a saída será falsa quando os dois sinais de entrada forem iguais. Prof. José Eustáquio do Amaral Pereira – 11/08/09 1 A B A' B' A' . B A . B' A'.B + A.B' 1 1 0 0 0 0 0 1 0 0 1 0 1 1 0 1 1 0 1 0 1 0 0 1 1 0 0 0 FACULDADE ESTÁCIO DE SÁ DE BELO HORIZONTE Curso Superior de Tecnologia em Redes de Computadores Disc: Arquitetura de Computadores Prof: José Eustáquio do Amaral Pereira. Como esse circuito é muito utilizado convencionou-se uma forma de representá-lo como se fosse uma porta com duas entradas e uma saída, mas na verdade, é um circuito com 5 portas (2 NÃO; 2 E; 1 OU). Prof. José Eustáquio do Amaral Pereira – 11/08/09 1