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

INF1009, Lógica para Computação, 2017.2, Prova 3 Profs. Cecília Englander e Guilherme F. Lima Matrícula/Nome:_____ Lucas Rebello Nóamo 1721275 Questão 1 Considere a linguagem não lógica |_|, onde Q é de aridade 2 é um símbolo predicativo, f de aridade e é um símbolo funcional e a é uma constante. Seja A a seguinte estrutura: †{|} = {(a, c), (b, b), (a), (c, c), (a, c), (b, b)}, (b, d, b) [](b, c(a, b, c), [c)] (a) Uma fórmula que defina o elemento a. “x = f (f(a)) (b) Uma fórmula que defina o conjunto {(b, c)}. x = f(f(p(a))) R: [x, f) ≡ a (f) e F(f(x)) continua. Full) Questão 2 Apresente uma estrutura em que a fórmula abaixo seja falsa e outra em que ela seja verdadeira. ¬(∀y∃x)P(x, y) ∧ P(y, 1)) [U] = {a, b, 1} ρ^ν = {(a, b)} é (a|x) = {a, b, 1} ρ^α = {(a, b), (b, 1), (1, 1)} Falso Questão 3 Considerando a estrutura ⟨N, +⟩ para a LPO com igualdade, defina a relação “x é maior que o triplo de y” sabendo que: (a) ‘+’ é o predicado ternário +⟨ⅲ, m, k⟩ que indica que k = m + n. T(x, y, m) ≡ ∃y ((y, y, y) ∧ (y, y; x)) R: [x] ≡ (∀x)([y]) → B(x)) (b) ‘+’ é a função binária soma. Mesmo a + T(x, y, m) ≡ ∃ⅲ (2x) R: T(y, y, y) = 3) ∧ Mesmo no(x, 1, ⅲ) Questão 4 Traduza as seguintes sentenças para a linguagem da lógica de primeira ordem. Apresente no primeiro campo a estrutura que você utilizou para simbolizar as sentenças dessa questão. D(x) = x é dragão ⟨D, V, L, E⟩ F(x) = x feliz E(x, x) = x encontra y L(x, y) = x vive y Dom = x pessoas ∉ animais z = zoológico (a) Todo dragão que vive no zoológico é feliz. ∀x (D(x) ∧ L(x, y)) → F(x)) (b) Todo visitante do zoológico é uma pessoa bondosa. ∀x (V(x, z) → B(x)) (c) Todo dragão que vive no zoológico encontra todo visitante do zoológico. ∀x ((D(x) ∧ L(x, z)) → ∀y (V(y, z) → E(x, y))) (d) Todo dragão que vive no zoológico que encontra visitantes do zoológico é feliz. ∀x ((D(x) ∧ L(x, z)) ∧ ∃y (V(y, z) ∧ E(x, y))) → F(x)) Questão 5 Verifique, através de tableaux, quais das seguintes afirmações são verdadeiras. Justifique sua resposta. ∀x(∃y P(x) ∧ ∀y(f(x) = y) |= ∀x P(f(x)) ∀b ∃y∀x P(x, y) |= ∀x∃y P(x, y) ∀e |= ∀x∃y(R(x, y) ∨ R(y, x)) O F ∃x (P(x) ∧ ∀y [f(x) = y]) |= ∀x P(P(x)) ∃x P(f(x)) ∧ ∀y (f(x) = y) [Afirmação é falsa!] Vx P (f(x)) [Contra exemplo:] F V Dom = {3, 6} F F P = {a, b, c} V F P = { \\\ } V F V V V V Vy [f(x) = y] V V P(f(0) = y V V P(f(0) = f(0) C) F ∃y (R(o, y) ∨ R(y, o)) F F R(o, o) ∨ R(0, o) F F R(o, 0) F F [Contra exemplo:] Dom = {a} R = { } F ∃y P(o, y) |= Vx ∃y [P(x, y) ∃y P (o, y )] F Vx ∃y P(x, y) V P(o, o) P(0, o) A afirmação 4 é verdadeira!