Baixe apostila - logica e outras Notas de aula em PDF para Informática, somente na Docsity! URI – Universidade Regional Integrada Campus de Erechim Curso de Ciência da Computação Apostila de Lógica para a Computação Prof. Neilor Tonin Erechim, 4 de Agosto de 2008 Apostila de Lógica para a computação 2 Plano de ensino da disciplina: 35-324 Lógica para a Computação Departamento: 03 Engenharias e Ciência da Computação Carga horária: 60 horas Créditos: 04 EMENTA: Álgebra booleana. Proposições. Operações Lógicas sobre Proposições. Construção de Tabelas-Verdade. Tautologia, Contradições e Contingências. Implicação Lógica. Álgebra das Proposições. Método Dedutivo. Argumentos , Regras de Inferência. Validade mediante Regras de Inferência. Cálculo de Predicados. OBJETIVOS: Formalização de idéias complexas de forma mais simples. Propicia um novo ou melhor entendimento das questões relacionadas com toda a Ciência da Computação. Auxilia no desenvolvimento de aplicações e solução de problemas reais que envolvem aplicação da computação. RELAÇÃO DOS CONTEÚDOS: 1. Proposições – Conectivos: • Valores lógicos; Proposições Simples e Proposições Compostas; Conectivos; Tabela-Verdade. 2. Operações Lógicas sobre Proposições: • Negação; Conjunção; Disjunção; Disjunção Exclusiva; Condicional; Bicondicional; 3. Construção de Tabelas-Verdade: • Tabela-Verdade de uma proposição composta; Número de Linhas; Construção de uma T.V.; Valor lógico 4. Tautologia, Contradições e Contingências: • Tautologia; Princípio de substituição; Contradição; Contingência. 5. Implicação Lógica: • Definição; Propriedades; Tautologia e equivalência Lógica; • Proposições associadas a uma condicional; • Negação conjunta de duas proposições; Negação disjunta de duas proposições; 6. Álgebra das Proposições 7. Método Dedutivo: Formas normais; Princípio da dualidade; 8. Argumentos , Regras de Inferência: • Definição; Validade; Critério; Condicional Associada; Argumentos Válidos; • Regras de Inferência; Validade mediante as Regras de Inferência 9. Cálculo de Predicados: • Quantificadores e Variáveis; Predicados e nomes próprios; Regras de formação; • Regras de inferência para o quantificador universal; • Regras de inferência para o quantificador existencial; • Teoremas e regras de equivalência do quantificador; • Identidade. BIBLIOGRAFIA BÁSICA (LIVROS TEXTOS): Sérates, Jonofon. Raciocínio Lógico. 8 ed – Brasília:Editora Jonofon LTDA, 1998. Nolt, J; Rohatyn, D. Lógica. Coleção Schaum, McGraw-Hill, Inc., 1991. BIBLIOGRAFIA COMPLEMENTAR (LIVROS REFERENCIADOS): James L. Hein. Discrete Structures, Logic and Computability; Jones & Bartlett 1995. H. B. Enderton. A mathematical introduction to logic, Academic Press, 2ed. 2001. D. M. Gabbay. Elementary Logics: a procedural perspective, Prentice Hall, 1998. Alencar Filho, Edgar de. Iniciação à Lógica Matemática. 8 ed. São Paulo: Ed. Nobel, 1976. Mendelson, B. Introduction to Mathematical Logic. Princeton, NJ, Van Nostrand, 1964. Cálculo da média semestral: (P1*4 + P2*4 + T*2 ) / 10 onde: P1 = Primeira prova P2 = Segunda prova T = Trabalho Apostila de Lógica para a computação 5 O valor lógico de uma expressão composta depende unicamente dos valores lógicos das expressões simples que compõem a mesma. Admitindo isso, recorre-se a um dispositivo denominado tabela – verdade para aplicar este conceito na prática. Na tabela – verdade figuram todos os possíveis valores lógicos da proposição correspondentes a todas as possíveis atribuições de valores lógicos às proposições simples componentes. Assim, por exemplo, uma proposição composta cujas proposições simples componentes são p e q pode ter as possíveis atribuições: p q 1 V V 2 V F 3 F V 4 F F Neste caso, as combinações entre os elementos são: VV, VF, FV e FF. As tabelas - verdade são construídas como arranjos dos elementos componentes, e como um elemento pode receber somente os valores V ou F, o tamanho de uma tabela é dado pela quantidade de elementos combinados: No caso de uma proposição composta com 3 elementos, teríamos 8 combinações possíveis: VVV, VVF, VFV, VFF, FVV, FVF, FFV, FFF. p q r 1 V V V 2 V V F 3 V F V 4 V F F 5 F V V 6 F V F 7 F F V 8 F F F Observação 1: a ordem das letras pode ser diferente e a combinação entre as letras também pode ser dirente da apresentada acima. Deve-se somente tomar o cuidado de não repetir duas combinações (2 linhas c/ VVF, por exemplo). Observação 2: Para construirmos as tabelas – verdade podemos usar as seguintes regras. O número de linhas sempre depende do número de elementos combinados, e como uma proposição pode assumir os valores V ou F, o número de linhas de uma tabela – verdade é dado por 2n. 1 elemento : 2 l linhas = 2 linhas 2 elementos: 22 linhas = 4 linhas 3 elementos: 2 3linhas = 8 linhas 4 elementos: 2 4linhas = 16 linhas Para construir a tabela inicia-se sempre atribuindo V, F,V, F,... para o elemento mais à direita da tabela, V, V, F, F,... para o segundo elemento da direita para a esquerda, V, V, V, V, F, F, F, F, ... para o terceiro elemento à partir da esquerda e assim, sucessivamente. Exercício: construa uma tabela – verdade para 4 elementos: p, q, r, s. 1.5. Notação O valor lógico para uma proposição simples p indica-se por V(p). Assim, exprime-se que p é verdadeiro escrevendo: V(p) = V. Analogamente, pode-se exprimir que a proposição p tem o valor falso utilizando-se V(p) = F. Considerando, por exemplo, as seguintes proposições simples: p: O Sol é verde q: um hexágono tem 6 lados r: 2 é um número ímpar s: um triângulo tem 4 lados Temos: V(p)=F V(q)=V V(r) =F V(s) =F Apostila de Lógica para a computação 6 2. Operações lógicas sobre as Proposições Quando pensamos, efetuamos muitas vezes certas operações sobre proposições, chamadas operações lógicas. Estas obedecem a regras de um cálculo, denominado Cálculo Proposicional, semelhante ao da aritmética sobre números. Serão apresentadas, a seguir, as operações lógicas fundamentais do cálculo proposicional. 2.1 Negação (~) Definição: chama-se negação de uma proposição p a proposição representada por “não p”, cujo valor lógico é verdade (V) quando p for Falso e falsidade (F) quando valor de p é verdadeiro. Assim, “não p” tem o valor oposto do valor de p. A negação de p indica-se com a notação “~p”, e é lido como “não p”. O valor lógico da negação de uma proposição é definido por uma tabela – verdade muito simples: p ~p 1 V F 2 F V Ou seja: ~V = F, ~F = V e V (~P) = ~ V(P) Exemplo: (1) r: Roma é a capital da França (F) V (~r) = ~V(r) = ~F = V Na linguagem comum a negação efetua-se, nos casos mais simples, antepondo o advérbio “não” ao verbo da proposição dada. Assim, por exemplo, considerando a proposição: p : O Sol é uma estrela sua negação é : ~p : O Sol não é uma estrela Outra maneira de efetuar a negação consiste em antepor à proposição dada expressões tais como “não é verdade que”, “é falso que”. Assim, por exemplo, considerando a proposição: q : Carlos é mecânico sua negação é : ~q : Não é verdade que Carlos é mecânico Deve-se tomar um pouco de cuidado com a negação, porque, por exemplo a negação de “Todos os homens são elegantes” é “Nem todos os homens são elegantes” e a de “Nenhum homem é elegante” é “Algum homem é elegante”. 2.2. Conjunção ( . , ^ ) Definição: chama-se conjunção de duas proposições p e q a proposição representada por “p e q”, cujo valor lógico é a verdade (V) quando as proposições p e q são ambas verdadeiras a falsidade (F) nos demais casos. Simbolicamente, a conjunção de duas proposições p e q indica-se com a notação: “p . q”, que se lê: “p e q”. O valor lógico da conjunção de duas proposições é, portanto, definido pela seguinte tabela – verdade: p q p . q V V V V F F F V F F F F ou seja, pelas igualdades: V . V = V, V . F = F, F . V, F . F = F e (p ^ q) = V (p) ^ V (q) Exemplos: Apostila de Lógica para a computação 7 (1) {p: A neveé branca V q: 25V  } p . q: A neve é branca e 2 < 5 (V) V (p . q) = V(p) . V(q) = V . V = V (2) {p:O enxofre é verdeF q:7 é umnúmero primoV } p ^ q : O enxofre é verde e 7 é um número primo (F) V (p ^ q) = V(p) ^ V (q) = F ^ V = F 2.3. Disjunção ( v , + ) Definição: chama-se disjunção de duas proposições p e q a proposição representada por “p ou q”, cujo valor lógico é a verdade( V ) quando ao menos uma das proposições p e q é verdadeira e a falsidade (F) quando as proposições p e q são ambas falsas. Simbolicamente, a disjunção de duas proposições p e q indica-se com a notação: “p + q”, que se lê: “p ou q”. O valor lógico da disjunção de duas proposições é, portanto definido pela seguinte tabela – verdade: p q p + q V V V V F V F V V F F F V (p + q) = V (p) + V (q) Exemplos: (1) {p: Parisé a capital da FrançaV q:9−4=5 V  } p + q: Paris é a capital da França ou 9 – 4 = 5 (V) V (p + q) = V(p) + V(q) = V + V = V (2) {p:Camõesescreveuos LusíadasV 22=3F  } p + q : CAMÕES escreveu os Lusíadas ou 2 + 2 = 3 (V) V (p + q) = V(p) + V(q) = V + F = V 2.4. Disjunção Exclusiva ( ⊕, + ) Na linguagem comum a palavra “ou” tem dois sentidos. Assim, p. ex., consideremos as duas seguintes proposições compostas: P : Carlos é médico ou professor Q: Mário é alagoano ou gaúcho Na proposição P se está a indicar que uma pelo menos das proposições “Carlos é médico”, “Carlos é professor” é verdadeira, podendo ser ambas verdadeiras: “Carlos é médico e professor”. Mas, na proposição Q, é óbvio que uma e somente uma das proposições “Mário é alagoano”, “Mário é gaúcho” é verdadeira, pois, não é possível ocorrer “Mário é alagoano e gaúcho”. Na proposição P diz-se que “ou” é inclusivo, enquanto que, na proposição Q, diz-se que “ou” é exclusivo. Apostila de Lógica para a computação 10 7) Traduza para a linguagem comum, sabendo que p: os preços são altos e q: os estoques são grandes. a) (p.q) ->p b) (p.~q) ->~p c) ~p . ~q d) p+~q e) ~(p.q) f) ~(p+q) g) ~(~p+~q) 8) Seja p a proposição “Jorge é alto” e q a proposição “Jorge é elegante”. Traduzir, para a linguagem simbólica, as seguintes proposições: a) Jorge é alto e elegante. b) Jorge é alto mas não é elegante. c) Não é verdade que Jorge é baixo ou elegante. d) Jorge não é baixo e nem é elegante. e) Jorge é alto, ou é baixo e elegante. f) Não é verdade que Jorge é baixo ou que não é elegante. 9) Determinar o valor lógico (V + F) de cada uma das seguintes proposições compostas: a) Se 1 + 2 = 5, então 3 + 3 = 6 b) Não é verdade que 2 + 2 = 7 se e somente se 4 + 4 = 9 c) DANTE escreveu os Lusíadas ou 5 + 7 < 2 d) Não é verdade que 1 + 1 = 3 ou 20 = 1 e) É falso que , se Lisboa é a capital da França, então Brasília é a capital da Argentina. 10) Escrever simbolicamente para p: João é esperto, q: José é tolo. a) João é esperto e José é tolo. b) João é esperto ou José é tolo. c) João é esperto e José não é tolo 11) Seja p: Vanda é aluna e q: Sílvia é professora. Escreva simbolicamente: Vanda é aluna ou não é verdade que Sílvia seja professora e Vanda seja aluna. 12) Símbolo para: Vanda tem 5 anos ou se Vanda é bonita, então, é tagarela. 13) Dar os valores das proposições abaixo: a) (8 > 2) . (4 <=4) b) (6 < 10) . (6 > 3/2) c) (6 < 2) + ((4-3) >=1) d) (5 > 8) ⊕ (4>3) e) (4 < 2) + (2<4) f) (8-3= 5) -> (2 <= 2) g) (8>10) -> (6-2 = 4) h) (8>10) -> (6 < 5) i) (4 < 2 ) <-> (8-2 = 15) 14) Dar o valor da proposição p nos casos adiantes: a) V(p→q) = V e V(q) = V b) V(q→p) = V e V(q) = F c) V(q+p) = F e V(q) = F d) V(q+p) = V e V(q) = V 15) Considerando V(p) = F , V(x) = F e V(y) = V a) V(((p + q) . (x + y) ) → p ) = b) V(x . y → p ) = c) V(p . y . p . x ) = 16) Verificar se a informação dada é suficiente para determinar o valor da expressão: a) (p → s) → r, onde r tem o valor V b) (p+r)+(s → q), onde q tem valor F c) ((p+q ) ↔ (q.p)) → ((r.p)+q), onde o valor de q é V. d) ((p ↔ q) → p, onde o valor de q é V. e) ((p ↔ q ↔ p)→ p+q, onde o valor de q é V. f) (p+q → r.p+q), onde o valor de q é F. Apostila de Lógica para a computação 11 3. Tabelas-verdades de proposições compostas: Dadas várias proposições simples p,q,r,..., podemos combiná-las mediante o uso dos conectivos: ~, ., +, , ↔ e construir proposições compostas, tais como: (p.(~qp)). ~((p↔~q)(q+p)) Com o emprego das tabelas-verdades das operações lógicas fundamentais é possível construir a tabela-verdade correspondente a qualquer proposição composta dada. Logicamente, o valor-verdade final depende dos valores lógicos das proposições componentes. Exercício: 17) Construir as tabelas-verdades: a) (q.r) + m b) (q+r) → ((q+s) → (p+s)) c) (p → r ) → p d) (p → r ) ⊕ p e) (p → (q → r)) → ((p → q) → (p → r )) f) ~ (p + q) ↔ (~~p + ~q) 4. Tautologia, contradição e contingência (indeterminada) As fórmulas proposicionais podem apresentar os seguintes casos quanto às suas tabelas-verdades: a) Última coluna da tabela-verdade apresenta somente V(s)  Fórmula tautológica  Tautologia b) Última coluna da tab. - verdade apresenta somente F(s)Fórmula contra-válidaContradição c) Última coluna da tabela-verdade apresenta V(s) e F(s)  Fórmula indeterminada Exercícios: 18) Verificar quais fórmulas são contradições, tautologias ou indeterminadas. a) p ↔ p+p b) (a → b) → ((b → c) → (a → c)) c) (a → b ) . (b → a) d) ã → a ⊕ b e) a. (ã + b) f) ~(~p . q ) ↔ ~p + ~q 5. Implicação Lógica e Equivalência Lógica 5.1. Relação de implicação: uma proposição p implica uma proposição q se e somente se p → q for uma tautologia. Obs.: o símbolo → é de operação lógica e o símbolo ⇒ é de relação. Ex.: p . q ⇒ p ↔ q uma vez que a operação condicional → gera uma tautologia. Tabela-Verdade: Apostila de Lógica para a computação 12 Exercícios: 19) Verificar as implicações. a) p ⇒ p + q b) p . q ⇒ p c) (p + q) . ~p ⇒ q d) (p ↔ q) . p ⇒ q e) (p → (q→ r)) ⇒ q → (p → r) 5.2. Relação de Equivalência: uma proposição p é equivalente a uma proposição q se e somente se p ↔ q for uma tautologia. Obs.: o símbolo ↔ é de operação lógica e o símbolo ⇔ é de relação. Ex.: “p → q” e “ ~p + q “ são proposições logicamente equivalentes pois possuem a mesma tabela-verdade. Então dizemos: p → q ⇔ ~p+q Tabela-Verdade: Exercício: 20)Verificar as equivalências. a) ~(p.~p) ⇔ (p+~p) b) p.(~p+q) ⇔ (p.q) c) (p → (q → r)) ⇔ q → (p→ r) Apostila de Lógica para a computação 15 Exercícios para compreensão e fixação das regras de inferência: MP (→ E) a) ~p→q, ~p ├ q b) ~p→(q→r), ~p, q ├ r ~E c) t→ ~~p, p→~q, t ├ ~q d) ~p → ~~q, ~~~p ├ q . I e) p→ q, r→s, p, r ├ q . s . E f) p→ (q . r), p ├ p . q g) p . q ├ q . p h) (p . q) → (r . s), ~~p, q ├ s i) p ├ p . p j) ~p . q → u, ~~~p, s→q, x→r.s, x ├ u k) s → ((p.q)→~~r), p.q, t.s ├ r.t + I l) p ├ (p+q) . (p+r) m) p, ~~(p→q) ├ q+ ~q n) p, ~~(p→q) ├ (r.s)+q o) p ├ p+p + E p) Hoje é Sábado ou Domingo. Se hoje é Sábado, então é fim-de-semana. Se hoje é Domingo, então é fim-de-semana. Conclui-se que hoje é fim-de-semana. q) (p+q).(p+r), p→s, q→s, p→t,r→t ├ s.t r) p+p, p→(q.r) ├ r ↔ I s) p→q, (p→q) → (q→p) ├ p ↔ q t) p ↔ q ├ q ↔ p u) s→(r→p), a.s, p→r ├ (p↔r) + q v) ~~(p↔x), ~~(q→x), x.p→k, p+q, k↔u ├ u ↔ E w) Hoje é fim-de-semana se e somente se hoje for Sábado ou Domingo. Hoje é Sábado. Então, hoje é fim-de-semana. Regras hipotéticas: PC (→ I) a) i, (i.c)→~s, ~s→~a ├ c → ~a b) p → q, q→r ├ p→r c) p ├ (p→q) → q d) (p.q)→r ├ p→ (q→r) e) p + q ├ q + p f) (p.q) + (p.r) ├ p. (q+r) RAA ( ~I) g) p→q, ~q ├ ~p h) p ↔ ~q ├ ~(p.q) i) ~p →p ├ p j) s→~~v ├ ~v → ~s k) (~s.v)→~p, p, v ├ s l) ~(~p.~q), ~p ├ q m) ~p + ~q ├ ~(p . q) n) p→q ├ ~p+q o) ~ ( p . q) ├ ~p + ~q Exercícios complementares a) (g+n)  ~c ├ ~~c  ~(g+n) 1. Formalize e prove os seguintes argumentos usando as 10 regras de introdução e eliminação: c A conclusão deste argumento é verdadeira p As premissas deste argumento são verdadeiras s Este argumento é correto v Este argumento é válido a) Este argumento não é incorreto. Portanto, este argumento é correto. b) Este argumento é correto. Portanto, este argumento não é incorreto. c) Se este argumento for correto, então ele será válido. Ele não é válido.Portanto, ele não é correto. d) Se este argumento for correto então ele não será inválido. Ele é correto. Daí, ele é válido. e) Se este argumento for correto então ele não será inválido. Assim, se ele for inválido, então ele será incorreto. f) Este argumento é correto e válido. Portanto, Ele é correto ou ele é inválido. g) Este argumento não é, ambos, correto e inválido. Ele é correto. Portanto, ele é válido. h) Este argumento é correto sse todas suas premissas forem verdadeiras. Suas premissas não são verdadeiras. Portanto, ele é incorreto. i) Se a conclusão deste argumento for não-verdadeira, então este argumento é incorreto. Assim sendo, não é o caso que este argumento é correto e sua conclusão não-verdadeira. j) Se este argumento for incorreto e válido, nem todas as suas premissas são verdadeiras. Todas as suas premissas são verdadeiras. Ele é válido. Portanto, ele é correto. k) Se este argumento for válido e todas as suas premissas forem verdadeiras, então ele será correto. Se ele for correto, então sua conclusão é verdadeira. Todas suas premissas são verdadeiras. Portanto, se este argumento for válido então sua conclusão será verdadeira. l) Ou este argumento é incorreto ou, caso contrário ele é válido e todas suas premissas são verdadeiras. Então, ele é incorreto ou válido. Apostila de Lógica para a computação 16 Teoremas Teorema se diferencia de argumento pelo fato de não ter nenhuma premissa, somente conclusão. Sua prova é então baseada somente em hipóteses, que são descartadas por PC ou RAA. Exemplos: ├ P → (P+Q) ├ P → ((P → Q) → Q) ├ P ↔ ~~P ├ P + ~P Vimos em uma aula anterior equivalência lógica. Quando a bicondicional entre duas expressões resultar em uma tautologia dizemos que essas expressões são equivalentes. Através das regras de inferência podemos também provar a equivalência lógica entre duas expressões. Exemplo: para provar a equivalência entre as expressões: ~(P.Q) e ~P + ~Q representaríamos como na letra a): ├ ~(P.Q) ↔ ~P + ~Q ├ ~(P+Q) ↔ ~P . ~Q Estratégias para provas Não há uma forma única de se construir uma prova. Se um argumento pode ser provado, ele pode ser provado por diferentes trocas de regra. Então, algumas estratégias ajudam, embora alguns problemas requeiram ainda, habilidade e engenhosidade. Estratégias para prova. Se a conclusão for Então faça Fórmula atômica Fórmula negada Conjunção Disjunção Condicional Bicondicional Se nenhuma ação parece ser imediata, coloca-se como hipótese a negação da conclusão para RAA. Se isso for bem - sucedido, então a conclusão pode ser obtida depois de RAA por ~E. Coloca-se como hipótese a conclusão, sem o símbolo da negação, para RAA. Se resultar uma contradição, a conclusão pode ser obtida por RAA Prove cada um dos conjunctos, separadamente e então faça a conjunção deles com .I. - Tenta-se provar os condicionais necessários para +E caso tenha + nas premissas. - Se não der certo pode-se usar como hipótese a negação da conclusão e tenta-se RAA. - Pode-se também provar um dos seus disjunctos e aplicar +I. Coloca-se como hipótese o seu antecedente e deriva-se o seu conseqüente por PC. Use PC, duas vezes, para provar os dois condicionais necessários para se obter conclusão por ↔ I. As 10 regras de Inferência (permitido utilizar em prova) 1. Modus Ponens: ( E) (MP) do condicional (α β) e seu antecedente (α), podemos inferir seu conseqüente (β). 2. Eliminação da negação (~E): a partir de uma expressão ~~α, podemos inferir α. 3. Introdução da conjunção (.I): a partir de duas expressões válidas quaisquer α e β, inferimos conjunção das duas: α.β. 4. Eliminação da conjunção (.E): De uma conjunção qualquer α.β, podemos inferir α ou β. 5. Introdução da disjunção (+I): a partir de uma expressão α, podemos inferir a disjunção de α com qualquer expressão. 6. Eliminação da disjunção (+E): De expressões quaisquer, na seqüência α+β, αδ e βδ, podemos inferir δ 7. Introdução do bicondicional (↔I): de duas expressões quaisquer, na forma αβ e βα, podemos inferir α ↔β. 8. Eliminação do bicondicional (↔E): de uma expressão qualquer, na forma α ↔β, podemos então inferir αβ ou βα. 9. Introdução da implicação (I) (PC). Derivando β a partir de uma hipótese α, descartamos a hip. α e inferimos αβ. 10. Introdução da negação (~I ou RAA). Derivando β+~β a partir de uma hipótese α, descartar a hip. e inferimos ~α. Apostila de Lógica para a computação 17 Regras de Equivalência ou Álgebra das proposições 1. Lei da dupla negação:  ⇔  2. Idempotência: ⋅ ⇔  |  ⇔  3. Comutatividade: ⋅ ⇔ ⋅ |  ⇔  4. Associatividade: α.(β.γ) ⇔ (α.β).γ 5. Distributivas: α.(β+γ) ⇔ (α.β) + (α.γ) 6. De Morgan ⋅ ⇔  |  ⇔ ⋅ 7. Eliminação da Condicional: α→β ⇔  8. Eliminação da Bicondicional: α ↔ β ⇔ ⋅⋅ 9. Regras para Absorção: a) ⋅ ⇔  | ⋅ ⇔  b) ⋅ ⇔  c) ⋅ ⇔ F d)  ⇔ V e) ⋅V ⇔  f) ⋅F ⇔ F g) V ⇔ V h) F ⇔  Forma Normal Disjuntiva Literais: São letras sentenciais ou negações de letras sentenciais: a, ã, p Conjunção fundamental: conjunção de 2 ou mais literais sem repetir a letra sentencial: a.b, ã.c, ~b.c Forma Normal Disjuntiva: Diz-se que uma expressão está na FND se: a) é uma letra sentencial, b) uma conjunção fundamental ou c) a disjunção de 2 ou mais conjunções fundamentais, nenhuma das quais incluída em outra. Assinale as expressões que estão na FND: ( ) a.b.~c ( ) a.b + c ( ) a ( ) ã.b + ã.b ( ) a.~b.~c + a.b + a.~c ( ) a.b + c ( ) ã + ã.b ( ) a.b + c.~b Apostila de Lógica para a computação 20 Circuitos Lógicos Um circuito lógico nada mais é do que a combinação de várias portas lógicas com o objetivo de realizar uma determinada tarefa. O processador de um computador não deixa de ser um aglomerado de circuitos lógicos. Qualquer operação feita em um computador, por mais complexa que seja, é derivada de combinação de tarefas lógicas e aritméticas simples tais como somar bits, mover bits, etc. Pode-se implementar um circuito lógico simples em um circuito Integrado. Abaixo é apresentado o circuito MC54F/74F00 da Motorola, composto de várias portas NAND. Uma ferramenta bastante simples que pode ser utilizada para projetar e testar circuitos lógicos é a Digital Works. Abaixo são apresentadas as opções da ferramenta que aparecem na tela principal e os passos para projetar um pequeno circuito (1) (2) (3) 21 3 VCC GND Apostila de Lógica para a computação 21 Minimização A minimização consiste em determinar métodos para se encontrar um circuito mais simples (i.e. mais barato) equivalente a uma expressão (circuito) dada. Suponhamos uma determinada expressão. Existem várias formas de se minimizar essa expressão: 1- Utilizar as regras de equivalência para encontrar a FND mais simples que represente a expressão (função de verdade) dada 2- Utilizar o método figurativo denominado mapas de Karnaugh (somente pode ser utilizado para simplificar expressões que estão na FNDC. Mapas de Karnaugh É conveniente sua utilização para problemas que envolvam no máximo 6 letras sentenciais. Mapas de Karnaugh para 2 letras sentenciais Neste caso o mapa é baseado na figura 1. Cada quadrado do mapa representa uma conjunção fundamental entre as letras das linhas e colunas. Na fig.2 está sendo representado A.B + Ã.B Na fig.3 está sendo representado A.B + Ã.B + A.~B A \ B 0 1 A \ B 0 1 A \ B 0 1 0 0 0 1 1 1 Figura 1 Figura 2 Figura 3 O processo de simplificação consiste em juntar quadrados adjacentes de 2 em 2, tracando uma oval ao redor de cada par. O literal que difere de um quadrado para outro deixa de existir. Neste caso, dois quadrados adjacentes representam uma única letra sentencial. Veja o ex. da fig. 2. Não deve-se deixar nenhum ponto “solto” no mapa, devendo cuidar para fazer o menor número possível de ligações. Para todos os tipos de mapas, quando se tem todos os quadrados preenchidos, a simplificação resulta em V (Veja a representação de AB+ÃB+A~b+Ã~B na fig. 4) Mapas de Karnaugh para 3 letras sentenciais Neste caso, o mapa pode ser montado como na figura 5 ou como na figura 6. Ex: Ã~B~C+ ÃB~C (figuras 5 e 6) deve-se cuidar apenas o seguinte detalhe. Nesses mapas foi utilizada a rotulação 00,01,11,10 de forma que quando se passa de um quadrado para o quadrado adjacente muda-se apenas um literal. Um ponto isolado no mapa representa a conjunção de 3 literais. Exemplo: ABC na figura 7. Dois quadrados adjacentes diferem em apenas um literal. Isso significa que o literal que difere de um quadrado para outro deixa de existir. Exemplo: Figura 8. AB \ C 0 1 00 01 11 10 Figura 6 A \ BC 00 01 11 10 0 1 Figura 5 A \ B 0 1 0 1 Figura 4 Apostila de Lógica para a computação 22 Quatro quadrados formando uma rede quadrada ou arranjados em linha representam um único literal. Figuras 9 e10. Resolva: a) ã~b~c+a~bc+abc+ab~c b) ã~b~c+a~b~c+a~bc+abc+ab~c+ãb~c c) bac+a~bc+ãbc+ab~c+ãb~c d) ã~b~c+a~b~c+a~bc+abc+ãb~c Mapas de Karnaugh para 4 letras sentenciais É semelhante ao mapa de 3 letras sentenciais. Neste caso, uma linha inteira ou coluna inteira representa a conjunção de 2 letras sentenciais. a) ab.~c.~d+ab~cd+abc+abcd b) ab~c.~d+a~b~c.~d+ãb~c.~d+~a~b~c~d c) ã~b~cd+a~bcd+abcd+ab~cd d) ã~b~c.d+a~b~c.~d+a~bc.d+abc~d+ab~c~d+ãb~c~d A \ BC 00 01 11 10 0 1 Figura 7 A \ BC 00 01 11 10 0 1 Figura 8 A \ BC 00 01 11 10 0 1 Figura 9 A \ BC 00 01 11 10 0 1 Figura 10 A \ BC 00 01 11 10 0 1 c) A \ BC 00 01 11 10 0 1 d) A \ BC 00 01 11 10 0 1 a) A \ BC 00 01 11 10 0 1 b) A \ BC 00 01 11 10 00 01 11 10 a) A \ BC 00 01 11 10 00 01 11 10 b) A \ BC 00 01 11 10 00 01 11 10 A \ BC 00 01 11 10 00 01 11 10 Apostila de Lógica para a computação 25 10)Considerando um esquema de transformação de um número de OCTAL (base 8) para binário (base 2), onde há 7 LEDS representando os números octais (de 0 até 7) sendo que por exemplo, para representar o número 4 deve-se deixar ligado somente o LED do dígito 4 (D4) na entrada, construa um circuito lógico onde as 3 saidas (LEDS) representem (em binário) o número colocado na entrada. ENTRADAS SAÍDAS D1 D2 D3 D4 D5 D6 D7 Decimal X Y Z 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 2 0 1 0 0 0 1 0 0 0 0 3 0 1 1 0 0 0 1 0 0 0 4 1 0 0 0 0 0 0 1 0 0 5 1 0 1 0 0 0 0 0 1 0 6 1 1 0 0 0 0 0 0 0 1 7 1 1 1 13) Construa um circuito lógico para simular 2 sinaleiras de uma rua, uma em sentido contrário à outra, cada uma contendo as 3 luzes (verde, amarela e vermelha) de forma que quando uma abre, a outra feche seguindo a sequência: Trabalho (em duplas e deve ser entregue até dia ______) --> Invente 3 exercícios semelhantes aos anteriores (parte prática) e resolva-os. Endereços sugeridos para material extra: http://fiddle.visc.vt.edu/courses/ee2504/combinational/logic_01.html http://www.eece.unm.edu/faculty/devries/Net/Homework/boolean.html Apostila de Lógica para a computação 26 Exercícios de Lógica -Parte prática – Resolução do 12 e 13 12) Considerando um esquema de transformação de um número de OCTAL (base 8) para binário (base 2), onde há 7 LEDS representando os números octais (de 0 até 7) sendo que por exemplo, para representar o número 4 deve-se deixar ligado somente o LED do dígito 4 (D4) na entrada, construa um circuito lógico onde as 3 saidas (LEDS) representem (em binário) o número colocado na entrada. ENTRADAS SAÍDAS D1 D2 D3 D4 D5 D6 D7 Decimal X Y Z 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 2 0 1 0 0 0 1 0 0 0 0 3 0 1 1 0 0 0 1 0 0 0 4 1 0 0 0 0 0 0 1 0 0 5 1 0 1 0 0 0 0 0 1 0 6 1 1 0 0 0 0 0 0 0 1 7 1 1 1 X = D4 + D5 + D6 + D7 : Na verdade o correto seria ~D1.~D2.~D3.D4.~D5.~D6.~D7 + ..., mas supõe-se que o usuário só escolha 1 dígito (D4) no caso. Y = D2 + D3 + D6 + D7 Z = D1 + D3 + D5 + D7 O exercício está resolvido. Apenas como curiosidade, poderia-se fazer aparecer o número em um mostrador digital. Dessa forma, segundo o exemplo acima, um mostrador deveria mostrar o número 5. Para isso, inicialmente teríamos que inserir um LED e desenhar todos os números de 1 a 7: Em seguida devemos, para cada um dos números de 0 até 7, indicar quais leds deverão ser acesos: X Y Z L1 L2 L3 L4 L5 L6 L7 0 0 0 1 1 1 1 1 1 0 0 1 1 1 0 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 L1 L2 L3 L4 L5 L6 L7 00 01 11 10 00 01 11 10 00 01 11 10 00 01 11 10 00 01 11 10 00 01 11 10 00 01 11 10 0 . . . 0 . . . . 0 . . . 0 . . . 0 . . 0 . 0 . . 1 . . . 1 . . 1 . . . . 1 . . 1 . 1 . . . 1 . . . L1= L2= L3= L4= L5= L6= L7= Podemos agora, definir o circuito independente de cada uma das “partes” do LED, pois como exemplo, a parte “L1” ficará ligada quando tivermos um destes números: 0,2,3,5,6,7. O circuito para a “parte” do LED L1 então seria: Devemos depois, simplificar o circuito da “parte” L1 através de mapa de karnaugh bem como os circuitos das outras partes (L2-L7). Apostila de Lógica para a computação 27 O circuito final é apresentado abaixo: 13) Construa um circuito lógico para simular 2 sinaleiras de uma rua, uma em sentido contrário à outra, cada uma contendo as 3 luzes (verde, amarela e vermelha) de forma que quando uma abre, a outra feche seguindo a sequência: X Y Z L1 L2 L3 L4 L5 L6 0 0 0 1 1 0 0 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 1 1 Como são seis lâmpadas de sinaleira no total (considerando as 2 sinaleiras) devemos construir 6 circuitos independentes. Como são 6 combinações de sinaleiras, precisamos de pelo menos 3 bits, que possibilita 8 combinações (0-7). L1 L2 L3 L4 L5 L6 00 01 11 10 00 01 11 10 00 01 11 10 00 01 11 10 00 01 11 10 00 01 11 10 0 . . . 0 0 . 0 . . 0 . 0 . 1 . 1 . 1 1 . . 1 1 L1= L2= L3= L4= L5= L6= L1 L2 L3 L4 L5 L7 L6 L1 L2 L3 L4 L5 L6 - No estágio 1 teremos as lâmpadas 1 e 6 acesas (L1 e L6) - No estágio 2 teremos as lâmpadas 1 e 5 acesas (L1 e L5) - No estágio 3 teremos as lâmpadas 1 e 4 acesas (L1 e L4) - No estágio 4 teremos as lâmpadas 3 e 4 acesas (L3 e L4) - No estágio 5 teremos as lâmpadas 2 e 4 acesas (L2 e L4) - No estágio 6 teremos as lâmpadas 1 e 4 acesas (L1 e L4) Devemos agora construir os 6 circuitos: L1, L2, L3, L4, L5 e L6