Computer Engineering - Logica e Algebra

Full exam

SOLUZIONE DELLA PROVA DEL 29/1/2019 Esercizio 1 Introduciamo delle lettere enunciative per indicare le proposizioni atomiche: A: “La ve rdura è trasportata ” B: “La verdura è venduta” C: “La verdura è immagazzinata” Allora le premesse si traducono nel segue nte 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 C 1 = {~ A, B }, C 2 = {A, B, C}, C 3 = {~ C, B}, C 4 = {~ 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 C 4) (IV) C2 = {A, B, C} (clausola di input) (V) C6 = { B, C} (risolvente di C 5 e C 2) (VI) C7 = {C} (risolvente di C 4 e C 6) (VII) C3 = {~ C, B} (clausola di input) (VIII) C8 = {B} (risolvente di C 7 e C 3) (IX) □ (risolvente di C 4 e C 3) Avendo ottenuto la clausola vuota si può c oncludere 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 e ssendo T ancora una relazione antisimmetrica si ha che T coincide con la chiusura d’ordi ne di R . T ha come diagramma di Hasse quello rappresentato a lato . Esiste un unico elemento massimale, 3, che quindi è anche massimo ed un unico elemento minimale, 1, che quindi è anche minimo. Risulta che Inf{2, 5} = 1 e Sup{2, 3} = 3. (c) La formula data è chiusa e quindi può essere solo o vera o falsa nell’interpretazione assegnata. Si traduce nel seguente modo nell’interpretazione assegnata: “Per ogni x, y ∊ X, se (x, y) ∊ R allora esiste z ∊ X tale che (x, z) ∊ R e (z, y) ∊ R”. La formula è vera in qu esta interpretazione infatti: (1, 3 ) ∊ R, ed esiste 2 ∊ X tale che (1, 2 ) ∊ R e (2 , 3) ∊ R; (1, 2) ∊ R, ed esiste 2 ∊ X tale che (1, 2) ∊ R e (2, 2) ∊ R; (1, 4) ∊ R, ed esiste 4 ∊ X tale che (1, 4) ∊ R e (4, 4) ∊ R; (2, 3) ∊ R, ed esis te 2 ∊ X tale che (2, 2) ∊ R e (2, 3) ∊ R; (4, 5) ∊ R, ed esiste 4 ∊ X tale che (4, 4) ∊ R e (4, 5) ∊ R; (5, 3) ∊ R, ed esiste 5 ∊ X tale che (5, 5) ∊ R e (5, 3) ∊ R. (d) Una formula che sia vera se è interpreta ta da ma sia falsa se è interpreta ta da R per esempio è la seguente: . Infatti R non è riflessiva mentre lo è. Esercizio 3 (a) Per mostrare che (Y, *) è un gruppo occorre provare le seguenti proprietà: * interna : già specificato nel testo; * associativa : già specificato nel testo; Esistenza dell’elemento neutro : l’elemento neutro rispetto a * è la coppia (0, 0) ∊ Z R, infatti , per ogni ∊ Z R. Esistenza dell’inverso : per ogni ∊ Z R, l’inverso è ∊ Z R, infatti: * commutativa : siano x, y ∊ Z e a, b ∊ R. Allora:   21A  21A ) , (21 x x Ax   ) , ( ) , ( )0,0( )0,0( ) , ( ax a x a x     ) , ( a x  ) , ( a x  ) , ( a x   ).0,0( ) , ( ) , ( ) , ( ) , (         a x a x a x a x Poiché , dalla genericità degli elementi x, y ∊ Z e a, b ∊ R segue che vale la proprietà commutativa. (b) Per dimo strare che ρ è una relazione di congruenza occorre provare che ρ è una relazione d’equivalenza e che è compatibile con l’operazione *: ρ riflessiva : sia ∊ Z R, allora quindi e e pertanto ρ . Dalla genericità di ∊ Z R segue che vale la proprietà riflessiva . ρ simmetrica : siano , ∊ Z R tali che ρ , allora e quindi e e pertanto ρ . Dalla genericità di , ∊ Z R segue che vale la proprietà simmetrica. ρ transitiva : siano , , ∊ Z R tali che ρ e ρ allora , e , . Pertanto esist ono h, k, r, s ∊ Z tali che , e , da cui seguono le seguenti relazioni: Poiché e si ha che ρ . Dalla genericità di , ∊ Z R segue che vale la proprietà transitiva . ρ compatibile con * : siano , , , ∊ Z R tali che ρ e ρ allora , e , . Pertanto esistono h, k, r, s ∊ Z tali che , e , da cui seguono le seguenti relazioni: Poiché e si ha che ρ e quindi ρ . Dalla genericità di , , , ∊ Z R segue che ρ è compatibile con * . (c) La f.b.f. data si traduce nel seguente modo nell’interpretazione assegnata: “Per ogni , , , ∊ Z R, se ρ e ρ allora ρ ”. Pertanto essa risulta essere vera in questa interpretazione in quanto traduce la proprietà di ρ di essere compatibile con l’ operazione *. ) , ( ) , ( ) , ( ) , ( ) , ( ) , ( a x by a bx y b a y x by a x          ) , ( ) , ( ) , ( ) , ( a x by by a x    ) , ( a x  0|n x x n  | a a n  | ) , ( a x ) , ( a x ) , ( a x  ) , ( a x ) , ( b y  ) , ( a x ) , ( b y y x n  | b a n  | x y n  | a b n  | ) , ( b y ) , ( a x ) , ( a x ) , ( b y  ) , ( a x ) , ( b y ) , ( cz  ) , ( a x ) , ( b y ) , ( b y ) , ( cz y x n  | b a n  | z y n  | c b n  | y x h n    b a k n    z y r n    c b s n    z x n r h n r n h n z y y x z x               | ) ( c a n s k n s n k n c b b a c a               | ) ( z x n  | c a n  | ) , ( a x ) , ( cz ) , ( a x ) , ( cz  ) , ( a x ) , ( b y ) , ( cz ) ,( dt  ) , ( a x ) , ( b y ) , ( cz ) ,( dt y x n  | b a n  | t z n  | d c n  | y x h n    b a k n    t z r n    d c s n    ) ( ) (| ) ( ) ( ) ( ) ( ) ( t y z x n r h n r n h n t z y x t y z x                   ) ( ) (| ) ( ) ( ) ( ) ( ) ( d b c a n s k n s n k n d c b a d b c a                   ) ( ) (| t y z x n    ) ( ) (| d b c a n    ) , ( c az x   ) , ( d bt y    ) ,( ) , ( cz a x   ) ,( ) , ( dt by  ) , ( a x ) , ( b y ) , ( cz ) ,( dt  ) , ( a x ) , ( b y ) , ( cz ) ,( dt  ) , ( a x ) , ( b y ) , ( cz ) ,( dt  ) ,( ) , ( cz a x   ) ,( ) , ( dt by  Non è una formula logicamente valida perché , ad esempio , non è vera nell’interpretazione in cui il dominio è Z e in cui R interpreta la relazione di minore ed f l’operazione di moltiplicazione. In tal caso infatti , per esempio, -2 < 3, -5 < 1 ma ( -2)·( -5)=10 > 3 ·1.