P2 - 2011.1 - Gabarito

Prévia do material em texto

P2 de Lo´gica (INF1009) – 2011.1
Profs. Alexandre Rademaker e Cecilia Lustosa
Nome/Matr.:
1. (1/4 points) Considere a linguagem na˜o lo´gica L =< P 2, Q1, f1, k0 >, onde P e Q, de aridades 2
e 1 respectivamente, sa˜o s´ımbolos predicativos, 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},
PA = {(a, b), (a, c), (a, d), (b, c), (b, d), (c, d)},
QA = {c, a},
fA = {(a, b), (b, c), (c, d), (d, a)}, kA = d >
Pede-se:
(a) O elemento de {a, b, c, d} denotado por cada um dos seguintes termos: f(k), f(f(k)), f1000(k)
e f10
103
(k). Obs: fn(x) e´ uma abreviac¸a˜o para f(f(. . . f(x) . . .))), n-vezes, isto e´, aplicar f
n-vezes a x.
Solution: f(k) = a, f(f(k)) = b, f1000(k) = d e f10
103
(k) = d.
(b) O valor de verdade de cada uma das seguintes fo´rmulas, isto e´, A |= α com α sendo: ∃w(f(w) =
w), ∃z∀x(x 6= z → P (z, x)) e ∃z1∃z2(f(z1) = f(z2) ∧ z1 6= z2).
Solution:
1. A 6|= ∃z1∃z2(f(z1) = f(z2) ∧ z1 6= z2),
2. A 6|= ∃w(f(w) = w) e
3. A |= ∃z∀x(x 6= z → P (z, x))
1
2. (1/4 points) Seja uma estrutura A como a do item anterior e uma func¸a˜o de associac¸a˜o de valores
a`s varia´veis σ. Uma fo´rmula α(x), que tem somente a varia´vel x livre, define um subconjunto do
domı´nio de A, a saber,
{a/a ∈ Dom(A) e A |= α(x)[σ[x← a]]}
Por exemplo a fo´rmula x = k define o conjunto formado unicamente por d e a fo´rmula Q(x) define
{c, a}. Esse conceito de fo´rmula definidora vale para qualquer estrutura e linguagem na˜o-lo´gica
associada. Quando a fo´rmula definidora e´ da forma β(x, y) , com x e y as u´nicas varia´veis livres,
β(x, y) define uma relac¸a˜o bina´ria.
(a) Considere a linguagem L2 =< P 2 >, e a parte da estrutura A, do ı´tem 1 que interpreta P , ou
seja, considere a estrutura < {a, b, c, d}, PA = {(a, b), (a, c), (a, d), (b, c), (b, d), (c, d)} >. Exiba
uma fo´rmula definidora para os elementos a e b do domı´nio.
Solution:
1. A(x) ≡ ∀y(x 6= y → P (x, y))
2. B(x) ≡ ∃ya∃yc∃ydP (ya, x) ∧ P (x, yc) ∧ P (x, yd) ∧ ya 6= yc 6= yd
O conjunto {a, b}, para quem entendeu o enunciado desta forma, poderia agora ser facilmente
definido como: A(x) ∨B(x).
(b) Considere a estrutura dos nu´meros reais com a operac¸a˜o de multiplicac¸a˜o. Defina: (1) o nu´mero
zero; (2) Os nu´meros negativos (e na˜o nulos); (3) o nu´mero -1. (Dica: resolva nesta ordem!)
Solution:
1. zero(x) ≡ ∀zz ∗ x = x
2. negativoNaoNulo(x) ≡ ¬(∃z(z ∗ z = x)) ∧ ¬zero(x)
3. menosUm(x) ≡ ∀z(∗(x ∗ x) = z) ∧ negativoNaoNulo(x)
(c) Em < Seres Humanos, Pai2,Mae2 >, defina a relac¸a˜o “tio” ou a relac¸a˜o “primo”.
Solution:
irmao(a, b) ≡ (∃x pai(x, a) ∧ pai(x, b)) ∨ (∃y mae(y, a) ∧mae(y, b))
tio(a, b) ≡ (∃x pai(x, b) ∧ irmao(x, a)) ∨ (∃y mae(y, b) ∧ irmao(y, a))
primo(a, b) ≡ ∃x∃y irmao(x, y) ∧ (pai(x, a) ∨mae(x, a)) ∧ (pai(y, b) ∨mae(y, b))
2
3. (1/4 points) Considere a linguagem de 1a ordem onde:
• R(x,y) – x respeita y
• M(x,y) – x esta´ matriculado na disciplina y (obs: de fato, ao dizer que y ja´ e´ disciplina, as
formalizac¸o˜es abaixo podem ser simplificadas).
• P(x) – x e´ um professor
• A(x) – x e´um aluno
• D(x) – x e´ uma disciplina
• “Maria” uma constante denotando o indiv´ıduo Maria.
Traduza cada uma das sentenc¸as abaixo para a linguagem de primeira ordem com o alfabeto acima:
(a) Maria respeita todos os professores
Solution: ∀y(P (y)→ R(Maria, y))
(b) Alguns professores respeitam Maria
Solution: ∃x(P (x) ∧R(x,Maria))
(c) Nenhum aluno esta´ matriculado em todas as disciplina
Solution:
¬∃x∀y(A(x) ∧D(y))→M(x, y)
(d) Na˜o ha´ disciplinas em que todos os alunos estejam nela matriculados
Solution:
¬∃x∀y(D(x) ∧A(y))→M(y, x)
4. (1/4 points) Defina uma linguagem para as estruturas abaixo e escreva uma sentenc¸a em lo´gica de
primeira ordem que diferencie as estruturas, isto e´, seja va´lida em uma e na˜o na outra:
G1 =< {a, b, c, d, e}, {(a, b), (c, a), (c, d), (d, b), (b, e), (d, e), (c, c)} >
G2 =< {a, b, c, d, e}, {(b, a), (a, c), (c, d), (d, b), (b, e), (d, e)} >
Solution: A linguagem e´ L =< A2 >. Basta um predicado bina´rio pois as duas estruturas
conte´m apenas uma relac¸a˜o bina´ria sobre elementos dos seus domı´nios.
∃x∀y¬(y = x)→ ¬A(y, x)
3