Lógica Aplicada a Computação Lista de Exercícios 03 – Lógica Proposicional – Propriedades Semântica Professor: Rosalvo Neto Aluno(a): Questão 01) Chama-se tautologia à proposição composta que possui valor lógico verdadeiro, quaisquer que sejam os valores lógicos das proposições que a compõem. Sejam p e q proposições simples e ~p e ~q as suas respectivas negações. Em cada uma das alternativas abaixo, há uma proposição composta, formada por p e q. Qual corresponde a uma tautologia? a) pΛq b) p Λ ~q c) (p Λ q) → (~p Λ q) d) (p Λ q) → (p Λ q) Não. V, F, F e F. INCLUIR A TABELA VERDADE. NÃO. F, V, F e F. INCLUIR A TABELA VERDADE. NÃO. F, V, V e V. INCLUIR A TABELA VERDADE. SIM. V, V, e V. INCLUIR A TABELA VERDADE. Questão 02) Demonstre se as afirmações são verdadeiras: a) b) c) Se (E ↔ G) e (G ↔ H) são tautologias, VERDADEIRA então (E ↔ H) é uma tautologia. DEMONSTRAÇÃO EM SALA. ~(E ↔ G) é tautologia, se, e somente se, E e FALSA ~G são tautologia DEMONSTRAÇÃO EM SALA. Se I[~(E→G)]=T, então I[E]=I[~G]=T VERDADEIRA DEMONSTRAÇÃO EM SALA. Questão 03) Sejam H e G as fórmulas indicadas a seguir. Identifique, justificando sua resposta, os casos em que H G a) H = P Λ Q, G = P É UMA CONSEQUENCIA LÓGICA. APÓS CONSTRUÇÃO DA TABELA VERDADE VERIFICAMOS QUE A 1 Lógica Aplicada a Computação Lista de Exercícios 03 – Lógica Proposicional – Propriedades Semântica Professor: Rosalvo Neto Aluno(a): IMPLICAÇÃO H EM G É UMA TAUTOLOGIA, POR ISSO É UMA CONSEQUENCIA LÓGICA. INCLUIR A TABELA VERDADE. b) H = P V Q, G = P NÃO É UMA CONSEQUENCIA LÓGICA. APÓS CONSTRUÇÃO DA TABELA VERDADE VERIFICAMOS QUE A IMPLICAÇÃO H EM G NÃO É UMA TAUTOLOGIA, POR ISSO NÃO É UMA CONSEQUENCIA LÓGICA. INCLUIR A TABELA VERDADE. c) H = P V ~Q, G = false NÃO É UMA CONSEQUENCIA LÓGICA. POIS EXISTE UMA INTERPRETAÇÃO I; I[H]=V, E COM ISSO A IMPLICAÇÃO H EM G TORNA-SE FALSA, OU SEJA A FÓRMULA NÃO É UMA TAUTOLOGIA. d) H = false, G = P É UMA CONSEQUENCIA LÓGICA, POIS QUANDO EM UMA IMPLICAÇÃO O ANTECEDENTE É FALSO A IMPLICAÇÃO SERÁ SEMPRE VERDADEIRA, LOGO A FÓRMULA É UMA TAUTOLOGIA. 2 Lógica Aplicada a Computação Lista de Exercícios 03 – Lógica Proposicional – Propriedades Semântica Professor: Rosalvo Neto Aluno(a): Questão 04) Demonstre se são verdadeiras ou falsas as afirmações a seguir: a) b) c) d) H não é satisfatível, se, e somente se, H é VERDADEIRA contraditório DEMONSTRAÇÃO EM SALA. H é satisfatível, se, e somente se, H é não VERDADEIRA contraditório DEMONSTRAÇÃO EM SALA. ~H é tautologia, se, e somente, H é contraditório VERDADEIRA DEMONSTRAÇÃO EM SALA. H não é tautologia, se, e somente, H é FALSA contraditório DEMONSTRAÇÃO EM SALA. Questão 05) Suponha que H G e H equivale a ~E. Demonstre se o conjunto de fórmulas {~G, E -> ~H, H} é satisfatível. O conjunto de fórmulas é insatisfatível. Suponha que o conjunto de formulas seja satisfativel. Logo existe uma interpretação I, tal que I[(~G)]=I[(E->~H)]=I[(H)]=T. Mas se I[H]=T, como H G, então I[G]=T, o que é um absurdo pois I[(~G)]=T. 3