p2-2012-1

Prévia do material em texto

UFPE / CIn/ Engenharia da Computação Lógica para Computação / Prova 2 / 2012.1 – 28/06/2012 
 
1. (3,0) Prove por resolução que 
 Dorme-de-luz-acesa(neto)  z(Dono(neto,z)  Rato(z)) 
É conseqüência lógica de: 
 x( Cachorro(x)  Uiva-noite(x) ) 
 xy( (Dono(x,y)  Gato(y))  (z(Dono(x,z)  Rato(z))) ) 
 x(Dorme-de-luz-acesa(x)  (y(Dono(x,y)  Uiva-noite(y)))) 
 x(Dono(neto,x)  (Gato(x)  Cachorro(x))) 
(obs: pode abreviar os predicados) 
2. (3,0) Seja A uma estrutura cujo domínio é o conjunto dos inteiros juntamente com as relações: 
Congruente-módulo(_,_,_) (ou seja, possui as tuplas (a,b,m) se a e b forem congruentes módulo 
m), Maior(_,_), Divide(_,_) e Primo-entre-si(_,_); funções: resto(_,_), mdc(_,_) , subtração(_,_), 
soma(_,_), divisão(_,_) e multiplicação(_,_); e os elementos destacados: 0 e 1. Defina uma 
assinatura e interpretação para expressar as seguintes declarações na lógica de primeira ordem: 
 
Obs.: em teoria dos números é usada a notação x  y (mod m) para expressar que x é congruente 
a y módulo m. 
 
a) O zero não divide nenhum número. 
b) Se x é um inteiro positivo, y é diferente de zero e o resto da divisão de x por y for igual a zero 
então x divide y. 
c) Todo número inteiro tem um número primo entre si com ele. 
d) Se o mdc de dois números é igual a um então eles são primos entre si. 
e) Se x é maior que y então o mdc de x e y é igual ao mdc de x e o resto da divisão de x por y. 
f) Se x e y são inteiros, m é um inteiro positivo e o resto da divisão de x por m for igual ao resto da 
divisão de y por m, então x  y (mod m). 
g) Se x,y e c são inteiros, m é um inteiro positivo e x  y (mod m) então (x + c)  (y + c) (mod 
m), (x – c)  (y – c) (mod m) e (x.c)  (y.c) (mod m). 
h) Se x e y são inteiros, m é um inteiro positivo e x  y (mod m) então (x ÷ c)  (y ÷ c) (mod m), 
somente quando c é diferente de zero e é primo entre si com m. 
i) Se m é um inteiro positivo e x e y são inteiros, logo se m divide (x - y ) então x  y (mod m). 
 
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, caso 
contrário, explique o motivo. 
a) { h(g(x,y,f(x)), h(g(f(z),y,f(f(x)) } 
b) { f(x,g(y,y),g(x,h(y)), f(h(y), g(y,a), g(x,x)) } 
 
4. (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, 3, 4,5, 7, 10}, (ii) relações: ‘divide(_,_)’ e primo(_) é uma 
subestrutura da estrutura com: (i) domíınio {1, 2, 3,4, 5, ,6,7 , 10, 16, 30}, (ii) relações ‘menor-ou-
igual(_,_)’ e ímpar(_). 
b) A estrutura com domínio {0,1,2,3,4} , destacando o 1, com a relação ‘divide(_,_)’, com a função 
`quadrado_módulo_5’ é um modelo para a sentença xyR(f(y),x). 
c) A lógica de primeira ordem é decidível pois conseguimos definir o modelo universal chamado 
Universo de Herbrand, onde é possível provar qualquer fórmula. 
d) As fórmulas xP(x,y)  yQ(y) e xy(P(x,y)  Q(y)) são logicamente equivalentes. 
e) No algoritmo de unificação os termos que substituem as variáveis são os elementos do Universo de 
Herbrand.