P3 - 2011.2

Prévia do material em texto

P3 de Lo´gica (INF1009) – 2011.2
Profs. Alexandre Rademaker e Cecilia Lustosa
Nome/Matr.:
1. Dada a estruturaA = 〈{a, b, c, d}, PA = {(a, b), (a, c), (a, d), (b, d), (c, a), (c, d)}〉. Escreva duas sentenc¸as,
uma verdadeira e outra falsa nesta estrutura. Traduza cada sentenc¸a para o portugueˆs.
2. Traduza para Lo´gica de Primeira Ordem apresentando a linguagem utilizada e identificando o domı´nio
sobre o qual a fo´rmula deve ser interpretada.
(a) Todo nu´mero primo possui exatamente dois divisores.
(b) Um dos divisores de um nu´mero primo e´ o pro´prio nu´mero primo.
(c) Se um nu´mero possuir mais de dois divisores distintos, enta˜o esse nu´mero na˜o e´ primo.
(d) Existe um nu´mero que e´ divisor de todo nu´mero.
3. Para cada item abaixo, responda se a afirmac¸a˜o e´ verdadeira ou falsa, justificando:
(a) α e β sa˜o logicamente equivalentes sse |= α→ β
(b) Se ∀xFx→ ∃yQy e´ va´lida, enta˜o ∃yQy e´ satisfat´ıvel.
(c) Se Γ e´ um conjunto de fo´rmulas va´lidas, e Γ |= α, enta˜o |= α
(d) Se α |= γ e γ |= β, enta˜o α |= β
4. Seja a estrutura dos reais 〈R,+,×〉 com a interpretac¸a˜o usual dos s´ımbolos de soma e multiplicac¸a˜o.
(a) Deˆ uma fo´rmula que defina o intervalo [0,∞)
(b) Deˆ uma fo´rmula que defina o conjunto {2}.
Page 2
5. Usando o Tableaux, responda se as fo´rmulas abaixo sa˜o tautologias ou na˜o. Caso na˜o sejam, interprete
o Tableaux constru´ıdo e apresente o contra-modelo.
(a) ∀z(Q(z)→ ∀y(S(z, y)→ P (y)))
(b) ∀x∃yQ(x, y)→ ∃y∀xQ(x, y)
(c) ∃xQ(x) |= ∀y(R(y)→ P (y))
Page 3
6. (opcional points) Usando Tableaux.
(a) Mostre A ∧B → C onde
A = ∀x∀y(Rxy → Ryx)
B = ∀x∀y∀z((Rxy ∧Ryz)→ Rxz)
C = ∀x∀y(Rxy → Rxx)
(b) Que propriedades sobre a relac¸a˜o R as fo´rmulas A, B e C esta˜o definido?
Page 4