Computer Engineering - Logica e Algebra

Full exam

1 Seconda prova in itinere Logica e Algebra 10 luglio 2015 Esercizio 1 Si considerino le seguenti formule della logica del primo ordine: a) b) c) . Si considerino ora le seguenti interpretazioni: 1) I nella quale il dominio è Z , è da interpretarsi come l’uguaglianza, come l’operazione di moltiplicazione, la costan te a come la classe dello 0 e la costante b come la classe di 1; 2) I nella quale il dominio è Z , è da interpretarsi come l’uguaglianza, come l’operazione di moltipl icazione, la costante a come la classe dello 0 e la costante b come la classe di 1. Si dica, per ciascuna delle formule, se sono vere, false, soddisfacibili ma non vere in ciascuna delle due interpretazioni assegnate. Si porti la formul a c) in forma norm ale pren essa e si dica se si tratta di una formula logicamente valida. Esercizio 2 Si consideri la struttura algebrica ( Z, ) in cui la legge di composizione interna  è così definita:  x, y ϵ Z x  y = x + y + 2 dove + denota l’usuale operazione di add izione di numeri interi. 1. Si dimostri che è un gruppo . 2. Denotati con P e D rispettivamente l’ (Z, ) insieme dei numeri pari e l’insieme dei numeri dispari, si stabilisca se ( P, ) e ( D, ) sono sottogruppi di (Z, ). In caso affermativo si stabilisca se sono sottogruppi normali. 3. Si consideri l’applicazione f : Z Z così definita:  x ϵ Z f (x) = 2x e si stabilisca se f è un omomorfismo tra i gruppi ( Z, ) e ( Z, +). GIUSTIFICARE OGNI RISPOSTA          a y x f A a y A a x A y x , , , , 21 21 21 21         b z x f Az , , 21 21           a y x f A a y A a x A y x , , , , 21 21 21 21         b z x f Az , , 21 21   1 7 21A 21f 2 6 21A 21f  2 Traccia di soluzione della seconda prova in itinere del 10/7/2015 Esercizio 1 La formula a) nell’interpretazione 1) dice che in Z7 esistono divisori dello 0 ed è quindi falsa poiché Z7 è un campo e come tale non ha divisori dello 0 . Nell’interpretazi one 2) invece dice che esistono divisori dello 0 in Z6 ed è vera in quanto ad esempio [2] 6, [3] 6 sono una coppia di divisori dello 0. La formula b) nell’interpretazione 1) dice che , per ogni elemento z di Z7, x ∙ z ≠ [1] 7 o, in altre parole , che x non ammette inverso rispetto al prodotto in Z7. Ovviamente è non soddisfatta in tutti gli assegnamenti che danno ad x un valore diverso da [0] 7 (in quanto ogni elemento di Z7\{[0] 7} ammette un inverso ) mentre è soddisfatta dall’assegnamento che pone x = [0] 7 (in quanto in ogni anello, quindi anche in Z7, il prodotto di ogni el emento dell’anello per lo zero dà come risultato zero ). Nell’interpretazione 2) la formula b) dice che , per ogni z elemento di Z6, x ∙ z ≠ [1] 6 7 o, in altre parole , che x non ammette inverso rispetto al prodotto in Z6. Tale formula è ancora soddisfatta dall’assegnamento x = [0] 6 ed è soddisfatta inoltre da tutti gli assegnamenti che attribuiscono ad x un valore diverso da [5] 6 o da [1] 6 (le restanti cl assi, infatti, avendo un rappresentante non primo con 6, non ammettono inverso). Le classi [5] 6 e [1] 6 invece ammettono rispettivamente come inversi [5] 6 e [1] 6 e quindi gli assegnamenti che danno ad x o il valore [5] 6 o il valore [1] 6 non soddisfano fa f ormula. In entrambe le interpretazioni, dunque , la formula b) è soddisfacibile ma non vera. La formula c) ha come antecedente la formula a) e come conseguente la fo rmula b), dunque è vera nell’interpretazione 1), perché l’antecedente è sempre falso, mentre è soddisfacibile ma non vera nella interpretazione 2) in quanto l’antecedente è vero e il conseguente soddisfacibile ma non vero (in particolare non è soddisfatta dagli ass egnamenti x = [1] 6 e x = [5] 6 mentre è soddisfatta dagli assegnamenti che danno ad x un qualsiasi altro valore in Z6). La forma normale prenessa di c) è . Tale formula è equivalente alla formula c) e quindi non è logicamente valida perché non è vera in ogni interpretazione, infatti ad esempio non è vera nell’interpretazione 2 ). Esercizio 2 1. Dimostriamo che ( Z, ) è un gruppo: Proprietà associativa : sian o x, y, z ϵ Z. Allora                 b z x f A a y u f A a y A a u A z y u , , , , , , 2 1 2 1 2 1 2 1 2 1 2 1          3 (x  y)  z = (x + y + 2)  z = x + y + 2 + z + 2 = x + y + z + 4 x  (y  z) = x  (y + z + 2 ) = x + y + z + 2 + 2 = x + y + z + 4 quindi (x  y)  z = x  (y  z). Esistenza dell’elemento neutro : siano x, y ϵ Z. Allora x  y = x se e solo se x + y + 2 = x e quindi se e solo se y = – 2. Inoltre – 2  x = – 2 + x + 2 = x quindi – 2 è l’elemento neutro di Z rispetto a . Esistenza dell’inverso : siano x, y ϵ Z. Allora x  y = – 2 se e solo se x + y + 2 = – 2 e quindi se e sol o se y = – x – 4. Inoltre ( – x – 4)  x = – x – 4 + x + 2 = – 2 quindi – x – 4 è l’ inverso di x in Z rispetto a . Segue che (Z, ) è un gruppo. 2. Verifichiamo se P è sottogruppo di ( Z, ). Siano 2x, 2y ϵ P, allora: 2x  (2y) -1 = 2x  (– 2y – 4) = 2x – 2y – 4 + 2 = 2x – 2y – 2 = 2 (x – y – 1) ϵ P. Per il criterio di caratterizzazione dei sottogruppi si ha che (P, ) è sottogruppo di ( Z, ). Inoltre (P, ) è un sottogruppo normale in quanto, per ogni z ϵ Z, risulta z  2x  z-1 = (z + 2x + 2)  (– z – 4) = z + 2x + 2 – z – 4 + 2 = 2x ϵ P. Si poteva arrivare alla stessa conclusione osservando che ( Z, ) è un gruppo abeliano (e quindi tutti i suoi sottogruppi sono normali), infatti x  y = x + y + 2 = y + x + 2 = y  x. Verifichiamo se D è sottogruppo di ( Z, ). Siano 2x + 1, 2y + 1 ϵ D, allora: (2x + 1)  (2y + 1) -1 = (2x + 1)  (– 2y – 1 – 4) = 2x + 1 – 2y – 1 – 4 + 2 = 2x – 2y – 2 = 2 (x – y – 1) e quindi, poiché (2x + 1)  (2y + 1) -1 non appartiene a D, p er il criterio di caratterizzazione dei sottogrupp i si ha che (D, ) non è sottogruppo di ( Z, ). 3. Verifichiamo se f è un omomorfismo. Siano x, y ϵ Z. Allora f (x  y) = f (x + y + 2) = 2 ( x + y + 2 ) = 2x + 2y + 4 f (x) + f (y) = 2x + 2y Poiché f (x  y) ≠ f (x) + f (y) segue che f non è un omomorfi smo tra i gruppi ( Z, ) e ( Z, +). 4 Recupero prima prova in itinere Logica e Algebra 10 luglio 2015 Esercizio 1 Si consideri la seguente tavola di verità A B C f (A, B, C ) ______________________________ _________ 1 1 1 0 1 1 0 0 1 0 1 0 1 0 0 1 0 1 1 0 0 1 0 1 0 0 1 0 0 0 0 1 a) Trovare una f.b.f. f (A, B, C ) contenente solo i connettivi  e  avente come tavola di verità quella data . b) Dire se valgono le seguenti deduzioni nella teoria L: . c) Provare i risultati trovati al punto precedente utilizzando la risoluz ione. Esercizio 2 Si consideri la relazione binaria R su Z definita nel seguente modo:  x, y ϵ Z (x, y ) ϵ R sse 3 | 2 x + y Si stabilisca quali proprietà soddisfa R e si dica se R è una relazione d’equivalenza o una relazione d’ordine. Posto A = { x ϵ Z | , x dispari}, si scriva la matrice d’incidenza della relazione S su A definita nel seguente modo:  x, y ϵ A (x, y ) ϵ S sse (x, y ) ϵ R ˄ e si dimostri che S è una relazione d’ordine . Si determinino, se esistono, gli elementi massimali, minimali, massimo e minimo di A rispe tto ad S. S i st abilisca se (A, S) è un reticolo e, in caso negativo , si consideri una relazione T contenent e S tale che (A, T) sia un reticolo. Si conti il numero di funzioni contenute in S e si esibisca un esempio di funzione , scelta fra esse, che non ammette inversa. GIUSTIFICARE OGNI RISPOSTA ) , , ( | C B A f B A L   ) , , ( | C B A f C A L    10 0   x y x 5 Traccia di soluzione del recupero della prima prova in itinere del 10/7/2015 Esercizio 1 a) Dalla tavola di verità ricaviamo la forma normale disgiuntiva della formula data: f ( A, B, C ) ≡ ≡ ≡ ≡ ≡ ≡ b) Per il teorema di correttezza e completezza forte risulta che e se e solo se e . Segue che la prima deduzione è falsa in quanto l’interpretazione v 1 tale che v 1(A) = v 1(B) = v 1(C) = 1 è un modello per ma non per . La seconda dedu zione , invece, è vera in quanto i modelli di sono le interpretazioni v 1 e v 3 tali che v 1(A) = v 1(B) = v 1(C) = 1 e v 3(A) = v 3(C) =1, v3(B) = 0 che sono entrambi modelli per . c) Proviamo i risultati trovati al pu nto precedente utilizzando la risoluzione . Scriviamo in forma a clausole le formule: Si ottiene l’insieme di clausole di input S = {{ A, B }, { B, C }, { A, C }} e risulta che Ris(S) = S. Poiché Ris(S) si ha che la deduzione è falsa. Pertanto, per il teorema di correttezza e completezza forte, anche è una deduzione falsa in L . Scriviamo in forma a clausole le altre formule: Si ottiene l’insieme di clau sole di input S = {{ A}, { C}, { A, B}, { C}} e quindi si ottiene subito la seguente derivazione per risoluzione della clausola vuota: (I) {C} (clausola di input) ) ( ) ( ) ( C B A C B A C B A           C B A B A B A         )) ( ) ( ) (( C B B A B A       ))) ( ( ) (( C A B A    ) ) (( C A B A A      )) ( ) (( ) ) (( ) ) ( ( ) ( C B A C A B C A B             ) , , ( | C B A f B A L   ) , , ( | C B A f C A L    ) , , ( | C B A f B A    ) , , ( | C B A f C A    B A  ) , , ( C B A f C A ) , , ( C B A f B A B A     ) ( ) ( ) ( ) ( ) ) (( ) , , ( C A C B C A B C A B C A B C B A f                 ) , , ( | C B A f B A    ) , , ( | C B A f B A L   C A C A B C B A f       ) ( )) , , ( ( 6 (II) {C} (clausola di input) (III)  (risolvente di (I) e (II)) Pertanto la deduzione è vera e quindi, per il teorema di correttezza e completezza forte, . Esercizio 2 La relazione R è riflessiva in quanto , per ogni x Z, 3 | 3x e quindi 3 | 2x + x da cui si segue che ( x, x )R. Pertanto R è anche seriale. La relazione R è simmetrica , infatti s e (x, y)R allora 3 | 2x + y e quindi esiste un intero h tale che 2x + y = 3h, da cui y = 3h - 2x . Allora 2y + x = 6h - 4x + x = 3(2h - x) con 2h - x intero . Pertanto 3 | 2y + x e così (y, x)R. Segue che R è simmetrica mentre non è antisimmetrica in qu anto se una relazione è contemporaneamente simmetrica e antisimmetrica deve essere contenuta nella relazione identica. La relazione R è transitiva, infatti se (x, y)R ed (y, z)R si ha che 3 | 2x + y, 3 | 2y + z, ovvero 2x + y = 3h, 2y + z = 3k con h, kZ. Sommando membro a membro queste ultime uguaglianze si ha 2x + 3y + z = 3(h+k) ovvero 2x + z = 3(h + k - y) con h + k - zZ. Pertanto 3 | 2x + z e quindi (x, z)R. La relazione R è dunq ue una relazione di equivalenza mentre non è una relazione d’ordine . Sia ora A = {1, 3, 5, 7, 9}. La relazione S ha la seguente matrice di incidenza : Si vede subito dalla matrice che S è rif lessiva (sulla diagonale principale ci sono solo 1 ) ed antisimmetrica (gli unici 1 fuori dalla diagonale princip ale presentano uno 0 in posizione simmetrica rispetto alla diagonale principale ). Si può arrivare alla stessa conclusione osservando che S è l’intersezione dell a relazione R (che è riflessiva ) con la relazione ≤ (che è riflessiva ed antisimmetrica ) ed è noto che l’intersezione di due relazioni riflessive è riflessiva e che ogni relazione contenuta in una relazione antisimmetrica è antisimmetrica . Infine R e ≤ sono entrambe transitive e quindi la loro intersezio ne S è transitiva. Pertanto S è una relazione d’ordine su A. ) , , ( | C B A f C A    ) , , ( | C B A f C A L                    1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 7 Il diagramma di Hasse della relazione S su A è il seguente 7 5∙ 9 1 3 dunque 7, 5, 9 sono elementi massimali e 1, 5, 3 sono elem enti minimali di A rispetto ad S. Non ci sono ovviamente né massimi né minimi. A non è un reticolo rispetto ad S in quanto ad esempio 1 e 5 non ammettono estremo sup eriore . Una relazione T che contenga S tale che (A,T) sia reticolo è, ad esempio, la seguente T={(1,1), (1,3),(1,7),(1, 9),(1,5),(3,3),(3,9),(3,5),(5,5),(7,7), (7,5) }. Infatti è facile osservare che T è riflessiva, antisimmetrica e transitiva e quindi è una relazione d’ordine, inoltre tutti gli elementi di R sono in T e quindi T contiene R, ed infine , per ogni x A, inf{1,x} = 1, sup {1,x} = x, inf{5,x) = x, sup{5,x} = 5, inf{x,x} = sup{x,x} = x, inf{3,7} = 1, sup{3,7}=5, inf{3,9} = 3, sup{3,9} = 9, inf{7,9} = 1, sup{7,9} = 5. Dunque (A,T) è un insieme parzialmente ordinato in cui ogni coppia di elementi di A ammette sia inf sia sup ed è un reticolo, come si poteva osservare facilmente dal diagramma di Hasse di A rispetto a T: 5 7 9 3 1 Le funzioni da A ad A contenute in S devono avere come matrice di incidenza una matrice che abbia un solo 1 per ogni riga e nessun 1 nelle posizioni in cui nella matrice di incidenza di S c’è 0. Per costruire la matrice di incidenza di una funzione contenuta in S dobbiamo quindi eliminare un 1 dalla prima riga e dalla seconda riga della matrice di incidenza di R e questo si può fare in 2  2 = 4 modi diversi. Ci sono quindi 4 fu nzioni del tipo richiesto. Una funzione da A ad A contenuta in R che non ammetta inversa è ad esempio la seguente f(1) = 1,f(3) = 9, f(5) = 5,f(7) = 7,f(9) = 9. Tale funzione infatti non è iniettiva (e quindi neppure suriettiva) in quanto f(3)=f(9) e pertanto non am mette inversa.