4. Individuals and Relations

Nel rappresentare la struttura del mondo, è utile ragionare in termini di individui e relazioni.

Gli individui sono entità del mondo, siano essi concreti, immaginari o concetti astratti.

Le relazioni specificano le verità riguardanti questi individui, in termini di proprietà su singoli individui, proposizioni sul singolo individuo e associazioni tra più individui.

I vantaggi di questa rappresentazione invece dell’utilizzo di sole features sono i seguenti:

In questa parte estendiamo il linguaggio delle clausole proposizionali per fare ragionamento su atomi, che ora hanno una struttura interna descritta in termini di relazioni e individui.

Il mapping tra simboli nella mente e individui e relazioni da essi denotati è detto concettualizzazione, questo viene fatto formalmente nelle ontologie.

1 Calcolo dei predicati (Logica del primo ordine)

Il calcolo dei predicati (logica del primo ordine) estende il calcolo proposizionale in due modi:

  • Gli atomi sono dotati di struttura con possibilità di includere variabili

  • Quantificazione delle variabili logiche

La sintassi di un predicato estende la sintassi del calcolo proposizionale come segue:

  • Un simbolo è una stringa alfanumerica comprendente anche _

  • Una variabile logica è un simbolo che inizia con una lettera maiuscola o _

    • es. Stanza, Lista, The_Dude

  • Una costante è un simbolo che inizia con minuscola, numero o stringa

  • Un simbolo di predicato è un simbolo che inizia con una minuscola. Costanti e predicati sono distinti a seconda del contesto

    • es. ciccio, r123, insegna_a possono essere sia costanti che predicati, 2019 solo costante

  • Un termine è una variabile o costante

    • es. ciccio, dib, Docenti, X

  • Un atomo è della forma p o p(t_1, …, t_n) con p simbolo di predicato e t_i i-esimo argomento del predicato.

    • es. aperto, insegna(pippokill, 69420), inserire(Dessert, menuT)

Una formula logica è costruita a partire dagli atomi usando connettivi logici e quantificatori:

  • \forall X p (per ogni X, p), X si dice quantificata universalmente

  • \exists X p (esiste un X tale che p), X si dice quantificata esistenzialmente

2 Semantica delle formule logiche di base

Un’espressione è ground se non contiene variabili, ad esempio teaches(chris, cs322) è ground, teaches(Prof, Course) non lo è.

Un’interpretazione delle espressioni ground è una tripla I = (D, \phi, \pi):

  • dominio D costituito da individui

  • \phi: c \rightarrow \phi(c): a ogni costante c assegna un individuo di D

  • \pi: p \rightarrow \pi(p) (\pi(p) : D^n \rightarrow {true, false}): quello che \pi restituisce è una funzione che ha come dominio il prodotto cartesiano di n volte D, dove n è l’arietà del predicato p, e il codominio è vero o falso perchè per ogni tupla del dominio ci dirà se p applicata a quegli argomenti è vera o falsa. Quindi è una funzione che associa al nome del predicato il suo significato.

Ogni termine ground denota un individuo in un’interpretazione.

Una costante c denota nell’interpretazione l’individuo \phi(c).

Un atomo ground p(t_1, …, t_n) è vero nell’interpretazione se \pi(p)(t_1^{'}, …, t_n^{'}) = true, dove t_i^{'} è un individuo denotato dal termine t_i.

Per definire la semantica delle formule logiche con variabili, un’assegnazione di variabile \rho è una funzione dall’insieme delle variabili al dominio D, cioè associa un elemento del dominio ad ogni variabile. Data l’interpretazione I = (D, \phi, \pi) e l’assegnazione \rho ogni termine denota un individuo del dominio: se il termine è costante, l’individuo è dato da \phi, se il termine è una variabile, l’individuo è dato da \rho.

Data un’interpretazione e un’assegnazione per ogni variabile, ogni atomo può essere vero o falso:

  • \forall X p è vera nell’interpretazione se p è vera per ogni assegnazione di variabile di X a un individuo.

  • \exists X p è vera nell’interpretazione se p è vera per almeno un’assegnazione di X ad un individuo.

Una formula con variabili è vera in I se e solo se per qualsiasi assegnazione la formula ground ottenuta applicando \rho alle sue variabili risulta vera.

Una formula è aperta se ha almeno una variabile senza quantificatori (\forall, \exists), per cui la semantica non è determinabile.

3 Datalog: linguaggio relazionale a regole

Il Datalog estende il linguaggio delle clausole definite proposizionali per includere individui e relazioni. Può essere visto come una forma ristretta dei predicati logici dove le sole formule permesse sono clausole definite della forma h \leftarrow a_1 \land … \land a_m e ogni variabile è da intendersi universalmente quantificata.

3.1 Query con variabili

Le query sono utilizzate per chiedere se un enunciato è conseguenza logica della KB.

Con le query decisionali, un utente può chiedere query con risposta yes o no.

Le query con variabili consentono all’utente di chiedere gli individui che rendono la query true.

Un’istanza di una query è ottenuta sostituendo i termini alle variabili nella query. Ogni occorrenza di una variabile nella query viene sostituita con lo stesso termine.

Data una query, una risposta è un’istanza della query che è conseguenza logica della KB, oppure no, ovvero nessuna istanza segue logicamente dalla KB, non significa che sia falsa nell’interpretazione intesa.

4 Dimostrazioni e Sostituzioni

Un’istanza di clausola è ottenuta sostituendo ogni occorrenza di ogni variabile con lo stesso termine.

Una sostituzione è un insieme della forma {V_1/t_1, …, V_n/t_n}, dove V_i sono variabili distinte e t_i termini. A ogni V_i viene associato un t_i. V_1/t_1 è detta associazione.

Una sostituzione è in forma normale se nessuna V_i occorre in un t_j. Ad esempio {X/Y, Z/chile} è in forma normale, ma {X/Y, Z/X} no perchè X occorre sia a sinistra sia a destra di associazioni.

L’applicazione di una sostituzione \sigma all’espressione (termine, atomo o clausola) e è un’espressione uguale a e dove ogni occorrenza di V_i è sostituita dal corrispondente termine t_i detta istanza e\sigma.

Una sostituzione \sigma è un unificatore delle espressioni e_1 ed e_2 se e_1 \sigma = e_2 \sigma produce un’unica istanza da più espressioni.

Un unificatore più generale \sigma di e_1 ed e_2 è un unificatore tale che, per qualunque altro loro unificatore \sigma^{'} si ha che e\sigma{'} è istanza di e\sigma per ogni espressione e.

4.1 Unificazione

Il problema dell’unificazione è il seguente: dati due termini o atomi, determinare se si unificano e, nel caso, restituire un loro unificatore. Definiamo di seguito un algoritmo per trovare un eventuale unificatore più generale di due atomi/termini.

L’algoritmo lavora con un insieme di uguaglianze E che implicano l’unificazione di t_1 e t_2. S è un insieme di associazioni per una sostituzione, se \alpha/\beta \in S, allora \alpha è una variabile che non appare altrove in S o in E. Nel caso di \alpha e \beta atomi questi devono avere stesso simbolo di predicato e stesso numero di argomenti, altrimenti l’unificazione fallisce.

4.2 Procedura Bottom-up con variabili

La procedura bottom-up proposizionale può essere estesa al Datalog usando delle istanze ground delle clausole, ottenute sostituendo le costanti della clausola con variabili (grounding). Le costanti richieste sono quelle che appaiono nella KB o nella query. Se non ci sono costanti, queste vanno inventate.

La procedura è corretta, perchè ogni istanza di ogni regola è vera in ogni modello. Questa procedura è la stessa del caso senza variabili, ma utilizza l’insieme di istanze ground delle clausole, che sono vere perchè le variabili sono quantificate universalmente.

L’algoritmo converge anche con clausole Datalog perchè vi è un numero finito di atomi da rendere ground e ad ogni iterata viene aggiunto un solo atomo ground all’insieme.

La procedura è anche completa per atomi ground g: se KB \models g allora KB \vdash g. Per dimostrarlo, come nel caso proposizionale, si costruisce un particolare tipo di modelli: una interpretazione di Herbrand (D, \phi, \pi) è un’interpretazione in cui il dominio fissato consiste di costanti presenti in KB e in g, ogni costante denota se stessa (\phi fissato, una costante viene inventata in caso di mancanza), mentre \pi è da definire per i predicati: gli atomi veri sono le istanze ground delle relazioni derivate dalla procedura.

Tale interpretazione si dimostra essere un modello minimale per la KB: se KB \models g, con g ground, allora g è vero nel modello minimale, quindi alla fine viene derivato.

4.3 Procedura top-down con variabili

La procedura top-down per le clausole proposizionali definite può essere estesa per gestire le variabili permettono istanze di regole che possono essere usate nella derivazione.

L’uso di yes consente l’estrazione della risposta: determinare quali istanze della query con variabili sono conseguenze logiche della KB.

Inizialmente si gestisce una clausola di risposta generalizzata della forma yes(V_1, …, V_k) \leftarrow q, dove V_1, …, V_k sono variabili della query q.

Questo significa che un’istanza di yes(V_1, …, V_k) è vera se q è vera. La procedura di dimostrazione ad ogni passo seleziona un atomo nel corpo della clausola di risposta e sceglie una clausola di KB la cui testa si unifichi con tale atomo.

La risoluzione SLD della clausola yes(t_1, …, t_k) \leftarrow \underline{a_1} \land a_2 \land … \land a_m, avendo selezionato a_1, con la clausola scelta nella KB a \leftarrow b_1 \land … \land b_p essendo a_1 e a unificabili dall’unificatore più generale \sigma, la nuova clausola di risposta è (yes(t_1, …, t_k) \leftarrow b_1 \land … \land b_p \land a_2 \land … \land a_m) \sigma, dove \sigma viene applicato all’intera clausola di risposta.

La risposta sarà dalla forma yes(t_1, …, t_n) in una dimostrazione terminata con successo. Quando questa occorre, l’algoritmo ritorna la risposta V = t_1, …, V_n = t_n.

La procedura è non deterministica: si possono trovare tutte le derivazioni tentando scelte appropriate che portino al successo, fallisce se tutte le scelte portano al fallimento.

La scelta della clausola può essere implementata come ricerca.

5 Simboli di funzione e strutture dati

Datalog lavora su un numero finito di individui dato che ogni individuo è individuato da una costante. Si vuole invece lavorare su un dominio infinito.

I simboli di funzione permettono di descrivere gli individui indirettamente: un individuo è descritto in termini di altri individui.

Sintatticamente, una funzione di simbolo è una parola che comincia con una lettera minuscola. Un termine è una variabile, costante o ha la forma f(t_1, …, t_n), con f simbolo di funzione n-aria e t_i termini.

Semanticamente, in ogni interpretazione (D, \phi, \pi) \phi viene estesa in modo da assegnare una funzione da D^n a D a ogni simbolo di funzione n-aria: per ogni termine ground specifica l’individuo denotato. Una costante può essere vista come una funzione senza argomenti (0-aria).

Con un solo simbolo di funzione e una sola costante, si può definire potenzialmente un numero infinito di termini/atomi ground, permettendo il ragionamento su infiniti individui.

5.1 Funzioni vs Predicati

I termini compaiono nelle clausole esclusivamente all’interno di atomi, e non direttamente come nei predicati.

5.2 Procedura Bottom-Up con Funzioni

Consiste nel grounding delle clausole insieme alla procedura BU proposizionale. La procedura bottom-up può generare un’infinita sequenza di conseguenze. Se la selezione è fair, ovvero il criterio di selezione delle clausole assicura che ogni clausola della KB prima o poi venga selezionata, allora la procedura è completa, ogni conseguenza sarà generata.

Il problema di clausole ignorate per sempre è chiamato starvation.

5.3 Procedura Top-Down con Funzioni

Si comporta come per il Datalog, ma l’unificazione diventa complicata perchè segue ricorsivamente l’applicazione di funzioni a più livelli. Si può fare un cambio nell’algoritmo di unificazione: se estraggo \alpha variabile e \beta atomo (o termine), o viceversa, restituisco \bot, questo per evitare una ricorsione all’infinito (controllo di occorrenza), altrimenti la procedura non è più corretta.

In Prolog questo non viene fatto in automatico per motivi di efficienza, ma può portare a dimostrazioni non corrette.

6 Uguaglianza

A volte è utile utilizzare più termini per denotare uno stesso individuo, altre volte serve che ogni nome si riferisca a un diverso individuo, spesso non si sa se due nomi denotino lo stesso individuo. Nelle procedure di ragionamento viste, tutte le risposte sono valide a prescindere dal fatto che i termini denotino gli stessi individui.

Introduciamo un predicato speciale = con interpretazione intesa standard indipendente dal dominio. t_1 = t_2 se nell’interpretazione I, t_1 e t_2 sono mappati sullo stesso individuo, cioè ci sono due costanti per un solo individuo, e non due individui simili nel dominio.

Per fare ciò ci sono due modi:

  1. Assiomatizzare l’uguaglianza come un qualunque altro predicato, ovvero scrivo le clausole di cosa significa essere uguale:

    • X = X (riflessività)

    • X = Y \leftarrow Y = Z (simmetria)

    • X = Z \leftarrow X = Y \land Y = Z (transitività)

    • f(X_1, …, X_n) = f(Y_1, …, Y_n) \leftarrow X_1 = Y_1 \land … \land X_n = Y_n

    • p(X_1, …, X_n) \leftarrow p(Y_1, …, Y_n) \land X_1 = Y_1 \land … \land X_n = Y_n

      • Di solito questa opzione non viene usata perchè appesantisce la KB

  2. Definire procedure di riscrittura per l’uguaglianza, ovvero internamente faccio chiamare nello stesso modo termini diversi che denotano lo stesso individuo. Usare l’uguaglianza come regola di riscrittura è detto paramodulazione: se t_1 = t_2 ogni occorrenza di t_1 può essere sostituita con t_2, quindi per ogni individuo si fissa una rappresentazione canonica, in modo da mappare tutte le rappresentazioni di un termine su quella rappresentazione.

6.1 Unique Names Assumption

Per l’uguaglianza, \phi non necessariamente iniettiva: termini diversi possono denotare lo stesso individuo o individui distinti. Per ogni coppia di termini ground distinti t_1 e t_2 la UNA assume che t_1 \neq t_2.

Sotto UNA, un atomo con \neq può occorrere nel corpo delle clausole. La UNA non segue dalla semantica del linguaggio delle clausole definite, secondo cui termini ground differenti potrebbero denotare anche lo stesso individuo.

6.1.1 Assiomatizzazione della UNA

Si aggiungono i seguenti assiomi:

  • c \neq c^{'} \forall c e c^{'} costanti

  • f(X_1, …, X_n) \neq g(Y_1, …, Y_m) \forall coppia di funzioni distinte f e g

  • f(X_1, …, X_n) \neq g(Y_1, …, Y_m) \leftarrow X_i \neq Y_i \forall f n-aria

  • f(X_1, …, X_n) \neq c \forallf e c

Termini ground sono identici se e solo se si unificano, ma non vale per i termini non ground, ad esempio a \neq X ha istanze vere nelle quali X ha un certo valore b, e un’istanza falsa in cui X ha il valore a.

6.1.2 Procedura Top-Down con UNA

Per incorporare la UNA la procedura non dovrebbe trattare la disuguaglianza come un altro predicato, perchè esistono avrei troppe diversità tra individui da specificare.

Piuttosto, per dimostrare che t_1 \neq t_2 ci sono 3 casi:

  1. t_1 e t_2 non si unificano, per cui t_1 \neq t_2 ha successo

  2. t_1 e t_2 sono identici, per cui t_1 \neq t_2 fallisce

  3. Ci sono istanze per cui t_1 \neq t_2 ha successo e altre in cui fallisce

    1. Le istanze ground compatibili con l’MGU dovrebbero fallire, le altre dovrebbero avere successo, ma enumerare tutte le istanze di successo è impraticabile perchè sarebbero troppe.

Per coppie di termini ground, gli unici casi possibili sono l’1 e il 2. La procedura top-down viene quindi estesa per incorporare la UNA considerando i 3 casi di prima:

  • Caso 1: successo

  • Caso 2: fallimento

  • Caso 3: le disuguaglianze vanno posticipate, attendendo altri atomi-goal che possano far unificare le variabili in modo da rientrare nei casi precedenti. Per farlo l’algoritmo seleziona un atomo non posticipato e, se non ci sono altri atomi da scegliere, e nessuno dei casi precedenti è applicabile, la query ha successo. C’è sempre un’istanza che ha successo, ovvero quella che assegna a ogni variabile una costante distinta non già usata. Le variabili libere (senza quantificatore) nella risposta vanno interpretate con cautela perchè creano ambiguità.

Il test di disuguaglianza potrebbe essere sempre fatto come ultima chiamata, ma questo non viene fatto per motivi di efficienza.

7 Assunzione di conoscenza completa

Estendiamo l’assunzione di conoscenza completa ai programmi logici considerando gli assiomi dell’uguaglianza, la proprietà di chiusura del dominio, e una nozione più sofisticata del completamento. Ciò definisce una forma di NAF. L’assunzione di conoscenza completa include la UNA, perciò si devono includere gli schemi di assiomi per uguaglianza e disuguaglianza.

Una forma normale di Clark della clausola p(t_1, ..., t_k) \leftarrow Bè la clausola p(V_1, ..., V_k) \leftarrow \exists W_1 ... \exists W_m V_1 = t_1 \land ... \land V_k = t_k \land Bdove V_1, …, V_k sono k variabili che non appaiono nella clausola originale, e W_1, …, W_m sono le variabili originarie della clausola. Supponendo che tutte le clausole vengano poste in forma normale di Clark p(V_1, ..., V_k) \leftarrow B_1, ..., p(V_1, ..., V_k) \leftarrow B_n sono equivalenti a p(V_1, ..., V_k) \leftarrow B_1 \lor ... \lor B_n

Completamento di Clark: \forall V_1 ... \forall V_k p(V_1, ..., V_k) \iff B_1 \lor ... \lor B_n.

7.1 Procedure di dimostrazione con NAF

Simile alla procedura top-down per le NAF proposizionali, come per la UNA si presenta un problema a causa delle variabili libere nei goal negati, la procedura dovrebbe posticipare il sotto-obiettivo negato fino a quando le variabili libere non vengono legate in un’associazione. Qualora ciò non fosse possibile in alcun modo, la dimostrazione si blocca e non si potrà concludere nulla su tale goal.