p2-2013-1

Prévia do material em texto

UFPE / CIn/ Engenharia da Computação Lógica para Computação / Segunda Avaliação/ 2013.1 
1. (2,4) Seja A uma estrutura cujo domínio é o conjunto das indústrias do mundo. As relações são as seguintes: 
- OP(_): contem as indústrias que praticam a obsolescência programada, que é a decisão do produtor de 
propositadamente desenvolver, fabricar e distribuir um produto para consumo de forma que se torne obsoleto 
para forçar o consumidor a comprar a nova geração de produtos. 
- ECO(_): contem as indústrias que praticam ações em defesa do meio ambiente. 
-MaiorFaturamento(_,_):o par (x,y) pertence à relação se e somente se x possui um maior faturamento que y. 
-Concorre(_,_): o par (x,y) pertence à relação se e somente se x e y são concorrentes 
Os destaques são: Pêra e Maisanto 
As funções são: 
união(x,y) : função cujo resultado é a indústria formada a partir de ex-funcionários das indústrias x e y; 
maior(x): resulta na indústria que é a maior concorrente da indústria x; 
 Seja a seguinte assinatura e interpretação: 
 Dois símbolos de relação unária: P
A
= OP e E
A
=ECO 
 Dois símbolos de relação binária: F
A
 = MaiorFaturamento e C
A
=Concorre 
 Dois destaques: Pêra
A
=p e Maisanto
A
=a 
 Um símbolo de função binária: união
A
=u 
 Um símbolo de função unária: maior
A
=m 
 
 Expresse em português as seguintes declarações escritas na lógica de primeira ordem. E em seguida, 
transforme-as para a forma padrão de Skolem. 
a) x(P(x)  E(x))  x(P(x)  E(x) ) 
b) P(m(p))  E(a) 
c) xy (C(x,y)  F(x,y))  (x=m(y)) 
d) xyz ((z=u(x,y))  (E(x)  P(y))) (E(z) P(z)) 
e) x ((P(x))  (x=p))  (E(x)  ((x=a))) 
f) x ( (P(x))  y(C(x,y)  (P(y)  E(y)))) 
 
2. (1,5) Considere a estrutura da questão anterior. Determine se essa estrutura é modelo ou contra-modelo para as 
seguintes fórmulas. Para isso, assuma os fatos: A indústria Pêra pratica a obsolescência programada e a 
Maisanto não pratica ações em defesa do meio ambiente. Não existe indústria com maior faturamento que a 
Maisanto. Toda empresa que pratica obsolescência programada não pratica ações em defesa do meio ambiente. 
Sempre existem empresas concorrentes que adotam práticas contrárias. Justifique apropriadamente. 
a) x(C(x, p)  E(x)) b) z(P(z)  ¬E(z)) 
c) x(C(x,a)  E(x)  F(x,a)) d) x( ((x=p)  (x=a))  E(x)) 
e) P(p)  E(p) 
 
3. (1,5) Determine se os seguintes pares de fórmulas são equivalentes. Justifique usando as identidades estudadas. 
a) xyR(x,y) e xyR(x,y) b) (xP(x)  xQ(x)) e x( (P(x))  (Q(x)) ) 
c) xP(x)  xQ(x) e xy(P(x)  Q(y)) 
4. (3,0) Verifique, usando resolução se 
{x(P(x)  S(x)), x(Q(x)  R(x)), x(R(x)S(x))} |= x(P(x)Q(x)). 
Em seguida, construa o universo de Herbrand para o conjunto de cláusulas usado na resolução. 
 
5. (1,6) 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, caso contrário, explique o motivo. 
a) {h(f(a), p(f(x)),z), h(y,p(y),z)} b) {q(a,g(f(x),g(y,z))), q(x,g(z, y))}. 
EXTRA (1,0) (SOMENTE PARA QUEM FALTOU UMA MINI-PROVA) 
 Seja R uma relação binária. Use o método da resolução para provar que tal consequência lógica é verdadeira: 
{R é transitiva, R é irreflexiva}╞ R é assimétrica 
Observações: 
1. Uma relação binária S é transitiva se sempre que S(a, b) e S(b, c) então temos S(a, c) 
2. Uma relação binária S é irreflexiva se nenhum par do tipo (a,a) ocorre em S. 
3. Uma relação binária S é assimétrica se sempre que S(a, b) então ¬S(b, a).