p1-2012.1

Prévia do material em texto

UFPE / CIn/ Engenharia da Computação 
Lógica para Computação / Primeira Prova - 2012.1 - 03/05/2012 
1. (1,5) Verifique, usando o método dos tableaux analíticos, se a proposição 
 ( A  B )  ( (A  C)  (C  (B)) ) é uma tautologia. Em caso negativo, dê 
uma valoração que a refute. 
 
2. (1,5) Use resolução para provar se 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ê é magia então não fuma cachimbo. 
– Se o saci-pererê é uma ilusão então não é um ser humano. 
– Se o saci-pererê fuma cachimbo então é magia ou um ser humano. 
 
3. (1,5) Verifique, usando o método da dedução natural se: 
 Ⱶ (P  R)  ((Q  R)  ((P  Q)  R)) 
 
4. (1,5) Verifique usando cálculo de sequentes se Ⱶ (P  Q)  (P  Q) 
 
5. (1,5) Considere P como o conjunto de cadeias de tamanho par que são 
palíndromos sobre o alfabeto {a,b,c}. 
a) 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). 
b) Descreva em poucas palavras quais são o menor e o maior conjunto 
indutivo sob X e F. 
c) O conjunto definido em (a) é livremente gerado? Justifique. 
 
6. (1,0) Dê um exemplo de uma prova em dedução natural com no mínimo 4 passos 
dedutivos e que contenha uma fórmula máxima. Mostre qual a fórmula máxima e 
transforme a derivação para a forma normal. 
 
 
7. (1,5) Para cada uma das afirmações abaixo, diga se é verdadeira ou falsa. 
(Atenção: uma resposta errada anula uma certa). 
a) Para qualquer que seja a fórmula A da lógica proposicional, o custo 
computacional para se resolver o problema “A é satisfatível?” pelo método 
da resolução é o mesmo que para se resolver pelo método dos tableaux 
analíticos. 
b) Se uma fórmula A da lógica proposicional é satisfatível então ela não pode 
ser refutável. 
c) Se ⊢(1 2 ... n) então ⊢(1 2 ... n-1)   n 
d) Se um método de prova é tal que toda vez que  |=  temos  ⊢  então 
podemos afirmar que ele é correto. 
e) O conjunto {AB,A, C} é consistente.