Baixe o app para aproveitar ainda mais
Prévia do material em texto
UNIVERSIDADE FEDERAL DA BAHIA GRADUAÇÃO EM CIÊNCIA DA COMPUTAÇÃO MATA47 – LÓGICA PARA COMPUTAÇÃO PROFESSORAS: ALINE MARIA SANTOS ANDRADE MONITOR: CARLOS VINÍCIUS ANDRADE SILVA LISTA I 1. Para as fórmulas abaixo prove se são satisfatíveis, válidas ou insatisfatíveis: a) (P (Q R)) (P (Q R)) b) (A C) (B C) (A B ) C c) P Q (P Q) 2. Prove usando os conceitos de conseqüência lógica e/ou contradição e/ou teorema da dedução: a) | (P Q) (Q P) b) {(Q P), P} |= (P Q) c) (A C) (B C) |= (A B ) C d) {(A B)} | (A B) e) {(A B), (B C)} | C 3. Escolha três equivalências da Lógica Proposicional dada em sala e prove usando o conceito de valoração. 4. Verifique se afirmações abaixo são verdadeiras ou falsas. Dê um contra-exemplo para as afirmações falsas e prove para as verdadeiras. a) A negação de uma fórmula válida é uma fórmula satisfatível. b) A negação de uma fórmula satisfatível é uma fórmula válida. c) A negação de uma fórmula insatisfatível é uma fórmula válida. d) Toda fórmula que não é válida é insatisfatível. 5. Para cada uma das sentenças abaixo, dizer se é insatisfatível, satisfatível ou válida: a. P P b. P P c. P P d. P P e. PQP 6. Provar que Se A | B e B | C, então A | C (transitividade da |) 7. Sejam P,Q conjuntos de fórmulas e seja p uma fórmula. Prove: a. Se P Q | p então P | p e Q | p b. Se P Q | p e para toda fórmula q Q, P | q, então P | p 8. Prove ou refute as afirmações abaixo. Para refutar pode mostrar um contra-exemplo. a) Se é satisfatível então {} é satisfatível. b) Se |= ou |= então |= . c) Se |= então |= ou |= . d) ( é tautologia |= ) é tautologia). 9. Sejam P,Q conjuntos de fórmulas e seja p uma fórmula. Prove: a) Se P Q | p então P | p e Q | p b) Se P Q | p e para toda fórmula q Q, P | q, então P | p 10. Prove por indução estrutural que toda fórmula da lógica proposicional tem o mesmo número de abre e fecha parênteses. 11. Seja P = {p0 p1, p1 p2, p2 p3, p3 p4, ....}. Existe um modelo para P? Justifique sua resposta. 12. Prove que ( Q P ) é uma conseqüência lógica de ( P Q ): a) Por definição de conseqüência lógica b) Pelo teorema da dedução c) Por contradição d) Usando dedução natural. 13. Formalize em lógica proposicional a) Maria não passará se não estudar b) Maria não passará a menos que estudar c) A cura do câncer não será descoberta a menos que sua causa seja descoberta e um novo medicamento seja encontrado. d) Chove u o céu é azul e se chove então não faz sol. 14. Prove os teoremas a seguir: a. é válida sse ¬ é insatisfatível. b. Uma fórmula é satisfatível e não válida sse ¬ é satisfatível e não válida. c. Se é insatisfatível ou é uma tautologia então é válida. 15. Prove os teoremas de conseqüência lógica a seguir: a. é insatisfatível sse , |= b. |= v c. |= (x v ) (x v ) d. {, } |= 16. Prove o teorema da contradição: |= sse {¬} é insatisfatível. 17. Prove os teoremas da reflexividade, monotocidade e Idempotência: a. Reflexividade: |= , b. Monotocidade: Se ’ e |= então ’ |= c. Idempotência: Se ’ |= e |= , ’ então |= 18. Verifique a equivalência entre os itens a., b. e c.: a. é satisfativel b. | para qualquer contradição c. Existe uma fórmula tal que | i. Dica: Faça (a. => b), (b=>c) e (c=>a) 19. Verifique o dual da questão 19, i.e. a. é insatisfativel b. |= para alguma contradição c. Para qualquer , |= 20. Provar: a. |= sse M() M() onde M(x) = modelo de x b. {( ^ ) , } |= ( ^ ) 21. Definir indutivamente o conjunto S de símbolos proposicionais de uma fórmula qualquer da Lógica Proposicional(L.P.). 22. Prove o Lema a seguir por indução estrutural a. Lema da Coincidência: Seja F. Se v1 e v2 são duas valorações tais que v1(p) = v2(p) para todo p S(), então v2() = v2(). i. Obs: S() é o conjunto de símbolos proposicionais de e F é o conjunto das fórmulas da L.P. 23. Prove as seguintes equivalências lógicas: a. v (Idempotência) b. ^ ^ (Comutatividade) c. ^ ( v x) ( ^) v ( ^ x) (Distributividade da Conjunção) d. v ( ^ x) ( v) v ( v x) (Distributividade da Disjunção) e. ^ ( ^ x) ( ^ ) ^ x (Associatividade) f. ¬( ^ ) ¬ v ¬ (De Morgan da Conjunção) g. ¬( v ) ¬ ^ ¬ (De Morgan da Disjunção) h. ( v ) ^ (Absorção) i. ( ^ ) v (Dual da Absorção) 24. Dê a forma normal conjuntiva e disjuntiva das fórmulas: a) (p q) ((r p q ) (r q)) b) (p q) (q r) 25. Prove (a) a (f) usando o sistema de dedução natural. Prove pelo menos 3 das afirmações abaixo usando tableaux e resolução: a) (P Q) (Q P) b) (Q P) (P Q) c) (A C) (B C) (A B ) C d) (A B ) ((A B) C) e) (A A) |-- A f) (A B) |-- (A B) 26. Prove usando Resolução: a. |- (A (B A) ) 27. Prove usando Tableaux: a. |- [p (q r ) ] [ (p q) (p r ) ] 28. Prove usando o método axiomático: a. |- ¬(A ^ ¬ A) b. |- c. , ¬ B |-
Compartilhar