Compito CL - Seconda Prova

Testo Compito

Domanda 1. ML: Informal to Formal (3pt)

Si consideri la seguente frase:

Non è possibile che, se Socrate è un uomo e gli uomini sono mortali, allora Socrate sia immortale.

Immaginando di utilizzare le seguenti lettere proposizionali:

SU = SocrateUomo, vera se Socrate è un uomo
UM = UominiMortali, vera se tutti gli uomini sono mortali
SM = SocrateMortale, vera se Socrate è mortale

indicare quele delle seguenti sono formalizzazioni corrette:

(33%) ¬ ⋄ (SU ∧ UM ⊃ ¬ SM)
(33%) □ ¬ (SU ∧ UM ⊃ ¬ SM)
(33%) □ (SU ∧ UM ∧ SM)
(-25%) ¬ ⋄ (SU ∧ UM) ⊃ ¬ ⋄ (¬ SM)
(-25%) □ (SU ∧ UM) ⊃ ⋄ (¬ SM)
(-25%) ¬ (⋄ (SU ∧ UM)) ⊃ ⋄ (¬ SM)

Domanda 2. ML: Proprietà Frame (4pt)

Si consideri il seguente frame

\[F = < W, R >\]

dove:

W = N, l’insieme dei numeri naturali
R = { (i,i+1) | i ∈ N and i >= 1 }

Si consideri una formula atomica \(\phi\) per cui vale la seguente proprietà:

I(ϕ) = { i | per ogni i dispari }

Dire quali delle seguenti affermazioni sono vere:

(33%) F ⊨ ϕ ⊃ □ ¬ ϕ
(33%) F ⊨ ¬ ϕ ⊃ □ ϕ
(33%) F ⊨ □ (¬ ϕ ⊃ ⋄ ϕ)
(-25%) F ⊨ □ □ ϕ
(-25%) F ⊨ ϕ ∧ □ ¬ ϕ
(-25%) F ⊨ ¬ (□ ϕ ∨ ¬ □ ϕ)

Domanda 3. ML: Teoria su Formule Modali (3pt)

Una formula A è valida

(25%) in un mondo w, se e solo se M , w ⊨ A per ogni I , con w ∈ W, F = <W, R> e M = <F,I>
(25%) nella classe dei frame seriali C, se e solo se F ⊨ A per ogni F = <W, R> e, per ogni w ∈ W, esiste w ′ tale che R(w, w′)
(25%) nella classe dei frame riflessivi C, se A è nella forma B ⊃ ⋄ B
(25%) nella classe dei frame simmetrici C, se A è nella forma B ⊃ □ ¬ □ ¬ B

Domanda 4. ML: Esercizio di soddisfacibilità di formula modale in frame (4pt)

Sia dato il frame F come nella seguente figura, in cui ogni nodo rappresenta un mondo, gli archi relazioni di accessibilità tra mondi e, in ogni mondo, ad esempio w1, viene riportato l’elenco delle formule vere nel mondo, ad es, A, B:

La formula C= ⋄ □ (A ∧ B) è tale per cui:

(50%) w2 ⊨ ¬ C
(50%) w3 ⊨ C
(-25%) F ⊨ ¬ ¬ C
(-25%) w1 ⊨ ¬ C

[Suggerimento: testate la soddisfacibilità di C nei tre casi (w1, w2, w3), un mondo alla volta, verificando ogni volta se C è vera in quel mondo.]

Domanda 5. ML: Tableaux (4pt)

Usando il metodo del Tableau, dire se la seguente formula è valida, soddisfacibile, insoddisfacibile.

¬ □ (⋄(A ∨ B) ⊃ ⋄ (¬ A ∧ ¬ B))

(100%) Soddisfacibile
(-25%) Valida
(-25%) Insoddisfacibile

Soluzione (Deduction)

¬ □ (⋄ (A ∨ B) ⊃ ⋄ (¬ A ∧ ¬ B))
¬ □ (⋄ (A ∨ B) ⊃ ⋄ (¬ (A ∨ B)))
⋄ ¬ (⋄ (A ∨ B) ⊃ ⋄ (¬ (A ∨ B)))
⋄ (⋄ (A ∨ B) ∧ (¬ ⋄ (¬ (A ∨ B))))
⋄ (⋄ (A ∨ B) ∧ □ (A ∨ B))
⋄ (⋄ P ∧ □ P)

Soluzione (Tableau)

alpha = DIAMOND (A OR B)
beta = DIAMOND (NOT A AND NOT B)

w |= NOT (BOX (alpha IMP beta))
|
w |/= BOX (alpha IMP beta)
|
wRw'
w' |/= alpha IMP beta
|
w' |= alpha  [DIAMOND (A or B)]
w' |/= beta  [DIAMOND (not A and not B)]
|
w'Rw''
w'' |= (A or B)
|
|
w'' |/= (not A and not B)
|
-----------------------------------------
w'' |= A                         w'' |= B

Domanda 6. DL: Informal to Formal (4pt)

Quale o quali delle seguenti formalizzazioni in DL sono compatibili con lo Schema Knowledge Graph (SKG) ed il Data Knowledge Graph (DKG) dati in figura?

Si noti che nel Data Knowledge Graph, il testo tra parentesi quadre indica la classe dell’istanza. Ad esempio “[balena] Willy” significa che Willy è una balena.

(100%)

TBOX = {
   balena ⊑ mammifero
   mammifero ⊑ animale
   […]
}
ABOX = {
   balena(Willy)
   vive_in(Willy, OceanoPacifico)
   […]
}
(-25%)

TBOX = {
  balena ⊑ mammifero ⊓ leone
  mammifero ⊑ animale
  […]
}
ABOX = {
  balena(Willy)
  […]
}
(-25%)

TBOX = {
   balena ⊑ mammifero
   mammifero ⊑ animale
   vive_in(Simba, Africa)
   […]
}
ABOX = {
  balena(Willy)
  vive_in(Willy, OceanoPacifico)
  […]
}
(-25%)

TBOX = {
  mammifero ⊑ balena ⊔ leone
  mammifero ⊑ animale
  […]
}
ABOX = {
  balena(Willy)
  […]
}

Domanda 7. DL: Mapping tra SKG e DKG (4pt)

Dati lo Schema Knowledge Graph (SKG) e il Data Knowledge Graph (DKG) in figura, quali delle seguenti affermazioni sono vere?

(Ricordiamo che si dice che una teoria è consistente se e solo se è soddisfacibile.)

(33%) Il Data Knowledge Graph è consistente con lo Schema Knowledge Graph
(33%) Se uno aggiunge nella TBOX l’assioma Disjoint(Man, Woman), il DKG è consistente con lo SKG
(33%) Se uno aggiunge nella ABOX l’asserzione ¬MotherOf(Mary,Fred) il DKG è consistente con lo SKG
(-25%) Se uno aggiunge nella ABOX l’asserzione ¬MotherOf(Mary,Fred) il DKG è consistente
(-25%) Il Data Knowledge Graph non è consistente

Domanda 8. DL: Domanda Teorica (TBOX/ABOX) (3pt)

Data una TBOX T e due formule P, Q, quali delle seguenti affermazioni sono vere?

(33%) P e Q sono soddisfacibili rispetto a T sse T ⊨ P ∧ Q
(33%) Disjointness (P,Q) implica ¬ ( P ⊑ Q )
(33%) Disjointness (P,Q) implica ¬ (Q ⊑ P ⊔ P ⊑ Q)
(-25%) ( P ⊑ Q) implica Disjointness (P, Q)
(-25%) Disjointness (P,Q) implica P ⊑ Q
(-25%) Disjointness (P,Q) se e solo se ¬ ( Q ⊑ P ⊔ P ⊑ Q)

Domanda 9. DL: Domanda Teorica/Generale (3pt)

Di seguito scriviamo CWA per significare Closed World Assumption and OWA per significare Open World Assumption. Si considerino la seguente TBOX ed ABOX:

TBOX = { A ⊑ B }

ABOX = { A(u1), C(u2) }

Dire quali delle seguenti affermazioni sono vere:

(33%) B(u1) può essere dedotto seguendo la regola della OWA applicata alla ABOX
(33%) ogni formula derivabile applicando la OWA può essere derivata applicando anche la CWA
(33%) not B(u2) (attenzione: u2!) può essere dedotto seguendo la regola della CWA applicata alla ABOX
(-25%) ogni formula derivabile applicando la CWA può essere derivata applicando anche la OWA
(-25%) not B(u1) può essere dedotto seguendo la regola dell OWA applicata alla ABOX

Domanda 10. DL: Espansione di ABOX in TBOX (4pt)

Data la seguente teoria:

TBOX = {
  A ≡ B ⊓ C
  C ≡ D ⊓ E
  E \(\sqsubseteq\) F ⊓ G
}
ABOX {
  A(1)
}

Espandere ABOX nella TBOX, ricordando che l’espansione contiene esclusivamente concetti primitivi e decidere quali di queste affermazioni sono vere.

(100%)

B(1)
D(1)
F(1)
G(1)

(-25%) (simboli primitivi)

A(1)
C(1)
E(1)

(-25%)

B(1)
D(1)
F(1) ⊔ G(1)

(-25%)

B(1) ⊓ C(1)
D(1) ⊓ E(1)
F(1) ⊓ G(1)