Esercizio - Logica proposizionale e logica del primo ordine a confronto (esempio d'esame 1)

Teoria: Agenti logici e logica proposizionale - inferenza e risoluzioneAgenti basati sulla conoscenza (KB, Tell e Ask), mondo del Wumpus come banco di prova, sintassi e semantica della logica proposizionale, conseguenza logica, equivalenze, inferenza per model checking (7 simboli, 128 modelli, 3 modelli della KB) e per risoluzione (CNF, regola di risoluzione, dimostrazione per assurdo). Limite: poca espressività, da cui la logica del primo ordine.Agenti logici e logica proposizionale - inferenza e risoluzione → e Logica del primo ordine - unificazione, forward e backward chainingLogica del primo ordine (oggetti, relazioni, funzioni, quantificatori e errori tipici), sostituzioni, istanziazione universale ed esistenziale (Skolem), proposizionalizzazione e suoi limiti, unificazione con occur check, risoluzione nel primo ordine con conversione in CNF, esempio Criminal(West), clausole definite, forward e backward chaining, ingegneria della conoscenza.Logica del primo ordine - unificazione, forward e backward chaining →. Domanda 7 del quiz da 9 CFU (la logica non è nel programma da 6 CFU).

Testo (risposta aperta). Spiegare le principali differenze, con vantaggi e svantaggi, tra logica proposizionale (propositional logic) e logica del primo ordine (first order logic), includendo un esempio per ognuna di esse.

Risposta modello

Logica proposizionale. Il mondo è fatto solo di fatti: simboli atomici veri o falsi ($P$, $Q$) combinati con $\neg,\land,\lor,\Rightarrow,\Leftrightarrow$. Esempio, mondo del Wumpus: $\neg B_{1,1}\Rightarrow(\neg P_{1,2}\land\neg P_{2,1})$, dove $B_{x,y}$ vale "c'è brezza in $[x,y]$" e $P_{x,y}$ "c'è un pozzo in $[x,y]$".

• Vantaggi: semantica semplice (tavole di verità, modelli); linguaggio dichiarativo e composizionale; inferenza completa e decidibile (i modelli sono finiti: model checking, risoluzione); ammette informazione parziale o disgiuntiva.
• Svantaggi: espressività molto limitata. Non ci sono oggetti, relazioni né quantificatori, quindi una regola generale va ripetuta per ogni caso: "i pozzi causano brezza nelle caselle adiacenti" richiede un enunciato per ciascuna delle 16 caselle di un mondo $4\times4$, e le formule crescono con il mondo.

Logica del primo ordine. Il mondo contiene oggetti, relazioni e funzioni; si hanno costanti, variabili, predicati, funzioni, uguaglianza e i quantificatori $\forall,\exists$. Esempio: $\forall s\ \big(Breezy(s)\Leftrightarrow\exists r\ (Adjacent(r,s)\land Pit(r))\big)$: una sola formula vale per ogni casella e per mondi di qualunque dimensione. Oppure: $\forall x\ (Man(x)\Rightarrow Mortal(x))$, $Man(Socrates)$, quindi $Mortal(Socrates)$.

• Vantaggi: molto più espressiva e concisa, vicina al linguaggio naturale; permette di parlare di tutti gli oggetti o di qualcuno senza nominarli; è il linguaggio di Prolog (clausole di Horn), sistemi esperti e basi di conoscenza.
• Svantaggi: l'inferenza è più complessa (serve l'unificazione; la proposizionalizzazione può generare infinite istanze se ci sono funzioni) e solo semidecidibile: se $KB\models\alpha$ un algoritmo lo dimostra, se non è conseguenza può non terminare. Inoltre non rappresenta l'incertezza (serve la probabilità) e modellare un dominio richiede ingegneria della conoscenza.

Sintesi. La proposizionale è semplice e decidibile ma poco espressiva; la FOL è espressiva e compatta ma con inferenza più costosa e semidecidibile.

Errori tipici nella risposta: dire che la proposizionale non può rappresentare nessuna regola generale (può, ma una per caso); dire che la FOL è decidibile; dimenticare gli esempi o i quantificatori.