Soluzionedellaprovadel29gennaio2019

Page 1

SOLUZIONE DELLA PROVA DEL 29/1/2019 Esercizio 1 Introduciamo delle lettere enunciative per indicare le proposizioni atomiche: A: “La verdura è trasportata” B: “La verdura è venduta” C: “La verdura è immagazzinata” Allora le premesse si traducono nel seguente modo: (a) A  B (b) ~ A  B  C (c) C  B mentre la negazione di (d) corrisponde a ~ B. Scriviamo le formule in forma a clausole: (a) A  B ≡ ~ A  B (b) ~ A  B  C ≡ A  B  C (c) C  B ≡ ~ C  B pertanto si ottengono le clausole C1 = {~ A, B }, C2 = {A, B, C}, C3 = {~ C, B}, C4 = {~ B}. Dalla teoria è noto che dalle premesse (a), (b), (c) si deduce la tesi (d) se e solo se l’insieme {A  B, ~ A  B  C, C  B, ~ B} è insoddisfacibile e quindi se e solo se { C1, C2, C3, C4}|-R □. Una derivazione per risoluzione della clausola vuota è la seguente: (I) C1 = {~ A, B } (clausola di input) (II) C4 = {~ B} (clausola di input) (III) C5 = {~ A} (risolvente di C1 e C4) (IV) C2 = {A, B, C} (clausola di input) (V) C6 = { B, C} (risolvente di C5 e C2) (VI) C7 = {C} (risolvente di C4 e C6) (VII) C3 = {~ C, B} (clausola di input) (VIII) C8 = {B} (risolvente di C7 e C3) (IX) □ (risolvente di C4 e C3) Avendo ottenuto la clausola vuota si può concludere che (d) si deduce dalle premesse (a), (b), (c). Esercizio 2 (a) R non è seriale in quanto non esiste alcun elemento y ∊ X tale che (3, y) ∊ R. R non è riflessiva in quanto, ad esempio, (1, 1)  R. R non è simmetrica in quanto, ad esempio, (1, 4) ∊ R ma (4, 1)  R. R è antisimmetrica in quanto, per ogni y, z ∊ X, se (y, z) ∊ R allora (z, y)  R. R non è transitiva in quanto, ad esempio, (1, 4) ∊ R, (4, 5) ∊ R ma (1, 5)  R. (b) Poiché R è antisimmetrica, potrebbe esistere la chiusura d’ordine di R. La chiusura riflessiva e transitiva T di R è T = R  {(1,1), (3,3), (1,5), (4,3)} ed…