[A/L] (2021/22) Logica - Esercizio 9

[matypist]

[Elia-Belli]

Abbiamo come ipotesi $A \notin UNSAT \Rightarrow A \in SAT$
"esiste $B \notin UNSAT$ tale che $B \models A \land \lnot(A \models B)$" vuol dire che "Esiste $B \in SAT$ tale che $B \models A \land \lnot(A \models B) \in SAT$ "

Possiamo riscrivere $B \models A \land \lnot(A \models B) \in SAT$ come $(\lnot B \lor A) \land \lnot(\lnot A \lor B) \in SAT = (\lnot B \lor A) \land (A \land \lnot B) \in SAT$

Se $A,B \in SAT$ sappiamo che esiste almeno un assegnamento che le rende vere: quindi per soddisfare la proposizione precedente possiamo prendere $A = 1 \land B = 0$.

Osservazione: $B \notin UNSAT$ è condizione sufficiente affinchè $B \in SAT$ ma non esclude che $B \in TAUT$, nell'esercizio abbiamo preso $B = 0$ ma se fosse stata una Tautologia la proposizione non sarebbe stata soddisfacibile.

[Colasuonno]

@Elia-Belli Ho un dubbio, quando la traccia chiede, esiste un B non in SAT.... se troviamo un valore di B (anche 0) per il quale vale la premessa la condizione è verificata giusto? Più generalmente indipendentemente dal valore di un letterale (0 o 1) quel letterale può essere in SAT o UNSAT, dipende tutto dall'ipotesi

[Elia-Belli]

@Elia-Belli Ho un dubbio, quando la traccia chiede, esiste un B non in SAT.... se troviamo un valore di B (anche 0) per il quale vale la premessa la condizione è verificata giusto? Più generalmente indipendentemente dal valore di un letterale (0 o 1) quel letterale può essere in SAT o UNSAT, dipende tutto dall'ipotesi

Si, non è importante il valore del literal affinchè sia $SAT$, ad esempio la proposizione $\bar q$ è $SAT$ per $q=0$.
Comunque attento, la traccia dice "esiste B non in UNSAT" cioè "esiste B in SAT".

[CiottoloMaggico]