Lista_de_Exercicios_Logica

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 |- 