lista5Gab PUC RIO Logica INf1009

Prévia do material em texto

Lógica para Computação
2016.1 – Lista 5
Exercícios para P2
Profs. Cecilia Englander e Guilherme Lima
1. Traduza as seguintes sentenças para a linguagem da LPO. Para isso, utilize:
b: Bruno
a: Andreia
E(x): x é engenheiro
G(x): x é geólogo
M(x): x é matemático
> (x, y): x é maior que y
p(x) : o pai de x
(1) Bruno é engenheiro.
Solução: E(b)
(2) Bruno é engenheiro ou geólogo
Solução: E(b)∨G(b)
(3) Bruno e Andreia são engenheiros.
Solução: E(b)∧E(a)
(4) Se Bruno é engenheiro, então ele não é geólogo.
Solução: E(b)→¬G(b)
(5) Se Bruno não é engenheiro, tampouco o é Andreia.
Solução: ¬E(b)→¬E(a)
(6) Ninguém é geólogo.
Solução: ¬∃xG(x) ou ∀x¬G(x)
(7) Todo mundo é geólogo.
Solução: ∀xG(x)
(8) Todo geólogo é engenheiro.
Solução: ∀x(G(x)→ E(x))
(9) Alguns geólogos são engenheiros.
Solução: ∃x(G(x)∧E(x))
(10) Alguns engenheiros são geólogos.
Solução: ∃x(E(x)∧G(x))
(11) Alguns engenheiros não são geólogos.
Solução: ∃x(E(x)∧¬G(x))
(12) Há quem não seja engenheiro nem geólogo.
Solução: ∃x(¬E(x)∧¬G(x))
(13) Há quem não seja engenheiro e geólogo.
Solução: ∃x¬(E(x)∧G(x))
(14) Se Andreia é geóloga, então ela é maior que algum matemático.
Solução: G(a)→∃x(M(x)∧> (a,x))
(15) Todo geólogo é maior que algum engenheiro.
Solução: ∀x(G(x)→∃y(E(y)∧> (x, y)))
(16) Todo geólogo que é engenheiro é maior que algum matemático.
Solução: ∀x((G(x)∧E(x))→∃y(M(y)∧> (x, y)))
(17) Alguns geólogos são maiores que qualquer engenheiro.
Solução: ∃x(G(x)∧∀y(E(y)→> (x, y)))
(18) Qualquer geólogo é maior que todo engenheiro.
Solução: ∀x(G(x)→∀y(E(y)→> (x, y)))
(19) Nenhum matemático é engenheiro ou geólogo.
Solução: ¬∃x((M(x)∧E(x))∨ (M(x)∧G(x))) ou ¬∃x(M(x)∧ (E(x)∨G(x)))
(20) Qualquer geólogo maior que um engenheiro é maior que um matemático.
Solução: ∀x((G(x)∧∃y(E(y)∧> (x, y)))→∃z(M(z)∧> (x,z)))
(21) Pelo menos um geólogo é maior que algum matemático.
Solução: ∃x(G(x)∧∃y(M(y)∧> (x, y)))
(22) Qualquer matemático é maior que Bruno e Andreia.
Solução: ∀x(M(x)→ (> (x,b)∧> (x,a)))
(23) Se Andreia é maior que algum engenheiro, então ela é maior que algum geólogo.
Solução: ∃x((E(x)∧> (a,x))→∃y(G(y)∧> (a, y)))
(24) Se todo engenheiro que for maior que Bruno é maior que Andreia, então Bruno é maior que Andreia.
Solução: (∀x((E(x)∧> (x,b))→> (x,a))→> (b,a))
(25) Se todo geólogo que é maior que Andreia é engenheiro, então Andreia é maior que qualquer matemático.
Solução: (∀x((G(x)∧> (x,a))→ E(x))→∀y(M(y)∧> (a, y)))
(26) Nenhum engenheiro é maior que algum geólogo.
Solução: ¬∃x(E(x)∧∃y(G(y)∧> (x, y)))
(27) Todo engenheiro é maior que Bruno, mas não maior que Andreia.
Solução: ∀x(E(x)→ (> (x,b)∧¬> (x,a)))
(28) Qualquer engenheiro maior que algum geólogo é maior que todos os matemáticos.
Solução: ∀x((E(x)∧∃y(G(y)∧> (x, y)))→∀z(M(z)→> (x,z)))
(29) Se Andreia é maior que qualquer matemático e ela é matemática, então Andreia é maior que si mesma.
Solução: ((∀x(M(x)→> (a,x)))∧M(a))→> (a,a)
(30) O pai de Bruno é engenheiro.
Solução: E(p(b))
(31) Todo engenheiro é maior que o pai de Bruno.
Solução: ∀x(E(x)→> (x,p(b)))
(32) O pai do pai de Bruno é engenheiro.
Solução: E(p(p(b)))
(33) O pai de algum engenheiro é matemático.
Solução: ∃x(E(x)∧M(p(x)))
(34) Bruno é o pai de Andreia.
Solução: b = p(a)
(35) O pai de Bruno é maior que o pai de Andreia.
Solução: > (p(b),p(a))
(36) Se Bruno é o pai de Andreia, então Bruno é maior que Andreia.
Solução: b = p(a)→> (b,a)
2. Traduza as seguintes sentenças para a linguagem da LPO:
1. Todo número primo é maior que 1.
2. Se existir um número tal que seu produto por qualquer número seja par, então existe número par.
Solução: N (x): x é um número
Par (x): x é par
X (x, y): o resultado do produto x.y
“Existe um número tal que seu produto por qualquer número é par”:
∃x(N (x)∧∀y(N (y)→ Par (X (x, y)))) ou ∃x∀y(N (x)∧ (N (y)→ Par (X (x, y))))
“Existe número par”: ∃x(N (x)∧Par (x))
Frase completa (resposta):
∃x(N (x)∧∀y(N (y)→ Par (X (x, y))))→∃x(N (x)∧Par (x))
3. Se todo número inteiro é divisível por x, então x é igual a 1.
4. Nem todo número natural é par;
5. Zero é um número.
6. Nenhum número natural é negativo;
Solução: Adotando a seguinte convenção:
N (x) : x é um numero natural,
M(x) : x é negativo.
obtemos a seguinte simbolização para a afirmação considerada: ¬∃x(N (x)∧M(x)).
7. Existe um número natural maior que 0;
Solução: Adotando a seguinte convenção:
N (x) : x é número natural,
M(x, y) : x é maior que y ,
0 : o número zero.
obtemos a seguinte simbolização para a afirmação considerada: ∃x(N (x)∧M(x,0))
8. A soma de dois números ímpares quaisquer resulta em um número par;
Solução: Adotando a seguinte convenção:
I (x) : x é um número impar,
g (x, y) : a soma de x e y ,
P (x) : x é um número par,
obtemos a seguinte simbolização para a afirmação considerada: ∀x∀y((I (x)∧ I (y))→ P (g (x, y))
9. Algum número natural divide algum número natural;
Solução: Podemos reescrever esse enunciado do seguinte modo:
‘Existe pelo menos um objeto x, tal que x é um número natural e existe pelo menos um objeto y , tal que
y é um número natural e x divide y .’
Adotando a seguinte convenção:
N (x) : x é um número natural,
D(x, y) : x divide y .
obtemos a seguinte simbolização para a afirmação considerada: ∃x(N (x)∧∃y(N (y)∧D(x, y)))
10. O conjunto dos naturais tem mínimo;
Solução: Podemos reescrever essa sentença como:
‘Existe um número natural que é menor que todos os outros números naturais’.
Adotando a seguinte convenção:
N (x) : x é número natural,
Assim, obtemos ∃x(N (x)∧∀y((N (y)∧¬(x = y))→ (x < y)))
11. O conjunto dos números naturais não tem elemento máximo;
Solução: Podemos reescrever essa sentença como:
‘Não existe um maior número natural’.
¬∃x((N (x)∧∀y((N (y)∧¬(x = y))→ x > y))
12. Zero é o menor número natural.
13. Zero é menor que qualquer número.
Solução: ∀x(N (x)→< (0,x))
14. Se qualquer número é natural, então zero é natural.
Solução: ∀x((N (x)→ I (x))→ I (0))
15. Nenhum número é menor que zero.
Solução: ¬∃x(N (x)∧< (x,0))≡∀x¬(N (x)∧< (n,0))≡∀x(N (x)→¬< (x,0))
16. Não existe um número tal que todos os números são menores do que ele.
Solução: ¬∃x(N (x)∧∀y(N (y)→< (y,x)))≡∀x¬(N (x)∧∀y(N (y)→< (y,x)))≡∀x(¬N (x)∨¬∀y(N (y)→<
(y,x)))
17. Não existe um número tal que nenhum número é menor do que ele.
Solução: ¬∃x(N (x)∧¬∃y(N (y)∧< (y,x)))≡∀x¬(N (x)∧∀y¬(N (y)∧< (y,x)))≡∀x(¬N (x)∨¬∀y¬(N (y)∧<
(y,x)))≡∀x(¬N (x)∨¬∀y(¬N (y)∨¬< (y,x)))
18. Um natural p > 1 é chamado um número primo se ele não é divisivel por qualquer natural diferente de 1 e
p.
19. Se um número p for igual a 2 ou se o resto da divisão de p por 4 for 1, então p será resultante da soma de
dois quadrados perfeitos.
20. Teorema de Pitágoras: “A soma dos quadrados dos catetos é igual ao quadrado da hipotenusa".
Solução: Sem levar em conta que tem que ser os catetos e a hipotenusa de um mesmo triâgulo:
q(x): o quadrado de x,
+(x, y): x+ y ,
C (x): x é cateto,
H(x): x é hipotenusa
∀x∀y∀z((C (x)∧C (y)∧H(z))→ (+(q(x),q(y))= q(z)))
ou
T (y): y é triângulo
q(x): o quadrado de x,
+(x, y): x+ y ,
C (x, y): x é cateto de y ,
H(x, y): x é hipotenusa de y
∀x∀y∀z∀t ((T (x)∧C (y,x)∧C (z,x)∧H(t ,x)∧¬y = z)→ (+(q(y),q(z))= q(t )))
21. Existe um número que somado ao triplo de 2 dá 20;
Solução: N (x): x é um número
t (x): o triplo de x
s(x, y): a soma x+ y
d : 2
v : 20
∃x(N (x)∧ s(x, t (d))= v)
22. Nenhum número é sucessivo de zero.
23. O sucessivo de zero é um.
24. Se o sucessivo de dois números são iguais, então esses números são iguais.
25. O cubo do quadrado de 2 é par.
26. A raiz quadrada de 3 é ímpar;
Solução: Adotando a seguinte convenção:
a : 3,
g (x) : raiz quadrada de x,
I (x) : x é ímpar,
obtemosa seguinte simbolização para a afirmação considerada: I (g (a)).
27. O triplo do dobro da raiz quadrada de 4 é par;
Solução: Adotando a seguinte convenção:
q : 4,
r (x) : raiz quadrada de x,
d(x) : o dobro de x,
t (x) : o triplo de x,
P (x) : x é par,
obtemos a seguinte simbolização para a afirmação considerada: P (t (d(r (q)))).