P2 - 2011.2

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

P2 de Lo´gica (INF1009) – 2011.2
Profs. Alexandre Rademaker e Cecilia Lustosa
Nome/Matr.:
1. Considere a estrutura dos nu´meros naturais com as func¸o˜es de multiplicac¸a˜o e soma, A = 〈N, ∗,+〉,
defina cada item abaixo. Dica: escolha a ordem correta de apresentar as definic¸o˜es, algumas podem
precisar de outras.
(a) A linguagem que voceˆ usara´ e a interpretac¸a˜o dos s´ımbolos da linguagem na estrutura.
(b) A relac¸a˜o “maior que”.
(c) O nu´mero zero.
(d) Os nu´meros primos.
(e) A relac¸a˜o “x e´ o quadrado de y”.
2. Na estrutura B = 〈Humanos, Pai,Mae,Casado〉, defina os itens abaixo. Dica: definic¸o˜es intermedia´rias
podem ajudar.
(a) A linguagem que voceˆ usara´ e a interpretac¸o˜a dos s´ımbolos da linguagem na estrutura.
(b) a relac¸a˜o “A e´ tio de B”.
(c) a relac¸a˜o “A e´ primo solteiro de primeiro grau de B”.
(d) a relac¸a˜o “A e´ cunhado de B”.
3. Escolha duas sentenc¸as abaixo e traduza para a linguagem L = 〈+2, ∗2, <2〉.
(a) O produto de dois nu´meros e´ maior que a sua soma.
(b) Zero na˜o e´ o quadrado de nenhum nu´mero.
(c) Existe um nu´mero que e´ menor que o produto de quaisquer dois nu´meros.
(d) Dado um nu´mero primo, existem exatamente dois nu´meros que o divide.
4. 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). Escolha dois itens abaixo, para cada item, desenhe um grafo com pelo menos treˆs
ve´rtices que satisfac¸a a fo´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)).
Page 2
5. Considere a linguagem na˜o lo´gica L =< P 2 >, onde P de aridade 2 e´ um s´ımbolo predicativo. Seja A a
sequinte estrutura:
〈{a, b, c, d},
PA = {(b, a), (b, c), (b, d), (c, a), (c, d)}〉
Pede-se:
(a) Duas sentenc¸as que na˜o sejam equivalentes e que sejam verdadeiras nessa estrutura.
(b) Uma fo´rmula que defina o elemento a.
6. (extra points) Considere as fo´rmulas ∃x∃y(p(x) = p(y) ∧ ¬(x = y)) e ∀x(p(x) = a → Q(a, x)) onde p e´
uma func¸a˜o, Q e´ uma relac¸a˜o bina´ria e a e´ uma constante. Construa:
(a) Uma estrutura na qual essas fo´rmulas sejam ambas verdadeiras.
(b) Uma estrutura na qual uma dessas fo´rmulas seja verdadeira e a outra seja falsa.
Page 3