Computer Engineering - Logica e Algebra

Full exam

LOGICA E ALGEBRA 23 SETTEMBRE 2016 PARTE DI ALGEBRA Esercizio 1 Sia N = {0, 1, 2, 3, …} l’insieme dei numeri naturali e si consideri la funzione definita nel seguente modo: a) Stabilire se f ammette inverse sinistre e/o destre e, in caso affermativo, fornirne un esempio. b) Posto , si definisca su X la seguente relazione binaria R: Stabilire quali proprietà soddisfa R. Può esistere la chiusura d’ordine T di R? In caso affermativo la si calcoli e si determinino, se esistono, elementi massimali, minimali, massimo e minimo di X rispetto a T. c) Si definisca su X la seguente relazione binaria S: Stabilire quali proprietà soddisfa S. Si determini la chiusura d’equivalenza  di S e l’insieme quoziente di X rispetto a . Esercizio 2 Si consideri l’anello . a) Si risolva l’equazione . b) Si forniscano due esempi di equazioni lineari a coefficienti in in modo tale che la prima equazione risulti impossibile mentre la seconda ammetta una sola soluzione. c) Si verifichi se il sottoinsieme di è un ideale bilatero di . d) Si stabilisca se esistono ideali propri di che contengono propriamente I e, in caso affermativo, se ne fornisca un esempio. GIUSTIFICARE OGNI RISPOSTA N N f  :         dispariè se 1 parè se 3 2 ) ( 2 n n i n n n f N n }5 |) ( {   n n f X ) ( ) ( e primo numero un è ) ( ) ( )) ( ), ( ( ) ( ), ( 2 1 2 1 2 1 2 1 n f n f n f n f sse R n f n f X n f n f      primi. numeri entrambi sono) ( ), ( )) ( ), ( ( ) ( ), ( 2 1 2 1 2 1 n f n f sse S n f n f X n f n f    ),, ( 9   Z 9 9 ]3[ ]6[  x ),, ( 9   Z }]6[,]3[,]0{[ 9 9 9 I ),, ( 9   Z ),, ( 9   Z ),, ( 9   Z Traccia di soluzione Esercizio 1 a) La funzione f è iniettiva, infatti se n ed m sono uno pari ed uno dispari le loro immagini sono rispettivamente dispari e pari e quindi sono diverse; se n ed m sono entrambi pari allora f (n) = f (m) significa 2 n + 3 = 2 m + 3 da cui n = m; s e n ed m sono entrambi dispari allora f (n) = f (m) significa n2 – 1 = m2 – 1 da cui ancora n = m essendo n ed m due numeri naturali. Dunque f ammette inversa destra. La funzione f non è suriettiva, infatti ad esempio 1 non ha controimmagini, infatti i numeri dispari sono immagini di numeri pari e ogni numero pari va in un intero x  3. Pertanto f non ha inversa sinistra e quindi neppure inversa. Un’inversa destra g di f può essere costruita così dove [ x] in dica la parte intera di x. b) Si ha X = {3, 0, 7, 8, 11, 24}. Pertanto è R={(3,8), (0,3), (0,7), (0,11), (7,24), (8,11)}. R è ovviamente antisimmetrica in quanto è contenuta nella relazione < su X che è antisimmetrica, non è seriale perché ad esempio 11 non è il primo elemento di alcuna coppia in R, quindi non è riflessiva, non è simmetrica perché ad esempio (0,3) R e (3,0) R e non è transitiva perché ad esempio (3,8) R e (8,11) R ma (3,11) R. Essendo R antisimmetrica la chiusura riflessiva e transitiva di R sarebbe la minima relazione d’ordine contenente R, se rimanesse antisimmatrica. La chiusura riflessiva e transitiva di R è T={(3,3),(3,8),(3,11),(0,0),(0,3),(0,8),(0,11),(0,7),(0,24),(7,7),(7,24), (8,8),(8,11),(11,11),(24,24)} ed essendo antisimmetrica è la chiusura d’ordine di R. Il diagramma di Hasse di T è 11 24 8 7 3 0 per cui 24 ed 11 sono elementi massimali, 0 è un minimale ed è anche minimo. c) Si ha S={(3,3),(3,7),(3,11),(7,3),(7,7),(7,11),(11,3),(11,7),(11,11)}. S è simmetrica e transitiva, non è seriale e quindi non riflessiva e non è antisimmetrica. La sua chiusura riflessiva rimane dunque simmetrica e transitiva ed è la relazione di equivalenza  generata da R. Si ha           pariè se 1 dispariè se }0,2 )3 ( max{ ) ( m m m m m g N m ={(3,3),(3,7),(3,11),(7,3),(7,7),(7,11),(11,3),(11,7),(11, 11),(0,0),(8,8),(24,24)}. Le classi di equivalenza sono allora 0={0}, 3={3,7,11}, 8={8}, 24={24} quindi X/ ={ 0, 3, 8, 24}. Esercizio 2 a) La classe [6] 9 non è invertibile in Z 9. Perciò l’equazione o è impossibile o ha più di una soluzione. Si vede subito che [2] 9 è soluzione, infatti , inoltre essendo [6] 9, [3] 9 e [6] 9, [6] 9 coppie di divisori dello zero in Z 9 anche e sono soluzioni dell’equazione. b) La classe [ 2] 9 è invertibile in Z 9 ed ha come inverso [5] 9, quindi ogni equazione lineare che abbia [2] 9 come coefficiente della x ha una ed una sola soluzione in Z 9, ad esempio l’equazione ha la sola soluzione x = [6] 9. L'e quazione è invece impossibile perché , come abbiamo già detto , [6] 9 non è invertibile. c) L'insieme è il sottogruppo ciclico generato da [3] 9 del gruppo additivo di Z 9, inoltre il prodotto di un qualsiasi elemento di Z 9 con un qualsiasi elemento di I restituisce un elemento di I (in quanto ogni elemento della classe prodotto è un multiplo di 3 e, modulo 9, è 0, 3 o 6). Dunque I è un ideale di Z 9. d) Tutti gli elementi di Z9 non contenuti in I sono invertibili perché i loro rap presentanti sono primi con 9 e dunque un ideale J che contenesse propriamente I dovrebbe contenere un elemento invertibile e anche il prodotto di quell'elemento per il suo inverso, che dà come risultato [1] 9. Ma se J contiene [1] 9, allora deve contenere tutti gli elementi di Z 9 essendo un ide ale. P ertanto J dovrebbe coincidere con Z9 e così non può esser e un ideale proprio. 9 9 ]3[ ]6[  x 9 9 9 9 ]3[ ] 12[ ]2[ ]6[    9 9 9 ]5[ ]3[ ]2[   9 9 9 ]8[ ]6[ ]2[   9 9 ]3[ ]2[  x   9 9 ]3[ ]5[ 9 9 ]1[ ]6[  x }]6[,]3[,]0{[ 9 9 9 I LOGICA E ALGEBRA 23 SETTEMBRE 2016 PARTE DI LOGICA Esercizio 1 Si consideri la seguente tavola di verità: A B C f (A, B, C ) _______________________________________ 1 1 1 1 1 1 0 x 1 0 1 0 1 0 0 1 0 1 1 y 0 1 0 1 0 0 1 z 1 0 0 1 a) Si completi la tavola attribuendo ad x, y e z i valori 0 oppure 1 in modo che risultino contemporaneamente verificate le seguenti relazioni: b) Provare i risultati del punto precedente utilizzando la risoluzione. Esercizio 2 Si formalizzi in un linguaggio del primo ordine la seguente frase: “Se x è pari allora esiste un y diverso da x, altrimenti esiste un y tale che x è il doppio di y.” a) Si dica se, usando come dominio gli interi, la formula A trovata è vera, falsa o soddisfacibile ma non vera nell’interpretazione assegnata. b) Si scriv ano le chiusure di A e se ne discuta la verità o falsità nell’interpretazione assegnata. c) Si porti la chiusura universale di A in forma di Skolem. GIUSTIFICARE OGNI RISPOSTA C) B, f(A, | C B ,C )B A(       C) B, f(A, | C A ,B A     Traccia di s oluzione Esercizio 1 a) I modelli di {(A  B)  CBC} sono v 1(A)= v1(B)= v 1(C)=0; v 2(A)= v 2(B)=0, v 2 (C)=1; v3(A)=0, v 3(B)= v 3(C)=1; v 4(A)=1, v 4(B)= v 4(C)=0; v 5(A)= v 5(B)= v 5(C)=1 e devono essere modelli per f(A,B,C), quindi deve essere y = z = 1. I modelli di {A B C} sono w1(A)= w1(B)=1, w1(C)=0 e w2(A)= w2(B)= w2(C)=1 e, poiché non devono essere entrambi modelli di f(A,B,C) , segue che x = 0. b) Segue dalla tavola completata che f(A,B,C) ( BC)( B C) BC) B C)) B C) BC). Per provare per risoluzione che basta verificare che da ={ (A  B)  CBC, f(A,B,C)} c si ricava per risoluzione la clausola vuota. Si ha subito che ={{  ,B, C},{ B, C},{  ,{B, C},{ B C}}. Dalla prima e terza clausola si ricava {B, C}, da questa con la quarta si ricava {B}, dalla seconda e dalla quinta si ricava {B} che con { B} dà la clausola vuota. Per provare invece che dobbiamo verificare che da ={ AB, A Cf(A,B,C)} c non è possibile ricavare per risoluzione la clausola vuota. Si ha subito che ={{ A} B}, AC} {B, C},{ B C}} , Ris( ={{A, B}C} ,},{ B},},{ C C}} = Ris 2(Γ). Abbiamo quindi saturato il risolvente senza ottenere la clausola vuota. Esercizio 2 Per scrivere la f.b.f richiesta serve una lettera predicativa P di arità 1 da interpretare come “essere primo”, una lettera predicativa U di arità 2 da interpretare come il predicato =, una lettera funzionale f di arità 1da interpretare come la funzione che restituisce il doppio dell'argomento e due variabile x,y. La formula è (P(x)  yU(x,y)) (P(x)  yU(x,f(y))) , che in forma chiusa diventa x((P(x)  yU(x,y)) (P(x)  yU(x,f(y)))). (La formula è considerata corretta in entrambe le accezioni). a) In forma non chiusa la formula è soddisfacibile ma non vera infatti P(x)  yU(x,y) è sempre vera in quanto è sempre vero il suo conseguente, inoltre nessun valore dispari assegnato ad x soddisfa P(x)  yU(x,f(y)), in quanto soddisfa l'antecedente ma non il conseguente, mentre ogni valore pari assegnato ad x soddisfa P(x)  yU(x,f(y)) in quanto non soddisfa l'antecedente. Pertanto la congiunzione delle due sottoformule c onsiderate è soddisfacibile ma non vera. Se si considera l a f.b.f data in forma chiusa , essa è falsa perché è la chiusura universale di una formula soddisfacibile ma non vera . C) B, f(A, | C B ,C )B A(       C) B, f(A, | C A ,B A     b) Con la formula data in forma non chiusa la sua chiusura universale è x((P(x)  yU(x,y)) (P(x)  yU(x,f(y)))), che essendo la chiusura universale di una f.b.f soddisfacibile ma non vera è falsa. La chiusura esistenzial e è x((P(x)  yU(x,y)) (P(x)  yU(x,f(y)))) c he essendo la chiusura esistenziale di una formula soddisfacibile è vera. Con la formula data in forma chiusa, basta osservare che la formula è già chiusa e quindi la sua chiusura coincide con la formula stessa . c) Portiamo la formula x((P(x)  yU(x,y)) (P(x)  yU(x,f(y)))) in forma normale prenessa : x((P(x)  yU(x,y)) (P(x)  yU(x,f(y))))  x( y(P(x)  U(x,y))  y(P(x)  U(x,f(y))))  xyz((P(x)  U(x,y)) (P(x)  U(x,f(z)))). La forma di Skolem è allora la seg uente: x((P(x)  U(x,g(x))) (P(x)  U(x,f(h(x))))) , dove g, h sono due nuove lettere funzionali di arità 1.