Computer Engineering - Logica e Algebra

Full exam

SOLUZIONE DELLA PROVA DEL 21/2 /2019 Esercizio 1 (a) Per il teorema di correttezza e completezza forte , F si deduce nella teoria L dall’insieme {A, B, ¬B  ¬C}se e solo se F si deduce semanticamente dallo stesso insieme. Gli unici modelli dell’insieme {A, B, ¬B  ¬C}sono v1 e v 2 tali che v1(A) = v1(B) = v1(C) = 1 e v2(A) = v2(B) = 1 v2(C) = 0 che risultano essere modelli anche per F perciò possiamo affermare che esiste una deduzione di F dall’insieme dato. (b) Per provare il risultato ottenuto utilizzando la risol uzione utilizziamo il teorema di risoluzione e il teorema che lega la deducibilità semantica all’insoddisfacibilità, cioè F si deduce da {A, B, ¬B  ¬C} se e solo se {A, B, ¬B  ¬C, ¬ F }è insoddisfacibile . Dobbiamo pertanto scrivere in clausole le formule dell’insieme {A, B, ¬B  ¬C}e la formula ¬ F. Risulta: ¬B  ¬C ≡ B  ¬C ¬ F ≡ (¬A˅¬B˅¬C)˄(¬A˅¬B˅ C)˄(¬A˅B˅C) ≡ ((¬A˅¬B )˅(C˄¬C) )˄(¬A˅B˅C) ≡ (¬A˅¬B ) ˄(¬A˅B˅C) ≡ (¬A˅(¬B˄(B˅C))) ≡ (¬A˅(¬B˄C)) ≡ (¬A˅¬B)˄(¬A˅C) Le clausole di input allora sono C 1 = {A }, C 2 = { B}, C 3 = { B,¬C }, C 4 = {¬A,¬B }, C5 = {¬A, C }. Una derivaz ione per risoluzione della clausola vuota è la seguente: (I) C4 = {¬A,¬ B} (clausola di input) (II) C2 = { B } (clausola di input) (III) C6 = { ¬A } (risolvente di C4 e C 2) (IV) C1 = {A} (clausola di input) (V) □ (risolvente di C6 e C1) Avendo ottenuto l a clausola vuota si può concludere che F si deduce da {A, B, ¬B  ¬C}. Esercizio 2 (a) Condizione necessaria affinché esista la chiusura d’ordine di R è che R sia antisimmetrica . Ma la doppia freccia tra gli elementi 2 e 3 mostra che R non lo è. (b) Il grafo di in cidenza di T = R2 è 1 3 4 2 5 Le funzioni contenute in T sono: f1= {(1,3),(2,2),(3,3),(4,2),(5,2)}, f2={(1,5),(2,2),(3,3),(4 ,2),(5,2) } f3= {(1,3),(2,2),(3,3),(4,3),(5,2)}, f 4={(1,5),(2,2),(3,3),(4,3),(5,2)}. Scegliendo come funzione f1 il quoziente X / ker(f 1) è {{1,3},{2,4,5}}, scegliendo f 2 il quoziente X / ker(f 2) è {{1},{3},{2,4,5}}, scegliendo f 3 il quoziente X / ker(f 3) è {{2,5},{3},{1 ,4}}, mentre scegliendo f 4 il quoziente X / ker(f 4) è {{1},{3,4},{2,5}}. (c) La chiusura d’ordine di T esiste in quanto T è antisimmetrica e la sua chiusura riflessiva e transitiva continua ad esserlo. Il diagramma di Hasse di tale chiusura è il seguente: 2 5 3 1 4 (d) Le formule date sono chiuse e quindi possono essere solo o vere o false nelle interpretazioni assegnate . (i) La formula F1 si traduce nel seguente modo nell’interpretazione assegnata: “Per ogni x, y , z ∊ X, se (x, y) ∊ R e (x, z) ∊ R allora (y, z) ∊ R”. La formula è falsa in qu esta interpretazione infatti (4, 3 ) ∊ R ,(4, 5 ) ∊ R ma (3, 5 ) ∉ R. La formula perciò non può essere logicamente valida. Non è neppure logicamente contraddittoria in quanto se A1 è interpretata dalla relazione universale allora F1 è vera. (ii) La formula F2 si traduce nel seguente modo nell’interpretazione assegnata: “Per ogni x, y, z ∊ X, se (x, y) ∊ T e (y, z) ∊ T allora (z, z) ∊ T”. La formula è vera in questa interpretazione infatti: da (1, 3 ) ∊ T e (3, 3 ) ∊ T segue (3, 3 ) ∊ T; da (3 , 3 ) ∊ T e (3, 3 ) ∊ T segue (3, 3 ) ∊ T; da (2 , 2) ∊ T e (2, 2) ∊ T segue (2, 2) ∊ T; da (1, 5) ∊ T e (5, 2) ∊ T segue (2, 2) ∊ T; da (5, 2) ∊ T e (2, 2) ∊ T segue (2, 2) ∊ T; da (4, 2) ∊ T e (2, 2) ∊ T segue (2, 2) ∊ T da (4, 3) ∊ T e (3, 3) ∊ T segue (3, 3) ∊ T La formula perciò non può essere logicamente contraddittoria. Non è neppure logicamente valida in quanto se A 2 è interpretata da R è falsa, infatti (1, 4) ∊ R e ( 4, 5) ∊ R ma (5, 5) non appartiene a R. Esercizio 3 (a) Per mostrare che (Y, *) è un gruppo occorre provare le seguenti proprietà: * asso ciativa : siano x, y, z ∊ Y, a llora: (x*y) *z = (x+y -xy) *z = x+y -xy+z –(x+y -xy)z = x+y -xy -xz -yz+ xyz x*(y *z) = x*(y+z -yz) = x+y+z -yz -x(y+z -yz) = x+y+z -yz -xy -xz+xyz pertanto segue la tesi. Esistenza dell’elemento neutro : l’elemento neutro rispetto a * è x = 0, infatti x*0 = x+0 -x·0 = x, per ogni x ∊ Y. Esistenza dell’inverso : per ogni x ∊ Y, l’inv erso è - x ∕ (1-x) ∊ Y infatti: x*(- x ∕ (1-x)) = x - x ∕ (1-x) + x2 ∕ (1-x) = 0. * commutativa : per ogni x, y ∊ Y si ha x*y = x+y -xy = y+x -yx = y* x . (b) La f.b.f. data si traduce nel seguente modo n ell’interpretazione assegnata: “Se , per ogni x, y ∊ Y, esiste z ∊ Y tale che x *z = y allora esiste z ∊ Y tale che, per ogni x ∊ Y, x*z = z”. L’antecedente della formu la è vero basta scegliere z = y -x ∕ (1-x), il conseguente invece è falso in quanto l’unico numero r azionale per cui è soddisfatta l’uguaglianza x+z -xz = z, qualunque sia x , è z = 1 che però non appartiene a Y. La formula perciò risulta falsa nell’interpretazione considerata. Da quanto osservato si deduce che la formula non è logicamente valida. La formula n on è neanche logicamente contraddittoria in quanto se si considera l’ interpretazione che ha dominio Q , nella quale * è l’usuale operazione di moltiplicazione e A è la relazione di uguaglianza, l’antecede nte è falso in quanto se x = 0 e y = 1 non esiste z che sodd isfi l’uguaglianza. Perciò la formula in questa interpretazione è vera. Per trovare la forma di Skolem della formula data portiamo prima la formula in forma normale prenessa: . E limin iamo poi i quantificatori esistenziali ed effe ttu iam o le seguenti sostituzioni:  = { a / x; b / y; g(z) / w }, dove a e b sono costanti e g è una lettera funzionale di arità 1. La forma di Skolem è quindi la seguente: . )) ), ,( ( ) ), , ( ( ( w wt f A y z x f At w z y x       )))( )),( ,( ( ) ), , ( ( ( t g t gt f A b z a f At z   