Lógica para Computação 2a Prova 2017 2 Inf1009

2. Usando apenas a relação F(x, y): x é filho de y, defina:\n(a) a relação I(x, y): x é irmão de y\n∀x ∃y [F(x, y) ∧ ∀z (F(z, y) → I(x, z))]\n\n(b) a relação C(x, y): x é primo de y\n∀x ∃y [F(x, y) ∧ ∀z (F(z, y) ∧ ∀t (F(t, x) ∧ ∀k (F(t, k) → C(k, y)))))\n\n3. Considere a seguinte sentença: Os pais de Maria e João são amigos. Traduza essa sentença para a linguagem da LPO usando os símbolos\nm: Maria\nj: João\nA(x, y): x é amigo de y.\nAlém desses símbolos, use:\n(a) P(x, y) é a relação \"x é pai de y\"\n∃x (P(x, m) ∧ ∃y0 (P(y0, m) ∧ A(y0, j)))\n\n(b) P(x) é a função \"o pai de x\"\nA(P(m), P(j))\n\n 4. Verifique, através de tableaux, quais das afirmações abaixo são verdadeiras. Não se esqueça de escrever a resposta:\n(a) ∀x(I(x, a) x = a) → ∀y.L(x, b)\nF(∀x (L(x, 0) ∧ x = a) → ∀y.L(x, b))\nV(∀x (L(x, 0) ∧ x = a))\nF(∀x (L(x, 0)))\n\nA afirmação é válida, pois ao usar o método de tableaux não encontramos situações que falsifiquem\n\n(b) ∃y∀x(P(y) → P(f(x)))\nF(∃y∀x(P(y) → P(f(x)))\nF(∀x(P(a) → P(f(x)))\nF(f(a) → P(f(b)))\nV(P(g))\nF(P(g))\n\nA afirmação é válida, pois não conseguimos encontrar uma valoração que a falsificam, provado pelo lado do método de tableaux\n c) ∃x∀y∀z(R(x, y) → ¬P(y)) ↔ ∀x∃yR(x, y) → ¬∃P(x)\n{∃x∀y ∃z(R(x, y) → ¬P(y))}\nF ∀y ∃z(R(x, y.¬P(z)))\n∃y3(R(x, y)→ R(z, y))\nV ∃y.\n∃y ∀z(R(x, y) → ¬P(z))\nF(R(i, c) → ¬P(id))\n\nA conclusão lógica não é válida pois, existe valoração que a falsifica, como demonstrado ao lado pelo método de tableaux.\n 5. Verifique, através de tableaux, se o seguinte argumento é válido:\nApenas uma pessoa é fazendeira. João é fazendeiro. João mora em Botafogo. Logo, todo mundo que é fazendeiro mora em Botafogo.\n\\[\\forall x (x \\text{ é fazendeiro} \\land x \\text{ mora em } y)\\]\n\\[\\exists x (\\text{pb} \\land \\forall y (t(x,y) \\rightarrow m(y)))\\]\\]\n\\[f(x)\\]\n\\[M(y)\\]\nF\n\\[\\forall x (\\text{pb}(x) \\rightarrow M(x,y))\\]\nF\\[\\exists\\]\n\\[V (\\exists x (t(x,y) \\land \\neg t(x,y)))\\]\n\\[V (\\exists x (t(x,y) \\land \\neg y))\\]\n\\[F\\] \nO argumento não é válido, para seguindo \nTabelas (ramo permanencia aberto). Lógica para Computação - 2017.1 - P2\nProf.s Cecilia Englander e Guilherme Lima\nNome: Luca Ribeiro Damasceno\n1772973\n\n1. Formalize as seguintes sentenças na lógica de primeira ordem. Para cada uma delas, defina os elementos sintáticos necessários (constantes, funções e predicados) e elabore a formalização das mesmas.\n\n(a) Se Andreia é maior que qualquer matemático, então todo geólogo que é maior que o pai de Andreia é engenheiro.\n\\[O: Andreia\\]\n\\[F(x) : x \\text{ é inglês}\\]\n\\[P(x,y): x \\text{ mora em } y\\]\n\\[M(x): x \\text{ é matemático}\\]\n\\[I: \\text{ geólogos}\\]\n\\[\\forall x (M(x) \\rightarrow (g(x) > (p(y)) \\rightarrow F(y))))\\]\n\n(b) Todo mundo ama quem ama alguém.\n\\[A(x,y): x \\text{ ama } y\\]\n\\[\\forall x (y)(A(x,y)\\land V(y))\\]\n\n(c) Apenas o que é azul está em alguma caixa.\n\\[A(x): x \\text{ é azul}\\]\n\\[E(x): x \\text{ é caixa}\\]\n\n(d) Nenhum animal é gato ou cachorro.\n\\[A(x): x \\text{ é animal}\\]\n\\[G(x): x \\text{ é gato}\\]\n\\[C(x): x \\text{ é cachorro}\\]\n\n(e) Apenas Pedro é amado por alguém.\n\\[P: Pedro\\]\n\\[A(x,y): x \\text{ é amado por } y\\]\n\\[\\exists x (\\forall y (A(y,p) \\land \\neg(x=p)))\\]\n\\[\\exists n (A(x,p) \\land \\forall y (A(y,p) \\rightarrow y=x))\\]