Computer Engineering - Logica e Algebra

Full exam

1 LOGICA E ALGEBRA 24 LUGLIO 2015 Parte di Logica Esercizio 1 Si consideri la seguente tavola di verità : A B C f (A, B, C ) _________________________________________ 1 1 1 0 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 0 0 1 0 0 0 0 1 0 0 0 0 1 a) Trovare una formula f (A, B, C ) contenent e solo i connettivi  e  ed avente come tavola di verità quella assegnata . b) Dire se gli insiemi { C, B  f (A, B, C )e { C  , B  f (A, B, C ) sono soddisfacibili. c) Provare i risultati trovati al punto b) utilizzando la teoria della risoluzi one. Esercizio 2 Si consideri la seguente formula : a) Si dic a se tale formula è vera, falsa o soddisfacibile ma non vera nell’inte rpretazione avente come dominio l’insieme R dei numeri reali ed in cui A interpreta l’usuale relazione < su R mentre f interpreta l’operazione di moltiplicazione fra numeri reali . b) Si scrivano la chiusura esistenziale e quella universale della formula data e se ne dis cuta la verità nell ’interpretazione assegnata al punto a) . c) Si consideri , ora , la formula seguente: La si porti in forma normale prenessa e si dica se si tratta di una formula logicamente valida o logicamente contra ddittoria.    ) , (21 z y Az y )) , ( ), , ( ( 21 21 21 z x f y x f A 21 21    ) , (21 z y Az y )) , ( ), , ( ( 21 21 21 z x f y x f Ax  2 Traccia di soluzione Esercizio 1 a) (A BC) (A BC) (A BC) (A BC) (A BC)  (A BC)  (A BC)  (A C) (BC)  C (A B)   ( (A B) C)   ( (B  A)  C). b) L’insieme {C, B  f (A, B, C) è insoddisfacibile in quanto i modelli della prima formula devono dare a C il valore 1 e quelli della terza hanno sempre 0 come valutazione di C, pertanto non si hanno modelli comuni alle tre formule. Invece l’insieme{ C  , B  f (A, B, C ) ha come modello ad esempio v(C)=0, v(B)=1, v(A)=0 ed è quindi soddisfacibile. c) Ess endo f(A,B,C)  C (A B) , si ha che f(A,B,C) in forma a clausole è {{ C},{A, B}} , quindi fra le clausole dell’insieme { C, B  f (A, B, C )ci sono {C} e {C} da cui si ricava subito la clausola vuota , pertanto è riconfermato che l’insieme è insoddisfa cibile. Scriviamo ora ={C , B  f (A, B, C ) in forma a clausole: la forma a clausole di C è { C, }, quella di B  è , infine , essendo   f (A, B,C )  C (A B) ) C(AB) CA)CB) , la forma a clausole di  f (A, B,C ) è {{ C,A},{C,B}}. L’insieme in forma a clausole è dunque ={ {C, }, {C,A},{C,B} }, da cui si ha Ris =  {{ C,B}, {A, A}, {C, C},{A,B}} Ris 2= Ris   e poi Ris 3= Ris 2, ovvero  Ris *= Ris 2. Poiché la clausola vuota non appartien e a Ris *, la c lausola vuota non può essere derivata da  e pertanto  è soddisfacibile. Esercizio 2 a) La formula nell’interpretazione da ta si legge così: “Se esistono y e z tali che y < z allora xy < xz ”. Il suo antecedente è ovviamente vero, il suo conseguente (in cui tutte le variabili sono libere) è soddisfatto ad esempio dall’assegnamento s(x) = 1, s(y) = 2, s(z) = 3, mentre non è soddisfatto ad esempio dall’assegnamento s(x) = -1, s(y) = 2, s(z) = 3, per cui il consegue nte della formula è soddisfacibile ma non vero e di conseguenza l’intera formula è soddisfacibile ma non vera. b) La chiusura esistenziale di è xyz( ) ed essendo la chiusura esistenziale di una formula soddisfacibile è vera. La chiusura universale di è xyz( )    ) , (21 z y Az y )) , ( ), , ( ( 21 21 21 z x f y x f A    ) , (21 z y Az y )) , ( ), , ( ( 21 21 21 z x f y x f A    ) , (21 z y Az y )) , ( ), , ( ( 21 21 21 z x f y x f A    ) , (21 z y Az y )) , ( ), , ( ( 21 21 21 z x f y x f A    ) , (21 z y Az y )) , ( ), , ( ( 21 21 21 z x f y x f A 3 ed essendo la chiusura universale di una formula soddisfacibi le ma non vera è falsa. c) La forma normale prenessa di è . Nell’interpretazione che è stata assegnata la formula ha l’antecedente vero e il conseguente falso infatt i, per ogni assegnamento ad y e z , se il valore dato ad y è minore di quello dato a z, valori negativi di x rendono xy maggiore di xz , se invece il valore dato ad y è maggiore di quello dato a z, valori positivi di x rendono xy maggiore di xz . La formula in quella interpretazione è quindi falsa e non può essere logicamente valida. Nell’ interpretazione avente come d ominio un insieme qualsiasi D, in cui A è la relazione vuota, l’antecedente della formula è sempre falso per cui la formul a è vera e quindi la formula non può essere logicamente contraddittoria.    ) , (21 z y Az y )) , ( ), , ( ( 21 21 21 z x f y x f Ax      ) , ( ( 2 1 v u A x v u ))) , ( ), , ( ( 2 1 2 1 2 1 z x f y x f A 21 4 LOGICA E ALGEBRA 24 LUGLIO 2015 Parte di Algebra Esercizio 1 Sia no dati l’insieme X = a, b, c, d, e, f e la relazione binaria R su X rappresentata dal seguente grafo di i ncidenza: a b c e f d a) Si provi che non esiste nessuna relazione d’ordine su X contenente R. b) Si determini un sotto insieme massimale Y di X tale che la relazione R ristrett a ad Y sia contenuta in una relazione d’ordine S su Y e si determini tale relazione S. c) Si trovi la relazion e d’equivalenza ρ generata da R e si determini l’insieme quoziente X / ρ . d) Si stabilisca se ρ coincide con la chiusu ra riflessiva e simmetrica di R. e) Mostrare che non esistono funzioni da X ad X né contenenti R né contenute in R. Esercizio 2 Si consider ino l’anello delle matrici quadrate di ordine 2 ad elementi in Z ed il suo sottoinsieme A così definito: A = , dove Z è l’insieme dei numeri interi. a) Si mostri che A è un anello rispetto alle usual i operazioni di addizione e moltiplicazione di matrici. b) Si stabilisca se il seguente sottoinsieme di A è un suo ideal e: B = c) Si mostri che la funzione f: A  Z definita nel seguente modo A f = a è un epi morfismo dell’anello A nell’anello Z . d) Si determin i la ker f - classe di 0 e si stabilisca se si tratta di un ideale di A. e) Si dica se A / ker f è isomorfo a Z . 3            3 , , 0 Z c b a c b a              0 , , , 0 3 c a Z c b a c b a 3      c b a 0           c b a 0 3 3 5 Traccia di soluzione Esercizio 1 a) La relazione R non è antisimmetrica in quanto (e,f) R ed (f,e) R. Ogni relazione contene nte R non è quindi antisimmetrica e perciò non può essere d’ordine. b) Un sottoinsieme massimale Y di X tale che la relazione R ristretta ad Y sia contenuta in una relazione d’ordine S su Y non può quindi contenere entrambi gli elementi e ed f. Possiamo perciò prendere Y={a,b,c,d,e}. La relazione R ristretta ad Y è allora formata da {(d,b),(b,a),(d,c),(c,a )}. La sua chiusura riflessiva e transitiva è allora {(d,b),(b,a),(d,c),(c,a),( a,a),(b,b),(c,c),(d,d),(e,e),( d,a)} ed è una relazione d’ordine perché è anche antisimmetrica . c) Dal grafo di incidenza di R si ottiene subito che la relazione d’equivalenza gene rata da R ha il seguente grafo di incidenza: a b c e f d e quindi la seguente matrice di incidenza Le -classi sono allora a = {a,b,c,d} = b = c = d, e = {e,f} = f, l’insieme quoziente X/  è dunque { a,e}. d) La chiusura riflessiva e simmetrica di R non coincide con  in quanto né la coppia (b, c) né la coppia (a,d) appartengono a tale relazione. e) In R nessun elemento è associato ad a e quindi in ogni relazione contenuta in R non ci sono elementi associati ad a, pertanto non ci sono funzioni contenute in R. I noltre in R l’elemento d è associato sia all ’elemento b sia all’elemento c quind i (d,b) e (d,c) appartengono ad ogni relazione che contenente R, per tanto non ci sono funzioni che contengono R. Esercizio 2 a) E’ noto che l’insieme delle matrici quadrate di uno stesso ordine n su un campo formano un anello rispetto alle usuali operazioni di somma e prodotto di matrici, quindi in particolare l’insieme M 2(Z 3) delle matrici quadrate di ordine 2 su Z 3 è un anello, pertanto per dimostrare 1 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 6 che l’insieme A = è un anello basta dimostrare che è un sottoanello di M 2(Z 3). Siano quindi A 1 = e A 2 = due generici elementi di A, si ha subito che A 1–A2= A, e A 1A2 = A, essendo ovviamente a-d, b-e, c-f, ad, bd+ce, cf elementi di Z 3, pertanto il criterio di sottoanello è soddi sfatto ed A è un anello. b) L’insiem e B non è un ideale di A infatti se pr endiamo la matrice B 1 = B e la matrice B 2 = B, si ha B 1B2= B (quindi B non è neppure un sottoanello, in quanto non è chiuso rispetto al prodotto). c) La funzione f:A  Z3 definita da f = a è ovviamente suriettiva in quanto ogni aZ3 proviene ad esempio dalla matrice . Verifichiamo che è un omomorfismo di anelli. Si ha f = f = a +d f + f = a +d , quindi f = f + f . A nalogament e f = f = ad f f = a d, quindi f = f f .            3 , , 0 Z c b a c b a     c b a 0     f e d 0        f c e b d a 0      cf ce bd ad 0     ]1[ 0 ]2[ b     ]2[ 0 ]1[ b     ]2[ ]2[ 0 ]2[ b           c b a 0     0 0 0 a               f e d c b a 0 0              f c e b d a 0           c b a 0           f e d 0               f e d c b a 0 0           c b a 0           f e d 0               f e d c b a 0 0            cf ce bd ad 0           c b a 0           f e d 0               f e d c b a 0 0           c b a 0           f e d 0 7 pertanto f conserva somma e pr odotto ed è un omomorfismo. E ssendo una applicazione suriettiva è un epimorfismo. d) La ker f classe dello 0 è formata da tutte e sole le matrici di A che hanno mediante f la stessa immagine della matrice nulla è quindi è formata da tutte e sole le matrici della forma con b ,cZ3. E’ noto che ker f è una relazione di congruenza su A (anell o) e che la R-classe di equivalenza dell o zero di un anello quando R è una congruenza dell’anello è un ideale, quindi la ker f classe dello zero di A è un ideale. Si poteva anche fare una verifica diretta. Siano e due elementi della ker f classe dello zero, la loro differenza sta ancora nella ker f classe dello zero, inoltre per ogni A e per ogni nella ker f classe dello zero, si ha = e = appartenenti alla ker f classe dello zero. E’ così verificato il criterio di caratterizzazione degli ideal i. e) Sappiamo dal t eorema di fattorizzazione degli omomorfismi che per ogni omomorfismo f di un ane llo A in un anello B esiste un omomorfismo iniettiv o g di A/ker f in B. Inoltre se f è un epimorfismo g diventa un isomorfismo. Nel nostro caso c’è un epimorfismo f da A a Z 3 e dunque c’è un isomorfismo di A/ker f su Z 3.     c b 0 0     c b 0 0     e d 0 0       e c d b 0 0     c b a 0     e d 0 0     c b a 0     e d 0 0     ce cd 0 0     e d 0 0     c b a 0      ce eb da 0 0 8 LOGICA E ALGEBRA 24 LUGLIO 2015 Prova di Laboratorio “Siano R ed S due relazioni binarie simmetriche su un insieme X. Allora RS è una relazione simmetrica se e solo se R ed S commutano fra loro.” Formalizzare il ragionamento in un linguaggio del I ordine e scrivere un programma SPASS per verificare la tesi. Traccia di soluzione Il dominio è X, R ed S sono predicati di arità 2. Per dire che R ed S sono simmetriche possiamo scrivere xy(R(x,y)  R(y,x) ) e xy(S(x,y)  S(y,x) ). Si ricorda che l a relazione RS è definita nel s eguente modo (x,y) RS se e solo se esiste z tale che (x,z) R e (z,y) S quindi per il momento scriviamo RS(x,y) come forma abbreviata per z(R(x,z) S(z,y)). Analogamente scriviamo SR(x,y) come forma abbreviata per z(S(x,z) R(z,y)). Di nuovo possiamo scrivere che RS è simmetrica nella forma xy(RS(x,y)  RS(y,x) ) che in forma estesa diventa xy(z(R(x,z) S(z,y))  v(R(y,v) S(v,x))). Possiamo scrivere che R ed S sono permutabili nella forma xy(RS(x,y)  SR(x,y)) che in forma estesa diventa xy(z(R(x,z) S(z,y))  v(S(x,v) R(v, y))). Ora i l nostro enunciato corrisponde nel provare che dalle due premess e: xy(R(x,y)  R(y,x)) , xy(S(x,y)  S(y,x)) } segue la congettura seguente: xy(z(R(x,z) S(z,y))  v(R(y,v) S(v,x)))  ( xy(z(R(x,z) S(z,y))  v(S(x,v) R(v,y))) ). Tralasciando le descriptions e limitandoci alla sola parte di Logica il nostro problem a nella sintassi di SPASS diventa : list_of_symbols. predicates[(R,2),(S,2)]. end_of_list. list_of_formulae(axioms). formula(forall([x,y],implies(R(x,y),R(y,x)))). formula(forall([x,y],implies(S(x,y),S(y,x)))). 9 end_of_list. list_of_formulae(conjectures). formula(equiv( forall( [x,y],implies( exists([z],and(R(x,z),S(z,y))), exists([ v],and(R(y, v),S( v,x))) )), forall([x,y],equiv( exists([z],and(R(x,z),S(z,y))), exists([ v],and(S(x, v),R( v,y))) )) )). end_of_list.