lista8GabParcial Linguagem de primeira ordem pucrio inf1009

Prévia do material em texto

Lógica para Computação
2016.1 - Lista 8
Profs. Cecilia Englander e Guilherme Lima
1. Considere a linguagemL = 〈R1,a0,b0, f 2〉 em que:
R é uma relação;
a e b são constantes;
f é uma função.
(a) Faça o que se pede:
1. Escreva 4 termos dessa linguagem.
2. Escreva 3 fórmulas sem utilizar constantes.
3. Escreva 3 fórmulas utilizando apenas constantes.
(b) Apresente uma estrutura paraL e diga quais fórmulas definidas no item anterior são verdadeiras e quais são
falsas.
2. Dada a linguagemL = 〈<2, s1,+2,×2,00〉 considere a seguinte estrutura:
〈|A| = números naturais,
<A = a relação menor que,
sA = a função sucessor, isto é, s(x)= x+1,
+A = a função soma,
×A = a função produto,
0A = o número zero〉
(a) Traduza para a linguagem deA:
1. 2+2 = 4
2. Zero é o único número que não é sucessor de nenhum número.
3. Não existe um número maior que todos os outros.
4. Todo número par maior que 2 pode ser escrito como a soma de dois primos.
5. Todo quadrado perfeito par é divisível por 4.
(b) Verifique se é verdadeiro ou falso, justificando:
1. ∀x∃y(+(x, y)= x∧∀z(+(x,z)= x→ z = y))
2. ∀x∃y(+(x, y)=×(x, y))
3. ∀x∀y∀z((x < y ∧ y < z)→ x < z)
4. ∀x∀y∀z((x <×(y,z)→ (x < y ∨x < z)
3. Escreva uma sentença em lógica de primeira ordem que diferencie as estruturas abaixo, isto é, seja válida em uma
e não na outra:
1. G1 =< {a,b,c,d ,e}, {(a,b), (b,c), (b,d), (d ,e), (e,c), (c,d)}>
2. G2 =< {a,b,c,d ,e, f }, {(c,a), (a,d), (a, f ), (b, f ), (e, f ), (d ,e)}>
4. Verifique se os seguintes itens são verdadeiros ou falsos. Justifique através de tableaux.
1. ∀x∀y(L(x, y)→ x = y) |= ∀xL(x,x)
2. |= ∀x∀y((x = y ∧R(x, y))→R(x,x))
3. ∃x(P (x)→Q(x)) |= ∃xP (x)→∃xQ(x).
5. Considerando a linguagem L = 〈+2〉, escreva fórmulas que definam os seguintes conjuntos e relações sobre nú-
meros naturais:
(a) O número zero 0
Solução: zero(x)≡∀y(+(y,x)= y)
(b) Número ímpar
Solução:
impar (x)≡¬par (x), onde:
par (x)≡∃y (x =+(y, y))
(c) Relação de “menor que”
Solução: MenorQue(x, y)≡∃z(+(x,z)= y ∧ (+(z,z) 6= z))
(d) Relação “x é o dobro de y”
Solução: dobro(x, y)≡ (x =+(y, y))
(e) O número 2
Solução:
doi s(x)≡ (∃y (+(y, y)= x∧um(y))), onde:
um(x)≡ (¬zero(x)∧∀y (MenorQue(y,x)→ zero(y)))
6. Traduza as seguintes sentençcas para a linguagem L = 〈+2,∗2,<2〉.
(a) O produto de dois números é maior que a sua soma.
(b) Zero não é o quadrado de nenhum número.
(c) Existe um número que é menor que o produto de quaisquer dois números.
(d) Dado um número primo, existem exatamente dois números que o divide.
Solução:
(a) ∀x∀y < (+(x, y),×(x, y))
(b) ∀x(zero(x)→¬∃y(x =∗(y, y))), onde zero(x)≡+(x,x)= x
(c) ∃x∀y∀z(< (x,∗(y,z)))
(d) ∀x(P (x)→∃y∃z(¬y = z∧D(x, y)∧D(x,z)∧∀w(D(x,w)→ (w = y ∨w = z)))) onde,
D(x, y)≡∃z(∗(y,z)= x) (x é divizível por z) e
P (x)≡∃y∃z(x =×(y,z)∧¬y = z∧∀t∀w(x =×(t ,w)→ (t = y ∨ y = z))).
7. Considere a estruturaN+ = 〈N,+,0〉 para a linguagem L = 〈+2,00〉. Existe alguma diferença entre + da estrutura e
o +2 da linguagem? E entre o 0 da estrutura e o 00 da linguagem?
Solução: O +2 da linguagem é o símbolo da função binaria que é interpretada no conjunto dos números
naturais com a operação soma indicada pelo símbolo + da estrutura. O 00 da linguagem é o símbolo da
função com aridade 0 que é interpretada no conjunto dos números naturais com a constante 0 da estrutura.
8. Exiba duas fórmulas verdadeiras e duas falsas em N+, na linguagem do item acima. Faça isso sem o uso de
variáveis livres.
Solução:
Fórmulas Verdadeiras: 1. ∀x + (x,0)= x, 2. ∀y∃x + (y, y)= x
Fórmulas Falsas: 1. ∀x∀y x = y , 2. ∀x (¬(x = 0)∧∃y + (y,x)= y)
9. Considere a linguagem não lógica L = 〈P2,k0,Q1, f 1〉, ondeP eQ, de aridades 2 e 1, respectivamente, são símbolos
predicativos, f e um símbolo funcional de aridade 1, e, k é uma constante. Note que a informação sobre as
aridades já está indicada nos respectivos superescritos. SejaA a sequinte estrutura:
〈|A| = {a,b,c,d},
PA = {(a,b), (a,c), (a,d), (b,c), (b,d), (c,d)},
QA = {c,a},
f A = {(a,b), (b,c), (c,d), (d ,d)},
kA = a〉
Seja σ :Var s→ {a,b,c,d}, tal que σ(x)= a, σ(z)= b, σ(y)= a. Claro que σ associa valores para todas as variáveis
da linguagem (Vars). Pede-se, considerando-seA e σ:
(a) O elemento de {a,b,c,d} denotado por cada um dos seguintes termos: f (k), f ( f (z)), f 1000(y) e f 10
103
(x).
Onde f n(x) é uma forma abreviada para f ( f ( f . . . f (x) . . .)), isto é, aplicação de f n vezes.
Solução:
• σ¯( f (k))= f A(kA)= f A(a)= b
• σ¯( f ( f (z)))= f A( f A(σ(z)))= f A( f A(b))= f A(c)= d
• σ¯( f 1000(y))= f 1000A(σ(y))= f 1000A(a)= f 999A(b)= f 998A(c)= f 997A(d)= d ... f A(d)= d
• σ¯( f 10
103
(x))= f 1010
3
A(σ(x))= f 1010
3
A(a)= d
(b) O valor de verdade de cada uma das seguintes fórmulas, isto é,A |=α[σ] com α sendo:
i. ∃w( f (w)=w)
Solução: Verdadeiro para w = d .
ii. ∀y∃z(Q(z)∧ (P (z, y)∨P (y,z)))
Solução: Verdadeiro.
iii. ∃z( f (z)= y)
Solução:
Falso.
iv. ∀z(Q(z)∨ z = f (k)∨ z = f (z))
Solução: Verdadeiro.
v. ∃z∀x(P (z,x)∨P (x,z))
Solução:
Falso.
vi. ∀x(¬(x = f (x))→∃zP (z,x))
Solução:
Falso.
vii. ∃z∀x(¬(x = f (x))→ P (z,x))
Solução:
Falso.
(c) O que podemos dizer sobre o que é definido a partir de uma fórmula α(x, y), com exatamente duas variáveis
livres (x e y)? Exiba uma fórmula que define o conjunto {(b,d), (c,a)}.
Solução: Na fórmula α(x, y), as variáveis x e y não são ligadas nem da forma ∀x nem da forma ∃x.
A interpretação para os símbolos não-lógicos presentes na fórmula α(x, y) será dada numa estrutura
A. A noção de satisfatibilidade depende dos valores que damos às variáveis livres x y que ocorrem na
fórmula.
Uma possivel fórmula φ que define o conjunto {(b,d), (c,a)} é a seguinte:
φ(x, y)≡ ((¬∃zP (y,z)∧x = f (k))∨ ( f ( f (y))= x∧ y = k))
( f ( f (y))= y ∧ f (k)= x)∨ (Q(x)∧¬x = y ∧ y = k)
10. Determine o valor verdade para cada uma dessas afirmações, sendo o domínio o conjunto dos números reais.
Onde for apropriado, apresente um contra-exemplo.
(a) ∃x x2 = 2
Solução:
�R ∃x x2 = 2[σ]
Existe n ∈ |R| tal que �R x2 = 2[σ[x/n]]
Existe n ∈ |R| tal que �R n2 = 2
n =p2 ∈ |R|, portanto é verdadeiro.
(b) ∃x x2 =−1
Solução:
�R (∃x x2 =−1)[σ]
Existe n ∈ |R| tal que �R x2 =−1[σ[x/n]]
Existe n ∈ |R| tal que �R n2 =−1
n =p−1, n ∉ |R|, portanto é Falso.
(c) ∀x x2 6= x
Solução: �R (∀x x2 6= x)[σ]
Para todo m ∈ |R| tal que �R x2 6= x[σ[x/m]]
Para todo m ∈ |R| tal que �Rm2 6=m
Falso para m = 1.
11. Na estrutura de primeira ordemH= 〈Seres Humanos,Pai ,Mae〉, defina usando fórmulas:
(a) irmão
Solução: Seja a Linguagem = 〈pai2,mae2〉 (usaremos a mesma para todas as respostas nesta questão)
irmão(w,z)≡ (∃x(( pai(x,w)∧ pai(x,z))∨ ( mae(x,w)∧mae(x,z)))∧w 6= z)
(b) primo
Solução: pr imo(w,z)≡∃x∃y(i rmao(x, y)∧ (pai (x,w)∨mae(x,w))∧ (pai (y,z)∨mae(y,z)))
(c) avô
Solução: avô(x)≡∃y∃z((Pai (y,z)∨Mae(y,z))∧Pai (x, y))
(d) avó
Solução: avó(x)≡∃y∃z((Pai (y,z)∨Mae(y,z))∧Mae(x, y))
(e) tio
Solução: t io(w,z)≡∃x(pai (x,z)∧ i rmao(x,w))∨∃y(mae(y,z)∧ i rmao(y,w))
12. Considere uma linguagem de primeira ordem com o símbolo predicativo R. Pode-se ver as estruturas para esta
linguagem como sendo grafos simples dirigidos tal que R(x, y) indica que existe uma aresta de x para y (dirigida).
Para cada item abaixo, desenhe um grafo com pelo menos três vértices que satisfaça a fórmula.
(a) ∀x∀y(R(x, y)∨R(y,x)).
(b) ∀x∃yR(x, y), ∀x∀y∀z((R(x, y)∧R(y,z))→R(x,z)).
(c) ∃x∃y(R(x, y)∧R(y,x)), ∀x∀y(R(x, y)→∃z(R(x,z)∧R(y,z)).
Solução:
(a) R = {(a,b), (a,c), (b,c), (a,a), (b,b), (c,c)}
(b) R = {(a,a), (b,b), (c,c)}
(c) R = {(a,b), (b,a), (b,b), (a,a)} - há um terceiro vértice que ná se relaciona com nenhum vértice.
13. Considere a linguagem não lógicaL =< P2 >, onde P de aridade 2 é um símbolo predicativo. SejaA a sequinte
estrutura:
〈{a,b,c,d},
PA = {(b,a), (b,c), (b,d), (c,a), (c,d),(d ,a)}〉
Pede-se:
(a) Duas sentenças que não sejam equivalentes e que sejam verdadeiras nessa estrutura.
(b) Uma fórmula que defina o elemento a.
Solução:
(a) ∃x∃y(P (x, y)) e ¬∃x(P (x,x))
(b) a(x)≡∀y(¬x = y→ P (y,x))
14. Usando Tableaux indique se as fórmulas abaixo são fórmulas válidas ou não. Caso não seja apresente um contra-
exemplo.
(a) ∀x∀y(x = y)→ (∀xG(x)∨∀x¬G(x))
Solução: 1. F ∀x∀y(x = y)→ (∀xG(x)∨∀x¬G(x))
2. V ∀x∀y(x = y)
3. F ∀xG(x)∨∀x¬G(x)
4. F ∀xG(x)
5. F ∀x¬G(x)
6. FG(a)
7. F ¬G(b)
8. VG(b)
9. V ∀y(a = y)
10. V a = b
11. FG(b)
X
15. Negue as seguintes sentenças e mostre por tableaux que a sua resposta está correta:
1. ∀x∃yR(x, y)
2. ∃x∀yR(x, y)
3. ∀x∀yx = y
4. ∀x∀y∀z((R(x, y)∧R(y,z))→R(x,z))
5. ∀x∀y(R(x, y)∨R(y,x))
6. ∃x∀y¬x = y
7. ∀x∃y¬x = y
8. ∀x∀y(R(x, y)→R(y,x))
9. ∃x∃y¬R(x, y)
10. ∀x(¬x = a→R(a,x))
16. Traduza as seguintes sentenças para a linguagem da LPO. Quando possível, use a estrutura da questão 2.
(a) 2+2= 4
(b) Todo número possui um sucessor.
(c) Todo número é menor que seu sucessor.
(d) Todo número é sucessor de algum número.
(e) Todo número, exceto o zero, é sucessor de algum número.
(f) Zero é o único número que não é sucessor de nenhum número.
(g) Todo número diferente de zero é sucessor de algum número.
(h) Há um número menor que todos os outros.
(i) Há um menor número primo. (Precisa definir primo).
(j) Todo número pode ser escrito como a soma de dois números.
(k) Zero é o menor número natural.
(l) Não existe um número maior que todos os outros.
(m) Nenhum número é menor que zero.
(n) Todo número par maior que 2 pode ser escrito como a soma de dois primos.
(o) Todo número ímpar maior que 5 pode ser expresso como soma de três números primos (Conjectura fraca de
Goldbach).
(p) Todo quadrado perfeito par é divisível por 4.
(q) Todo número multiplicado por zero dá zero.
17. Negue as sentenças da questão anterior.