succ  prec  indice 

Generalizzazione

 
 
 

Sostituzione

Una sostituzione  e' una funzione (theta)  tra variabili logiche e termini:
 
theta = { X1/t1, ..., Xk/tk }
Data una "formula-ben-formata" W, l'applicazione a questa di una sostituzione theta (indicata con W.theta) si ottiene rimpiazzando ordinatamente tutte le occerrenze di ogni variabile Xi con ti nella formula W.
 

Generalizzazione (theta-subsumption)

Data una clausola c:
c = head( X1, ...,  Xh) :- body1( Xi,...,Xj), ... , bodym( Xl,...,Xk).
questa puo' essere espressa come insieme di clausole disgiunte:
c = { head( X1, ...,  Xh), not body1( Xi,...,Xj), ... , not bodym( Xl,...,Xk) }
Se c e c' sono due clausole, si dice che c "theta-generalizza" c'  (c theta-subsumes c') se esiste una sostituzione theta, tale che c.theta e' incluso in c' (c.theta e c' intesi come insiemi di clausole disgiunte).
Se c "theta-generalizza" c' e c' "theta-generalizza" c allora c e c' si dicono theta.equivalenti .
Una clausola si dice ridotta se non risulta theta-equivalente a nessuna suo sottoinsieme proprio.

 
Esempio:

Sia c la clausola:
 

c = figlia( X, Y ) :- genitore( Y, X ).
 
sia theta la sostituzione:
theta = { X/maria, Y/anna }
 
allora l'applicazione di theta a c ':
c.theta = figlia( maria, anna ) :- genitore( anna, maria ).
 
la clausola c, rappresentata con insieme di disgiunti diventa:
c = {  figlia(X,Y), not genitore(Y,X)  }
 
la clausola c, theta-generalizza la clausola c', attraverso la sostituzione vuota theta = {}:
c' = figlia( X,Y ) :- femmina( X ), genitore( Y,X ).
infatti, la clausola c':
 
c' = {  figlia(X,Y), not femmina(X), not genitore(Y,X)  }
 
contiene (propriamente) la clausola c.

la clausola c theta-generalizza la clausola c'', con la sostituzione theta = { Y/X }
 

c'' = figlia( X,X ) :- femmina( X ), genitore( X,X ).
 
la clausola c theta-generalizza la clausola c''', con la sostituzione theta = {X/maria,Y/anna},
c''' = figlia( maria,anna ) :- femmina( maria ), genitore(anna,maria),
genitore(anna,piero).
considerata la clausola d:
d = figlia( X,Y ) :- genitore( Y,X ), genitore( W,V ).
le clausole c e d sono theta-equivalenti ( d theta-generalizza c con theta = { W/Y, V/X } ), ma mentre c e' ridotta, d non lo e'.

La theta-generalizzazione e' importante perche' permette di introdurre una relazione di generalita' (  c < c'  <=> c  e'generale almeno quanto c'   <=>  c  theta-subsume c'  ), definita in modo puramente sintattico.

Alcuni autori indicano la relazione c  e'generale almeno quanto c' come c > c', sottolineando la maggiore generalita', invece della relazione di inclusione.

Inotre la theta-generalizzazione presenta l'importante proprieta' che se c theta-generalizza c', allora c' consegue logicamente da c :

Generalizzazione Relativa (relative subsumption)

Introdotta da Plotkin, consente di tenere in considerazione la  conoscenza di fondo nella classificazione di generalita'.
Date c e d clausole e B insieme di clausole della teoria, si dice che "c generalizza d relativamente a B" ( c <B d ), se esiste una sostituzione theta, tale che, per ogni possibile aasegnazione delle variabili libere,  "c.theta impica d" consegue logicamente da B:
 
B     |=     per_ogni variabili libere(c.theta -> d)
Esempio:

siano c e d due cluause e B la conoscenza di base cosi' definite:
 

c = liscia( X ) :- biglia( X )

d = rotola( X ) :- discesa( X ), biglia( X ).
 

B = { sfera(X) :- biglia(X),  rotola(X) :- liscia(X),discesa(X),sfera(X) }
 

allora "c generalizza d relativamente a B" ( c <B d ).

La nozione di generalizzazione relativa e' piu' forte della generalizzazione semplice, infatti
 

c  <theta c'    ->     c  <B c'                ( c  <B={} c'    ->     c  <theta c' )
 
 
 

 succ  prec  indice