Computer Engineering - Logica e Algebra

Full exam

LOGICA E ALGEBRA 20 febbraio 2018 Esercizio 1 Sull’insieme Z×Z si consideri la relazione R definita come segue (a,b ) R (c,d ) se e solo se a c (mod 3) e b d (mod 5) Si d imos tri che R è una relazione d’ equivalenza e si determinino gli elementi dell’insieme quoziente . Descrivere in un opportuno linguaggio del primo ordine (specificando l’alfabeto usato e l’interpretazione usata) la relazione di congruenza a c (mod 3) interpretata dalla lettera predicativa C(a,c). Esercizio 2 Si a A l’insieme delle matrici quadrate di ordine 2 sul campo reale della forma Si provi che A, rispetto alle usuali operazioni di somma e prodotto di matrici , è un anello non commutativo privo di unità. Esercizio 3 Si consideri la formula Si dica se è un teorema di L e poi si provi il risultato trovato utilizzando la risoluzione. Esercizio 4 Si consideri la formula del primo ordine ) e l’interpretaz ione avente come dominio i reali R ed in cui la lettera predicativa B è interpretata come la relazione di uguaglianza, mentre A è la relazione di minore stretto < tra reali, e è la funzione esponenziale e x. Si dica se in tale interpretazione la formula è vera, falsa, soddis facibile . Quali proprietà sono richieste ad una funzione f generica affinché soddisfi la precedente formula? La formula è logicamente valida? GIUSTIFICARE OGNI RISPOSTA Traccia Soluzione Esercizio 1 Dobbiamo verificare che la relazione sia:  riflessiva: (a,b) R (a,b) dato che a a (mod 3) e b b (mod 5) per la riflessività della relazione di congruenza modulo n;  simmetrica: se (a,b) R (c,d), allora a c (mod 3) e b d (mod 5), da cui segue (c,d) R (a,b) per la simmetria della relazione di congruen za modulo n;  transitiva: se (a,b) R (c,d) e (c,d) R (e,f) allora a c (mod 3), b d (mod 5) e c e (mod 3), d f (mod 5), da cui segue a e (mod 3) e b f (mod 5) per la transitività della relazione di congruenza modulo n . Quindi (a,b) R (e,f). La classe di equ ivalenza di una generica coppia (a,b) è compos ta da tutte le coppie (x,y) tali che a x (mod 3) e b y (mod 5), in formule: Un insieme di rappresentanti le cui classi sono disgiunte è (i,j) con i = 0, 1, 2 e j = 0, 1, 2, 3, 4 quindi ci sono quindici classi d’equivalenza . Per descrivere la congruenza modulo 3, ci poniamo nel dominio degl i interi Z, dove abbiamo bisogno di una costante c che interpreta il numero “3”, di una lettera predicativa binaria D(x, y) che interpreta la relazione di divisibilità “x divide y” e di una lettera funzionale binaria f(x, y) che interpreta la funzione che ad ogni coppia (x,y) associa la lor “ x – y” . Quindi la formula è ) Esercizio 2 Dato che A è un sottoinsieme dell’anello M(2, R) delle matrici 2x2 su l campo reale, per verificare che A è un anello è sufficiente dimostrare che sia sottoanello di M(2, R), cioè basta dimostrare che valgono i seguenti fatti:  per ogni M, N matrici di A, M – N è ancora una matrice d ell’insieme A ;  per ogni M, N matrici di A, il prodotto righe per colonne MN è ancora una matrice dell’insieme A . Sia , allora . Segue che la prima condizione è soddisfatta dato che c – a, d – b sono entrambi numeri reali. Sia , allora . Segue che la seconda condizione è soddisfatta d ato che ac, ad sono entrambi numeri reali. Quindi A è un sottoanello dell’anello delle matrici 2x2 a coefficienti reali e pert anto è un anello. A n on possiede identità, infatti se esistesse un’identità , cioè una matrice E tale che, per ogni avessimo , allora dovrebbero essere valide le seguenti uguaglianze ax = a e a y = b, bx = b per ogni a, b numeri reali. Da questa equazione deduciamo che necessariamente x = 1, ma il problema è l’equazione ay = b. Infatti, non esiste nessun numero reale fissato y che soddisfi ay = b per tutti i numeri reali a, b. Mos triamo che A non è commutativo. Infatti , ad esempio, Esercizio 3 Per il teorema di correttezza e completezza per la teoria L, abbiamo che la formula assegnata è un teorema della teoria L se e solo se è un tautologia. Ragion ando per assurdo, supponiamo che esi sta un assegnamento v che renda falsa la precedente formula. Segue che tale asseg namento renderà falsa e renderà vera . Quindi necessariamente v (A) = 1 e v(C) = 0 da cui segue che v(B) = 1 altrimenti la formula sareb be falsa . Ma allora v non è un modello di e quindi v non è modello per . Ciò è assurdo q uindi la formula di partenza è una tautologia. Verifichiamo il precedente risultato usando la risoluzio ne. Sappiamo che per verificare se una formula è una t autologia basta dimostrare che la sua negata è insoddisfacibile. Quindi usando il teorema di correttezza e completezza per refutazione basta verificare che dalle clausole derivanti dalla formula si possa ricavare la clausola vuota. Le clausole che si ottengono sono , da cui Esercizio 4 La formula ) è vera in quanto la funzione esponenziale è una funzione strettamente monotona crescente quindi l’antecedente è vero , inoltre la funzione esponenziale è anche iniettiva e quindi è vero anche il consegunte . Essendo la formula vera , essa è anche soddisfa cibile e non è falsa . Una lettera funzionale generica non deve soddisfare p articolari proprietà affinché la precedente formula sia vera (se non si cambia l’interpretazione dei restanti simboli). La formula non è logicamente valida, infatti basta cambiare l’interpretazione della lettera predicativa facendo sì che interpret i la relazione di . Allora per esempio interpretando com e la funzione costante f(x)=1, si ha che l’antecende è vero, essendo f(x)=1 monotona, ma non è iniettiva, quindi il conseguente è falso.