Baixe o app para aproveitar ainda mais
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 {AB,A, C} é consistente.
Compartilhar