lista 04 - FTC

Prévia do material em texto

Universidade Federal da Grande Dourados
Faculdade de Ciências Exatas e Tecnologia
Curso de Bacharelado em Sistemas de Informação
Fundamentos de Teoria da Computação
Prof. Rodrigo Yoshikawa Oeiras
Lista de Exercícios 04: Lógica de Predicados
1. É possível chegar a uma conclusão a partir da frase: “Todas as flores são plantas. 
Amores-perfeitos são flores.” (OBS. Amores-perfeitos é um tipo de flor).
2. É possível chegar a uma conclusão a partir da frase: “Algumas flores são vermelhas. 
Algumas flores são roxas. Amores-perfeitos são flores.” 
3. Justifique cada passo da sequência de demonstração a seguir para a fbf:
( x)[P(x)∃ →Q(x)]→[( x)P(x)∀ →( x)Q(x)]∃
1. ( x)[P(x)∃ →Q(x)]
2. P(a)→Q(a)
3. ( x)P(x)∀
4. P(a)
5. Q(a)
6. ( x)[Q(x)]∃
4. Justifique cada passo da sequência de demonstração a seguir para a fbf:
( x)P(x) ( x)(P(x)∃ ∧ ∀ →Q(x))→( x)Q(x)∃
1. ( x)P(x)∃
2. ( x)(P(x)∀ →Q(x))
3. P(a)
4. P(a)→Q(a)
5. Q(a)
6. ( x)Q(x)∃
5. Considere a FBF abaixo:
( y)( x)Q(x,y)∀ ∃ →( x)( y)Q(x,y)∃ ∀
a) Considerando o domínio dos inteiros, encontre uma interpretação em que a FBF 
não é válida.
b) Encontre o erro na demonstração abaixo.
1. ( y)( x)Q(x,y)∀ ∃ hipótese
2. ( x)Q(x,y)∃ 1,pu
3. Q(a,y) 2,pe
4. ( y)Q(a,y)∀ 3,gu
5. ( x)( y)Q(x,y)∃ ∀ 4,ge
6. Mostre que as FBFs abaixo são válidas:
a) ( x)P(x)∀ →( x)[P(x) ∀ ∨ Q(x)]
b) ( x)( y)P(x,y)∃ ∃ →( y)( x)P(x,y)∃ ∃
c) ( x)( y)Q(x,y)∀ ∀ → ( y)( x)Q(x,y)∀ ∀
d) ( x)( R(x) ∃ ∨ S(x) ) → { [( x)R(x)]∃ ' → ( x)S(x) ∃ }
e) (∀x)[P(x) → Q(x)] → [ ( x)P(x)∀ → ( x)Q(x) ∀ ]
f) (∀y)[Q(x,y) → P(x)] → [ ( y)Q(x,y)∃ → P(x) ]
Universidade Federal da Grande Dourados
Faculdade de Ciências Exatas e Tecnologia
Curso de Bacharelado em Sistemas de Informação
7. Use a lógica de predicados para provar o argumento: “Algumas plantas são flores. 
Todas as flores têm um cheiro doce. Portanto, algumas plantas têm um cheiro doce”. 
Use P(x), F(x), D(x). para denotar plantas, flores e doce.
8. Use a lógica de predicados para provar o argumento: Todo crocodilo é maior do que 
qualquer jacaré. Samuca é um crocodilo, mas existe uma serpente e Samuca não é 
maior do que esta serpente. Portanto, alguma coisa não é um Jacaré. C(x), J(x) , 
M(x,y), s, S(x).
9. Use a lógica de predicados para provar o argumento: “Existe um ator de cinema que é 
mais rico que todo o mundo. Qualquer pessoa que é mais rica do que odo o mundo 
paga mais imposto do que todo o mundo. Portanto existe um ator de cinema que 
paga mais imposto do que todo o mundo. A(x), R(x,y) e I(x,I)” 
Respostas
1. A conclusão é que Amores-perfeitos são plantas. Em lógica de predicados, a 
expressão fica: ( x)(F(x)∀ →P(x)) (F(a)). Desta expressão podemos concluir que P(a).∧
2. Lendo as frases, não podemos fazer uma conclusão. Do ponto de vista de lógica 
predicada, temos: ( x)(F(x) V(x)) (( x)(F(x) R(x))) (F(a)). Nas hipóteses, temos∃ ∧ ∧ ∃ ∧ ∧ 
expressões com o quantificador existencial. Poderíamos pensar em aplicar o “pe” 
para introduzir a constante “a”. Entretanto, o “a” já foi usado anteriormente e deve 
aparecer numa hipótese. Se o quantificador fosse universal, poderíamos usar o “pu”.
3. (1) hip; (2) pe; (3) hip(dedução); (4) pu; (5) 2,4,mp; (6) 5,ge.
4. (1) hip; (2) hip; (3) 1,pe; (4) 2,pu; (5) 3,4,mp; (6) 5,ge.
5. a) Se Q(x,y) é “x<y”, para todo o y há um x em que x<y, mas não há um inteiro x que 
é sempre menor do que qualquer y. b) de 3 para 4, não podemos usar gu porque y é 
uma variável livre (veja o passo 2).
6.
a) ( x)P(x)∀ →( x)[P(x)∀ ∨Q(x)]
1. ( x)P(x) hipótese∀
2. P(x) 1,pu
3. P(x) Q(x) 2,ad∨
4. ( x)(P(x)∀ ∨Q(x)) 3,gu
b) ( x)( y)P(x,y)∃ ∃ →( y)( x)P(x,y)∃ ∃
1. ( x)( y)P(x,y) hipótese∃ ∃
2. ( y)P(a,y) 1,pe∃
3. P(a,b) 2,pe
4. ( x)P(x,b) 3,ge∃
5. ( y)( x)P(x,y) 4,ge∃ ∃
c) ( x)∀ ( y)Q(x,y)∀ → ( y)( x)Q(x,y)∀ ∀
1. ( x)( y)Q(x,y)∀ ∀ hipótese
2. ( y)Q(x,y)∀ 1,pu
3. Q(x,y) 2,pu
4. ( x)Q(x,y) 3,gu∀
5. ( y)( x)Q(x,y) 4,gu∀ ∀
d) ( x)(R(x)∃ ∨S(x)) → [(( x)R(x)∃ )' → ( x)S(x)∃ ]
1. (∃x)(R(x)∨S(x)) hipótese
Universidade Federal da Grande Dourados
Faculdade de Ciências Exatas e Tecnologia
Curso de Bacharelado em Sistemas de Informação
2. ((∃x)R(x))' hipótese
3. R(a)∨S(a) 1,pe
4. ( x)∀ (R(x))' 2,neg
5. (R(a))' 4,pu
6. S(a) 3,5,sd
7. (∃x)S(x) 6,ge
e) (∀x)[P(x) → Q(x)] → [( x)P(x)∀ → ( x)Q(x)∀ ]
1. (∀x)[P(x) → Q(x)] hipótese
2. (∀x)P(x) hipótese
3. P(x) → Q(x) 1,pu
4. P(x) 2,pu
5. Q(x) 3,4,mp
6. (∀x)Q(x) 5,gu
f) (∀y)[Q(x,y) → P(x)] → [( y)Q(x,y)∃ → P(x)]
1. (∀y)[Q(x,y) → P(x)] hipótese
2. (∃y)Q(x,y) hipótese
3. Q(x,a) 2,pe
4. Q(x,a) → P(x) 1,pu
5. P(x) 3,4,mp
7. (∃x)[P(x)∧F(x)]∧(∀y)[F(y) → D(y)] → (∃x)[P(x)∧D(x)]
1. (∃x)[P(x)∧F(x)] hipótese
2. (∀y)[F(y) → D(y)] hipótese
3. P(a)∧F(a) 1,pe
4. F(a) → D(a) 2,pu
5. F(a) 3,simp
6. D(a) 4,5,mp
7. P(a) 3,simp
8. P(a)∧D(a) 6,7,conj
9. (∃x)[P(x)∧D(x)] 8,ge
8. ( x)( y)[C(x) J(y) → M(x,y)] C(s) ( x)[S(x) M’(s,x)] → ( x)[J(x)]’∀ ∀ ∧ ∧ ∧ ∃ ∧ ∃
1. ( x)( y)[C(x) J(y) → M(x,y)]∀ ∀ ∧ hip
2. C(s) hip
3. ( x)[S(x) M’(s,x)]∃ ∧ hip
4. ( y)[C(s) J(y) → M(s,y)]∀ ∧ 1, pu
5. S(a) M’(s,a)∧ 3, pe 
6. C(s) J(a) → M(s,a)∧ 4, pu
7. M’(s, a) 5, simp
8. [C(s) J(a)]’∧ 6, 7, mt
9. C’(s) ∨ J’(a) 8, De Morgan
10. [C’(s)]’ 2, dn
11. [C’(s)]’ → J’(a) 9, cond
12.C(s) → J’(a) 11, dn
13.J ’(a) 2,12,mp
14. ( x)[J(x)]’∃ 13, ge
9. (∃x)(A(x)∧(∀y)R(x,y))∧(∀x)(∀y)(R(x,y) → I(x,y)) → (∃x)(A(x)∧(∀y)I(x,y))
1. (∃x)(A(x)∧(∀y)R(x,y)) hipótese
2. A(a)∧(∀y)R(a,y) 1,pe
Universidade Federal da Grande Dourados
Faculdade de Ciências Exatas e Tecnologia
Curso de Bacharelado em Sistemas de Informação
3. A(a) 2,simp
4. (∀x)(∀y)(R(x,y) → I(x,y)) hipótese
5. (∀y)(R(x,y) → I(x,y)) 4,pu
6. R(a,y) → I(a,y) 5,pu
7. (∀y)R(a,y) 2,simp
8. R(a,y) 7,pu
9. I(a,y) 6,8,mp
10.(∀y)I(a,y) 9,gu
11.A(a)∧(∀y)I(a,y) 3,10,conj
12.(∃x)(A(x)∧(∀y)I(x,y)) 11,ge