Exercício3 - Lógica Proposicional

Prévia do material em texto

MINISTÉRIO DA EDUCAÇÃO 
UNIVERSIDADE FEDERAL DO PIAUÍ 
CAMPUS SENADOR HELVÍDIO NUNES DE BARROS 
Curso de Sistemas de Informação 
 
 
3ª Lista de exercícios de Lógica para Computação 
 
 
1. Considere os conjuntos de fórmulas a seguir. Determine quais conjuntos são 
satisfatíveis. 
a) {P, P}. 
b) {S  Q, P  (S  P), S}. 
c) {(Q  P), P  R, Q  R}. 
d) {(Q  R)  P, Q  (P  R), P  R}. 
e) {P  Q, Q  R, R  S, S  P}. 
f) {P  Q, (P  R)  (P  Q  R), (Q  R  S)}. 
g) {P  Q, (Q  R), R  S, (S  P)}. 
 
2. Considere os conjuntos de sentenças indicados a seguir. Que conjuntos de sentenças 
são satistafíveis? 
a) Marcos não está feliz, ou se Sílvia foi ao baile; então Marcos também foi ao baile. 
Se Marcos está feliz, então Sílvia não foi ao baile. Se Marcos foi ao baile, então 
Sílvia também foi ao baile. 
b) Um casamento é feliz, se, e somente se, os noivos têm objetivos comuns. Os 
noivos têm objetivos comuns, se, e somente se, os noivos cursam disciplinas em 
áreas comuns. Há divórcio, se, e somente se, o casamento é infeliz. Há divórcio, se 
e somente se, os noivos não cursam disciplinas em áreas comuns. 
 
3. Considere a fórmula H 
 
H = ((P  Q)  R  S)  (P1  Q1) 
 
a) Construa uma árvore semântica associada a H e identifique se H é uma tautologia, 
é satisfatível ou contraditória. 
b) Quantas linhas tem a tabela-verdade associada a H? 
 
4. 
a) Demonstre, utilizando o método da negação, ou redução ao absurdo, se as 
fórmulas a seguir são tautologias ou não. 
 
G = (P  Q)  ((Q  P)  (P  R)) 
 H = (P  (Q  R))  ((P  Q)  R) 
 G1 = H1  (H1  G2) 
 
b) Na demonstração de que G1 não é tautologia, quando consideramos I[H1] = T, 
obtemos um absurdo. Mas quando I[H1] = F, não é observado nenhum absurdo. 
Comente o significado de tais fatos. 
 
 
 
5. Demonstre, utilizando o método da negação, ou redução ao absurdo, que: 
 
 (P → P1)  (Q → Q1) l= (P → Q1)  (Q → P1) 
 
6. Considere as fórmulas a seguir: 
 
 (P  Q) → (R  S) ((P  Q)  R  S)  (P1  Q1) 
 
a) Construa a árvore semântica associada a cada fórmula H. 
b) Identifique, a partir das árvores semânticas determinadas no item anterior, uma 
interpretação I tal que I[H] = F e uma interpretação J tal que J[H] = T, para cada 
fórmula. 
 
7. 
a) Considere as fórmulas a seguir: 
 
 
H = ((P  Q)  R)  (R → (Q → P)) 
 E = (((P  S)  P)  (P → P1)) → ((((P  Q)  P)  ((P  R)  R) → P) 
 G = (P  Q)  (P  Q) 
 
Utilize o método da negação, ou redução ao absurdo, para demonstrar se tais fórmulas 
são tautologias. No caso em que a fórmula não for uma tautologia, utilize o resultado 
do método para identificar uma interpretação, que interprete a fórmula como sendo 
falsa. 
b) Suponha que I[P] = T, o que podemos concluir a respeito de I[H], I[G], onde 
H = (((P  S)  P2)  (P3 → P4)) → (((P  Q)  P1)  ((P5  R1)  R) → P)) → 
((P4  P)  P4) 
G = (((R  (S  P1)) → ((P2  S1)  R3)) → P)  (P  (P → ((R5 → P)  (S 
 P))))? 
 
8. (Alírio indeciso) Considere as três afirmações a seguir. 
H1: Se Alírio toma vinho e o vinho está ruim, ele fica com ressaca. 
H2: Se Alírio fica com ressaca, então ele fica triste e vai para casa. 
H3: Alírio vai ao seu encontro romântico com Virgínia ou ele fica triste e vai para 
casa. 
Suponha que as três afirmações anteriores são verdadeiras. A partir desse fato, qual 
das afirmações a seguir também é verdadeira. 
G1: Se Alírio toma vinho e este está ruim, então ele perde seu encontro romântico com 
Virgínia. 
G2: Se Alírio fica com ressaca e vai para casa, então ele não perde seu encontro 
romântico com Virgínia. 
G3: Se o vinho está ruim, então Alírio não o toma ou ele não fica com ressaca. 
G4: Se o vinho está ruim ou Alírio fica com ressaca, então ele fica triste. 
G5: Se Alírio toma vinho e vai para casa, então ele não fica triste se o vinho está ruim. 
 
9. Considere as sentenças a seguir: 
H1: Se Adriane não é inteligente, então Joyce é linda. 
H2: Se Joyce não é loura, então Érica é interessante. 
H3: Se Érica é linda ou interessante, então Adriane é inteligente. 
H4: Se Luciana não é inteligente, então Érica é interessante. 
H5: Se Luciana é linda, então Érica é interessante. 
Supondo que essas sentenças são verdadeiras. A partir desse fato, deduza o atributo de 
cada uma das meninas. Considere na solução as restrições a seguir. 
a) Há uma correspondência biunívoca entre pessoas e atributos. 
b) Na solução, conclui-se que Joyce é loura. 
 
10. Quatro detetives, Ana, Teresa, Cynthia e Melo estão investigando as causas de um 
assassinato, e cada um deles concluiu uma das afirmações a seguir: 
Ana: Se há pouco sangue na cena do crime, então o matador é um profissional. 
Teresa: Houve poucos ruídos no momento do crime ou o matador não é um 
profissional. 
Cynthia: A vítima estava toda ensanguentada ou houve muitos ruídos no momento do 
crime. 
Melo: Houve pouco sangue na cena do crime. 
Determine se o conjunto de conclusões dos detetives é satisfatível.