Computer Engineering - Logica e Algebra

Full exam

1 Durata della prova: 1 h 30’ Esame di Logica e Algebra Politecnico di Milano – Ingegneria Informatica – 15 giugno 2019 Cognome: Nome: Matricola: Tutte le risposte devono essere motivate. Gli esercizi vanno svolti su questi fogli, nello spazio so tto il testo e sul retro. I fogli di brutta non devono essere consegnati. I compiti privi di indicazione leggibile di nome e cognome non verranno corretti. Esercizio 1 Si consideri la seguente tavola di verità: A B C f (A,B,C) 0 0 0 1 0 0 1 x 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 y 1 1 1 z con x, y, z {0; 1}. 1. Si attribuiscano ad x, y, z dei valori in modo tale che valgan o contemporaneamente le due seguenti condizioni: A  B | -L f(A,B,C) f (A,B,C) |  C (BA). 2. Si scriva una f ormula in cui compaiano solo i connettivi  e  e che abbia come tavola di verità quella che si ottie ne sostituendo nella tavola data i valori di x, y, z trovati al punto precedente. 3. Si verif ichi che f (A,B,C) | C (B A) usando la risoluzione. Svolgimento 1. Poiché i modelli della formula A  B sono gli ultimi due che compaiono nella tavola di verità assegnata, allora, affinchè valga la de duzione A  B | -L f(A,B,C) è necessario che y = z = 1. Per soddisfare la condizione f (A,B,C) |  C (BA) è necessario che f (A,B,C) abbia un modello in corrispondenza del quale la f.b.f. C  (BA) sia falsa e ciò può accadere solo se x = 1. 2. Risulta: f (A,B, C) ≡ (~ A  ~B  ~C)  (~ A  ~B  C)  (A  B  ~C)  (A  B  C) ≡ ((~ A  ~B)  (~C  C))  ((A  B)  (~C  C)) ≡ (~ A  ~B )  (A  B ) ≡ ~(~ A  ~B )  (A  B ) ≡ A  B  ~( A  ~B ) ≡ (~ A  B)  ~( A  ~B ) 3. Trasformiamo le formule f (A,B,C) e ~(C  (B A)) in forma a clausole: f (A,B,C) ≡ (~ A  ~B )  (A  B ) ≡ (~ A  (A  B ))  (~ B  (A  B )) ≡ (~ A  B)  (~ B  A) ~(C  (B A)) ≡ ~(~C  B  A) ≡ C  ~B  ~A Si ottiene allora il seguente insieme di clausole di input: 2 S = {{ ~A, B}, {~ B, A}, { C}, {~ B}, {~A} } Risulta Ris(S) = S  {{ ~A, A}, { ~B, B }} e Ris 2(S) = Ris(S). Poiché □ Ris(S) segue che f (A,B,C) | C (B A). Esercizio 2 Si consideri la re lazione binaria R sull’insieme X = a,b,c,d,e,f  definita dalla seguente matrice di incidenza : 1) Si costruisca la relazione di equivalenza S generata da R e si determini l’insieme quoziente X / S. 2) Si dimostri che esiste la minima relazione d’ordine T contenente R e si determinino, se esistono, gli elementi massimali , minimali, massimo e minimo di X rispetto a T. 3) Si consideri la seguente formula della logica del primo ordine: e si stabilisca se è vera, falsa o soddisfacibile ma non vera nell’interpretazione avente come dominio l’insieme X e in cui la lettera predicativa è interpretata dalla relazione d’ordine T trovata al punto precedente mentre è interpretata dalla relazione di uguaglianza. Portare infine la formula data in forma di Skolem. Soluzi one 1) La chiusura riflessiva e simmetrica F di R ha la seguente matrice d’incidenza: M F = Determiniamo la sua chiusura transitiva: M F2 = M F3 = = M F4 Segue che S = F  F2  F3 = F3 e quin di l’insieme quoziente è X / S = {[a] S, [d] S, [e] S}, dove [a] S = {a, b, c, f}, [d] S = {d}, [e] S = {e}. 2) La relazione R è antisimmetrica quindi può esistere la sua chiusura d’ordine. Effettuiamo la chiusura riflessiva G di R:                    1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0  ) , ( ) , ( ) , ( 22 21 21 y x A x y A y x y x yA x      21A 22A                   1 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 0 0 0 1 1 0 1 0 0 1 0 1                   1 0 0 1 0 1 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 1 1 1 0 0 0 1 1 1 1 0 0 1 1 1                   1 0 0 1 1 1 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 3 M G = Que sta coincide con il suo quadrato e pertanto la relazione G è transitiva. Inoltre G è ancora antisimmetrica quindi essa è la minima relazione d’ordine T contenente R. Gli elementi massimali di X rispetto a T sono f, e, c, d mentre i minimali sono a, e, d, b mentre n on esistono né massimo né minimo. 3) La traduzione della formula nell’interpretazione assegnata è la seguente: “Per ogni x ∊ X esiste y ∊ X tale che (x, y) ∊ T ed esiste x ∊ X tale che, per ogni y ∊ X, se (y, x) ∊ T allora x = y”. La proposizione “per ogni x ∊ X esiste y ∊ X tale che (x, y) ∊ T” risulta vera poiché la relazione T è seriale. La proposizione “esiste x ∊ X tale che, per ogni y ∊ X, se (y, x) ∊ T allora x = y” risulta anch’essa vera poiché corrisponde alla definizione di elemento mini male e, come visto al punto precedente, esistono elementi minimali di X rispetto a T. Pertanto la formula risulta vera nell’interpretazione assegnata poiché è la congiunzione di due formule vere. Determiniamo la forma normale prenessa della formula assegna ta: Considerata la sostituzione , risulta che la forma della formula data è la seguente: . Esercizio 3 Si consideri il campo ( Z13, +, · ) delle classi di resto modulo 13 e la seguente fu nzione: . 1) Si dimostri che f è un omomorfismo del gruppo (Z13, + ) in sé stesso . 2) Si stabilisca se f è anche un omomorfismo di (Z13, ·) in sé stesso. 3) Si consideri la seguente f.b.f. della logica del primo ordine: . Si stabilisca se è vera, falsa o soddisfacibile ma non vera nell’interpretazione in cui il dominio è Z13, è interpretata dalla relazione di uguaglianza, è interpre tat a dalla funzione f precedentemente ass egnata e è interpre tat a dall’operazione di addizione definita in Z13. Svolgimento 1) Siano . Allora Pertanto f è un omomorfismo del gruppo (Z13, + ) in sé stesso.                   1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 1 0 1      ),( ) ,( ) , ( ) , ( ) , ( ) , ( 22 21 21 22 21 21 tz A zt A y x At z y x y x A x y Ay x y x yA x            } /) ( ; /) ( { 12 11 z x f y x f      ) ), ( ( )) ( ,( )) ( , ( 12 22 12 21 11 21 t x f A x f t A x f x At x     13 13 13 13 13 13 ] [ 2 ) ] ([ ] [ ) , ( ) , (: a a f Z a Z Z f          ))) ( ), ( ( ) , ( ( ))) ( ), ( ( )), , ( ( ( 11 11 21 21 11 11 21 21 11 21 y f x f A y x A x f x f f y x f f Ay x       21A 11f 21f 13 13 13 ] [, ] [ Z b a  ) ] ([ ) ] ([ ] [ 2 ] [ 2 ) ] [ ] ([ 2 ] [ 2 ) ] ([ ) ] [ ] ([ 13 13 13 13 13 13 13 13 13 13 b f a f b a b a b a b a f b a f                4 2) Siano . Risulta: Pertanto f è non è un omomorfismo di (Z13, ·) in sé stesso essendo . 3) La traduzione della formula nell’interpretazione assegnata è la seguente: “Per ogni x, y ∊ Z13, e, se allora ”. L’uguaglianza è sempre verificata essendo f un omomorfismo del gruppo (Z13, + ) in sé stesso. Inoltre anche la proposizione “se allora ” è vera poiché f è iniettiva. Infatti siano tali che e supponiamo per assurdo che . Allora da cui segue che . Pertanto 13 divide 2 a – 2b e quindi 13 divide 2( a – b). Ciò implica che 13 divide a – b e che quindi a ≡ b (mod 13). Ma ciò è assurdo in quanto, per ipotesi, . Segue che se allora e quindi f è iniettiva. In alternativa, per dimostrare l’iniettività di f si poteva far vedere che a classi distinte corrispondono immagini distinte per via esaustiva: . Possiamo concludere quindi che la formula assegnata è vera essendo la chiusura universale della congiunzione di due formule vere. 13 13 13 ] [, ] [ Z b a  ) ] [ ] ([ 4 ] [ 2 ] [ 2 ) ] ([ ) ] ([ ) ] [ ] ([ 2 ] [ 2 ) ] ([ ) ] [ ] ([ 13 13 13 13 13 13 13 13 13 13 13 13 b a b a b f a f b a b a b a f b a f                  ) ] ([ ) ] ([ ) ] [ ] ([ 13 13 13 13 b f a f b a f    ) ( ) ( ) ( y f x f y x f    y x ) ( ) ( y f x f  ) ( ) ( ) ( y f x f y x f    y x ) ( ) ( y f x f  13 13 13 ] [ , ] [ Z b y a x    y x ) ( ) ( y f x f  13 13 ] [ 2 ] [ 2 b a    13 13 ] 2[ ] 2[ b a  13 13 ] [ ] [ b a  y x ) ( ) ( y f x f  13 13 ]0[ ]0[ 2   13 13 ]2[ ]1[ 2   13 13 ]4[ ]2[ 2   13 13 ]6[ ]3[ 2   13 13 ]8[ ]4[ 2   13 13 ] 10[ ]5[ 2   13 13 ] 12[ ]6[ 2   13 13 ]1[ ]7[ 2   13 13 ]3[ ]8[ 2   13 13 ]5[ ]9[ 2   13 13 ]7[ ] 10[ 2   13 13 ]9[ ] 11[ 2   13 13 ] 11[ ] 12[ 2  