Appello Febbraio 2021

Sia data la seguente descrizione (parziale) del funzionamento di un sistema operativo:

1. Se il sistema sta funzionando normalmente, il kernel sta funzionando.
2. Delle due l’una: o il kernel non sta funzionando o il sistema è in modo interrupt.

Utilizzando le seguenti lettere proposizionali:

1. SYSTEM_OK, vera se il sistema sta funzionando normalmente
2. KERNEL_OK, vera se il kernel sta funzionando
3. INTERRUPT_MODE, vera se il sistema è in modo interrupt

Dire quali dei seguenti insiemi di assiomi modellano il dominio informale descritto sopra:

1. [SI]
   1. SYSTEM_OK imp KERNEL_OK
   2. (not KERNEL_OK or INTERRUPT_MODE) and not (not KERNEL_OK and INTERRUPT_MODE)
2. [SI]
   1. SYSTEM_OK imp KERNEL_OK
   2. not (KERNEL_OK and not INTERRUPT_MODE) and not (not KERNEL_OK and INTERRUPT_MODE)
3. 1. not SYSTEM_OK imp not KERNEL_OK
   2. (not KERNEL_OK or INTERRUPT_MODE) and not (not KERNEL_OK and INTERRUPT_MODE)
4. 1. KERNEL_OK imp SYSTEM_OK
   2. not (KERNEL_OK and not INTERRUPT_MODE) and not (not KERNEL_OK and INTERRUPT_MODE)
5. 1. KERNEL_OK iff SYSTEM_OK
   2. (not KERNEL_OK or INTERRUPT_MODE) or not (not KERNEL_OK and INTERRUPT_MODE)
6. Nessuna

Data la formula:

\(\alpha = (\neg A \vee \neg B)\)

e la formula:

\(\beta = (A \vee C)\)

usando le tabelle di verità, dire se:

1. [SI] \(\alpha \vee \beta\) è valida
2. [SI] \(\alpha \supset \beta\) è vera per la seguente assegnazione \(I(A) = F\), \(I(B) = F\), \(I(C) = V\)
3. \(\alpha\) è conseguenza logica di \(\beta\)
4. \(\alpha\) è logicamente equivalente a \(\beta\)
5. \(\alpha \supset \beta\) è insoddisfacibile
6. \(\alpha \supset \beta\) è vera per la seguente assegnazione \(I(A) = V\), \(I(B) = F\), \(I(C) = V\)

Si consideri l’algoritmo decisionale DPLL. Rispondere alle seguenti domande:

1. [SI] Un qualunque problema decisionale della logica proposizionale può essere risolto usando DPLL
2. [SI] Durante l’esecuzione di DPLL, l’euristica di Unit Propagation si applica quando esiste almeno una clausola che contiene un solo letterale
3. [SI] Una formula A è insoddisfacibile se per qualsiasi assegnazione di verità ai letterali di A, DPLL riduce una delle clausole di A nella clausola vuota, cioè {}
4. [SI] Una formula A è soddisfacibile se esiste un’assegnazione di valori di verità dei letterali di A per la quale DPLL applicato ad A ritorna la clausola vuota, cioè {}
5. [SI] DPLL ritorna l’insieme dei letterali che se, resi veri, rendono la formula in input vera
6. [SI] Una formula \(\neg A\) è valida se DPLL, per qualsiasi assegnazione di verità ai letterali di A, riduce una delle clausole di A nella clausola vuota, cioè {}
7. DPLL prende in input una formula proposizionale qualunque
8. DPLL assegna un valore di verità a tutti i letterali che occorrono nella formula in input
9. Il tempo di esecuzione di DPLL cresce esponenzialmente con la lunghezza della formula
10. In DPLL UnitPropagation non viene mai applicata dopo l’applicazione di una SPLIT rule

Una famosa canzone di Adriano Celentano si intitolava “Chi non lavora, non fa l’amore”, da intendersi nel seguito come “Tutti quelli che non lavorano non fanno l’amore con nessuno”. Come formalizzereste il titolo in logica del primo ordine, avendo a disposizione le lettere predicative di arità 1 \(Lavora\) e la lettera predicativa \(FaAmore\) di arità 2.

1. [SI] \(\forall x. (\neg Lavora(x) \supset \neg \exists y. FaAmore(x, y))\)
2. [SI] \(\forall x. \forall y. (\neg Lavora(x) \supset \neg FaAmore(x, y))\)
3. [SI] \(\forall x. (\exists y. FaAmore(x, y)) \supset Lavora(x))\)
4. \(\forall x. (\neg Lavora(x) \supset \exists y. \neg FaAmore(x, y))\)
5. \(\exists x. (\neg Lavora(x) \supset \forall y. \neg FaAmore(x, y))\)
6. \(\exists x. (\neg Lavora(x) \supset \neg \forall y. FaAmore(x, y))\)

Sia L un linguaggio del primo ordine ed M = (D,I) un’interpretazione di L.

L’alfabeto di L sia costruito utilizzando i seguenti simboli (dove per {a,b} si intende l’insieme degli elementi a, b):

Costanti = { Mario, Maria, Marina, Enrico }

dove le costanti sono da intendersi come i nomi delle persone rappresentate nel dominio di interpretazione.

Funzioni = { padre-di }

dove “padre-di” ha arità 1.

Predicati= {donna, uomo}

dove “donna”, “uomo” hanno arità 1.

Sia:

D = {n | n è n numero naturale e n < 100}.

Sia I definita come segue:

• I(Mario) = 1
• I(Maria) = 2
• I(Marina) = 3
• I(Enrico) = 3
• I(padre-di) = { (1, 2) }, dove il primo elemento della coppia è il dominio di padre-di
• I(uomo) = { n \(\in\) D | n è un numero naturale dispari}
• I(donna) = { n \(\in\) D | n è un numero naturale pari}

Dire quale delle seguenti affermazioni sono vere:

1. [SI] Marina è un uomo
2. [SI] La formula forall x. (uomo(x) iff not donna(x)) è vera in M
3. [SI] Gli elementi del dominio D sono in numero finito
4. La persona con nome Enrico ha un solo nome
5. uomo(padre-di(Mario)) è vero nel modello
6. I termini ben formati in L sono in numero finito

Utilizzare il metodo del Tableau per verificare se la seguente formula è …

\(\forall y (P(y) \wedge Q(y)) \supset \exists x (\neg Q(x) \supset P(x))\)

1. [SI] Valida
2. Soddisfacibile
3. Insoddisfacibile
4. Nessuna delle precedenti

Si consideri il seguente frame

F = < W, R >

dove:

• W = { 1, 2, 3, 4}
• R = { (1,1), (1,2), (1,3), (1,4), (3,4), (2,4), (4,4) }

Sia data la seguente funzione di interpretazione

• I(A) = { 1, 4 }
• I(B) = { 2, 3, 4 }

Dire quali delle seguenti affermazioni sono vere:

1. [SI] \(F \models A \supset (B \vee \square A)\)
2. [SI] \(F \models \neg B \vee \square B\)
3. [SI] \(F \models A \vee \diamond B\)
4. [SI] \(F \models \diamond \, \square A\)
5. \(F \models A \supset \square A\)
6. \(F \models \square (A \supset B)\)

Sia MML una logica multimodale con \(N\) operatori \(\square_i\) modali distinti. dire quale dei seguenti fatti sono veri

1. [SI] I frame F in cui viene interpretata MML sono costituiti da un insieme di mondi \(W\) e \(N\) relazioni di accessibilità distinte, \(R_1\), …, \(R_n\)
2. [SI] Per ogni modalità \(\square_i\), vale “\(\square_i(A \supset B) \supset (\square_i A \supset \square_i B)\)”
3. [SI] La credenza \(\square_i\) di un agente \(a_i\) può essere assiomatizzata tramite gli assiomi k45d
4. [SI] \(\square_i (A \wedge \neg A)\) può essere parte di una teoria consistente che assiomatizza le credenze dell’agente \(a_i\).
5. I frame F in cui viene interpretata MML sono costituiti da \(N\) insiemi di mondi \(W_1\), …, \(W_n\), uno per ciascuna relazione di accessibilità, e \(N\) relazioni di accessibilità distinte, \(R_1, \ldots, R_n\).
6. Siano \(R_i\), \(R_j\) le relazioni di accessibilità associate a \(\square_i\), \(\square_j\) in un frame \(F\). Allora vale il seguente fatto: se \(R_i \subseteq R_j\) allora \(F \models \diamond_j A \supset \diamond_i A\), per tutte le formule \(A\)
7. Siano \(\square_i\) e \(\square_j\) le due modalità che formalizzano le credenze di due agenti \(a_i\) e \(a_j\) in MML interpretata nel frame \(F\). Allora le relazioni di accessibilita \(R_i\) e \(R_j\) in \(F\) associate a \(\square_i\) e \(\square_j\) devono entrambe soddisfare gli stessi assiomi modali

Sia \(T\) una terminologia in Description Logics scritta in un linguaggio \(L\). Sia \(I\) una funzione di interpretazione per \(T\) con dominio di interpretazione \(D\). Siano \(C\), $$C_1$ e \(C_2\) tre formule in \(T\).

Quali delle seguenti affermazioni sono vere:

1. [SI] se \(T \not\models C_1\) allora \(T \models C_1 \sqsubseteq C_2\) per ogni formula \(C_2\)
2. [SI] \(I(\exists R. True) = \{ a \in D | \mbox{ esiste } b \mbox{ tale che } (a,b) \in I(R) \}\)
3. \(I(C_1 \sqcap C_2) = True\) se e solo se \(I(C_1)= True\) e \(I(C_2)= True\)
4. \(T \models C\) se esiste una interpretazione \(I\) tale che \(I \models C_i\) per tutti i \(C_i \in T\) e \(I(C) = True\)