P3 - 2011.1 - Gabarito

Prévia do material em texto

P3 de Lo´gica (INF1009) – 2011.1
Profs. Alexandre Rademaker e Cecilia Lustosa
Nome/Matr.:
1. Resolva os itens abaixo.
(a) Considerando a estrutura < Nat,+3 > escreva uma fo´rmula que defina a relac¸a˜o “x e´ menor que o triplo de
y”. A relac¸a˜o +(n,m, k) indica que k = m+ n.
Solution:
T<(x, y) ≡ ∃nT (n, y) ∧ ¬(x ≥ n)
onde
T (y, x) ≡ ∃z + (x, x, z) ∧+(z, x, y)
onde
x ≥ y ≡ ∃n+ (y, n, x)
(b) Considerando a estrutura < Nat,+2 >, esreva uma fo´rmula que defina “os nu´meros pares”.
Solution:
par(x) ≡ ∃z + (z, z) = x
(c) Escreva uma sentenc¸a que distingua as estruturas < N,≤2> e < R,≤2>.
Solution:
∃x∀yx ≤ y
ou
∀x∃yy ≤ x ∧ ¬(x = y)
ou
∀x∀y(x ≤ y)→ (∃z(x ≤ z) ∧ ¬(z ≤ y) ∧ ¬(x = z) ∧ ¬(z = y)
2. Considere a linguagem na˜o lo´gica L =< f1, k0 >, onde f e´ um s´ımbolo funcional de aridade 1, e, k e´ uma constante.
Note que a informac¸a˜o sobre as aridades ja´ esta´ indicada nos respectivos superescritos. Seja A a sequinte estrutura
< {a, b, c, d},
fA = {(a, b), (b, c), (c, d), (d, a)},
kA = d >
Pode-se definir, nesta estrutura, o conjunto {c, a} atrave´s de uma fo´rmula da linguagem L? Se sim, apresente uma
fo´rmula que defina o conjunto.
Solution:
C(x) ≡ x = f3(k)
e
A(x) ≡ x = f(k)
logo {c, a} ≡ C(x) ∨A(x).
Outra soluc¸a˜o e´ poss´ıvel, C(x) ≡ f(x) = k ∨ f(k) = x.
3. Argumente sobre a validade da seguinte afirmac¸a˜o: “Fixada uma estrutura A e uma fo´rmula α que na˜o possui
varia´veis livres, tem-se que A |= α [σ1] tem o mesmo valor de verdade de A |= α [σ2] para quaisquer func¸o˜es σ1 e
σ2.
1
Solution: O argumento fundamental e´ mostrar que se a fo´rmula na˜o tem varia´veis livres, as func¸a˜o de
substituic¸a˜o na˜o sera˜o usadas para sua avaliac¸a˜o na estrutura.
4. Usando Tableaux, escolha dois itens abaixo e verifique se cada item abaixo e´ verdadeiro ou falso, justificando
(via Tableaux).
(a) ∃xA(x)→ ∃xB(x) |= ∃x(A(x) ∧B(x))
(b) ∃x∀yR(x, y) |= ∀y∃xR(x, y)
(c) ¬∀x¬A(x) |= ∃xA(x)
(d) ∀xA(x) ∧ ∀xB(x) |= ∀x∀y(A(x) ∧B(y))
Solution: Apenas a letra A na˜o e´ consequeˆncia lo´gica. Os Tableaux podem ser produzidos no site http:
//www.umsu.de/logik/trees/.
2