Home » Intelligenza Artificiale » 📋 URL
La logica proposizionale è la tipologia più semplice di logica. Tratta soltanto proposizioni atomiche e permette le seguenti operazioni:
- Negazione: \neg
- Congiunzione (AND): \wedge
- Disgiunzione (OR): \vee
- Implicazione: \Rightarrow
- Bicondizionale: \iff
Nota bene: l’ordine di precedenza degli operatori è dall’alto verso il basso.
Per esempio, applicando al mondo del Wumups tale notazione, si avrebbe
Dove possiamo indicare tramite P_{i,j}=\text{Vero} se c’è una buca (pit) nel quadrato [i,\,j], mentre utilizziamo B_{i,j}=\text{Vero} se c’è brezza nel quadrato [i,\,j].
Utilizzando tale notazione possiamo indicare le seguenti relazioni:
- \neg P_{1,1}: non c’è una bula nella casella [1,\,1]
- B_{1,1} \iff (P_{1,2} \vee P_{2,1}): nella casella [1,\,1] si sente la brezza se è presente una buca nelle caselle di fianco
- B_{2,1} \iff (P_{1,1}\vee P_{2,2} \vee P_{3,1}): la casella [2,\,1] ha tre altri quadrati adiacenti, dunque in essa si sente la brezza se in uno degli altri quadrati c’è una buca
- \neg B_{1,1}: per indicare che non c’è brezza nella casella [1,\,1]
- B_{2,1}: per indicare che non c’è brezza nella casella [2,\,1]
Possiamo inoltre trasformare i diversi operatori in altri tramite l’algebra delle proposizioni equivalenti riportata di seguito:
La forma CNF (Conjunctive normale form)
Per poter applicare le regole dell’inferenza per la logica proposizionale abbiamo bisogno di esprimere le proposizioni in forma normale congiuntiva, ovvero CNF (Conjunctive normale form).
Una frase in CNF è composta da congiunzioni di disgiunzioni, ovvero AND di OR.
\underbrace{\underbrace{(A\vee\neg B)}_{\text{clausola}}\wedge\underbrace{(B\vee\neg C\vee\neg D)}_{\text{clausola}}}_{\displaystyle\text{CNF}}Per esempio, utilizzando le traduzioni riportate nella tabella precedente, possiamo tradurre l’informazione B_{1,1} \textcolor{00ffa1}{\iff} (P_{1,2} \vee P_{2,1}) come:
- Eliminiamo \iff utilizzando le equivalenze in tabella
B_{1,1}\textcolor{00ffa1}{\Rightarrow} (P_{1,2} \vee P_{2,1}) \wedge ((P_{1,2}\vee P_{2,1})\textcolor{00ffa1}{\Rightarrow} B_{1,1}) - Eliminiamo \Rightarrow
(\neg B_{1,1} \vee P_{1,2} \vee P_{2,1} \wedge (\textcolor{00ffa1}{\neg}(P_{1,2} \vee P_{2,1}) \vee B_{1,1}) - Portiamo dentro la parentesi il \neg
(\neg B_{1,1}\vee P_{1,2} \vee P_{2,1}) \wedge ((\neg P_{1,2}\textcolor{00ffa1}{\wedge} \neg P_{2,1})\textcolor{00ffa1}{\vee} B_{1,1} - Distribuendo \vee su \wedge
(\neg B_{1,1} \vee P_{1,2} \vee P_{2,1}) \wedge (\neg P_{1,2} \vee B_{1,1}) \wedge (\neg P_{2,1} \vee B_{1,1})
Inferenza per la logica proposizionale
Chiamiamo resolution la tecnica per produrre nuove proposizioni partendo da due o più clausole che contengono dei literal complementari (ovvero, ad esempio, è necessario che le clausole contengano sia c che \neg c).
Esempio: consideriamo la seguente espressione
\dfrac{a\vee b,\quad\neg a\vee c}{a\vee c}\leftarrow\text{linea di ``entails"}Dobbiamo trovare dei valori per a,\,b e c che rendano vera l’espressione, ovvero che tramite le espressioni al numeratore otteniamo sempre l’espressione al denominatore, ovvero che il numeratore “entails” il denominatore.
Notiamo subito che per ottenere a\vee c=\text{vero} è sufficiente avere c=\text{vero} per qualunque valore di a.
In questo modo l’espressione \neg a\vee c sarà a sua volta sempre vera per qualunque valore di a.
In maniera simile, se poniamo b=\text{vero} si verificano tutte le tre condizioni.
Esercizio: porre b=c=\text{vero} e a=\text{qualunque} è l’unico modo perché l’espressione proposta sia verificata? Giustificare la propria risposta.
Soluzione
No: si provi per esempio a porre a=\text{vero},\,b=\text{falso} e c=\text{vero} oppure a=\text{falso},\,b=\text{vero} e c=\text{falso} per averne la conferma.
Esercizio: dopo aver espresso B_{1,1} \iff (P_{1,2} \vee P_{2,1}) in CNF (già svolto in un esempio precedente), controllare se da tale informazione è possibile ottenere il valore \alpha=\neg P_{1,\,1}.
Soluzione
L’espressione in forma CNF da studiare è la seguente
(\neg P_{2,\,1}\vee B_{1,\,1})\wedge(\neg B_{1,\,1}\vee P_{1,\,2}\vee P_{2,\,1})\wedge(\neg P_{1,\,2}\vee B_{1,\,1})\wedge(\neg B_{1,\,1})\quad\quad\alpha=\neg P_{1,\,2}Dobbiamo dunque mettere “a sistema” le varie condizioni per ottenere
\begin{aligned}
&1)\quad\neg P_{2,1}\vee B_{1,1}\\
&2)\quad\neg B_{1,1}\vee P_{1,2}\vee P_{2,1}\\
&3)\quad\neg P_{1,2}\vee B_{1,1}\\
&4)\quad\neg B_{1,1}\\
&5)\quad P_{1,2}\equiv\neg\alpha\\
&\,\,\textcolor{00ffa1}{\text{uniamo le righe 3 e 4}}\\
&6)\quad\neg P_{1,2}\\
&\,\,\textcolor{00ffa1}{\text{uniamo le righe 5 e 6}}\\
&7)\quad\emptyset
\end{aligned}Poiché non c’è soluzione per \text{KB}\wedge\neg\alpha, (lo indichiamo tramite l’insieme vuoto) l’affermazione \text{KB}\wedge P_{1,2} è assurda, dunque falsa. Se P_{1,2} è falsa l’unica possibilità è che
\neg P_{1,\,2}=\text{vero}che conclude dunque il nostro compito: abbiamo dimostrato che dall’informazione di partenza non si può ottenere il valore di \alpha, e per farlo abbiamo utilizzato una dimostrazione per assurdo, che ci permesso di evidenziare l’inconsistenza del problema posto in origine.
In poche parole
✅ La logica proposizionale è la forma più semplice di logica, che si occupa delle proposizioni atomiche e dei loro operatori logici come la negazione, la congiunzione, la disgiunzione, l’implicazione e il bicondizionale.
✅ La forma normale congiuntiva (CNF) rappresenta le proposizioni come congiunzioni di disgiunzioni.
✅ La tecnica della resolution è un metodo di inferenza per la logica proposizionale.