Baixe Apostila de Introdução à Lógica e outras Notas de estudo em PDF para Informática, somente na Docsity! U N I M I N A S Sistemas de Informação Disciplina: Lógica para Computação Prof. Walteno Martins Parreira Júnior www.waltenomartins.com.br waltenomartins@yahoo.com 2009 Lógica Para Computação Prof. Walteno Martins Parreira Jr Página 1 1 – INICIAÇÃO À LÓGICA A lógica iniciou seu desenvolvimento na Grécia Aristóteles (384 – 322 AC) e os antigos filósofos gregos passaram a usar em suas discussões sentenças enunciadas nas formas afirmativa e negativa, resultando em grande simplificação e clareza. Em 1847, Augustus DeMorgam (1806-1871) publicou o tratado Formal Logic. Em 1848, George Boole (1815-1864) escreveu The Mathematical Analysis of Logic e depois publicou um livro sobre o que foi denominado posteriormente de Álgebra de Boole. Em 1879, Gotlob Frege (1848-1925) contribuiu no desenvolvimento da lógica com a obra Begriffsschrift. As idéias de Frege só foram reconhecidas pelos lógicos mais ou menos a partir de 1905. A escola italiana, que desenvolveu quase toda simbologia da matemática utilizada atualmente, é composta de Giuseppe Peano (1858-1932) e também por Burali-Forti, Vacca, Pieri, Pádoa, Vailati, etc. Bertrand Russell (1872-1970) e Alfred North Whitehead (1861-1947) iniciam o atual período da lógica com a publicação da obra Principia Mathematica no início do século XX. Também contribuem para o estágio atual, David Hilbert (1862-1943) e sua escola alemã com von Neuman, Bernays, Ackerman e outros. Em 1938, Claude Shannon mostrou a aplicação da álgebra de Boole na analise de circuitos de relês. Podemos dizer que a lógica estuda as condições objetivas e ideais para justificar a verdade e não cuida da própria verdade. Ela estuda as condições formais para justificar a verdade, isto é, as condições que o pensamento deve preencher para ser coerente consigo mesmo e demonstrar a verdade já conhecida. A lógica estuda as relações do pensamento consigo mesmo para possibilitar a construção de um contexto correto de justificação, isto é, para a definição argumentativa de premissas corretamente dispostas para uma conclusão justificada. Uma das condições para se ter a verdade demonstrada, e portanto justificada, é que o pensamento seja coerente consigo mesmo, isto é, que siga as leis da razão expressa linguisticamente. 1.1 - PROPOSIÇÃO Definição: todo conjunto de palavras ou símbolos que exprimem um pensamento de sentido completo. As proposições transmitem pensamentos, isto é, afirmam fatos ou exprimem juízos que formamos a respeito de determinados entes. Exemplos: Japão está situado no continente africano. A lâmpada da sala está acesa. A cidade de Recife é a capital de Pernambuco. Na linguagem natural nos acostumamos com vários tipos de proposições ou sentenças: a) Declarativas Márcio é engenheiro. Todos os homens são mortais. sen (π/2) = 1 A lua gira em torno da terra. b) Interrogativas Será que o Roberto vai ao cinema hoje? Lógica Para Computação Prof. Walteno Martins Parreira Jr Página 4 1.7 – PROPOSIÇÕES COMPOSTAS Definição: são as proposições formadas por duas ou mais proposições simples e ligadas pelos conectivos lógicos. Exemplos: P: Carlos é careca e Pedro é estudante. Q: Carlos é careca ou Pedro é estudante. R: Se Carlos é careca, então Carlos é infeliz. S: Carlos é careca se, e somente se Pedro é estudante. 1.8 – TABELA-VERDADE Segundo o Princípio do terceiro excluído, toda proposição simples P é verdadeira ou é falsa, isto é, tem valor lógico V (verdade) ou o valor lógico F (falsidade). Em uma proposição composta, a determinação do seu valor lógico é feito segundo o princípio: “O valor lógico de qualquer proposição composta depende unicamente dos valores lógicos das proposições simples componentes, ficando por eles univocamente determinado.” Para aplicar este princípio na prática, recorre-se ao uso do dispositivo denominado Tabela-verdade, que apresenta todos os possíveis valores lógicos da proposição composta correspondentes a todas as possíveis atribuições de valores lógicos às proposições simples correspondentes. O número de linhas da tabela-verdade de uma proposição composta está em função do número de proposições simples que a compõem. A tabela-verdade de uma proposição composta com n proposições simples contém 2n linhas. Portanto, podemos observar: a) Para uma proposição simples P, o numero de linhas da tabela-verdade será: 21 = 2, representando na tabela-verdade: P V F b) Para uma proposição composta cujas proposições simples componentes são P e Q, o número de linhas da tabela-verdade será: 22 = 4 , que será representada: P Q V V V F F V F F Lógica Para Computação Prof. Walteno Martins Parreira Jr Página 5 c) Para uma proposição composta cujas proposições simples componentes são P, Q e R, o número de linhas da tabela-verdade será: 23 = 8 , que será representada: P Q R V V V V V F V F V V F F F V V F V F F F V F F F Observe que os valores lógicos V e F se alternam de quatro (4) em quatro para a primeira proposição (P), de dois (2) em dois para a Segunda proposição (Q) e de um (1) em um para a terceira proposição (R). 1.9 – OPERAÇÃO LÓGICA 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 é a verdade (V) quando P é falsa e a falsidade (F) quando P é verdadeira. Simbolicamente, a negação de P indica-se com a notação “~P”, que se lê: “NÃO P” A tabela-verdade: P ~P V F v(~P) = ~ v(P) F V Para uma proposição P, podemos formar a sua negação de qualquer um dos seguintes modos: “não é verdade que P” “é falso que P” “não“ em P Exemplo: P: Lídia é estudiosa. ~P: Não é verdade que Lídia é estudiosa. ~P: É falso que Lídia é estudiosa. ~P: Lídia não é estudiosa. Observações: Pode-se ter algumas variações, por necessidades da língua portuguesa, por exemplo: P: Todos os homens são elegantes. Lógica Para Computação Prof. Walteno Martins Parreira Jr Página 6 ~P: Nem todos os homens são elegantes. Q: Nenhum homem é elegante. ~Q: Algum homem é elegante. 1.10 – OPERAÇÃO LÓGICA 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 e 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”. A tabela-verdade: P Q P ∧ Q V V V V F F v(P∧Q) = v(P) ∧ v(Q) F V F F F F Exemplo: P: Pitágoras era Grego Q: Descartes era Francês P ∧ Q: Pitágoras era Grego e Descartes era Francês. v(P) = V e v(Q) = V ⇒ v(P ∧ Q) = V 1.11 – OPERAÇÃO LÓGICA DISJUNÇÃO 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 conjunção de duas proposições P e Q indica-se com a notação “P ∨ Q “, que se lê “P OU Q”. A tabela-verdade: P Q P ∨ Q V V V V F V v(P∨Q) = v(P) ∨ v(Q) F V V F F F Exemplo: P: A cidade de Paris é a capital da França Q: O sol é um satélite artificial da terra Lógica Para Computação Prof. Walteno Martins Parreira Jr Página 9 1.14 – ORDEM DE PRECEDENCIA DOS CONECTORES Para reduzir o número de parêntesis necessários em uma proposição composta (fórmula lógica proposicional), estipula-se uma ordem na qual os conectores são aplicados. A ordem de precedência é: maior a) conectivos dentro de parêntesis, do mais interno para o mais externo b) ~ c) ∧ d) ∨ e) → f) ↔ menor Quando há dois ou mais conectivos de mesma ordem de precedência, o conectivo mais a esquerda na fórmula proposicional tem prioridade sobre o conectivo à direta. Exemplos: a) “p ∨ ~ q “ eqüivale a “ ( p ∨ ( ~ q ) ) ” b) “p ∨ q → r “ eqüivale a “ ( ( p ∨ q ) → r ) “ c) “p ∨ q ∧ r → p ∧ q “ eqüivale a “( ( p ∨ ( q ∧ r ) ) → ( p ∧ q ) ) “ p ∨ q ∧ r → p ∧ q 1º 2º 3º 4º Lógica Para Computação Prof. Walteno Martins Parreira Jr Página 10 Exercício: Obter a fórmula proposicional a partir de sua tabela- verdade: P Q ? V V V V F V F V F F F F PASSOS NECESSÁRIOS PARA RESOLUÇÃO: a) Selecionar todos os resultados com valor lógico verdade (V); e selecionar todos com valor lógico falsidade (F); b) Fazer a conjunção de cada linha da tabela, se o valor lógico da proposição simples for falsidade (F), faz-se a negação da proposição; P Q ? V V V p ∧ q V F V p ∧ ~q F V F ~p ∧ q F F F ~p ∧ ~q c) Fazer a disjunção das linhas da tabela-verdade que tem como resultado o mesmo valor lógico, isto é, se tiver mais de uma linha com o mesmo resultado; P Q ? V V V p ∧ q V F V p ∧ ~q R1: ( p ∧ q ) ∨ ( p ∧ ~q ) F V F ~p ∧ q F F F ~p ∧ ~q R2: ( ~p ∧ q ) ∨ ( ~p ∧ ~q ) d) Fazer a negação da expressão originada da(s) linha(s) que tem o valor lógico falsidade(F); R1: ( p ∧ q ) ∨ ( p ∧ ~q ) Solução dos valores lógicos verdade (V) R2: ~( ( ~p ∧ q ) ∨ ( ~p ∧ ~q )) Solução dos valores lógicos falsidade (F) e) Montar a tabela-verdade da expressão encontrada para mostrar a equivalência entre a expressão e a tabela-verdade original. P Q ~q P ∧ q p ∧ ~q ( p ∧ q ) ∨ ( p ∧ ~q ) V V F V F V V F V F V V F V F F F F F F V F F F P Q ~p ~q ~P ∧ q ~p ∧ ~q ( ~p ∧ q ) ∨ ( ~p ∧ ~q ) ~(() ∨ ()) V V F F F F F V V F F V F F F V F V V F V F V F F F V V F V V F Lógica Para Computação Prof. Walteno Martins Parreira Jr Página 11 2 – TAUTOLOGIA, CONTIGENCIA E CONTRADIÇÃO 2.1 – TAUTOLOGIA Definição: denomina-se tautologia a proposição composta que é sempre verdadeira. Na tabela-verdade de uma proposição tautológica, a última coluna (à direita) contém somente V’s (verdade). Em outros termos, tautologia é toda proposição composta P (p,q,r,...) cujo valor lógico é sempre V (verdade), quaisquer que sejam os valores lógicos das proposições simples componentes p, q, r, ... As tautologias são também denominadas proposições tautológicas ou proposições logicamente verdadeiras. Exemplo: a proposição “ ~( p ∧ ~p) “ denominado de Princípio da não contradição é tautológica, conforme se vê pela tabela-verdade: p ~p p ∧ ~p ~( p ∧ ~p ) V F F V F V F V Portanto, dizer que uma proposição não pode ser simultaneamente verdadeira e falsa é sempre verdadeiro. 2.2 – CONTRADIÇÃO Definição: denomina-se contradição a proposição composta que é sempre falsa. Na tabela-verdade de uma proposição contraditória, a última coluna (à direita) contém somente F’s (falsidade). Como uma tautologia é sempre verdadeira (V), a negação de uma tautologia é sempre falsidade (F), ou seja, é uma contradição e vice-versa. As contradições são também denominadas proposições contraválidas ou proposições logicamente falsas. Exemplo: a proposição “ p ↔ ~p “é uma contradição, conforme se vê pela tabela- verdade: p ~p p ↔ ~p V F F F V F Exercício: Dada a proposição composta abaixo, determinar se a proposição é uma contradição. a) ( p ∧ q ) ∧ ~( p ∨ q ) b) ~p ∧ ( p ∧ ~q ) 2.3 – CONTIGÊNCIA Definição: denomina-se contingência a proposição composta que pode ser verdadeira e pode ser falsa. Na tabela-verdade de uma proposição contigencial, a última coluna (à direita) contém V’s (verdadeiros) e F’s (falsidades), cada um pelo menos uma vez. Lógica Para Computação Prof. Walteno Martins Parreira Jr Página 14 3 – IMPLICAÇÕES LÓGICAS O estudo da implicação lógica é de grande relevância na lógica. As implicações lógicas que serão tratadas levarão em conta a condicional como implicação material. O símbolo “→” representa uma operação entre duas proposições, resultando uma nova proposição. O símbolo “⇒” indica apenas uma relação entre duas proposições dadas. Exemplo: Dadas as proposições p ∧ q e p ∨ q, a relação de implicação lógica entre elas é denotada por p ∧ q ⇒ p ∨ q. Resolução: desenvolvendo a tabela-verdade. p q p ∧ q p ∨ q p ∧ q → p ∨ q V V V V V V F F V V F V F V V F F F F V Como o resultado (última coluna à direita) é uma Tautologia, logo a relação é Verdadeira. 3.1 – IMPLICAÇÃO ENTRE PROPOSIÇÕES Diz-se que uma proposição p implica logicamente uma proposição q quando, em suas tabelas-verdade, não ocorre “VF” nesta ordem. Exemplo: verificar se p ⇒ q → p p q q → p V V V V F V F V F F F V Comparando os valores lógicos da coluna p com os valores lógicos da coluna q → p, verificamos que não ocorre “VF” em nenhuma linha, logo p ⇒ q → p é uma relação válida. Desenvolvendo a tabela-verdade temos: p q q → p p → (q → p) V V V V V F V V F V F V F F V V Observando o resultado da tabela- verdade, podemos ver que a proposição p → (q → p) é uma tautologia, logo a relação p ⇒ q → p é verdadeira 3.2 – IMPLICAÇÃO ENTRE SENTENÇAS ABERTAS Diz-se que uma sentença aberta implica uma outra sentença aberta quando o conjunto- verdade de uma delas está contido no conjunto-verdade da outra. Exemplo: Julgar a sentença x – 3 = 0 ⇒ x2 = 9 Resolução: Determinando o conjunto-verdade da primeira sentença aberta: x – 3 = 0 temos que x = 3 logo, V1 = { 3 } Determinando o conjunto-verdade da segunda sentença aberta: x2 = 9 x = ± 3 logo, V2 = { -3, 3 } Podemos observar que { 3 } ⊂ { -3, 3 } Portanto, podemos dizer que a implicação é verdadeira, logo a sentença x – 3 = 0 ⇒ x2 = 9 está correta 3.3 – PROPRIEDADES DAS IMPLICAÇÕES LÓGICAS São: 1) A condição necessária e suficiente para que uma implicação p ⇒ q seja verdadeira é que uma condicional p → q seja uma tautologia; 2) Propriedade reflexiva: p ⇒ p; 3) Propriedade transitiva: Se p ⇒ q e q ⇒ r, então p ⇒ r. 3.4 – IMPLICAÇÕES NOTÁVEIS Estas implicações são consideradas notáveis (ou clássicas), pois são argumentos válidos fundamentais, usados para fazer “inferências”, isto é, executar os “passos” de uma demonstração ou de uma dedução. Também chamadas de Regras de Inferência. a) Adição p ⇒ p ∨ q q ⇒ p ∨ q p q p ∨ q p q p ∨ q V V V V V V V F V V F V F V V F V V F F F F F F Não há “VF”, logo p ⇒ p ∨ q Não há “VF”, logo q ⇒ p ∨ q b) Conjunção p ∧ q ⇒ p e p ∧ q ⇒ q q ∧ p ⇒ p e q ∧ p ⇒ q c) Simplificação p ∧ q ⇒ p p ∧ q ⇒ q d) Simplificação Disjuntiva (p ∨ q) ∧ (p ∨ ~q) ⇒ p e) Absorção p → q ⇒ p → (p ∧ q) f) Regra Modus Ponens Lógica Para Computação Prof. Walteno Martins Parreira Jr Página 16 ( p → q) ∧ p ⇒ q g) Regra Modus Tollens ( p → q) ∧ ~q ⇒ ~p h) Regra do Silogismo Disjuntivo (p ∨ q) ∧ ~p ⇒ q (p ∨ q) ∧ ~q ⇒ p i) Silogismo Hipotético (p → q) ∧ (q → r) ⇒ p → r j) Dilema Construtivo ( (p → q) ∧ (r → s) ∧ (p ∨ r) ) ⇒ q ∨ s k) Dilema Destrutivo ( (p → q) ∧ (r → s) ∧ (~p ∨ ~s) ) ⇒ ~p ∨ ~r 3.5 – TEOREMA CONTRA-RECÍPROCO A proposição “p(x) ⇒ q(x) é verdadeira se, e somente se “~q(x) ⇒ ~p(x)” é verdadeira. Assim, afirmar “Se p, então q” é o mesmo que afirmar “se ~q, então ~p”. Portanto, “p(x) ⇒ q(x)” é equivalente a “~q(x) ⇒ ~p(x)”. Exemplo: A sentença “Se comeu, então matou a fome” é equivalente a “Se não matou a fome, então não comeu”. 3.6 – RELAÇÃO ENTRE IMPLICAÇÕES a) Implicações recíprocas p ⇒ q e q ⇒ p Duas proposições recíprocas não são logicamente equivalentes, uma pode ser verdadeira sem que a outra o seja. b) Implicações Inversas p ⇒ q e ~p ⇒ ~q Duas proposições inversas não são logicamente equivalentes, uma pode ser verdadeira sem que a outra o seja. c) Implicações Contrapositivas p ⇒ q e ~q ⇒ ~p Duas proposições contrapositivas são logicamente equivalentes, sempre que uma é verdadeira, a outra também será. 3.7 – EQUIVALENCIAS ENTRE IMPLICAÇÕES a) p ⇒ q ⇔ ~q ⇒ ~p b) p ⇒ q ⇔ ~ (p ∧ ~q) c) p ⇒ q ⇔ ~p ∨ q Lógica Para Computação Prof. Walteno Martins Parreira Jr Página 19 p ∧ (q ∨ r) ⇔ (p ∧ q) ∨ (p ∧ r) p ∨ (q ∧ r) ⇔ (p ∨ q) ∧ (p ∨ r) G) Condicionais Das proposições: i) p → q (condicional) ii) q → p (recíproca da condicional) iii) ~q → ~p (contrapositivo) iv) ~p → ~q (recíproca do contrapositivo) resultam as duas equivalência: p → q ⇔ ~q → ~p q → p ⇔ ~p → ~q H) Bicondicionais p ↔ q ⇔ (p → q) ∧ (q → p) p q p ↔ q p → q q → p (p → q) ∧ (q → p) V V V V V V V F F F V F F V F V F F F F V V V V Desenvolver as provas por tabela-verdade. iguais, logo equivalentes Lógica Para Computação Prof. Walteno Martins Parreira Jr Página 20 5 – MÉTODOS PARA DETERMINAÇÃO DA VALIDADE DE FÓRMULAS São métodos usados para determinar ou verificar se a fórmula lógica proposicional é válida ou quais os valores lógicos apresentados. 5.1 – MÉTODO DA TABELA-VERDADE O método da Tabela-verdade é o método da força bruta utilizado na determinação da validade de fórmulas da lógica proposicional. No método da tabela-verdade são consideradas todas as possibilidades de valores de verdade associados a esses símbolos proposicionais. Na coluna de resultado, observamos uma das três soluções: Tautologia, Contradição ou Contingência. 5.2 – ÁRVORE SEMÂNTICA DEF. Uma árvore é um conjunto de nós ou vértices ligados por arestas ou ramos, conforme é indicado na figura abaixo. Os nós são rotulados por números inteiros, e os nós finais (na figura: 2, 6, 7 e 5) são denominados de folhas. 1 2 3 4 5 6 7 DEF. Uma árvore semântica é uma árvore na qual os vértices internos representam proposições, as arestas representam os valores lógicos de uma proposição e as folhas representam os resultados finais e que serve para determinar a validade de uma fórmula (ou proposição) a partir da estrutura de dados do tipo árvore. Exemplos: 1) Dada a proposição “p ∨ q”, determinar se a proposição é tautologia, contradição ou contingência. 1 v(q) = V v(q) = F 2 3 v(p) = V v(p) = F v(p)=V v(p)=F 4 5 6 7 V V V F portanto, é uma contingência. 2) Dada a proposição “p ∨ ~ ( p ∧ q )”, determinar se a proposição é tautologia, contradição ou contingência. Folha Raiz Ramo p q p ∨ q V V V V F V F V V F F F Nó Lógica Para Computação Prof. Walteno Martins Parreira Jr Página 21 1 v(q)=V v(q)=F 2 3 v(p)=V v(p)=F V 4 5 V V CONCLUSÃO: como todas as folhas tem valor lógico V (verdade), então a fórmula proposicional é tautologia. 3) Dada a proposição “p ∨ ( p ∧ ~ q )”, determinar se a proposição é tautologia, contradição ou contingência. 1 v(p)=V v(p)=F 2 3 V F CONCLUSÃO: Como aparecem V e F, logo temos uma contingência. Exercícios: 1) Determinar, usando árvore semântica, quais das proposições abaixo são tautologia, contradição ou contingência. a) ( p ∨ ( p ∧ q )) ↔ p b) ( ~p ∧ ~q ) ∨ ( p → q ) c) ( p ∨ ~q ) ↔ (( p → r ) ∨ q ) 2) Determinar, usando árvore semântica, a validade da relação abaixo: a) p ∧ q ⇒ p b) ( p ∧ q ) ⇒ ( p ∧ ~q ) c) ~p ∧ ~p ⇔ ~p d) ~ ( ~ ( p ∨ q )) ⇔ p ∨ q e) p ∨ q ⇔ p nó 2: p ∨ ~ ( p ∧ q ) ? ? V nó 3: p ∨ ~ ( p ∧ q ) ? ? F V F V nó 4: p ∨ ~ ( p ∧ q ) V V V F V V nó 5: p ∨ ~ ( p ∧ q ) F F V V F V nó 2: p ∨ ( p ∧ ~ q ) V V ? V nó 3: p ∨ ( p ∧ ~q ) F F ? F F Lógica Para Computação Prof. Walteno Martins Parreira Jr Página 24 6 – ÁLGEBRA DE BOOLE 6.1 – INTRODUÇÃO O matemático inglês George Boole (1815-1864) desenvolveu a álgebra booleana em 1854. Boole estava interessado em regras “algébricas” para o raciocínio lógico, semelhantes às regras algébricas para o raciocínio numérico. É uma maneira formal para escrever e manipular proposições lógicas como se fosse uma fórmula algébrica. Em 1938, Claude Shannon demonstra a aplicação da álgebra booleana na análise de circuitos à relês. A eletrônica digital, que usa dígitos binários, utiliza alguns circuitos lógicos básicos conhecidos como portas OU, E, NÃO, ... através da utilização conveniente desses circuitos, podemos “implementar” todas as expressões geradas pela álgebra de Boole. Há uma relação entre a estrutura de álgebra de Boole e os diagramas para os circuitos elétricos em computadores, calculadoras, dispositivos industriais de controle, sistemas de telecomunicações, etc. 6.2 – CIRCUITOS LÓGICOS Chamamos interruptor ao dispositivo ligado a um ponto do circuito elétrico, que pode assumir um dos dois estados: fechado (1) ou aberto (0). Quando fechado, o interruptor permite que a corrente elétrica passe através do ponto, e quando aberto nenhuma corrente elétrica pode passar pelo ponto. Representação: aberto fechado A A Por conveniência, representamos os interruptores da forma: A neste caso, somente conhecemos o estado do interruptor se tivermos a indicação de que A=1 ou A=0. 6.3 – VARIÁVEIS E EXPRESSÕES NA ÁLGEBRA DE BOOLE As variáveis booleanas, que são representadas através de letras, podem assumir apenas dois valores: 0 e 1. Expressão booleana é uma expressão matemática cujas variáveis são booleanas e seu resultado assumirá apenas dois valores: 0 e 1. 6.4 – POSTULADOS a) Postulado da Complementação Chamamos de A’ o complemento de A. Dizemos “A BARRA”. Poder ser: A i) se A = 0 então A’ = 1 Lógica Para Computação Prof. Walteno Martins Parreira Jr Página 25 ii) se A = 1 então A’ = 0 através do postulado da complementação, podemos estabelecer a seguinte identidade: A’’ = A b) Postulado da Adição i) 0 + 0 = 0 ii) 0 + 1 = 1 iii) 1 + 0 = 1 iv) 1 + 1 = 1 através deste postulado, podemos estabelecer as seguintes identidades: i) A + 0 = A ii) A + 1 = 1 iii) A + A = A iv) A + A’ = 1 O Circuito lógico que executa o postulado da adição é o circuito OU, representado por “dois interruptores em paralelo”, com a representação: A A + B B c) Postulado da Multiplicação i) 0 • 0 = 0 ii) 0 • 1 = 0 iii) 1 • 0 = 0 iv) 1 • 1 = 1 através deste postulado, podemos estabelecer as seguintes identidades: i) A • 0 = 0 ii) A • 1 = A iii) A • A = A iv) A • A’ = 0 O circuito lógico que executa o postulado da multiplicação booleana é o circuito E, representado por dois interruptores em série, cuja representação é: A B A • B Lembrar que: p ∨ q Lembrar que: p ∧ q Lógica Para Computação Prof. Walteno Martins Parreira Jr Página 26 6.5 – OBSERVAÇÕES a) Neste primeiro momento, usaremos somente três operadores: Lógica Booleana Lógica Proposicional conectivo Exemplo Booleano Exemplo Proposicional • ∧ E p • q p ∧ q + ∨ OU p + q p ∨ q − ou ’ ~ NÃO ( p + q )’ ~ ( p ∨ q ) b) 1 + 1 = 1, visto que não existe o 2 na lógica booleana. Define-se, por convenção que 1 + 1 = 1, porque em lógica booleana o 1 corresponde a V (verdade) e como o valor lógico de V ∨ V é V no cálculo preposicional, então temos 1 como resultado. c) As regras para formar expressões válidas em álgebra booleana são as mesmas para formar fórmulas lógicas no cálculo proposicional: i) Uma variável é uma expressão booleana: p; ii) Se p é uma expressão booleana, então também é o p’; iii) Se p e q são expressões booleanas, então também são o p • q e p + q; iv) Se p é uma expressão booleana, então também é o ( p ). d) As regras esquerda-para-direita e a precedência dos operadores para avaliação de fórmulas lógicas também se aplicam às expressões booleanas, assim: ( ) maior precedência ’ • + menor precedência e) Em álgebra booleana, quando duas expressões são equivalentes, usamos o sinal de igualdade para representar. Exemplo: p • q + p • r + q’ • r = p • q + q’ • r isto afirma que os valores de ambos os lados da equação são iguais para todos os possíveis valores das variáveis. Provando a igualdade das expressões, temos: p q r q’ p•q p•r q’•r p•q + p•r p•q + p•r + q’•r p•q + q’•r 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 1 0 1 1 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 1 1 0 1 1 1 1 1 1 1 0 0 1 0 0 1 1 1 1 1 1 0 1 1 0 1 1 1 iguais Lógica Para Computação Prof. Walteno Martins Parreira Jr Página 29 S = A • B’ + A • C + A’ • B + B • C + A’ • C + B’ • C + C colocando C em evidencia (propriedade distributiva), temos: S = A • B’ + C • ( A + B + A’+ B’+ 1) + A’ • B usando a identidade da adição: X + X’= 1 e X + 1 = 1, temos: S = A • B’ + C • 1 + A’ • B usando a identidade da multiplicação: X • 1 = X, temos: S = A • B’ + C + A’ • B portanto: S = ( A + B + C ) • ( A’ + B’ + C ) = A • B’ + C + A’ • B 4) Provar que a expressão (A + B) • (A + C) = A + B • C é válida: Vamos desenvolver o lado esquerdo, logo: (A + B) • (A + C) Usando a propriedade distributiva: A • A + A • B + A • C + B • C Usando a identidade da multiplicação X • X = X, temos: A + A • B + A • C + B • C Usando a Propriedade distributiva: A • ( 1 + B + C ) + B • C Usando a identidade da soma X + 1 = 1, temos: A • ( 1 ) + B • C Usando a identidade da multiplicação X • 1 = x, temos: A + B • C que é a expressão procurada, logo: (A + B) • (A + C) = A + B • C é válida. 5) Usando as propriedades da Álgebra de Boole, provar que a expressão (A + B ) • (A’ + C) = A • C + A’ • B é válida, indicando a propriedade usada em cada passagem. (A + B ) • (A’ + C) = A • C + A’ • B DISTRIBUTIVA A • A’ + A • C + A’ • B + B • C IDENTIDADE DA MULTIPLICAÇÃO: X • X’ = 0 A • C + A’ • B + B • C IDENTIDADE DA SOMA: 1 = X + X’ A • C + A’ • B + B • C • ( A + A’ ) DISTRIBUTIVA A • C + A’ • B + A • B • C + A’ • B • C DISTRIBUTIVA A • C • ( 1 + B ) + A’ • B • ( 1 + C ) IDENTIDADE DA SOMA: 1 + X = 1 A • C • 1 + A’ • B • 1 IDENTIDADE DA MULTIPLICAÇÃO: X • 1 = X A • C + A’ • B Para provar, usar um lado da expressão para chegar no outro lado da expressão. veja a solução ao lado, letra e Lógica Para Computação Prof. Walteno Martins Parreira Jr Página 30 6.10 – MAPA DE KARNAUGH Simplificamos expressões booleanas usando as propriedades, postulados e identidades da álgebra de Boole, no entanto não há um conjunto de procedimentos a serem seguidos, funciona por tentativa e erro, cada solução é diferente da anterior. Pode-se usar os diagramas de Veitch-Karnaugh para efetuar as simplificações nas expressões booleanas. B B A A • B A • B A A • B A • B B B B B B’ B’ B B A A B C A B C A B C A B C A’ A’B’C’ A’B’C A’B C A’B C’ A A B C A B C A B C A B C A A B’C’ A B’C A B C A B C’ C C C C C’ C C C’ Dada a função booleana S = F(A,B) = A’ • B’ + A • B, vamos montar o mapa de Karnaugh. Solução: Como temos duas proposições (ou variáveis), teremos 22 células, montando o mapa: As parcelas que temos na expressão são transcritas para o mapa com o valor igual a 1: B B A 1 A 1 completando com zeros as células vazias: B B A 1 0 A 0 1 6.10.1 - OBTENDO A SIMPLIFICAÇÃO DE UMA EXPRESSÃO COM 2 VARIÁVEIS 1) Dada a expressão booleana: S = A’ • B + A • B’ + A • B 2) Desenhar o diagrama. Como temos duas variáveis, teremos 4 células. B B A A 3) Para cada parcela que aparece na expressão, colocar o numeral um na célula correspondente. Número De Células: 2N onde N é o número de variáveis 22 = 4 células Portanto, temos o mapa montado. Lógica Para Computação Prof. Walteno Martins Parreira Jr Página 31 B B A 1 A 1 1 4) Completar com o numeral zero (0) as células restantes que estão vazias. B B A 0 1 A 1 1 5) Para obter a expressão simplificada, devemos observar: i) Agrupar as células adjacentes (na horizontal ou vertical) onde aparecem o numeral 1, um mesmo numeral 1 pode ser componente de mais de um par. Todos os numerais 1 do diagrama devem pertencer a pelo menos um agrupamento; B B A 0 1 A 1 1 B B A 0 1 A 1 1 ii) O par 1 ocupa a região do diagrama onde A é igual a 1, logo o seu valor será: par 1 = A; iii) O par 2 ocupa a região do diagrama onde B é igual a 1, logo o seu valor será par 2 = B iv) Somando os pares para obter a expressão simplificada: S = A + B 6.10.2 - SIMPLIFICAÇÃO DE UMA EXPRESSÃO COM 3 OU MAIS VARIÁVEIS 1) Dada a expressão booleana: S = A’ • B • C + A • B’ + A • B + A’ • B’ • C’ 2) Desenhar o diagrama. Como temos três variáveis, teremos 8 células. A A A A C C B B B B 3) Para cada parcela que aparece na expressão, colocar o numeral um na célula correspondente. A A A A C 1 1 1 C 1 1 1 B B B B par 1 par 2 Lógica Para Computação Prof. Walteno Martins Parreira Jr Página 34 6.10.5 – SOMA DE PRODUTOS Todos os exemplos e exercícios apresentados até o momento são denominados de soma de produtos. Como pode ser observado, cada parcela da expressão é um produto de variáveis e que são somadas para formar a expressão. É denominada de Forma Normal Disjuntiva. Exemplo: S = A • B + A’ • B • C + B’ • C A A A A C 1 C 1 1 1 1 B B B B S = A • B + C Exercício: Encontrar a expressão booleana definida pela tabela-verdade, representá-la no mapa de karnough e encontrar a expressão mais simples. A B C S 1 1 1 1 A • B • C 1 1 0 1 A • B • C’ 1 0 1 1 A • B’ • C S1 = A•B•C + A•B•C’ + A•B’•C + A’•B•C 1 0 0 0 0 1 1 1 A’ • B • C 0 1 0 0 0 0 1 0 0 0 0 0 Montando o Mapa de Karnaugh: A’ A’ A A C’ 0 0 1 0 S1 = A•B + A•C + B•C C 0 1 1 1 B’ B B B’ A • B C Lógica Para Computação Prof. Walteno Martins Parreira Jr Página 35 6.10.6 – PRODUTOS DA SOMA Como o próprio nome indica, cada parcela da expressão é uma soma e que serão reunidas através de produtos para formar a expressão. É denominada de Forma Normal Conjuntiva. Para desenvolver o Mapa de Karnaugh e achar a expressão na forma de Produto da Soma, desenvolve-se: a) Os agrupamentos com os numerais zero (0) no lugar do numeral 1 (um) da mesma forma que estudada anteriormente; B B B B A 1 1 0 0 A 0 0 1 1 C C C C b) Montar a expressão, onde cada agrupamento será somado para formar a expressão, mas como foi desenvolvido a partir das células com numeral 0 (zero), o resultado será negado; Z’ = A’ • B + A • B’ c) Para encontrar a expressão, tem-se que inicialmente negar os dois lados e assim eliminar a negação no resultado; Z’’ = ( A’ • B + A • B’ ) ‘ d) Aplicar o teorema de DeMorgan duas vezes, encontrando assim, a expressão na forma de Produto da Soma. Z = ( A’ • B )‘ • ( A • B’ )‘ Z = ( A’’ + B’ ) • ( A’ + B’’ ) Z = ( A + B’ ) • ( A’ + B ) Exemplo: S = A • B + A’ • B • C + B’ • C A A A A C 0 0 1 0 C 1 1 1 1 B B B B S’ = A’ • C’ + B’ • C’ S’’ = (A’ • C’ + B’ • C’ )’ S = ( A’ • C’ )‘ • ( B’ • C’ )‘ S = ( A’’ + C’’) • ( B’’ + C’’) S = ( A + C) • ( B + C ) A’B AB’ A’ • C’ B’ • C’ Lógica Para Computação Prof. Walteno Martins Parreira Jr Página 36 6.11 – MÉTODO DE QUINE-McCLUSKEY Este método aplica-se exclusivamente a funções booleanas na Forma Normal Disjuntiva e com notação binária. Supera a limitação do mapa de Karnaugh, permitindo a aplicação em funções com mais de seis (6) variáveis. O método consiste na aplicação sucessiva do teorema expresso por A • B + A • B’ = A , a termos que diferem entre s apenas por um dígito binário. Para desenvolver o método: a) Classificam-se e agrupam-se os termos da função de acordo com os seus índices; b) Comparam-se todos os termos de um dado grupo (é organizado em função da quantidade de 1 que tem) com cada termo do grupo seguinte, ou seja, de índice imediatamente superior, para a aplicação do teorema. Aplica-se sucessivamente esse teorema comparando cada termo do grupo de índice i com todos os termos do grupo com índice i+1 até esgotarem todas as possibilidades. O termo resultante é representado com o único digito diferente substituído por um traço e marca-se os termos comparados; c) Após tabular os termos comparados, procede-se novamente ao item b até o esgotamento das possibilidades. No final, os termos que ficarem sem a marcação formam o conjunto de termos irredutíveis. Exemplo: Dada a função Z = A’B’C + ABC’ + A’BC’ + A’BC + AB’C + ABC Solução: f(A,B,C) = (001,100,010,011,101,111) montando o diagrama: A B C 2º passo A B C 3º passo A B C 1 0 0 1 √ 1,3 0 - 1 √ 1,3,5,7 - - 1 -> C 2 0 1 0 √ 1,5 - 0 1 √ 1,5,3,7 - - 1 -> C 4 1 0 0 √ 2,3 0 1 - -> A’B 3 0 1 1 √ 4,5 1 0 - -> AB’ 5 1 0 1 √ 3,7 - 1 1 √ 7 1 1 1 √ 5,7 1 - 1 √ Como 1,3,5,7 e 1,5,3,7 representam o mesmo termo, não será repetido, ficando então a expressão: Z = A’B + AB’ + C Lógica Para Computação Prof. Walteno Martins Parreira Jr Página 39 5) Simplificar o circuito lógico apresentado ao lado, usando o mapa de karnaugh. Solução: S = A • B + C’ • D + A’ • B + A’ • C • D colocando no mapa de karnaugh, temos: B’ B’ B B A’ 0 0 1 1 D’ A’ 1 1 1 1 D A 1 0 1 1 D A 0 0 1 1 D’ C’ C C C’ logo, a nova expressão é: S = B + A’ • D + C’• D e o novo circuito será: C’• D B A’ • D Lógica Para Computação Prof. Walteno Martins Parreira Jr Página 40 1º Lista de Exercícios 1) determinar quais das frases abaixo são proposições declarativas a) Doze é um número primo. e) Boa tarde! b) Dez é menor que sete. f) Uberlândia tem quantas escolas superiores? c) Qual será o resultado do futebol? g) Marcela é bonita. d) Muitos alunos de lógica podem ser aprovados este semestre. 2) Nas expressões a seguir, quais são sentenças abertas e quais são proposições declarativas. a) x + 5 = 9 d) 4 > 5 b) 5 + 4 = 9 e) 6 < 7 e 3 + 2 = 8 c) x é filho de z, então é neto de y. f) 2 – y ≥ 6 3) Determinar o valor lógico ( V ou F ) de cada uma das seguintes proposições. a) O número 23 é primo. e) π = 3 b) Goiânia é a capital de Tocantins. f) 3 > 2 c) O número 25 é quadrado perfeito. g) π > 3 d) Todo número divisível por 5 termina com 5. h) √ 4 = 2 4) Sejam as proposições: p: O empregado foi demitido. q: O patrão indenizou o empregado. Escreva em notação simbólica, cada uma das proposições abaixo: a) O empregado não foi demitido. b) O patrão não indenizou o empregado. c) O empregado foi demitido e o patrão indenizou o empregado. d) É falso que o empregado foi demitido ou o patrão indenizou o empregado. e) O empregado foi demitido ou o patrão não indenizou o empregado. f) não é verdade que o empregado não foi demitido. 5) Sejam as proposições: p: Rosas são vermelhas. q: Violetas são azuis. r: Cravos são amarelos. Escreva em notação simbólica, cada uma das proposições compostas abaixo: a) Rosas são vermelhas e violetas são azuis. b) Rosas são vermelhas, ou violetas são azuis ou os cravos são amarelos. c) Se violetas são azuis, então as rosas são vermelhas e os cravos são amarelos. d) Rosas são vermelhas se e somente se, as violetas não forem azuis e os cravos não são amarelos. e) Rosas são vermelhas e, se os cravos não são amarelos então, as violetas não são azuis. 6) Sejam as proposições: p: Jô Soares é gordo. q: Jô Soares é artista. r: Paulo é cantor. Escreva em notação simbólica, cada uma das proposições abaixo: a) Jô Soares não é gordo. b) Jô Soares não é artista. c) Não é verdade que Jô Soares não é gordo d) Jô Soares é gordo ou artista. e) Se Jô Soares não é artista então Paulo não é cantor. f) Jô Soares é artista se e somente se Paulo é cantor 7) Sejam as proposições: p: João joga futebol. q: Pedro joga tênis. Traduzir as formulas lógicas para o português. a) p ∨ q b) p ∧ q c) p ∧ ~q d) p → ~q e) ~p ∧ ~q f) ~~p g) ~(~p ∧ ~q) h) ~p ↔ ~q Lógica Para Computação Prof. Walteno Martins Parreira Jr Página 41 8) Sejam as proposições: p: A bola é vermelha. q: O bambolê é amarelo. Traduzir as formulas lógicas para o português. a) p ∨ q b) p ∧ q c) p ∧ ~q d) ~p ∧ ~q e) ~~p f) ~(~p ∧ ~q) g) ~p ↔ ~q h) p → ~q i) ~(~q → p) 9) Determinar o valor lógico (V ou F) de cada uma das proposições compostas abaixo, sabendo o valor lógico de cada proposição simples v(p) = V e v(q) = F. a) p ∨ q b) p ∧ q c) p ∧ ~q d) p ∨ (~p ∧ ~q) e) ~p ∧ ~q f) ~~p g) p ↔ (~p → ~q) h) p ↔ ~q → p i) ~p ∧ q j) p → ~q k) p ∧ (~q → p) l) ~(r ∧ ~q) ↔ p 10) Construa a tabela-verdade de cada uma das seguintes proposições: a) p ∨ q b) p ∧ q c) p ∧ ~q d) ~p ∧ ~q e) ~~p f) p ∨ (~p ∧ ~q) g) ~p ∧ q ↔ ~q → p h) p → ~q i) p ∧ (~q → p) j) ~p ∨ r ↔ ~q ∨ r k) p ∧ r → ~q l) ~(r ∧ ~q) → p 11) Construir as tabelas-verdade das seguintes proposições: a) ~ p ∧ r → q ∨ ~ r b) p → (p → ~ r) ↔ q ∨ r c) p → r ↔ q ∨ ~ r d) (p ∧ q → r) ∨ (~ p ↔ q ∨ ~ r) 12) Determinar P(VV, VF, FV, FF) em cada um dos seguintes casos: a) P(p, q) = ~ (~ p ↔ q) b) P(p, q) = ~ p ∨ q → p c) P(p, q) = (p ∨ q) ∧ ~ (p ∧ q) d) P(p, q) = (p ∧ ~ q) ∨ (~ p ∧ q) e) P(p, q) = ~ ((p ∨ q) ∧ (~p ∨ ~q)) f) P(p, q) = ~ q ∨ p ↔ q → ~ p g) P(p, q) = (p ∨ q) ∧ ~ p → (q → p) h) P(p, q) = (p ∧ ~ q) ∨ (~ p ∧ q) → p 13) Determinar P(VVV, VVF, FFF) em cada um dos seguintes casos: a) P(p, q, r) = p ∨ (q ∧ r) b) P(p, q, r) = (p ∧ ~ q) ∨ r c) P(p, q, r) = ~ p ∨ (q ∧ ~ r) d) P(p, q, r) = (p ∨ q) ∧ (p ∨ r) e) P(p, q, r) = (p ∨ ~ r) ∧ (q ∨ ~ r) f) P(p, q, r) = ~ (p ∨ ~ q) ∧ (~ p ∨ r) 14) Determinar P(VFV) em cada um dos seguintes casos: a) P(p, q, r) = p ∧ ~ r → ~ q b) P(p, q, r) = ~ p ∧ (q ∨ ~ r) c) P(p, q, r) = ~ (p ∧ q) ↔ ~ (p ∨ ~ r) d) P(p, q, r) = (r ∧ (p ∨ ~ q)) ∧ ~ (~ r ∨ (p ∧ q)) e) P(p, q, r) = (p ∨ q → r) → q ∨ ~ r f) P(p, q, r) = (p ∨ (q → ~ r)) ∧ (~ p ∨ r ↔ ~ q) 15) Sabendo que os valores lógicos das proposições p e q são respectivamente F e V, determinar o valor lógico (V ou F) da proposição: (p ∧ (~ q → p)) ∧ ~ ((p ↔ ~ q) → q ∨ ~ p) 16) Sejam as proposições p: tg(π – x) = ctg(x) e q: π < 2. Determinar o valor lógico (V ou F) de cada uma das seguintes proposições: (a) (~ p ∧ q) ∨ (p ∧ ~ q) (c) ~ (p ∧ q) ↔ ~ p ∨ ~ q (b) (p → q) ∧ ~ p → ~ q (d) (p ∨ (~ p ∨ q)) ∨ (~ p ∧ ~ q) 17) Sabendo que os valores lógicos das proposições p, q e r são respectivamente V, F e F, determinar o valor lógico (V ou F) de cada uma das seguintes proposições: a) (p ↔ p → q) ∨ (p → r) b) (p → ~ q) ↔ ((p ∨ r ) ∧ q) c) (p ∧ q → r) → (p → (q → r)) d) p → q ↔ q → p ∧ r ∧ q 18) Sabendo que as proposições p, q são verdadeiras e que as proposições r e s são falsas, determinar o valor lógico (V ou F) de cada uma das seguintes proposições: a) p ∧ q → r b) (q ∨ r) ∧ (p ∨ s) c) r ∨ s → q Lógica Para Computação Prof. Walteno Martins Parreira Jr Página 44 2ª Lista de Exercícios 1) Determinar se as proposições a seguir são tautologia, contradição ou contigência, usando o método da Tabela-verdade. a) p ∧ ( q ∨ r ) ↔ ( p ∧ q ) ∨ ( p ∧ r ) b) p ∨ ( p ∧ q ) → p c) ~ ( p ∨ q ) ∨ ( ~ p ∧ r ) ↔ ~ r d) p ∧ ( p ∨ q ) → p 2) Determinar se as proposições a seguir são tautologia, contradição ou contigência, usando o método da Árvore semântica a) ~p ↔ (q ∧ p) b) (p ∧ q ) → ~q c) ~q ∨ p d) ( p ∧ (p ∨ q )) ↔ p 3) Determinar, usando árvore semântica, se as proposições abaixo são tautologia, contradição ou contigência: a) p ∧ ( q ∨ r ) ↔ ( p ∧ q ) ∨ ( p ∧ r ) b) p ∨ ( p ∧ q ) → p c) ~ ( p ∨ q ) ∨ ( ~p ∧ q ) ↔ ~p d) p ∧ ( p ∨ q ) → p e) ( p ∧ q ) ∨ ~p ↔ ~p ∨ q f) p ∧ ( ~p ∨ q ) → p ∧ q 4) Determinar se as proposições a seguir são tautologia, contradição ou contigência, usando os seguintes métodos: Tabela-verdade, Árvore semântica e Negação ou absurdo. a) ~ (p ∧ q) → ~ p ∨ ~ q b) (p → q) ∧ q c) (p ↔ q) ∨ p → q d) ~ (p → q) → (p ∧ ~q) e) ~ ( p ∧ q) ↔ ~ ( ~ p ∧ q) f) p ∧ ( p ∨ q ) → p 5) Verificar se as proposições são tautologia, contradição ou contigência usando os métodos: tabela- verdade, árvore semântica e Negação ou absurdo. a) ~ (p ∧ q) ↔ ~p ∨ ~q b) ~ (p ∨ q) → ~p ∧ ~ q c) ~ (r ∧ p) ∨ q ↔ ~ (p ∧ q) ∨ r d) (p ↔ q) ∨ r → (p → q) ∨ r e) ( p → ~r ) ∧ ( q → ~p ) ↔ r → ( p ∨ q ) f) ( p → q ) → r → ( p ∧ ~r ) → ~q g) ~ ( p ∧ q) ↔ ~ ( ~ p ∧ q) h) ~ (p → q) → (p ∧ ~q) 6) Construir a tabela-verdade para a fórmula P e, usando a tabela-verdade desenvolvida obter as duas proposições possíveis. Mostrar que as proposições encontradas são equivalentes. a) P: ~ (p ↔ q) b) P: (~ p ∧ q) c) P: (p → ~ q) d) P: (p ∨ ~ q) 7) Considere as fórmulas a seguir: E: (~(p ∧ ~ q) ∨ r) ∨ (r → (q → p) ) F: ( ( ( p ∧ s) ↔ p) ↔ (p → p) ) → ( ( (p ∧ q) ↔ p) ∧ ( ( p ∧ r) ↔ r) → p) G: ( p ∧ q) ∨ ( ~p ∨ q) H: ~ (p → p) → (p ∧ ~q) utilize o método da negação ou absurdo para demonstrar se tais fórmulas são tautológicas. No caso em que a fórmula não for uma tautologia, utilize o resultado do método para identificar um valor lógico, que interpreta a fórmula como sendo falsa. 8) Julgar cada uma das seguintes proposições (dizer se são verdadeiras ou falsas as relações): a) ~p ∧ ~p ⇔ ~p b) ~ p ∨ ~( p ∨ q ) ⇔ p ∨ q c) ( p ∧ ~q ) ∨ ( p ∧ ~q ) ⇔ p ∧ ~q d) ( p → q ) ∨ r ⇔ ( p ∧ ~r ) → ( q ∧ r ) e) ( p → ~r ) ∧ ( q → ~p ) ⇔ r → ( p ∨ q ) f) ( p → q ) → r ⇔ ( p ∧ ~r ) → ~q 9) Considere as proposições: p, q, r, s dadas por: p: 5 = 8 q: 4 < 5 r: 9 > 7 s: 8 < 10 e diga se são verdadeiras ou falsas as relações abaixo: a) r ⇔ s b) r ⇔ q c) ~ p ⇔ s d) p ⇔ q e) ~ r ⇔ ( q ∧ ~s ) f) ~ r ⇔ ( s ∨ ~ q ) g) p ⇒ q h) ~ r ⇒ q i) ~ r ⇒ s j) ( p → p ) ⇒ ( q ∧ r ) k) ~ r ⇒ ( q ∧ ~s ) l) ~ r ⇒ ( s ∨ ~ q ) Lógica Para Computação Prof. Walteno Martins Parreira Jr Página 45 10) Considere as proposições: p, q, r, s dadas por: p: 7 + 2 = 9 q: ( 7 + 2 )2 = 81 r: 20 = 1 s: 02 = 2 e dê o valor lógico (verdadeiro ou falso) das relações abaixo: a) r ⇔ s b) r ⇔ q c) ~ p ⇔ s d) p ⇔ q e) ~ r ⇔ ( q ∧ ~s ) f) ~ r ⇔ ( s ∨ ~ q ) g) p ⇒ q h) ~ r ⇒ q i) ~ r ⇒ s j) ( p → p ) ⇒ ( q ∧ r ) k) ~ r ⇒ ( q ∧ ~s ) l) ~ r ⇒ ( s ∨ ~ q ) 11) Usando as equivalências tautológicas, mostrar que as proposições abaixo podem ser escritas usando os conectivos ∧, ∨ e ~. Depois simplifique as expressões o máximo possíveis. a) (r → (q → p) b) q ∨ r → (q → p) c) p ∧ r → (q → r) d) (r ∧ q) → (~q → p) e) (p ∧ q) → ( p ∧ ~q) f) (p ∧ r) → ((q ∧ p) → r) g) ~ ( p ∧ q ) → p h) ( p ∧ q ) → r → ( p ∨ r ) i) ~ ( p ∧ q ) → ( p ∧ q ) 12) Usando as equivalências tautológicas, mostrar que as proposições abaixo podem ser escritas usando os conectivos: ∨ e ~. Depois simplifique as expressões o máximo possíveis. a) (r ∧ q) → (q → p) b) (p ∧ q) → p c) (p ∧ r) → ((q ∧ p) → r) d) (r → (q → p) e) q ∨ r → (q → p) f) p ∧ r → (q → r) 13) Usando as equivalências tautológicas, simplificar as proposições abaixo: a) (~ (p ∧ q) ∧ r) → (~p ∨ ~q) b) (p ∧ q) → p ∨ p c) (p ∧ q) → ((q ∧ p) → r) d) ~ ( p ∧ q ) ∨ ~p → ( ~p ∨ q ) e) (p ∧ q) → (q → p) f) p ∧ ( ~p ∨ q ) ⇒ p ∧ q g) ( p ∧ q ) → r → ( p ∨ r ) h) ~ ( p ∧ q ) → p i) ~ ( p ∧ q ) → ( p ∧ q ) j) ( p ∧ q ) → (( p ∧ r ) → (p ∨ q )) k) ~ ( p ∧ r ) → ((r → ( q ∧ r )) TRABALHO: os alunos vão fazer os exercícios definidos abaixo, conforme o seu último digito do número de matrícula (exemplo o aluno 11021005 fará os exercícios da coluna numerada com o número 5) e entregar no dia DD/MM Último digito do Nro A B C D E F G H I J Exercícios 1A 1B 1C 1D 1A 1B 1C 1A 1B 1C 2A 2B 2D 2A 2B 2D 2A 2B 2D 2A 3A 3B 3C 3D 3C 3D 3A 3B 3C 3D 5A 5B 5C 5D 5E 5A 5B 5C 5D 5E 8D 8C 8B 8A 8A 8B 8C 8D 8B 8C 10J 10K 10L 10K 10J 10K 10L 10J 10K 10L 11A 11B 11C 11D 11D 11C 11B 11A 11A 11C Lógica Para Computação Prof. Walteno Martins Parreira Jr Página 46 3a LISTA DE EXERCÍCIOS 1. Identificar a expressão Booleana que gera o mapa de Karnaugh abaixo: a) A A A A b) C 0 0 1 0 D A A A A C 1 0 0 0 D C 0 0 1 0 C 1 0 0 1 D C 1 1 0 1 C 0 0 0 0 D B B B B B B B B 2. Identificar a expressão Booleana mais simples (soma de produto) a partir do mapa de Karnaugh abaixo: a) A A A A b) A A A A C 0 1 1 1 D C 1 1 0 1 D C 0 1 1 0 D C 1 1 0 1 D C 0 0 0 0 D C 1 1 0 1 D C 0 1 1 0 D C 1 1 0 1 D B B B B B B B B c) A A A A d) A A A A C 1 1 1 0 D C 1 1 1 0 D C 1 1 0 0 D C 1 1 0 0 D C 1 0 0 1 D C 1 0 0 1 D C 1 0 1 1 D C 1 0 1 1 D B B B B B B B B e) f) A A A A A A A A C 0 1 1 0 C 1 0 0 0 C 1 0 0 1 C 1 1 0 1 B B B B B B B B g) h) A A A A A A A A C 1 1 0 0 C 1 1 0 1 C 1 1 0 1 C 0 1 0 1 B B B B B B B B Lógica Para Computação Prof. Walteno Martins Parreira Jr Página 49 4a LISTA DE EXERCÍCIOS 1. Identificar a expressão Booleana mais simples (soma de produto) a partir do mapa de Karnaugh abaixo, depois representar a expressão simplificada usando portas lógicas. a) b) A A A A A A A A C 1 0 0 1 C 0 0 1 0 C 0 1 0 0 C 0 1 1 0 B B B B B B B B c) A A A A d) A A A A C 1 0 1 1 D C 1 1 1 0 D C 0 1 1 0 D C 1 1 1 0 D C 0 1 1 0 D C 1 0 0 0 D C 1 0 0 1 D C 1 0 1 0 D B B B B B B B B 2. Identificar a expressão Booleana mais simples (produto de soma) a partir do mapa de Karnaugh abaixo, depois representar a expressão simplificada usando portas lógicas. a) A A A A b) A A A A C 1 0 0 1 D C 1 1 1 0 D C 0 1 1 0 D C 1 1 1 0 D C 0 1 1 1 D C 1 0 1 1 D C 1 0 0 1 D C 1 1 1 0 D B B B B B B B B c) d) A A A A A A A A C 0 0 1 1 C 1 0 0 1 C 0 0 1 0 C 0 1 1 0 B B B B B B B B 3. Seja a expressão booleana dada a seguir. Representá-la no mapa de Karnaugh e depois simplificá-la. Representar a expressão simplificada usando portas lógicas. e) S = f(A,B,C) = A • B + B’ • C + A’ • B’ + A’ • B • C f) S = f(A,B,C) = A • B • C + B’ • A + A • C + A’ • B g) S = f(A,B,C) = A • B • C’ + B • C’ + A’ • C’ + A • B’ h) S = f(A,B,C,D) = A • B • C + A • B’ • C + A • C + B • C + A’ • D + B’ • D i) S = f(A,B,C,D) = A • B • D + A’ • B • C + B • C’ • D’ + B • C • D + A • B • D’ j) S = f(A,B,C,D) = A’ • B • D + A • B’ • C + A • B • C + A’ • C • D + A’ • B • D’ Lógica Para Computação Prof. Walteno Martins Parreira Jr Página 50 4. Escrever a expressão booleana representada pelo circuito a seguir. Representá-la no mapa de Karnaugh e depois simplificá-la. Representar a expressão simplificada usando portas lógicas. f) 5. Escrever a expressão booleana representada pelo circuito abaixo: a) c) d) e) A B C A B C A C D B C D A B A C B C A B A C A B A C A B A B C A B C D A B A B C C D C D C b) Lógica Para Computação Prof. Walteno Martins Parreira Jr Página 51 6. Dada a tabela verdade abaixo, achar uma expressão booleana que a represente. Simplificar a expressão encontrada usando o mapa de karnaugh e depois desenhar o circuito lógico correspondente a expressão simplificada. a) A B C S 1 1 1 1 1 1 0 0 1 0 1 0 1 0 0 1 0 1 1 0 0 1 0 1 0 0 1 1 0 0 0 0 c) A B C D S 1 1 1 1 1 1 1 1 0 1 1 1 0 1 0 1 1 0 0 1 1 0 1 1 1 1 0 1 0 1 1 0 0 1 1 1 0 0 0 0 0 1 1 1 0 0 1 1 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 b) A B C S 1 1 1 1 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 0 0 1 0 1 0 0 1 1 0 0 0 0 d) A B C D S 1 1 1 1 0 1 1 1 0 0 1 1 0 1 0 1 1 0 0 1 1 0 1 1 1 1 0 1 0 1 1 0 0 1 1 1 0 0 0 0 0 1 1 1 0 0 1 1 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 1 1 0 0 1 0 1 0 0 0 1 1 0 0 0 0 0 7. Dada a tabela-verdade abaixo, achar as duas expressões booleanas que a represente. Depois fazer os circuitos lógicos correspondentes. a) A B C S 1 1 1 1 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 0 0 1 0 0 0 0 1 1 0 0 0 1 b) A B C S 1 1 1 1 1 1 0 0 1 0 1 0 1 0 0 1 0 1 1 0 0 1 0 1 0 0 1 0 0 0 0 1 c) A B C D S 1 1 1 1 0 1 1 1 0 1 1 1 0 1 0 1 1 0 0 1 1 0 1 1 1 1 0 1 0 0 1 0 0 1 1 1 0 0 0 0 0 1 1 1 0 0 1 1 0 1 0 1 0 1 0 0 1 0 0 0 0 0 1 1 1 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0