Esercizio - Tabelle di verità, equivalenze e model checking (slide del corso)

Punto 1: De Morgan e implicazione

Le due variabili danno $2^2 = 4$ righe. Si calcola ogni colonna dalla definizione dei connettivi.

• Le colonne $\neg(P \land Q)$ e $\neg P \lor \neg Q$ sono uguali riga per riga: equivalenti. Lo stesso per $\neg(P \lor Q)$ e $\neg P \land \neg Q$.
• $P \Rightarrow Q$ e $Q \Rightarrow P$ differiscono nelle righe $2$ e $3$: non equivalenti. L'implicazione non è simmetrica.

Punto 2: validità

Sillogismo ipotetico $((P \Rightarrow Q) \land (Q \Rightarrow R)) \Rightarrow (P \Rightarrow R)$. Una formula $A \Rightarrow B$ è falsa solo se $A$ è vera e $B$ falsa. Qui $P \Rightarrow R$ falsa richiede $P$ vero e $R$ falso. Con $P$ vero, $P \Rightarrow Q$ vera richiede $Q$ vero; ma con $Q$ vero e $R$ falso $Q \Rightarrow R$ è falsa, quindi l'antecedente non è vero. Non esiste riga falsa: la formula è valida (controllate tutte le $8$ righe).

Affermazione del conseguente $(Q \land (P \Rightarrow Q)) \Rightarrow P$. Con $P$ falso e $Q$ vero: $Q$ vero, $P \Rightarrow Q$ vero (antecedente falso), quindi l'antecedente è vero e il conseguente $P$ è falso. La formula è falsa in quel modello: non valida (è il ragionamento sbagliato "piove implica pavimento bagnato, il pavimento è bagnato, dunque piove").

Punto 3: model checking sulla KB del Wumpus

I simboli sono $7$ ($B_{1,1}, B_{2,1}, P_{1,1}, P_{1,2}, P_{2,1}, P_{2,2}, P_{3,1}$): $2^7 = 128$ modelli. Si scrive la KB come funzione e si enumerano.

from itertools import product
syms = ["B11", "B21", "P11", "P12", "P21", "P22", "P31"]

def kb(m):
    return (not m["P11"]                                        # R1
            and m["B11"] == (m["P12"] or m["P21"])              # R2
            and m["B21"] == (m["P11"] or m["P22"] or m["P31"])  # R3
            and not m["B11"] and m["B21"])                      # R4, R5

modelli = [dict(zip(syms, v)) for v in product([False, True], repeat=7)]
buoni = [m for m in modelli if kb(m)]
print(len(modelli), len(buoni))                       # 128 3
print(all(not m["P12"] for m in buoni))               # True
print(all(not m["P22"] for m in buoni))               # False

Output atteso: 128 3, True, False. I $3$ modelli della KB si trovano anche a mano (vedi la nota): $B_{1,1}$, $P_{1,1}$, $P_{1,2}$, $P_{2,1}$ falsi, $B_{2,1}$ vero, e $(P_{2,2}, P_{3,1}) \in \{(0,1), (1,0), (1,1)\}$.

• $P_{1,2}$ è falso nei $3$ modelli: $KB \models \neg P_{1,2}$, sì.
• $P_{2,2}$ è vero nel secondo e nel terzo: $KB \models \neg P_{2,2}$, no.

L'agente può quindi andare in $[1,2]$ senza rischio, ma non può escludere un pozzo in $[2,2]$ né in $[3,1]$.