Corso di “Rappresentazione e Algoritmi” 2014-15 Modulo I - 6 CFU

Laurea Magistrale in “Cinema e Media”

Corso di “Rappresentazione e Algoritmi” 2014-15 Modulo I - 6 CFU

mutuato da

Laurea Magistrale in “Scienze del Corpo e della Mente”

6 CFU

Laurea Magistrale in “Scienze della Mente”

Corso di “Intelligenza artificiale” 2013-14 Modulo I - 4 CFU

Vincenzo Lombardo

Note per il corso

Queste note per i corsi di “Rappresentazione e algoritmi” sono parte del programma d’esame 2014/15. L’idea di scrivere le note scaturisce dalla considerazione che, essendo frequentato il corso anche da studenti provenienti da altre sedi in Italia o all’estero, spesso la preparazione di base dell’informatica non è sufficiente per affrontare lo studio dei testi adottati (come da guida degli studi).

Dopo una ricerca sul web di testi e dispense possibili, mi sono convinto che sono tutti pensati per scopi diversi da un corso nell’ambito dei media o della psicologia.

Gli esempi riportati, la presentazione degli argomenti, l’obiettivo a cui è destinato lo studio non sono familiari agli studenti di “Cinema e media” e di “Scienze del Corpo e della Mente”.

Capitolo 4

La logica dei predicati Commenti benvenuti!

Aggiornamento: 24 ottobre 2017

Capitolo 4

La logica dei predicati

Come abbiamo visto nel capitolo precedente, la logica proposizionale non riesce a cogliere la struttura interna delle proposizioni, anche se queste presentano similarità molto forti. Ad esempio, non si riesce a generalizzare sulla rappresentazione che ci sia un pozzo in una cella qualsiasi. Le rappresentazioni in logica proposizionale di “C’è un pozzo in [1,2].” e “C’è un pozzo in [2,1].”, che noi abbiamo rappresentato con i simboli proposizionali P1,2 e P2,1 rispettivamente, non hanno alcuna relazione tra di loro. L’idea di associare un fatto simile, l’esistenza di un pozzo in una cella, a più istanze di cella, è una conoscenza di cui gli esseri umani dispongono e, dal punto di vista della rappresentazione, evita il proliferarsi di espressioni logiche. In poche parole, la logica proposizionale manca del potere espressivo sufficiente a rappresentare la conoscenza che è di interesse nella maggior parte dei domini delle attività umane.

Tuttavia, la logica proposizionale ha contribuito a rendere esplicita la conoscenza impiegata (conoscenza dichiarativa) che negli algoritmi tradizionali è nascosta nel codice. Occorre avvicinarsi un po’ di più a come l’uomo rappresenta la conoscenza, rivolgendoci ad altri formalismi logici. Rammentiamo che non possiamo usare il linguaggio naturale (che rimane un nostro importante termine di paragone) perché siamo interessati a linguaggi formali non ambigui, su cui si possano innestare procedure di inferenza. Il candidato immediato è la logica dei predicati (o del prim’ordine), su cui si sono concentrati gli sforzi dei ricercatori in ambito filosofico, matematico e informatico per più di un secolo (se consideriamo la sua versione moderna). Dopo le premesse introduttive, affrontiamo lo studio del linguaggio della logica dei predicati e delle procedure di inferenza ad essa associate.

Indice

1. La questione dell’impegno ontologico

2. Sintassi e semantica della logica dei predicati 3. Inferenza con la logica dei predicati

4. Esempio di rappresentazione della conoscenza e di inferenza con la logica dei predicati

1. La questione dell’impegno ontologico

La logica proposizionale, nella rappresentazione della conoscenza, presenta molti vantaggi e qualche svantaggio. Innanzitutto è dichiarativa, cioè consente di separare la conoscenza, esprimendola in modo esplicito. Ricordiamo la differenza con gli algoritmi tradizionali incontrati nel Capitolo 1, che “occultano” nella logica della procedura la conoscenza implicata. Inoltre, la logica proposizionale, grazie soprattutto ai connettivi di negazione e di disgiunzione, permette la rappresentazione della conoscenza parziale (“Non so per colpa di quale pozzo ho una corrente d’aria in una cella, ma sarà uno di questi due o entrambi.”). Poi, la logica proposizionale ha la proprietà di essere composizionale, cioè il significato di proposizioni complesse si ricava dalle proposizioni semplici, associando un significato ai connettivi (formulato mediante le tabelle di verità). Ad esempio il significato di

𝐵","∧ 𝑃",&

si ricava dai significati di B1,1 e di P1,2. Infine, in logica proposizionale, il significato è indipendente dal contesto (a differenza del linguaggio naturale, che è dipendente dal contesto linguistico - “Signori si nasce e io modestamente lo nacqui”, e extra-linguistico - “In questa classe ci sono alcuni studenti preparati.”). Questo è un vantaggio perché permette di superare i problemi dovuti all’ambiguità e la difficoltà di reperire i referenti coinvolti dalle espressioni pronominali o deittiche, rispettivamente.

Contro tutti questi vantaggi, la logica proposizionale ha un potere espressivo limitato (il confronto si fa almeno con il linguaggio naturale, in cui è espressa la maggior parte della nostra conoscenza). Non si può dire, ad esempio, “I pozzi causano correnti d’aria nelle celle adiacenti.”, ma occorre scrivere un enunciato o proposizione per ogni cella. A questi aspetti di generalizzazione, risponde, con un po’ di sacrificio, la logica dei predicati (o del prim’ordine, presto si capirà perché), che si presenta con un maggiore impegno ontologico. L’ontologia, lo studio dell’esistente, determina le categorie fondamentali mediante le quali si interpreta il mondo. Laddove la logica proposizionale assume che il mondo si possa rappresentare come un insieme di fatti, atomici o composti con l’introduzione dei connettivi, la logica dei predicati (come fa del resto il linguaggio naturale) assume che il mondo sia fatto di

• Oggetti o individui, che popolano il mondo: persone, palazzi, numeri, colori, partite di calcio, guerre, stanze, squadre di calcio, …; si tratta di oggetti concreti e astratti, detti anche entità, eventualmente con estensione spaziale e/o temporale (nel caso di oggetti concreti);

• Funzioni che individuano oggetti a partire da altri oggetti: “madre di”, “miglior amico di”, “la gamba sinistra di”, “il primogenito di”, …; si tratta di un modo indiretto di identificare oggetti del mondo (gli oggetti di partenza sono argomenti della funzione, l’oggetto che si intende identificare è il valore della funzione);

• Relazioni e proprietà, che valgono tra gli oggetti del mondo: la proprietà di un oggetto di essere “rosso”, “rotondo”, “primo”, …; le relazioni tra due o più oggetti, ad esempio, “madre di”, “parte di”, “ama”, “in mezzo a”…, “regala”,

“…; le relazioni sono o proprietà, cioè attributi, qualcosa che si predica, di un singolo oggetto, o legami tra più oggetti del mondo;

Notiamo come “madre di” sia stato riportato sia tra le funzioni sia tra i predicati: come funzione, si intende l’oggetto “madre di x” che viene individuato a partire dall’oggetto

“x”; come predicato, si intende la relazione tra due individui, “x” e “y”. Come significato, le funzioni sono individui, mentre le relazioni sono vere e o false (si veda dopo).

2. Sintassi e semantica della logica dei predicati

Come nel calcolo proposizionale, anche la logica dei predicati è priva di assiomi, cioè non si esprimono contenuti veri e propri, ma si definiscono solo gli aspetti formali, con i quali viene codificata una KB. Inoltre, anche qui c’è bisogno di definire il sottoinsieme di tutte le stringhe, partendo dagli atomi. Si parla di enunciati o formule. Cominciamo dalla sintassi, esemplificando i concetti introdotti, ricorrendo di nuovo al mondo del Wumpus.

Costanti: 𝑊𝑢𝑚𝑝𝑢𝑠, 𝑈𝑠𝑒𝑟, 𝐺𝑜𝑙𝑑, [1,2], [2,1], [2,2], [2,3], ...

Variabili: 𝑥, 𝑦, 𝑎, 𝑏, ...

Funzioni: 𝐴𝑟𝑚𝑎_𝑑𝑖(_), 𝐶𝑒𝑙𝑙𝑎_𝑑𝑖(_), 𝑃𝑜𝑧𝑧𝑜_𝑑𝑖(_), ...

Predicati: 𝐼𝑛(_ , _), 𝑃𝑜𝑧𝑧𝑜(_), 𝐵𝑟𝑒𝑧𝑧𝑎(_), 𝑜𝑘(_), 𝐴𝑑𝑖𝑎𝑐𝑒𝑛𝑡𝑒(_ , _), ...

Connettivi: ¬, ∧, ∨, ⇒, ⇔ Uguaglianza: _ = _ Quantificatori: ∃, ∀

Una costante è un singolo e noto oggetto del dominio; una variabile è un singolo e non noto oggetto del dominio; una funzione individua univocamente un oggetto del dominio tramite una relazione tra altri n oggetti del dominio (detti argomenti, che abbiamo indicato con dei segnaposto “_”); un predicato è una relazione tra n oggetti (argomenti) del dominio; i connettivi, gli stessi della logica proposizionale, permettono di costruire predicati complessi a partire da predicati semplici, in modo ricorsivo; l’uguaglianza tra oggetti è un tipo speciale di predicato con due argomenti, riportato con una notazione simmetrica per comodità, invece di parentesi di argomenti; infine, i quantificatori, come vedremo determinano il comportamento delle variabili.

Sintassi della logica dei predicati

Un enunciato (o formula o predicato) atomico è formato da un predicato (che ha una determinata arità) e da un numero di argomenti pari all’arità del predicato stesso:

Predicato (Termine1, Termine2, ..., Terminen) oppure

Termine1 = Termine2

dove Termine è una costante, una variabile o una funzione (simbolo funzionale e argomenti) applicata un certo numero di termini. Per cui il Termine ha una definizione ricorsiva.

Costante oppure Variabile

oppure

Simbolo di funzione (Termine1, Termine2, ..., Terminem) Vediamo alcuni esempi.

𝐼𝑛(𝑊𝑢𝑚𝑝𝑢𝑠, [1,2]) 𝐼𝑛(𝑊𝑢𝑚𝑝𝑢𝑠, 𝑥)

𝐼𝑛(𝐴𝑟𝑚𝑎_𝑑𝑖(𝑈𝑡𝑒𝑛𝑡𝑒), [2,1]) 𝐼𝑛(𝐴𝑟𝑚𝑎_𝑑𝑖(𝑊𝑢𝑚𝑝𝑢𝑠), [1,2]) 𝐶𝑒𝑙𝑙𝑎_𝑑𝑖(𝐺𝑜𝑙𝑑) = [2,3]

𝐶𝑒𝑙𝑙𝑎_𝑑𝑖(𝐴𝑟𝑚𝑎_𝑑𝑖(𝐶𝑒𝑙𝑙𝑎_𝑑𝑖(𝑊𝑢𝑚𝑝𝑢𝑠))) = [2,2]

Si noti che non tutti gli enunciati riportati come esempio sono veri (della semantica ci occupiamo tra un attimo).

Gli enunciati composti sono formati da enunciati atomici mediante l’uso dei connettivi:

• Se 𝑆 è un predicato o un uguaglianza, ¬𝑆 è un predicato (negazione);

• Se 𝑆_" e 𝑆_& sono predicati o uguaglianze, 𝑆_"∧ 𝑆_& è un predicato (congiunzione);

• Se 𝑆_" e 𝑆_& sono predicati o uguaglianze, 𝑆_"∨ 𝑆_& è un predicato (disgiunzione);

• Se 𝑆_" e 𝑆_& sono predicati o uguaglianze, 𝑆_" ⇒ 𝑆_& è un predicato (implicazione);

• Se 𝑆_" e 𝑆_& sono predicati o uguaglianze, 𝑆_" ⇔ 𝑆_& è un predicato (bi- condizionale).

Alcuni esempi:

𝐼𝑛(𝑊𝑢𝑚𝑝𝑢𝑠, [1,2]) ∧ 𝐼𝑛(𝐴𝑟𝑚𝑎_𝑑𝑖(𝑈𝑡𝑒𝑛𝑡𝑒), [2,1]) 𝐼𝑛(𝑊𝑢𝑚𝑝𝑢𝑠, 𝑥) ∨ 𝐶𝑒𝑙𝑙𝑎_𝑑𝑖(𝐺𝑜𝑙𝑑) = [2,3]

¬𝐼𝑛(𝐴𝑟𝑚𝑎_𝑑𝑖(𝑈𝑡𝑒𝑛𝑡𝑒), [2,1])

𝐼𝑛(𝐴𝑟𝑚𝑎_𝑑𝑖(𝑊𝑢𝑚𝑝𝑢𝑠), [1,2]) ⇒ 𝐶𝑒𝑙𝑙𝑎_𝑑𝑖(𝐺𝑜𝑙𝑑) = [2,3]

(𝐶𝑒𝑙𝑙𝑎_𝑑𝑖(𝐺𝑜𝑙𝑑) = [2,3]) ⇔ (𝐼𝑛(𝑊𝑢𝑚𝑝𝑢𝑠, [1,2]) ∧ 𝐼𝑛(𝑊𝑢𝑚𝑝𝑢𝑠, [2,3]))

Semantica della logica dei predicati

Gli enunciati sono veri o falsi rispetto a un modello e a un’interpretazione. Nella figura sottostante abbiamo un modello in cui sono indicati gli oggetti e le relazioni; inoltre, è indicata un’interpretazione, che mette in relazione costanti, funzioni e predicati con gli elementi del modello. Le costanti sono posizionate vicino agli oggetti, le funzioni sono indicate con linee tratteggiate (dall’argomento alla funzione, dalla funzione al valore), i predicati sono indicati con linee solide verso gli argomenti.

Quindi, il modello contiene oggetti (cioè elementi del dominio) e relazioni tra di essi;

l’interpretazione specifica i referenti per

• simboli di costante, che sono interpretati come oggetti;

• simboli di funzione, che sono interpretati come relazioni funzionali, cioè relazioni che identificano un solo oggetto a partire da altri oggetti come argomenti;

• simboli di predicato, che sono interpretati come relazioni tra un certo numero di oggetti.

Un enunciato atomico

Predicato (Termine1, ..., Terminen) oppure

Termine1 = Termine2

è vero se e solo se gli oggetti a cui si riferiscono i termini Termine1, ..., Terminen sono tra di loro nella relazione a cui si riferisce Predicato. Gli enunciati composti sono valutati secondo le tabelle di verità dei singoli connettivi, che abbiamo studiato per la logica proposizionale.

Prima di procedere con i quantificatori, che rappresentano la novità principale introdotta dalla logica dei predicati dal punto di vista operativo delle procedure di inferenza,

riprendiamo l’esercizio dell’arringa dell’avvocato per proporne una rappresentazione basata sulla logica dei predicati.

Esercizio di conseguenza logica: L’arringa dell’avvocato adattato da

[http://nicolas.thiery.name/macs358/Notes/1_FormalLogic/PropositionalLogic.pdf]

Arringa:

“Se il mio cliente è colpevole, allora il coltello era nel cassetto. Ma, o il coltello non era nel cassetto o Tullio Malesano lo avrebbe visto, il coltello. Tuttavia, se il coltello non era lì il 10 ottobre, allora Tullio Malesano non lo ha visto, il coltello. Inoltre, se il coltello fosse stato lì il 10 ottobre, allora non solo il coltello sarebbe stato nel cassetto ma anche il martello sarebbe stato nel ripostiglio. Ma tutti sappiamo che il martello non era nel ripostiglio. Per cui, signore e signori della giuria, il mio cliente è innocente.”

Procediamo identificando le frasi semplici che costituiranno gli enunciati atomici in logica dei predicati (sempre scorporando i connettivi analizzati nel linguaggio naturale e riportando le espressioni a una forma neutra al presente):

• “Il mio cliente è colpevole.” diventa l’enunciato 𝐶𝑜𝑙𝑝𝑒𝑣𝑜𝑙𝑒(𝑀𝑖𝑜𝐶𝑙𝑖𝑒𝑛𝑡𝑒)

• “Il coltello è nel cassetto.” diventa l’enunciato 𝐼𝑛(𝐶𝑜𝑙𝑡𝑒𝑙𝑙𝑜, 𝐶𝑎𝑠𝑠𝑒𝑡𝑡𝑜)

• “Tullio Malesano vede il coltello.” 𝑉𝑒𝑑𝑒𝑟𝑒(𝑇𝑀, 𝐶𝑜𝑙𝑡𝑒𝑙𝑙𝑜)

• “Il coltello è lì il 10 ottobre.” diventa l’enunciato 𝐼𝑛(𝐶𝑜𝑙𝑡𝑒𝑙𝑙𝑜, 𝐿ì)

• “Il martello è nel ripostiglio.” diventa l’enunciato 𝐼𝑛(𝑀𝑎𝑟𝑡𝑒𝑙𝑙𝑜, 𝑅𝑖𝑝𝑜𝑠𝑡𝑖𝑔𝑙𝑖𝑜) I vocabolari terminologici impiegati sono i seguenti:

Predicati: Colpevole(_), In(_,_), Vedere(_,_)

Costanti: MioCliente, TM, Coltello, Cassetto, Ripostiglio, Martello

Si noti che negli enunciati atomici abbiamo trascurato la data del 10 ottobre, che non viene rappresentato. Questa scelta è motivata dal fatto che “10 ottobre” compare soltanto nel contesto della frase “Il coltello è lì il 10 ottobre.” in due periodi dell’arringa. Quindi

“10 ottobre” non è influente isolatamente dal “Lì”, che diventa una costante unica (che indica una sorta di spazio-tempo, come pure “Cassetto” e “Ripostiglio”, e tutte le costanti che eventualmente occuperanno il II argomento del predicato “In(_,_)”).

Una possibile KB è la seguente (si ricordi che la KB dipende dal compito, che nel nostro caso è limitato a verificare a):

• R1:

o Se il mio cliente è colpevole, allora il coltello è nel cassetto.

o 𝐶𝑜𝑙𝑝𝑒𝑣𝑜𝑙𝑒(𝑀𝑖𝑜𝐶𝑙𝑖𝑒𝑛𝑡𝑒) ⇒ 𝐼𝑛(𝐶𝑜𝑙𝑡𝑒𝑙𝑙𝑜, 𝐶𝑎𝑠𝑠𝑒𝑡𝑡𝑜)

• R2:

o O il coltello non è nel cassetto o Tullio Malesano vede il coltello. Cioè

“Non è vero che il coltello non è nel cassetto se e solo se Tullio Malesano vede il coltello”

o ¬(¬𝐼𝑛(𝐶𝑜𝑙𝑡𝑒𝑙𝑙𝑜, 𝐶𝑎𝑠𝑠𝑒𝑡𝑡𝑜) ⟺ 𝑉𝑒𝑑𝑒𝑟𝑒(𝑇𝑀, 𝐶𝑜𝑙𝑡𝑒𝑙𝑙𝑜)))

• R3:

o Se il coltello non è lì il 10 ottobre, allora Tullio Malesano non vede il coltello.

o (¬𝐼𝑛(𝐶𝑜𝑙𝑡𝑒𝑙𝑙𝑜, 𝐿ì) ⇒ ¬𝑉𝑒𝑑𝑒𝑟𝑒(𝑇𝑀, 𝐶𝑜𝑙𝑡𝑒𝑙𝑙𝑜))

• R4:

o Se il coltello è lì il 10 ottobre, allora il coltello è nel cassetto e il martello è nel ripostiglio.

o 𝐼𝑛(𝐶𝑜𝑙𝑡𝑒𝑙𝑙𝑜, 𝐿ì) ⇒ (𝐼𝑛(𝐶𝑜𝑙𝑡𝑒𝑙𝑙𝑜, 𝐶𝑎𝑠𝑠𝑒𝑡𝑡𝑜) ∧ 𝐼𝑛(𝑀𝑎𝑟𝑡𝑒𝑙𝑙𝑜, 𝑅𝑖𝑝𝑜𝑠𝑡𝑖𝑔𝑙𝑖𝑜))

• R5:

o Il martello non è nel ripostiglio.

o ¬𝐼𝑛(𝑀𝑎𝑟𝑡𝑒𝑙𝑙𝑜, 𝑅𝑖𝑝𝑜𝑠𝑡𝑖𝑔𝑙𝑖𝑜)

Con

• a:

o Il mio cliente è innocente.

o ¬𝐶𝑜𝑙𝑝𝑒𝑣𝑜𝑙𝑒(𝑀𝑖𝑜𝐶𝑙𝑖𝑒𝑛𝑡𝑒)

Dimostriamo che a è conseguenza logica di KB mediante le regole di inferenza e le equivalenze logiche introdotte in precedenza. I predicati introdotti verranno usati esattamente come le proposizioni (calcolare con la stringa P2 o con la stringa 𝐼𝑛(𝐶𝑜𝑙𝑡𝑒𝑙𝑙𝑜, 𝐶𝑎𝑠𝑠𝑒𝑡𝑡𝑜) è equivalente per un programma); questa KB si dice infatti proposizionalizzata perché non contiene variabili e quantificatori, come vedremo in seguito. Il motivo di questa denominazione è che i predicati si comportano esattamente come simboli proposizionali anche se strutturati come predicati più argomenti in parentesi tonde. Per motivi di chiarezza della scrittura, reintroduciamo i simboli 𝑃_Z:

• “Il mio cliente è colpevole.” - 𝐶𝑜𝑙𝑝𝑒𝑣𝑜𝑙𝑒(𝑀𝑖𝑜𝐶𝑙𝑖𝑒𝑛𝑡𝑒) - P1

• “Il coltello è nel cassetto.” - 𝐼𝑛(𝐶𝑜𝑙𝑡𝑒𝑙𝑙𝑜, 𝐶𝑎𝑠𝑠𝑒𝑡𝑡𝑜) - P2

• “Tullio Malesano vede il coltello.” - 𝑉𝑒𝑑𝑒𝑟𝑒(𝑇𝑀, 𝐶𝑜𝑙𝑡𝑒𝑙𝑙𝑜) - P3

• “Il coltello è lì il 10 ottobre.” - 𝐼𝑛(𝐶𝑜𝑙𝑡𝑒𝑙𝑙𝑜, 𝐿ì) - P4

• “Il martello è nel ripostiglio.” - 𝐼𝑛(𝑀𝑎𝑟𝑡𝑒𝑙𝑙𝑜, 𝑅𝑖𝑝𝑜𝑠𝑡𝑖𝑔𝑙𝑖𝑜) - P5

e la KB sarà:

• R1: 𝑃_" ⇒ 𝑃_&

• R2: ¬(¬𝑃_& ⟺ 𝑃_[)

• R3: ¬𝑃_\ ⇒ ¬𝑃_[

• R4: 𝑃_\ ⇒ (𝑃_& ∧ 𝑃_])

• R5: ¬𝑃_] Con

• a: ¬𝑃_"

Si noti che l’unica differenza con la KB del Capitolo 3 è rappresentata da R2; tuttavia ora i simboli 𝑃_Z sono utilizzati unicamente come sostituti pratici di predicati e per dimostrare che con una KB proposizionalizzata non cambia nulla nelle procedure di inferenza. Ecco la dimostrazione.

R₄: 𝑃_\⇒ (𝑃_& ∧ 𝑃_])

Eliminazione dell’implicazione in R4: R₆: ¬𝑃_\ ∨ (𝑃_&∧ 𝑃_])

Distributività dell’OR sull’AND in R6:

R₇: ¬𝑃_\∨ 𝑃_& ∧ (¬𝑃_\ ∨ 𝑃_])

Eliminazione della congiunzione in R7: R₈: ¬𝑃_\ ∨ 𝑃_]

Introduzione dell’implicazione in R₈: R₉: 𝑃_\⇒ 𝑃_]

Contrapposizione in R₉: R10: ¬𝑃_]⇒ ¬𝑃_\

Modus Ponens da R₁₀ e R₅: R11: ¬𝑃_\

Modus Ponens da R3 e R11: R₁₂: ¬𝑃_[

Modus Ponens da R₂₂ e R₁₂: R₂₃: ¬𝑃_&

Contrapposizione in R₁:

R₂₄: ¬𝑃_&⇒ ¬𝑃_"

Modus Ponens da R₂₄ e R₂₃: R₂₅: ¬𝑷_𝟏

R2: ¬(¬𝑃_& ⟺ 𝑃_[)

Eliminazione della bi-implicazione in R₂: R13: ¬( ¬𝑃_& ⇒ 𝑃_[ ∧ 𝑃_[⇒ ¬𝑃_& )

Eliminazione delle implicazioni in R₁₃: R14: ¬( 𝑃_& ∨ 𝑃_[ ∧ ¬𝑃_[∨ ¬𝑃_& )

De Morgan in R14: R₁₅: ¬ 𝑃_& ∨ 𝑃_[ ∨ ¬ ¬𝑃_[∨ ¬𝑃_&

De Morgan in R15:

R₁₆: ¬𝑃_&∧ ¬𝑃_[ ∨ 𝑃_[∧ 𝑃_&

Distributività dell’OR sull’AND in R₁₆:

R₁₇: ¬𝑃_&∧ ¬𝑃_[ ∨ 𝑃_[ ∧ ¬𝑃_&∧ ¬𝑃_[ ∨ 𝑃_&

Eliminazione della congiunzione in R₁₇:

R₁₈: ¬𝑃_&∧ ¬𝑃_[ ∨ 𝑃_[

Distributività dell’OR sull’AND in R18:

R₁₉: ¬𝑃_&∨ 𝑃_[ ∧ ¬𝑃_[∨ 𝑃_[

Eliminazione della congiunzione in R₁₉:

R₂₀: ¬𝑃_&∨ 𝑃_[

Commutatività dell’OR in R₂₀:

R21: 𝑃_[∨ ¬𝑃_&

Introduzione dell’implicazione in R₂₁:

R22: ¬𝑃_[⇒ ¬𝑃_&

Ora completiamo la presentazione del linguaggio della logica dei predicati con variabili e quantificatori.

Quantificatori

I quantificatori sono utili per esprimere caratteristiche di interi insiemi di oggetti, senza dovere introdurre predicati che enumerano gli oggetti uno per uno. Ad esempio, i quantificatori possono esprimere una conoscenza del tipo “I pozzi causano correnti d’aria nelle celle adiacenti.”, riportato in precedenza. Esistono due quantificatori nella logica dei predicati, il quantificatore universale ∀ e il quantificatore esistenziale ∃.

Cominciamo dal primo.

Le formule con la quantificazione universale delle variabili sono del tipo:

∀ < 𝒗𝒂𝒓𝒊𝒂𝒃𝒊𝒍𝒊 > < 𝒆𝒏𝒖𝒏𝒄𝒊𝒂𝒕𝒐 >

L’esempio “Tutti gli studenti di Rappresentazione e Algoritmi sono intelligenti.” si può codificare nel modo seguente:

∀𝑥 𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒(𝑥, 𝑅𝑒𝐴) ⇒ 𝐼𝑛𝑡𝑒𝑙𝑙𝑖𝑔𝑒𝑛𝑡𝑒(𝑥) La semantica delle formule quantificate universalmente è la seguente:

La formula ∀𝑥 𝑆 è vera in un modello m se e solo 𝑆 è vera con x che può riferirsi a ogni possibile oggetto del mondo.

E’ come se l’espressione con il quantificatore universale fosse equivalente alla congiunzione delle istanziazioni di 𝑆. Cioè, se nel nostro modello abbiamo oggetti (in questo esempio non ci sono funzioni, solo costanti),

{𝐷𝑜𝑐𝑒𝑛𝑡𝑒, 𝐶𝑎𝑡𝑡𝑒𝑑𝑟𝑎, 𝐿𝑎𝑣𝑎𝑔𝑛𝑎, 𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒1, 𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒2, 𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒3, 𝑅𝑒𝐴}

inserire il quantificatore universale davanti alla formula 𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒(𝑥, 𝑅𝑒𝐴) ⇒ 𝐼𝑛𝑡𝑒𝑙𝑙𝑖𝑔𝑒𝑛𝑡𝑒(𝑥), è equivalente, dal punto di vista del significato, ad avere una KB fatta in questo modo:

(𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒(𝐷𝑜𝑐𝑒𝑛𝑡𝑒, 𝑅𝑒𝐴) ⇒ 𝐼𝑛𝑡𝑒𝑙𝑙𝑖𝑔𝑒𝑛𝑡𝑒(𝐷𝑜𝑐𝑒𝑛𝑡𝑒))

∧

(𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒(𝐶𝑎𝑡𝑡𝑒𝑑𝑟𝑎, 𝑅𝑒𝐴) ⇒ 𝐼𝑛𝑡𝑒𝑙𝑙𝑖𝑔𝑒𝑛𝑡𝑒(𝐶𝑎𝑡𝑡𝑒𝑑𝑟𝑎))

∧

𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒(𝐿𝑎𝑣𝑎𝑔𝑛𝑎, 𝑅𝑒𝐴) ⇒ 𝐼𝑛𝑡𝑒𝑙𝑙𝑖𝑔𝑒𝑛𝑡𝑒(𝐿𝑎𝑣𝑎𝑔𝑛𝑎)

∧

𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒(𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒1, 𝑅𝑒𝐴) ⇒ 𝐼𝑛𝑡𝑒𝑙𝑙𝑖𝑔𝑒𝑛𝑡𝑒(𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒1)

∧

𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒(𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒2, 𝑅𝑒𝐴) ⇒ 𝐼𝑛𝑡𝑒𝑙𝑙𝑖𝑔𝑒𝑛𝑡𝑒(𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒2)

∧

𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒(𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒3, 𝑅𝑒𝐴) ⇒ 𝐼𝑛𝑡𝑒𝑙𝑙𝑖𝑔𝑒𝑛𝑡𝑒(𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒3)

∧

𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒(𝑅𝑒𝐴, 𝑅𝑒𝐴) ⇒ 𝐼𝑛𝑡𝑒𝑙𝑙𝑖𝑔𝑒𝑛𝑡𝑒(𝑅𝑒𝐴)

La variabile è stata sostituita con tutti i cosiddetti termini ground, cioè termini che non contengono variabili.

Si può osservare che:

L’implicazione (⇒) è il principale connettivo in uso con il quantificatore universale ∀.

Se consideriamo il significato della formula

∀𝑥 𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒(𝑥, 𝑅𝑒𝐴) ⇒ 𝐼𝑛𝑡𝑒𝑙𝑙𝑖𝑔𝑒𝑛𝑡𝑒(𝑥)

notiamo che essa è vera quando l’antecedente è falso (e ciò vale per tutte le costanti che non sono studenti) e quando sono veri sia l’antecedente che il conseguente (sono sia studenti sia intelligenti). Corrisponde alla seguente espressione in linguaggio naturale:

“Per ogni individuo del modello, se è uno studente di ReA, allora è intelligente.”. Si noti anche che la formula è vera anche se non esiste nessuno studente al corso di ReA; nel momento in cui esista, deve essere anche intelligente. Vediamo cosa succede se usiamo gli altri connettivi nella formula.

• ∀𝑥 𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒(𝑥, 𝑅𝑒𝐴) ∧ 𝐼𝑛𝑡𝑒𝑙𝑙𝑖𝑔𝑒𝑛𝑡𝑒(𝑥)

o Corrisponde all’espressione “Tutti gli individui del modello sono studenti di ReA e sono intelligenti.”.

o Si capisce che è un’interpretazione molto vincolante rispetto alla frase italiana di partenza “Tutti gli studenti di ReA sono intelligenti.”

• ∀𝑥 𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒(𝑥, 𝑅𝑒𝐴) ∨ 𝐼𝑛𝑡𝑒𝑙𝑙𝑖𝑔𝑒𝑛𝑡𝑒(𝑥)

o Corrisponde all’espressione “Tutti gli individui del modello o sono studenti di ReA o sono intelligenti o entrambe le cose.”.

o Continua a essere molto vincolante perché richiede che tutti gli individui siano una delle due cose o entrambe.

• ∀𝑥 𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒(𝑥, 𝑅𝑒𝐴) ⇔ 𝐼𝑛𝑡𝑒𝑙𝑙𝑖𝑔𝑒𝑛𝑡𝑒(𝑥)

o Corrisponde all’espressione “Tutti gli individui del modello sono studenti di ReA se e solo se sono intelligenti.”.

o Vincola gli studenti di ReA a essere intelligenti (come succede per l’implicazione sopra), ma purtroppo vincola gli individui intelligenti a essere studenti di ReA (e questo non era nell’enunciato originale).

Le formule con la quantificazione esistenziale delle variabili sono del tipo:

∃ < 𝒗𝒂𝒓𝒊𝒂𝒃𝒊𝒍𝒊 > < 𝒆𝒏𝒖𝒏𝒄𝒊𝒂𝒕𝒐 >

L’esempio “Qualche studente di Rappresentazione e Algoritmi è preoccupato.” si può codificare nel modo seguente:

∃𝑥 𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒(𝑥, 𝑅𝑒𝐴) ∧ 𝑃𝑟𝑒𝑜𝑐𝑐𝑢𝑝𝑎𝑡𝑜(𝑥) La semantica delle formule quantificate esistenzialmente è la seguente:

La formula ∃𝑥 𝑆 è vera in un modello m se e solo se 𝑆 è vera con 𝑥 legato a un qualche oggetto del modello (almeno uno).

E’ equivalente alla disgiunzione delle instanziazioni di 𝑆. Cioè, con gli oggetti del modello sopra, si ha che l’espressione è equivalente alla KB seguente:

(𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒(𝐷𝑜𝑐𝑒𝑛𝑡𝑒, 𝑅𝑒𝐴) ∧ 𝑃𝑟𝑒𝑜𝑐𝑐𝑢𝑝𝑎𝑡𝑜(𝐷𝑜𝑐𝑒𝑛𝑡𝑒))

∨

(𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒(𝐶𝑎𝑡𝑡𝑒𝑑𝑟𝑎, 𝑅𝑒𝐴) ∧ 𝑃𝑟𝑒𝑜𝑐𝑐𝑢𝑝𝑎𝑡𝑜(𝐶𝑎𝑡𝑡𝑒𝑑𝑟𝑎))

∨

𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒(𝐿𝑎𝑣𝑎𝑔𝑛𝑎, 𝑅𝑒𝐴) ∧ 𝑃𝑟𝑒𝑜𝑐𝑐𝑢𝑝𝑎𝑡𝑜(𝐿𝑎𝑣𝑎𝑔𝑛𝑎)

∨

𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒(𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒1, 𝑅𝑒𝐴) ∧ 𝑃𝑟𝑒𝑜𝑐𝑐𝑢𝑝𝑎𝑡𝑜(𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒1)

∨

𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒(𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒2, 𝑅𝑒𝐴) ∧ 𝑃𝑟𝑒𝑜𝑐𝑐𝑢𝑝𝑎𝑡𝑜(𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒2)

∨

𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒(𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒3, 𝑅𝑒𝐴) ∧ 𝑃𝑟𝑒𝑜𝑐𝑐𝑢𝑝𝑎𝑡𝑜(𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒3)

∨

𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒(𝑅𝑒𝐴, 𝑅𝑒𝐴) ∧ 𝑃𝑟𝑒𝑜𝑐𝑐𝑢𝑝𝑎𝑡𝑜(𝑅𝑒𝐴) Si può osservare che:

La congiunzione (∧) è il principale connettivo in uso con il quantificatore esistenziale ∃.

Per esempio, se consideriamo il significato inteso della formula

∃𝑥 𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒(𝑥, 𝑅𝑒𝐴) ∧ 𝑃𝑟𝑒𝑜𝑐𝑐𝑢𝑝𝑎𝑡𝑜(𝑥)

notiamo che essa è vera solo quando entrambi i congiunti sono veri (un individuo esiste davvero che è sia studente di ReA sia preoccupato). Corrisponde alla seguente espressione in linguaggio naturale: “Esiste almeno un individuo del modello, che è sia uno studente di ReA sia preoccupato.”. Si noti che stavolta la formula è vera solo se esiste veramente almeno uno studente al corso di ReA che è anche preoccupato.

Vediamo cosa succede se usiamo gli altri connettivi nella formula.

• ∃𝑥 𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒(𝑥, 𝑅𝑒𝐴) ⇒ 𝑃𝑟𝑒𝑜𝑐𝑐𝑢𝑝𝑎𝑡𝑜(𝑥)

o Corrisponde all’espressione “Esiste un individuo tale che se si tratta di uno studente di ReA allora è preoccupato.”.

o Si capisce che è un’interpretazione poco vincolante rispetto alla frase italiana di partenza “Qualche studente di ReA è preoccupato.”, che richiede l’effettiva esistenza dell’individuo.

• ∃𝑥 𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒(𝑥, 𝑅𝑒𝐴) ∨ 𝑃𝑟𝑒𝑜𝑐𝑐𝑢𝑝𝑎𝑡𝑜(𝑥)

o Corrisponde all’espressione “Esiste un individuo tale che o è uno studente di ReA o è preoccupato o entrambe le cose.”.

o Continua a essere poco vincolante, perché va bene anche se lo studente non è preoccupato o addirittura se esiste uno preoccupato che non sia studente.

• ∃𝑥 𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒(𝑥, 𝑅𝑒𝐴) ⇔ 𝑃𝑟𝑒𝑜𝑐𝑐𝑢𝑝𝑎𝑡𝑜(𝑥)

o Corrisponde all’espressione “Esiste un individuo tale che è uno studente di ReA se e solo se è preoccupato.”.

o E’ molto vicina alla congiunzione, ma è vera anche se l’individuo non è né studente di ReA né preoccupato.

Alcune proprietà comuni dei quantificatori sono le seguenti:

• Dire ∀𝑥 ∀𝑦 𝑆 o ∃𝑥 ∃𝑦 𝑆 è equivalente, dal punto di vista logico, a ∀𝑦 ∀𝑥 𝑆 o

∃𝑦 ∃𝑥 𝑆, rispettivamente, dato il carattere indipendente dei due quantificatori;

• ∃𝑥 ∀𝑦 𝑆 è invece diverso da ∀𝑦 ∃𝑥 𝑆, in quanto l’interpretazione dipende dall’ordine dei quantificatori. Si consideri ad esempio la frase “Tutti amano qualcuno.”

o La formula ∀𝑦 ∃𝑥 𝐴𝑚𝑎(𝑦, 𝑥) interpreta la frase come se il qualcuno x dipenda dall’individuo y selezionato di volta in volta (“Ognuno ama qualcuno.”).

o La formula ∃𝑥 ∀𝑦 𝐴𝑚𝑎(𝑦, 𝑥) interpreta la frase come se il qualcuno x esista indipendente dall’individuo y selezionato di volta in volta (“Qualcuno è amato da tutti.”).

• Dualità dei quantificatori: ogni quantificatore si può esprimere con l’altro quantificatore e la negazione (leggi di De Morgan per i quantificatori)

o ∀𝑥 𝑆 è come dire ¬∃𝑥¬𝑆; ad esempio

∀𝑥 𝑃𝑖𝑎𝑐𝑒(𝑥, 𝐺𝑒𝑙𝑎𝑡𝑜) e ¬∃𝑥¬𝑃𝑖𝑎𝑐𝑒(𝑥, 𝐺𝑒𝑙𝑎𝑡𝑜), cioè “a tutti piace il gelato” è come dire che “non esiste qualcuno a cui non piaccia il gelato”;

o ∃x S è come dire ¬∀x¬S; ad esempio

∃𝑥 𝑃𝑖𝑎𝑐𝑒(𝑥, 𝐵𝑎𝑐𝑐𝑎𝑙𝑎) e ¬∀𝑥¬𝑃𝑖𝑎𝑐𝑒(𝑥, 𝐵𝑎𝑐𝑐𝑎𝑙𝑎), cioè “a qualcuno

piace il baccalà” è come dire che “non è vero che a nessuno piace il baccalà”;

Concludiamo questa rassegna sulla rappresentazione della conoscenza con la logica del prim’ordine con l’uguaglianza, un predicato di arità due, che si può scrivere in modo simmetrico.

Termine1 = Termine2 è vero sotto una data interpretazione se e solo se Termine1

e Termine2 si riferiscono allo stesso oggetto.

Esempi di rappresentazione della conoscenza con la logica dei predicati 1) Esempio: variazione sull’arringa dell’avvocato

Se il mio cliente è colpevole, allora il coltello era nel cassetto. Ma, o il coltello non era nel cassetto o chiunque lo avrebbe visto, il coltello. Tuttavia, se il coltello non era lì il 10 ottobre, allora non lo ha visto nessuno, il coltello. Inoltre, se il coltello fosse stato lì il 10 ottobre, allora non solo il coltello sarebbe stato nel cassetto ma anche il martello sarebbe stato nel ripostiglio. Ma tutti sappiamo che gli utensili non erano nel ripostiglio. Per cui, signore e signori della giuria, il mio cliente è innocente.

adattato da

[http://nicolas.thiery.name/macs358/Notes/1_FormalLogic/PropositionalLogic.pdf]

Si possono identificare le seguenti proposizioni atomiche (scorporando i connettivi analizzati nel linguaggio naturale e riportando le espressioni a una forma neutra al presente).

• P1: Il mio cliente è colpevole.

• P2: Il coltello è nel cassetto.

• P3: Chiunque vede il coltello.

• P4: Il coltello è lì il 10 ottobre.

• P5: Il martello è nel ripostiglio.

• P6: Gli utensili sono nel ripostiglio.

Predicati: Colpevole(_), In(_,_), Vedere(_,_), Lì(_,_)

Costanti: MioCliente, Lì, Coltello, Cassetto, Ripostiglio, Martello

Una possibile KB è la seguente (si ricordi che la KB dipende dal compito, che nel nostro caso è limitato a verificare a):

• R1:

o Se il mio cliente è colpevole, allora il coltello è nel cassetto.

o 𝐶𝑜𝑙𝑝𝑒𝑣𝑜𝑙𝑒(𝑀𝑖𝑜𝐶𝑙𝑖𝑒𝑛𝑡𝑒) ⇒ 𝐼𝑛(𝐶𝑜𝑙𝑡𝑒𝑙𝑙𝑜, 𝐶𝑎𝑠𝑠𝑒𝑡𝑡𝑜)

• R2:

o O il coltello non è nel cassetto o chiunque vede il coltello.

o (¬𝐼𝑛(𝐶𝑜𝑙𝑡𝑒𝑙𝑙𝑜, 𝐶𝑎𝑠𝑠𝑒𝑡𝑡𝑜) ∨ ∀𝑥 𝑉𝑒𝑑𝑒𝑟𝑒(𝑥, 𝐶𝑜𝑙𝑡𝑒𝑙𝑙𝑜)) ∧

¬(¬𝐼𝑛(𝐶𝑜𝑙𝑡𝑒𝑙𝑙𝑜, 𝐶𝑎𝑠𝑠𝑒𝑡𝑡𝑜 ∧ ∀𝑥 𝑉𝑒𝑑𝑒𝑟𝑒(𝑥, 𝐶𝑜𝑙𝑡𝑒𝑙𝑙𝑜))

• R3:

o Se il coltello non è lì il 10 ottobre, allora nessuno vede il coltello.

o (¬𝐼𝑛(𝐶𝑜𝑙𝑡𝑒𝑙𝑙𝑜, 𝐿ì) ⇒ ∀𝑥 ¬𝑉𝑒𝑑𝑒𝑟𝑒(𝑥, 𝐶𝑜𝑙𝑡𝑒𝑙𝑙𝑜))

• R4:

o Se il coltello è lì il 10 ottobre, allora il coltello è nel cassetto e il martello è nel ripostiglio.

o (𝐼𝑛(𝐶𝑜𝑙𝑡𝑒𝑙𝑙𝑜, 𝐿ì) ⇒ 𝐼𝑛(𝐶𝑜𝑙𝑡𝑒𝑙𝑙𝑜, 𝐶𝑎𝑠𝑠𝑒𝑡𝑡𝑜) ∧ 𝐼𝑛(𝑀𝑎𝑟𝑡𝑒𝑙𝑙𝑜, 𝑅𝑖𝑝𝑜𝑠𝑡𝑖𝑔𝑙𝑖𝑜))

• R5:

o Gli utensili non sono nel ripostiglio.

o (∀𝑥 𝑈𝑡𝑒𝑛𝑠𝑖𝑙𝑒 𝑥 ⇒ ¬𝐼𝑛(𝑥, 𝑅𝑖𝑝𝑜𝑠𝑡𝑖𝑔𝑙𝑖𝑜))

Con

• a:

o Il mio cliente è innocente.

o ¬𝐶𝑜𝑙𝑝𝑒𝑣𝑜𝑙𝑒(𝑀𝑖𝑜𝐶𝑙𝑖𝑒𝑛𝑡𝑒)

Si noti che sarà difficile fare qualche inferenza significativa se non si aggiungono alla base di conoscenza la formule che rappresenta il fatto che il martello sia un utensile, cioè:

• R6 (conoscenza aggiuntiva) o Il martello è un utensile.

o 𝑈𝑡𝑒𝑛𝑠𝑖𝑙𝑒 𝑀𝑎𝑟𝑡𝑒𝑙𝑙𝑜

[Esercizio: Trasformare la costante Martello in un oggetto generico della categoria dei Martelli e usarlo negli altri enunciati della KB.]

2) Esempio: dominio della parentela

Si assumo come primitivi (non definiti) i predicati 𝐺𝑒𝑛𝑖𝑡𝑜𝑟𝑒(_, _) e 𝐹𝑒𝑚𝑚𝑖𝑛𝑎(_).

• Definizione di Consanguineo, basandosi sul predicato Genitore:

∀𝑥 ∀𝑦 𝐶𝑜𝑛𝑠𝑎𝑛𝑔𝑢𝑖𝑛𝑒𝑜(𝑥, 𝑦) ⇔ (¬(𝑥 = 𝑦) ∧ ∃𝑚 ∃𝑝 ¬(𝑚 = 𝑝) ∧ 𝐺𝑒𝑛𝑖𝑡𝑜𝑟𝑒(𝑚, 𝑥) ∧ 𝐺𝑒𝑛𝑖𝑡𝑜𝑟𝑒(𝑝, 𝑥) ∧ 𝐺𝑒𝑛𝑖𝑡𝑜𝑟𝑒(𝑚, 𝑦) ∧ 𝐺𝑒𝑛𝑖𝑡𝑜𝑟𝑒(𝑝, 𝑦))

• I fratelli sono consanguinei: ∀𝑥 ∀𝑦 𝐹𝑟𝑎𝑡𝑒𝑙𝑙𝑜(𝑥, 𝑦) ⇒ 𝐶𝑜𝑛𝑠𝑎𝑛𝑔𝑢𝑖𝑛𝑒𝑜(𝑥, 𝑦)

• La madre di qualcuno è il suo genitore femmina: ∀𝑚 ∀𝑓 𝑀𝑎𝑑𝑟𝑒(𝑓) = 𝑚 ⇔ (𝐹𝑒𝑚𝑚𝑖𝑛𝑎(𝑚) ∧ 𝐺𝑒𝑛𝑖𝑡𝑜𝑟𝑒(𝑚, 𝑓))

• La consanguineità è una proprietà simmetrica: ∀𝑥 ∀𝑦 𝐶𝑜𝑛𝑠𝑎𝑛𝑔𝑢𝑖𝑛𝑒𝑜(𝑥, 𝑦) ⇔ 𝐶𝑜𝑛𝑠𝑎𝑛𝑔𝑢𝑖𝑛𝑒𝑜(𝑦, 𝑥)

3. Inferenza con la logica dei predicati

L’approccio seguito per le inferenze con la logica dei predicati è di rendere la KB in termini proposizionali e quindi agire come per la logica proposizionale vista in precedenza. La cosiddetta proposizionalizzazione prevede la sostituzione delle variabili in termini ground, cioè termini che non contengono variabili. Un predicato proposizionalizzato è come se fosse una proposizione vera e propria della logica

proposizionale. Con l’ottica della proposizionalizzazione, introduciamo due regole di inferenza.

Istanziazione universale (Universal instantiation – UI)

Ogni istanziazione di un enunciato quantificato universalmente è conseguenza logica di esso:

∀𝑣 𝛼 𝑆𝑢𝑏𝑠𝑡({𝑣/𝑔}, 𝛼) per ogni variabile 𝑣 e termine ground 𝑔.

Ad esempio, riconsiderando il caso dell’enunciato:

∀𝑥 𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒(𝑥, 𝑅𝑒𝐴) ⇒ 𝐼𝑛𝑡𝑒𝑙𝑙𝑖𝑔𝑒𝑛𝑡𝑒(𝑥) con le costanti:

{𝐷𝑜𝑐𝑒𝑛𝑡𝑒, 𝐶𝑎𝑡𝑡𝑒𝑑𝑟𝑎, 𝐿𝑎𝑣𝑎𝑔𝑛𝑎, 𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒1, 𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒2, 𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒3, 𝑅𝑒𝐴}

si ha che i seguenti enunciati sono tutti conseguenze logiche:

(𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒(𝐷𝑜𝑐𝑒𝑛𝑡𝑒, 𝑅𝑒𝐴) ⇒ 𝐼𝑛𝑡𝑒𝑙𝑙𝑖𝑔𝑒𝑛𝑡𝑒(𝐷𝑜𝑐𝑒𝑛𝑡𝑒)) (𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒(𝐶𝑎𝑡𝑡𝑒𝑑𝑟𝑎, 𝑅𝑒𝐴) ⇒ 𝐼𝑛𝑡𝑒𝑙𝑙𝑖𝑔𝑒𝑛𝑡𝑒(𝐶𝑎𝑡𝑡𝑒𝑑𝑟𝑎))

𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒(𝐿𝑎𝑣𝑎𝑔𝑛𝑎, 𝑅𝑒𝐴) ⇒ 𝐼𝑛𝑡𝑒𝑙𝑙𝑖𝑔𝑒𝑛𝑡𝑒(𝐿𝑎𝑣𝑎𝑔𝑛𝑎) 𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒(𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒1, 𝑅𝑒𝐴) ⇒ 𝐼𝑛𝑡𝑒𝑙𝑙𝑖𝑔𝑒𝑛𝑡𝑒(𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒1) 𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒(𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒2, 𝑅𝑒𝐴) ⇒ 𝐼𝑛𝑡𝑒𝑙𝑙𝑖𝑔𝑒𝑛𝑡𝑒(𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒2) 𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒(𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒3, 𝑅𝑒𝐴) ⇒ 𝐼𝑛𝑡𝑒𝑙𝑙𝑖𝑔𝑒𝑛𝑡𝑒(𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒3)

𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒(𝑅𝑒𝐴, 𝑅𝑒𝐴) ⇒ 𝐼𝑛𝑡𝑒𝑙𝑙𝑖𝑔𝑒𝑛𝑡𝑒(𝑅𝑒𝐴)

Istanziazione esistenziale (Existential instantiation - EI)

Dati l’enunciato α, la variabile v e il simbolo di costante k che non è presente nella KB, si ha che:

∃𝑣 𝛼 𝑆𝑢𝑏𝑠𝑡({𝑣/𝑘}, 𝛼)

dove k è un nuovo simbolo di costante, detta costante di Skolem.

Ad esempio, riconsiderando il caso dell’enunciato:

(∃𝑥 𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒 𝑥, 𝑅𝑒𝐴 ∧ 𝑃𝑟𝑒𝑜𝑐𝑐𝑢𝑝𝑎𝑡𝑜 𝑥 ) con l’insieme solito di costanti:

{𝐷𝑜𝑐𝑒𝑛𝑡𝑒, 𝐶𝑎𝑡𝑡𝑒𝑑𝑟𝑎, 𝐿𝑎𝑣𝑎𝑔𝑛𝑎, 𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒1, 𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒2, 𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒3, 𝑅𝑒𝐴}

(𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒(𝐶1, 𝑅𝑒𝐴) ∧ 𝑃𝑟𝑒𝑜𝑐𝑐𝑢𝑝𝑎𝑡𝑜(𝐶1))

Applicando le istanziazioni universale ed esistenziale, si riesce quindi a proposizionalizzare la KB. Notiamo infatti che un enunciato che contiene solo termini ground altri non è che una proposizione: solo gli umani assegnano a una stringa come

𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒(𝐶1, 𝑅𝑒𝐴)

un significato che dipende dalle sottostringhe 𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒 e 𝑅𝑒𝐴; per la macchina, non vi è alcuna differenza con 𝑃1. Il significato di una stringa non dipende dalle componenti delle stringhe stesse, ma da come una stringa si relaziona con altre stringhe.

Per fare delle inferenze con una KB che è stata proposizionalizzata, si possono applicare le tecniche utilizzate per la logica proposizionale. Supponiamo che la KB contenga solo le seguenti formule:

∀𝑥 𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒(𝑥, 𝑅𝑒𝐴) ⇒ 𝐼𝑛𝑡𝑒𝑙𝑙𝑖𝑔𝑒𝑛𝑡𝑒(𝑥) 𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒(𝑆1, 𝑅𝑒𝐴)

𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒(𝑆2, 𝑁𝑃) 𝐶𝑢𝑔𝑖𝑛𝑜(𝑆1, 𝑆2)

Usando l’istanziazione universale con tutte le costanti della KB, la KB contiene le seguenti formule:

𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒(𝑆1, 𝑅𝑒𝐴) ⇒ 𝐼𝑛𝑡𝑒𝑙𝑙𝑖𝑔𝑒𝑛𝑡𝑒(𝑆1) 𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒(𝑆2, 𝑅𝑒𝐴) ⇒ 𝐼𝑛𝑡𝑒𝑙𝑙𝑖𝑔𝑒𝑛𝑡𝑒(𝑆2) 𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒(𝑅𝑒𝐴, 𝑅𝑒𝐴) ⇒ 𝐼𝑛𝑡𝑒𝑙𝑙𝑖𝑔𝑒𝑛𝑡𝑒(𝑅𝑒𝐴)

𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒(𝑁𝑃, 𝑅𝑒𝐴) ⇒ 𝐼𝑛𝑡𝑒𝑙𝑙𝑖𝑔𝑒𝑛𝑡𝑒(𝑁𝑃) 𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒(𝑆1, 𝑅𝑒𝐴)

𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒(𝑆2, 𝑁𝑃) 𝐶𝑢𝑔𝑖𝑛𝑜(𝑆1, 𝑆2)

Questa nuova KB si dice proprio KB proposizionalizzata, come se contenesse i seguenti simboli “proposizionali” (diversi dai soliti P1, P2, …, solo perché possiedono una struttura di predicato, comprensibile dagli umani per i nomi scelti):

𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒(𝑆1, 𝑅𝑒𝐴) 𝐼𝑛𝑡𝑒𝑙𝑙𝑖𝑔𝑒𝑛𝑡𝑒 𝑆1 𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒(𝑆2, 𝑅𝑒𝐴)

𝐼𝑛𝑡𝑒𝑙𝑙𝑖𝑔𝑒𝑛𝑡𝑒(𝑆2) 𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒(𝑅𝑒𝐴, 𝑅𝑒𝐴)

𝐼𝑛𝑡𝑒𝑙𝑙𝑖𝑔𝑒𝑛𝑡𝑒(𝑅𝑒𝐴) 𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒(𝑁𝑃, 𝑅𝑒𝐴)

𝐼𝑛𝑡𝑒𝑙𝑙𝑖𝑔𝑒𝑛𝑡𝑒(𝑁𝑃) 𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒(𝑆2, 𝑁𝑃) 𝐶𝑢𝑔𝑖𝑛𝑜(𝑆1, 𝑆2)

Ogni KB in logica dei predicati può essere proposizionalizzata in modo da mantenere la nozione di conseguenza logica. In particolare si può dimostrare facilmente che:

Un enunciato ground è conseguenza logica della KB proposizionalizzata se e solo se è conseguenza logica della KB originale.

Quindi, l’idea è di proposizionalizzare la KB e applicare i metodi di inferenza della logica proposizionale.

Esiste però un problema con i simboli di funzione, perché possono rendere la proposizionalizzazione un processo infinito (in particolare, si possono creare infiniti termini ground). Ad esempio, se ho la funzione 𝑃𝑎𝑑𝑟𝑒_𝑑𝑖(_) e la costante 𝑃𝑖𝑒𝑡𝑟𝑜 , non so quando fermarmi nella generazione degli individui ottenuti applicando la funzione anche a tutti gli individui generati:

𝑃𝑖𝑒𝑡𝑟𝑜

𝑃𝑎𝑑𝑟𝑒_𝑑𝑖(𝑃𝑖𝑒𝑡𝑟𝑜)

𝑃𝑎𝑑𝑟𝑒_𝑑𝑖(𝑃𝑎𝑑𝑟𝑒_𝑑𝑖(𝑃𝑖𝑒𝑡𝑟𝑜))

𝑃𝑎𝑑𝑟𝑒_𝑑𝑖(𝑃𝑎𝑑𝑟𝑒_𝑑𝑖(𝑃𝑎𝑑𝑟𝑒_𝑑𝑖(𝑃𝑖𝑒𝑡𝑟𝑜)))

…

Il problema è stato risolto (parzialmente) nel 1930 da Herbrand, che dimostrò il suo teorema:

Se un enunciato α è conseguenza logica di una KB in logica dei predicati, allora esso è conseguenza logica di un sottoinsieme finite della KB proposizionalizzata.

L’idea del teorema, come della dimostrazione, è simile all’idea che sta alla base dell’algoritmo di ricerca detto approfondimento iterativo: a ogni iterazione, si fissa un livello di profondità n e si generano i termini ground applicando funzioni fino alla profondità di annidamento n. Ora, visto che α è conseguenza logica della KB originale per ipotesi di teorema, esiste necessariamente un tale n al cui livello la KB proposizionalizzata ha α come conseguenza logica. Il livello di profondità aumenta di 1 a ogni ciclo; o prima o poi raggiungeremo il livello giusto, quel livello tale che la KB proposizionalizzata di quel livello ha come sua conseguenza logica α. A questo punto, sembra tutto risolto, ma non è vero.

Come si può notare, il problema esiste quando α non è conseguenza logica, perché in questo caso la ricerca del livello di profondità n proseguirà all’infinito. E, infatti, Turing e Church dimostrarono nel 1936 che per la logica dei predicati la nozione di conseguenza logica è semi-decidibile. Cioè in generale,

se α è conseguenza logica di KB, allora esiste un algoritmo (nel caso di Herbrand, trovare una KB proposizionalizzata adatta) in grado di rispondere “Si. E’ conseguenza logica!”; se, invece, α non è conseguenza logica, non si riesce a trovare un algoritmo in grado di rispondere “No.

Non è conseguenza logica!”.

Anche nel caso positivo, comunque, esiste un problema di performance. Il processo di proposizionalizzazione genera comunque una marea di enunciati irrilevanti che non vengono presi in considerazione per dimostrare una certa conseguenza logica: infatti, così come avveniva per le “inutili” righe della tabella di verità che contenevano simboli

proposizionali necessariamente falsi, istanziare il predicato 𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒 𝑥, 𝑅𝑒𝐴 su 𝑆𝑒𝑑𝑖𝑎, 𝐷𝑜𝑐𝑒𝑛𝑡𝑒, 𝐶𝑎𝑡𝑡𝑒𝑑𝑟𝑎, … non è utile per la dimostrazione della conseguenza logica 𝐼𝑛𝑡𝑒𝑙𝑙𝑖𝑔𝑒𝑛𝑡𝑒(𝑆1). Per questo motivo, si può proposizionalizzare in modo mirato.

L’operazione opportuna si chiama unificazione. In questo caso, si può calcolare l’inferenza applicando una sostituzione θ che renda uguali due predicati. Ad esempio, se consideriamo i predicati

𝐴𝑚𝑎 𝑅𝑒𝑛𝑧𝑜, 𝑦 e 𝐴𝑚𝑎 𝑥, 𝐿𝑢𝑐𝑖𝑎

e applichiamo la sostituzione 𝜃 = {𝑥/𝑅𝑒𝑛𝑧𝑜, 𝑦/𝐿𝑢𝑐𝑖𝑎}, otteniamo l’uguaglianza dei due predicati, in quanto diventano entrambi 𝐴𝑚𝑎 𝑅𝑒𝑛𝑧𝑜, 𝐿𝑢𝑐𝑖𝑎 , in cui la variabile 𝑥 è stata sostituita dalla costante 𝑅𝑒𝑛𝑧𝑜 e la variabile 𝑦 è stata sostituita dalla costante 𝐿𝑢𝑐𝑖𝑎. L’unificazione di due predicati è quindi una sostituzione delle variabili che renda i due predicati uguali.

𝑈𝑛𝑖𝑓𝑖𝑐𝑎𝑧𝑖𝑜𝑛𝑒(𝛼, 𝛽) = 𝜃 𝑠𝑒 𝛼𝜃 = 𝛽𝜃

Cioè l’unificazione dei predicati α e β è una sostituzione θ che applicata a α e β, producendo αθ e βθ li rende uguali.

Nella seguente tabella si hanno un po’ di casi possibili.

𝒑 𝒒 𝜽

𝑨𝒎𝒂 𝑹𝒆𝒏𝒛𝒐, 𝒚 𝐴𝑚𝑎 𝑅𝑒𝑛𝑧𝑜, 𝐿𝑢𝑐𝑖𝑎 {𝑦/𝐿𝑢𝑐𝑖𝑎}

𝑨𝒎𝒂 𝑹𝒆𝒏𝒛𝒐, 𝒚 𝐴𝑚𝑎 𝑥, 𝐿𝑢𝑐𝑖𝑎 {𝑥/𝑅𝑒𝑛𝑧𝑜, 𝑦/𝐿𝑢𝑐𝑖𝑎}

𝑨𝒎𝒂 𝑹𝒆𝒏𝒛𝒐, 𝒚 𝐴𝑚𝑎 𝑥, 𝐶𝑜𝑚𝑝𝑎𝑔𝑛𝑎_𝑑𝑖_𝑏𝑎𝑛𝑐𝑜(𝑥) {𝑥/𝑅𝑒𝑛𝑧𝑜,

𝑦/𝐶𝑜𝑚𝑝𝑎𝑔𝑛𝑎_𝑑𝑖_𝑏𝑎𝑛𝑐𝑜(𝑅𝑒𝑛𝑧𝑜)}

𝑨𝒎𝒂 𝑹𝒆𝒏𝒛𝒐, 𝒚 𝐴𝑚𝑎 𝑦, 𝐿𝑢𝑐𝑖𝑎 NON UNIFICA

𝑨𝒎𝒂 𝑹𝒆𝒏𝒛𝒐, 𝒚 𝐴𝑚𝑎 𝑥, 𝑧 {𝑥/𝑅𝑒𝑛𝑧𝑜, 𝑦/𝑧}

Come si vede, in presenza di variabile e costante, la variabile viene sostituita semplicemente dalla costante, anche nel caso di più sostituzioni o se la variabile è utilizzata all’interno di una funzione (vedi 𝐶𝑜𝑚𝑝𝑎𝑔𝑛𝑎_𝑑𝑖_𝑏𝑎𝑛𝑐𝑜); nel caso in cui si cerca di sostituire la stessa variabile con due valori diversi, l’unificazione fallisce.

Osserviamo un paio di questioni operative.

1. Prima di procedere all’unificazione, conviene sempre rendere i nomi delle variabili unici in modo da non introdurre vincoli che non ci sono nella KB originale: ad esempio, se in un enunciato abbiamo il predicato 𝐴𝑚𝑎 𝑦, 𝐿𝑢𝑐𝑖𝑎 e in un altro enunciato abbiamo il predicato 𝑈𝑐𝑐𝑖𝑑𝑒 𝑅𝑒𝑛𝑧𝑜, 𝑦 , le variabili 𝑦 non sono vincolate a essere unificate con la stessa costante perché provengono da due enunciati diversi (si dice che lo “scope”, cioè l’ambito in cui vale la variabile, è limitato all’enunciato, e non va oltre l’enunciato);

procedendo a una sostituzione di variabili prima di procedere all’unificazione – cioè, 𝐴𝑚𝑎 𝑦, 𝐿𝑢𝑐𝑖𝑎 diventa 𝐴𝑚𝑎 𝑧, 𝐿𝑢𝑐𝑖𝑎 , si evita il problema di imporre che sia necessario sostituirli con la stessa costante.

2. Si noti infine che nell’ultima riga della tabella, si ha un caso in cui una variabile è sostituita da un’altra variabile (y/z). Sarebbero possibili altre unificazioni, cioè sostituzioni che rendono uguali i due predicati (𝐴𝑚𝑎 𝑅𝑒𝑛𝑧𝑜, 𝑦 e 𝐴𝑚𝑎 𝑥, 𝑧 ): ad esempio la sostituzione

{𝑥/𝑅𝑒𝑛𝑧𝑜, 𝑦/𝑅𝑒𝑛𝑧𝑜, 𝑧/𝑅𝑒𝑛𝑧𝑜}

è anche un’unificazione, ma sarebbe meno generale della prima, in quanto la prima non vincola a una costante specifica i valori di 𝑦 e 𝑧, ma solo a essere uguali.

Nell’unificazione, si prende sempre la sostituzione più generale (si chiama Most General Unifier, MGU).

Se, grazie all’unificazione, riusciamo a rendere uguali due predicati, allora si può procedere a lavorare con le regole di inferenza. Come nel caso della logica proposizionale, noi possiamo utilizzare sia equivalenze logiche sia conseguenze logiche per inferire dalla KB la proposizione cercata. Per la logica dei predicati, ci concentriamo su una sola regola di inferenza, che si rivela molto utile nelle applicazioni comuni della logica nel Semantic Web. E’ una forma generalizzata del Modus Ponens.

Nel Capitolo 3, abbiamo introdotto il Modus Ponens per la logica proposizionale:

l’enunciato (𝛼 ∧ (𝛼 → 𝛽)) → 𝛽) è valido.

Ora lo generalizziamo nel senso di applicarlo alla logica dei predicati, mediante il supporto dell’unificazione, per implementare l’uguaglianza tra due predicati. La regola del Modus Ponens Generalizzato (GMP) si può schematizzare nel seguente modo:

𝒑_𝟏^…, 𝒑_𝟐^…, … , 𝒑_𝒏^…, (𝒑_𝟏∧ 𝒑_𝟐∧ … ∧ 𝒑_𝒏 ⇒ 𝒒) 𝒒𝜽

dove 𝑝_Z^…𝜃 = 𝑝_Z𝜃, per tutte le i.

Si intende che le 𝑝_Z^… sono uguali 𝑝_Z a meno della sostituzione 𝜃, che viene applicata alla conclusione 𝑞. Infatti, la conclusione vale solo per la 𝑞 con la sostituzione (cioè per 𝑞𝜃).

Facciamo un esempio. Consideriamo le due proposizioni:

“Tutti gli studenti di ReA che hanno consegnato gli esercizi possono sostenere l’orale. Giorgio Rossi è uno studente di ReA e ha consegnato gli esercizi.”

La rappresentazione del Modus Ponens Generalizzato (GMP) in questo caso sarà:

𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒(𝐺𝑅, 𝑅𝑒𝐴), 𝐶𝑜𝑛𝑠𝑒𝑔𝑛𝑎(𝐺𝑅, 𝐸𝑠𝑒𝑟𝑐𝑖𝑧𝑖), ∀𝑥 𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒(𝑥, 𝑅𝑒𝐴) ∧ 𝐶𝑜𝑛𝑠𝑒𝑔𝑛𝑎(𝑥, 𝐸𝑠𝑒𝑟𝑐𝑖𝑧𝑖) ⇒ 𝑂𝑟𝑎𝑙𝑒(𝑥) 𝑂𝑟𝑎𝑙𝑒(𝐺𝑅)

dove

• 𝜃 = {x/GR},

• 𝑝_"^…𝜃 = 𝑝_"𝜃 = 𝑆𝑡𝑢𝑑𝑒𝑛𝑡𝑒(𝐺𝑅, 𝑅𝑒𝐴),

• 𝑝_&^…𝜃 = 𝑝_&𝜃 = 𝐶𝑜𝑛𝑠𝑒𝑔𝑛𝑎(𝐺𝑅, 𝐸𝑠𝑒𝑟𝑐𝑖𝑧𝑖).

GMP è un metodo corretto e completo quando la KB consiste di clausole definite.

Assumendo che tutte le variabili siano quantificate universalmente e la quantificazione esistenziale sia stata sostituita da una skolemizzazione, una clausola definita ha la forma di disgiunzione di proposizioni di cui una sola positiva:

Se raccogliamo in parentesi (per l’associatività della disgiunzione) e applichiamo De Morgan (vedi Capitolo 3), otteniamo

¬(𝑝_"∧ 𝑝_&∧ … ∧ 𝑝_Œ) ∨ 𝑞

che corrisponde in forma di implicazione (vedi equivalenze nel Capitolo 3) a

𝒑_𝟏∧ 𝒑_𝟐∧ … ∧ 𝒑_𝒏 ⇒ 𝒒

Una clausola definita senza proposizioni negate (ad esempio, 𝑝) è detta fatto. Quindi, se riusciamo a esprimere una KB in forma di clausole definite possiamo applicare la regola del Modus Ponens Generalizzato (GMP).

Per dimostrare che l’enunciato 𝛼 è conseguenza logica di KB, si procede applicando la regola di inferenza GMP. Per rappresentare il processo di inferenza, si può usare un grafo and/or e il metodo di concatenazione all’indietro (Backward Chaining).

In questa parte del grafo AND/OR troviamo una rappresentazione dell’applicazione del Modus Ponens. In alto ci sono i predicati dell’antecedente, a cui è stata già applicata la sostituzione 𝜃; in basso, il conseguente (unico, nelle clausole definite) dell’implicazione, anch’esso con la sostituzione 𝜃 già applicata; l’arco disegnato tra le connessioni indica che tutte i predicati dell’antecedente sono in AND. Il grafo AND/OR di un’inferenza prevede più applicazioni del Modus Ponens, diventando di più livelli connessi tra loro.

Più in basso vediamo un esempio.

4. Esempio di rappresentazione della conoscenza e di inferenza con la logica dei predicati

Ora applichiamo tutto ciò che sappiamo sulla formalizzazione in logica dei predicati a un esempio di rappresentazione della conoscenza e di inferenza. La conduzione della soluzione completa dell’esempio ci consente di introdurre le pratiche dell’ingegneria della conoscenza, che traducono la conoscenza da un testo alla formalizzazione logica, e di eseguire dei test di inferenza con la regola del Modus Ponens Generalizzato in modo immediato. Saremo molto attenti a usare predicati che sono nella forma delle clausole definite e introdurremo delle linee guida che il lettore potrà usare in futuro nella costruzione eventuale di basi di conoscenza. Cominciamo dal testo, la nostra fonte di conoscenza espressa in linguaggio naturale, e dal problema da risolvere.

Il crimine del Colonnello West [Russell, Norvig]

p₁'θ!$! p₂'θ!$! …! p_n'θ!$!

qθ!$!

La legge americana dice che è un crimine per un americano vendere armi a nazioni ostili. Il paese Nono, un nemico dell’America, possiede alcuni missili. Tutti i suoi missili gli sono stati venduti dal Colonnello West, che è americano. Dimostrare che il Colonnello West è un criminale.

Nella pratica dell’ingegneria della conoscenza (knowledge engineering), occorre innanzitutto identificare il compito, l’obiettivo per cui si costruisce la base di conoscenza. E’ un passo fondamentale per un semplice motivo: ogni volta che si rappresenta della conoscenza, occorre porsi dei limiti sulla profondità dei nostri enunciati. Se, per esempio, devo parlare del calore e della temperatura, scenderò al livello di descrizione dell’agitazione termica delle molecole, se l’obiettivo è inferire la nozione del passaggio di stato di un materiale, ma mi limiterò a dire che sono in proporzione diretta se devo solo inferire che la temperatura di un corpo scende quando il corpo perde calore. Nel nostro esempio, l’obiettivo è già richiesto dall’esercizio, cioè dimostrare che il Colonnello West è un criminale.

Una volta che l’obiettivo è individuato, occorre recuperare tutta la conoscenza possibile sull’argomento. Si possono studiare le enciclopedie e i manuali specialistici (scritti in linguaggio naturale e/o tecnico), consultare siti web specialistici, intervistare gli esperti di dominio, per comprendere la relazione tra la conoscenza e l’obiettivo, astrarre gli aspetti importanti per il compito, evitare di essere troppo specifici, … nella codifica successiva della conoscenza. Nel nostro esempio (è un esercizio!), la conoscenza viene comunicata dal testo stesso (anche se occorrerà aggiungere delle informazioni) per riuscire a completare il compito. Tornando invece all’esempio citato in precedenza, occorre mettere insieme la conoscenza fisica intorno a calore e temperatura al livello richiesto dal compito.

A questo punto, inizia la fase di codifica vera e propria. Consiste di tre sotto-fasi che operano in parallelo, influenzandosi l’una con l’altra, con andate e ritorni:

• compilare un vocabolario di predicati, funzioni e costanti;

• codificare la conoscenza generale sul dominio;

• codificare la conoscenza specifica (cioè la descrizione) del problema.

Si procede spezzando, come abbiamo già fatto nel caso dell’arringa dell’avvocato, in enunciati in linguaggio naturale. Si identificano gli oggetti del dominio, che diventeranno costanti, nel caso in cui siano identificabili direttamente,

• “la Repubblica Italiana” – 𝑅𝑒𝑝𝑢𝑏𝑏𝑙𝑖𝑐𝑎𝐼𝑡𝑎𝑙𝑖𝑎𝑛𝑎,

• “la guerra di Crimea” – 𝐺𝑢𝑒𝑟𝑟𝑎_𝑑𝑖_𝐶𝑟𝑖𝑚𝑒𝑎,

• “Claudia” – 𝐶𝑙𝑎𝑢𝑑𝑖𝑎,

• …

e funzioni, per gli oggetti identificati in relazione ad altri oggetti,

• “il presidente della Repubblica Italiana” – 𝑃𝑟𝑒𝑠𝑖𝑑𝑒𝑛𝑡𝑒(𝑅𝑒𝑝𝑢𝑏𝑏𝑙𝑖𝑐𝑎𝐼𝑡𝑎𝑙𝑖𝑎𝑛𝑎),

• “il luogo della guerra di Crimea” – 𝐿𝑢𝑜𝑔𝑜(𝐺𝑢𝑒𝑟𝑟𝑎_𝑑𝑖_𝐶𝑟𝑖𝑚𝑒𝑎),

• “la stanza di Claudia” – 𝑆𝑡𝑎𝑛𝑧𝑎(𝐶𝑙𝑎𝑢𝑑𝑖𝑎),

• …

Si identificano quindi le relazioni tra gli oggetti, considerando la conoscenza generale, che coinvolge variabili e quantificatori (soprattutto universali) e scritte, nel nostro caso, in forma di clausole definite. Vediamo due esempi.

• “Se uno fa una lesione al suo prossimo, si farà a lui come egli ha fatto all'altro”

[legge del taglione, Codice di Hammurabi, Bibbia]

∀𝑥 ∀𝑦 ∀𝑧 ∃𝑦^…𝑃𝑒𝑟𝑠𝑜𝑛𝑎(𝑥) ∧ 𝑃𝑒𝑟𝑠𝑜𝑛𝑎(𝑦) ∧ 𝐴𝑧𝑖𝑜𝑛𝑒(𝑧, 𝑥, 𝑦) ∧ 𝐿𝑒𝑠𝑖𝑜𝑛𝑒(𝑧, 𝑦)

⇒ 𝐴𝑧𝑖𝑜𝑛𝑒(𝐴𝑧𝑖𝑜𝑛𝑒𝑆𝑖𝑚𝑚𝑒𝑡𝑟𝑖𝑐𝑎(𝑧), 𝑦^…, 𝑥)

Per ogni coppia di persone <x,y> e un’azione z compiuta da x su y che procura una lesione a y, esiste un qualcuno o qualcosa y’ che compirà l’azione simmetrica di z su x. Notare che AzioneSimmetrica è una funzione che data z, restituisce un’azione simmetrica ad essa. Non avessimo avuto il vincolo delle clausole definite, la versione più adeguata sarebbe stata:

∀𝑥 ∀𝑦 ∀𝑧 𝑃𝑒𝑟𝑠𝑜𝑛𝑎(𝑥) ∧ 𝑃𝑒𝑟𝑠𝑜𝑛𝑎(𝑦) ∧ 𝐴𝑧𝑖𝑜𝑛𝑒(𝑧, 𝑥, 𝑦) ∧ 𝐿𝑒𝑠𝑖𝑜𝑛𝑒(𝑧, 𝑦) ⇒ ∃𝑦^…∃𝑧^… 𝑇𝑖𝑝𝑜𝐴𝑧𝑖𝑜𝑛𝑒(𝑧) = 𝑇𝑖𝑝𝑜𝐴𝑧𝑖𝑜𝑛𝑒(𝑧^…) ∧ 𝐴𝑧𝑖𝑜𝑛𝑒(𝑧^…, 𝑦^…, 𝑥)

• “I cetacei sono animali acquatici dotati di respirazione polmonare.” [Aristotele]

∀𝑥 𝐶𝑒𝑡𝑎𝑐𝑒𝑜(𝑥) ⇒ 𝐴𝑛𝑖𝑚𝑎𝑙𝑒𝐴𝑐𝑞𝑢𝑎𝑡𝑖𝑐𝑜(𝑥) ∧ 𝑅𝑒𝑠𝑝𝑖𝑟𝑎𝑧𝑖𝑜𝑛𝑒(𝑥, 𝑃𝑜𝑙𝑚𝑜𝑛𝑎𝑟𝑒) interpretata come condizione necessaria, ma non sufficiente.

Infine si codifica la descrizione specifica del problema, tipicamente con fatti, cioè clausole definite che sono formate solo dalla proposizione positiva. Di nuovo, vediamo due esempi.

• “Pasquale ha ferito Ciro, rompendogli un dente.”

𝑃𝑒𝑟𝑠𝑜𝑛𝑎(𝑃𝑎𝑠𝑞𝑢𝑎𝑙𝑒) ∧ 𝑃𝑒𝑟𝑠𝑜𝑛𝑎(𝐶𝑖𝑟𝑜) ∧

𝐴𝑧𝑖𝑜𝑛𝑒(𝐹𝑒𝑟𝑖𝑟𝑒𝑃𝐶, 𝑃𝑎𝑠𝑞𝑢𝑎𝑙𝑒, 𝐶𝑖𝑟𝑜) ∧ 𝐿𝑒𝑠𝑖𝑜𝑛𝑒𝐷𝑒𝑛𝑡𝑒(𝐹𝑒𝑟𝑖𝑟𝑒𝑃𝐶, 𝐶𝑖𝑟𝑜)

• “Moby Dick è una balena.”

𝐵𝑎𝑙𝑒𝑛𝑎(𝑀𝑜𝑏𝑦𝐷𝑖𝑐𝑘)

Durante queste codifiche, si fa crescere un vocabolario, in modo da tenere conto delle costanti, funzioni e predicati che vengono introdotti dalle formule che descrivono la conoscenza generale e la situazione specifica.

• Costanti: 𝑅𝑒𝑝𝑢𝑏𝑏𝑙𝑖𝑐𝑎𝐼𝑡𝑎𝑙𝑖𝑎𝑛𝑎, 𝐺𝑢𝑒𝑟𝑟𝑎_𝑑𝑖_𝐶𝑟𝑖𝑚𝑒𝑎, 𝐶𝑙𝑎𝑢𝑑𝑖𝑎, 𝑃𝑎𝑠𝑞𝑢𝑎𝑙𝑒, 𝐶𝑖𝑟𝑜, 𝐹𝑒𝑟𝑖𝑟𝑒𝑃𝐶, 𝑀𝑜𝑏𝑦𝐷𝑖𝑐𝑘, …;

• Funzioni: 𝑃𝑟𝑒𝑠𝑖𝑑𝑒𝑛𝑡𝑒(_), 𝐿𝑢𝑜𝑔𝑜(_), 𝑆𝑡𝑎𝑛𝑧𝑎(_), 𝐴𝑧𝑖𝑜𝑛𝑒𝑆𝑖𝑚𝑚𝑒𝑡𝑟𝑖𝑐𝑎(_), …

• Predicati: 𝑃𝑒𝑟𝑠𝑜𝑛𝑎(_),𝐴𝑧𝑖𝑜𝑛𝑒(_ , _ , _), 𝐿𝑒𝑠𝑖𝑜𝑛𝑒(_ , _), 𝐿𝑒𝑠𝑖𝑜𝑛𝑒𝐷𝑒𝑛𝑡𝑒(_ , _), 𝐶𝑒𝑡𝑎𝑐𝑒𝑜(_), 𝐴𝑛𝑖𝑚𝑎𝑙𝑒𝐴𝑐𝑞𝑢𝑎𝑡𝑖𝑐𝑜(_), 𝑅𝑒𝑠𝑝𝑖𝑟𝑎𝑧𝑖𝑜𝑛𝑒(_ , _), 𝐵𝑎𝑙𝑒𝑛𝑎(_), …

Costruendo il vocabolario, si nota che 𝐿𝑒𝑠𝑖𝑜𝑛𝑒𝐷𝑒𝑛𝑡𝑒(_ , _) sarà distinto da 𝐿𝑒𝑠𝑖𝑜𝑛𝑒(_ , _) e che 𝐵𝑎𝑙𝑒𝑛𝑎(_) è distinto da 𝐶𝑒𝑡𝑎𝑐𝑒𝑜(_), per cui bisogna introdurre altri predicati per fare in modo che si possa realizzare una corrispondenza che il Modus Ponens possa sfruttare per realizzare le inferenze. In particolare, occorrono due formule simili del tipo:

• “Le lesioni ai denti sono lesioni.”

∀𝑥 𝐿𝑒𝑠𝑖𝑜𝑛𝑒𝐷𝑒𝑛𝑡𝑒(𝑥) ⇒ 𝐿𝑒𝑠𝑖𝑜𝑛𝑒(𝑥)

• “Le balene sono cetacei.”