Computer Engineering - Logica e Algebra

Full exam

LOGICA E ALGEBRA 26 luglio 2018 Esercizio 1 Sia X = {1 , 2, 3, 4, 5} e sia R  X  X la relazione avente la matrice di incidenza M quadrata di ordine 5 con tutti gli elementi nulli tranne m 11 = m 12 = m22 = m 34 = m 54 = 1 e m21= k ∊ {0,1}. a) Si mostri che R è una relazione transitiva su X. b) Al variare di k ∊ {0,1} si determini, se esiste , una relazione d’ordine T su X che contenga R. In caso affermativo la si costruisca e si determinino gli elementi massimali e minimali di X rispetto a T. c) Nel cas o k = 1 si determini la relazione d’equivalenza S generata da R e si descriva X / S. Si stabilisca se S coincide con la chiusura riflessiva e simmetrica di R. Esercizio 2 Sia f (A,B,C) l a f.b.f. avente la seguente tavola di verità: A B C f (A,B,C ) _________________________________________ 1 1 1 1 1 1 0 0 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) Dire se esiste nella teoria L una deduzione di C  f (A,B,C) dall’insieme { A, B}. b) Provare il risultato ottenuto al punto precedente utilizzando la risoluzione. Esercizio 3 a) Si scriva in un opportuno linguag gio del primo ordine la seguente proposizione : « Due numeri interi sono congrui a zero modulo n se e solo se lo è la loro somma » Attenzione : oltre ai connettivi, le variabili, i quantificatori e le parentesi, s i usi solo una lettera predicativa U per la relazione di uguaglianza, una costante per denotare l’intero n, due lettere funzionali S e P per le operazioni di addizione e moltiplicazione tra interi . b) Si stabilisca se la formula ottenuta è vera nell’interpretazione assegnata e se è logicamente valida. c) Sia, ora, A = Z n l’anello degli interi modulo n ed a un suo elemento. Si v erifichi che l’insieme H a = {x ∊ A | x · a = [0] n} è un sottoanello di A. E’ anche un suo ideale? TRACCIA DI SOLUZIONE Esercizio 1 a) Si osservi che la matrice d’incidenza di R è la seguente Calco lando la relazione R2 si ottiene la matrice Si può osservare che sia per k = 0 che per k = 1 R2 è contenuta in R e perc iò R è transitiva per ogni k. b) Si osservi poi che per k = 1 R non è antisimmetrica e perciò non può esistere la relazione d’ordine T che contenga R. Per k = 0 R è antisimmetrica, controlliamo se esiste la rel azione d’ordine T contenente R: calcol ando la chiusura riflessiva e transitiva di R , se questa è ancora antisimmetrica , sarà la relazione T richiesta. La chiusura r iflessiva e transitiva di R corrisponde alla sua chiusura riflessiva in quanto R è transitiva e chiudendo riflessivamente non si perde tale la transitività . Perciò la chiusura riflessiva e transitiva di R avrà la seguente matrice d’incidenza dalla quale si evince che conserva l’antisimmetria. Tale matrice è pertanto la matrice d’incidenz a della relazione T cercata il cui diagramma di Hasse è 2 4 1 3 5 Gli elementi massimali d i X rispetto a T sono pertanto 2 , 4; gli elementi minimali sono 1, 3, 5. c) Si consideri ora la relazione R nel caso k = 1. Costruendo la chiusura riflessiv a, simmetrica e transitiva di R si ottiene la seguente matrice che risulta essere la matrice d’incidenza della relazione d’equivalenza S generata da R. Le classi di equivalenza sono [ 1]S = { 1, 2 } e [3]S = { 3, 4, 5 } e l ’insieme quoziente è X / S = { [1]S, [3]S}. La chiusura riflessiva e simmetrica di R presenta invece la seguente matrice d’incidenza : e non coincide pertanto con S. Esercizio 2 a) Esiste la deduzione {A, B} |- L C  f (A,B,C) se e solo se, per il teorema di correttezza e completezza forte, vale la deduzione semantica {A, B} |= C  f (A,B,C) . Pertanto basta verificare che i modelli di {A, B} sono modelli anche per C  f (A,B,C) . I modelli di {A, B} sono le interpretazioni v 1 e v 2 tali che v1(A) = v1(B) = v1(C) = 1, v2(A) = v2(B) = 1, v2(C) = 0 che risultano essere modell i anche per C  f (A,B,C) . Segue che la deduzione {A, B} |- L C  f (A,B,C) esiste. b) L’insieme {A, B} gen era le clausole { A}, { B}. Scriviamo in forma a clausole la negazione di C  f (A,B,C) : Si ottengono così le clausole . Scriviamo la derivazione per risoluzione della clausola vuota: 1) {A} (clausola di input ) 2) (clausola di input ) 3) (risolvente di 1) e 2) ) 4) {B} (clausola di input ) 5) (risolvente di 3) e 4 )) 6) {C} (clausola di input ) 7) □ (risolvente di 5) e 6 )) Esercizio 3 a) La form ula richiesta è la seguente: , dove b è la costante che interpreta il numero n. b) La formula trovata non è vera in quanto se la somma di due interi è congrua a zero modulo n non è detto che ciascu no dei due numeri lo sia. Infatti se, ad esempio, x = n + 1, y = n – 1, allora x + y = 2n e quindi x + y ≡ 0 ( mod n) ma x ed y non sono congrui a 0 modulo n (si ricordi che per poter definire la relazione di congruenza modulo n occorre prendere n > 1 ). Segue immediatamente che la formula non può essere logicamente valida in quanto già non è vera nella precedente interpretazione. c) Siano . Valgono: e pertanto . Da l criterio di car atterizz azione dei sottoanelli segue che è un sottoanello di A. Inoltre è anche un ideale poiché , presi due generici elementi , risulta e quindi . ) ( ) ( ))) ( ) (( ( ))) ( ) (( ( )))) ( ) (( ) (( ( ))) ( ) ( ) (( ( )) , , ( ( C B C B A C C B C B A C C B C B A C C B A A C B A C C B A C B A C B A C C B A f C                                               } , {}, , , {}, { C B C B A C    } , , { C B A    } , { C B   } { C ))) ,( ), , ( ( )) , ( , ( )) , ( , ( ( bz P y x S Uz b k P y Uk bh P x Uh y x       aH y x  , n n n a y a x a y x ]0[ ]0[ ]0[ ) (          n n x a y x a y x ]0[ ]0[ ) ( ) (         a a H y x H y x     , aH aH A z H x a   , n n z z a x a z x a x z ]0[ ]0[ ) ( ) ( ) (            a a H x z H z x     ,