pf-2011-1

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

UFPE / CIn/ Engenharia da Computação 
Lógica para Computação / Prova Final - 2011.1 - 12/07/2011
(1,5) Verifique, usando o método dos tableaux analíticos, se a proposição ( A (BC) ) ((A B) ( A (D) )) é uma tautologia. Em caso negativo, dê, se possível, uma valoração que a satisfaça e uma valoração que a refute. 
 
(2,0) Use resolução para provar que o seguinte argumento é válido:
– Se o saci-pererê fuma cachimbo então ele é lenda.
É conseqüência lógica de:
– Se o saci-pererê não é uma ilusão então ele é lenda.
– Se o saci-pererê fuma cachimbo então é magia ou um ser humano.
– Se o saci-pererê é magia então não fuma cachimbo.
– Se o saci-pererê é uma ilusão então não é um ser humano.
(1,5) Considere P como o conjunto de cadeias que são palíndromes sobre o alfabeto binário. 
 Dê uma definição indutiva para P e identifique o conjunto base (i.e. X) da geração indutiva e o conjunto de funções geradoras (i.e. F).
 Descreva em poucas palavras quais são o menor e o maior conjunto indutivo sob X e F. 
 O conjunto definido em (i) é livremente gerado? Justifique.
(1,0) Dê uma estrutura que seja modelo para as fórmulas abaixo e outra que seja contra-modelo. Para cada caso, defina uma assinatura e uma interpretação. 
xy (P (x) R(g(y),c)).	b) xy ((P(x) P(y)) P(f(x,y)))
 (2,0) Dada a estrutura A: (i) domínio: o conjunto dos números inteiros; (ii) elementos destacados: o número 0; (iii) relações: Maior-Que (binária), Impar (unária), Par (unária); (iv) funções: sucessor (unária), soma (binária) 
a) Defina uma assinatura L para A. 
b) Defina indutivamente o conjunto dos termos de L 
c) Defina o diagrama positivo de A
d) Dê uma fórmula na qual A seja modelo
e) Dê uma fórmula na qual A seja contra-modelo 
(2,0) Use resolução para provar que a seguinte fórmula é válida:
 x(P(x) R(a,x))y(P(y) R(a,y))