Generalizzazione Relativa Meno Generica

Operatore di Generalizzazione

Data una clausola c, l'operatore di generalizzazione p(c) ritorna l'insieme delle clausole c' (consentite dal linguaggio L) che siano minori di c, rispetto all'ordinamento indotto da theta-subsumpion
 

p(c) = { c' | c' appartiene a L, c' <_theta-sub. c }

1. applicazione di una sostituzione inversa alla clausola c
2. rimozione di un  letterale dal corpo della clausola

Generalizzazione Meno Generica

Piu' precisamente, lgg(c',c'') puo' venire introdotto come segue:
 

• lgg di termini: lgg(t',t'')
• lgg(t,t) = t
• lgg( f (s₁, ... ,s_m),f (t₁, ... ,t_m)) = lgg( s₁, t₁ ), ... , lgg( s_m, t_m )
• lgg( f (s₁, ... ,s_m),f (t₁, ... ,t_m)) = V, se f  != g e dove V e' una nuova variabile

che rappresenta lgg( f (s₁, ... ,s_m),f (t₁, ... ,t_m))
• lgg(s,t) = V, se s != t ed s oppure t  e' una variabile; in questo caso, V e' una variabile che rappresenta lgg(s,t)

Esempi:
 

• lgg([a,b,c], [a,c,d]) = [a,X,Y]
• lgg( f (a,a), f(b,b) ) = f( lgg( a,b ), lgg( a,b) ) = f( V,V ) , dove V e' una variabile che rappresenta lgg( a,b ); l'univocita' di quasta rappresentazione deve essere mantenuta per tutte le sostituzioni appropriate.
 
• lgg di atomi: lgg(A',A'')
• lgg( p( s₁, ... s_m ), p( t₁, ... t_m ) ) = p( lgg( s₁, t₁), ... ,lgg( s_m, t_m) )
• lgg( p( s₁, ... s_m ), q( t₁, ... t_m ) ) = non definito se p != q
 
• lgg di letterali: lgg(L',L'')
• se L' e L'' sono atomi, lgg(L',L'') e' definito come nel punto precedente
• se sia L' che L'' sono letterali negati ( L' = not A',  L'' = not A''),

allora lgg(L',L'') = lgg( not A', not A'' ) = not lgg ( A', A'' )
• se L' e' un letterale positivo mentre L'' e' negato, allora lgg(L',L'') e' non definito
 
Esempi:
 
• lgg( genitore(anna,maria), genitore( anna, tommaso )) = genitore( anna, X )
• lgg( genitore(anna,maria), not genitore( anna, tommaso )) = non definito
• lgg( genitore(anna,X), figlia( maria, anna )) = non definito
 
• lgg di clausole: lgg(c',c'')
• usando la notazione

c = H :- B₁,...,B_n, = (H v not B₁v ... v not B_n ) = { H, not B₁, ... ,not B_n} = { c₁,...,c_n+1 },

date  c',c''  c' = { L₁,...,L_n }, c' = { K₁,...,K_m },
lgg( c', c'' ) = { M_ij = lgg( L_i,K_j ) | L_i e' in c' K_j  e' in c'' ed lgg( L_i,K_j )  e' definito }

Esempi:
 

• se c' = figlia(maria,anna) :- femmina(maria), genitore( anna, maria )

e se c'' = figlia(eva,tommaso) :- femmina(eva), genitore( tommaso, eva )

allora lgg( c', c'') = figlia(X,Y) :- femmina(X), genitore( Y, X ),

dove X rappresenta lgg( maria, eva ) e Y rappresenta lgg(anna,tommaso)
 
 

Metodo di induzione usato da  GOLEM, applica la ricerca di lgg(e',e'') a due esempi positivi, considerando le possibili generalizzazioni relativamente alla conoscenza di base, per ottenere la clausola di induzione rlgg( e',e'' ) come generalizzazione minima dei due esempi.