p2-2011.1

Prévia do material em texto

UFPE / CIn/ Engenharia da Computação 
Lógica para Computação / Segunda Avaliação/ 2011.1 
1. (1,5) Use o cálculo de seqüentes para provar a seguinte fórmula da lógica 
proposicional: (Q R) ((P Q) (P R)) 
 
2. (2,5) Verifique, usando resolução se 
{ x(Q(x) P(g(a,h(x))), x(Q(x) P(g(y,z))} |= x Q(x) 
 
3. (2,0) Use o algoritmo de Herbrand para determinar se os seguintes conjuntos 
de termos são unificáveis. Mostre os passos do algoritmo. Se a unificação for 
possível mostre o unificador (ou seja, as substituições necessárias), caso 
contrário, explique o motivo. 
 
a) {p(a,x,f(g(y))), p(z,h(z,w)), f(w)), p(a,h(a,g(b)),f(g(v)))} 
b) {h(f(a), g(x)), h(y,x)} 
 
4. (2,0) Seja A uma estrutura cujo domínio é o conjunto dos números naturais, 
juntamente com a relação Par(_); as funções soma, sucessor e o elemento 0 
destacado. Defina uma assinatura e interpretação para responder os seguintes 
itens. 
a) Qual o conjunto de termos que define o conjunto de números ímpares? 
b) Expresse as seguintes declarações na lógica de primeira ordem: 
b.1) Todo número inteiro ímpar somado com o seu sucessor resulta em um 
número ímpar. 
b.2) Todo número inteiro somado a zero resulta nele próprio. 
b.3) Se um número inteiro é ímpar então seu sucessor é par. 
b.4) A soma de dois números ímpares resulta em um número ímpar. 
 
5. (2,0) Para cada item abaixo diga se é verdadeiro (V) ou falso (F) (Atenção: 
duas respostas erradas anulam uma certa) 
a) A estrutura com: (i) domíınio {1, 2, 10, 30}, (ii) relação ‘divide(_,_)’ não é uma 
subestrutura da estrutura com: (i) domíınio {1, 2, 5, 10, 13, 26, 30}, (ii) relação 
‘menor-ou-igual(_,_)’. 
b) A estrutura com domínio N (naturais) , destacando o 0, com a função 
‘sucessor’, a relação maior que’, e o predicado ‘primo’ é um modelo para a 
sentença x(R(x, c) ¬P(g(x))). 
c) A estrutura com o predicado ‘´ımpar’, e o restante igual à anterior, é um contra-
modelo para z(P(g(z)) ¬R(c, z))). 
d) As fórmulas x(P(x) Q(x)) e y(P(y) Q(y)) são logicamente 
equivalentes. 
e) O método de resolução proposto por Robinson é mais eficiente que as 
tentativas anteriores de implementar o teorema de Herbrand pois não gera os 
vários conjuntos de instâncias básicas de cláusulas. 
 
EXTRA (1,0) (SOMENTE PARA QUEM FALTOU UMA MINI-PROVA) 
 
y(Q(y) Q(f(y))) é uma consequência lógica do seguinte conjunto { x(P(x,b) Q(x)), 
y( P(f(y),b) Q(z) } ? (use resolução para justificar a sua resposta)