Computer Engineering - Logica e Algebra

Full exam

LOGICA E ALGEBRA 2 febbraio 2015 PARTE DI ALGEBRA Esercizio 1 1) Si consideri l’insieme X = a,b,c,d,e,f  e la relazione R sull’insieme X così definita : R = (a,d), (b,a), (c,a), (d,d)  . a) Si costruisca la relazione d’equiv alenza S generata da R e se ne deter minino le classi d’equivalenza. b) Si consideri la chiusura riflessiva e transitiva R* di R e s i dica se R* è una relazione d’ordine su X . In caso affermativo si indichino gli elementi massimali, minimali, ma ssimi e minimi di X rispetto a R* e si dica se X rispetto a R* è un reticolo. In caso negativo si dica se esiste un sottoinsi eme Y di X tale che Y rispetto a R* sia un reticolo . c) Si consideri infine la chiusura simmetrica T di R* e si dica se coincide con la relazione d’equivalenza generata da R*. Esercizio 2 Sia ( A, +, · ) un anello unitario . Si consideri l’operazione ◦ su A così definita : a ◦ b = a + b + a · b a) Si provi che ( A, ◦ ) è un monoide . b) Si consideri l’applicazione f : A  A definita ponendo , per ogni a ϵ A, f (a) = a + 1. Si provi che f è un isomorfismo tra il monoide ( A, ◦ ) e il monoide ( A, · ). c) ( A, +, ◦ ) è un anello unitario ? GIUSTIFICARE OGNI RISPOSTA A b a   , Traccia di soluzione della parte di Algebra Esercizio 1 a) Rappresentiamo R attraverso il suo grafo di incidenza: a● ● b e ● c ● ● d f ● di conseguenza la relazione d’equivalenza S generata da R ha il seguente grafo d’incidenza: a● ● b e ● c ● ● d f ● Le classi di equivalenza di S sono le seguenti: [ a ] S = { a, b, c, d } [ e ] S = { e } [ f ] S = { f } b) La chiusura riflessiva e transitiva R* di R ha il seguente grafo di incidenza: a● ● b e ● c ● ● d f ● da cui si evince che R* è una relazione d’o rdine in quanto è riflessiva e transitiva per costruzione ed inoltre è antisimmetrica in quanto da ogni vertice esce al più un arco. Dal diagramma di Hasse di R* a lato si vede che gli elementi massimali sono d, e, f mentre i minimali sono b, c, e, f. Non esistono né massimo né minimo di X rispetto ad R* . (X, R*) non è un reticolo in quanto, ad esempio, non esiste inf{e, b}. Posto Y = {a, d, c}, risulta che Y è un sottoinsieme di X e che (Y, R*) è un reticolo in quanto, per ogni coppia di elementi di Y, e sistono inf e sup. c) La chiusura simmetrica T di R* ha il seguente grafo di incidenza: a● ● b e ● c ● ● d f ● da cui risulta evidente che T non coincide con la relazione d’equivalenza generata da R* in quanto T non è transitiva (c T a, a T b ma c non è in relazione con b). Esercizio 2 a) Proviamo che ◦ è associativa. Siano , allora: (a ◦ b ) ◦ c = (a + b + a · b) ◦ c = a + b + a · b + c + (a + b + a · b) ∙ c = a + b + a · b + c + a ∙ c + b ∙ c + a · b ∙ c a ◦ ( b ◦ c ) = a ◦ (b + c + b · c) = a + b + c + b · c + a ∙ (b + c + b · c) = a + b + c + b · c + a ∙ b + a ∙ c + a · b ∙ c Poiché abbiamo dimostrato che (a ◦ b ) ◦ c = a ◦ ( b ◦ c ) si ha che ◦ è associativa. L’element o neutro rispetto a ◦ è lo 0, infatti, per ogni , a ◦ 0 = a + 0 + a · 0 = a = 0 ◦ a. Segue che ( A, ◦ ) è un monoide. b) Proviamo che f è un omomorfismo. Siano , allora: f ( a ◦ b ) = f ( a + b + a · b) = a + b + a · b + 1 f ( a) · f ( b) = (a + 1) · (b + 1 ) = a · b + a + b + 1 Poiché f ( a ◦ b ) = f ( a) · f (b) si ha che f è un omomorfismo . Dimostriamo che f porta l ’unità di ( A , ◦ ) , cioè l’elemento 0, nell ’unità di ( A , · ) , cioè l’elemento 1: f ( 0) = 0 + 1 = 1 Possiamo pertanto concludere che f è un omomorfismo di monoidi. Proviamo, ora, che f è biunivoca. Siano tali che f (a) = f (b). Allora a + 1 = b + 1 e quindi a = b, pertanto f è iniettiva. Sia , allora, posto b = a – 1, risulta f ( b) = b + 1 = a – 1 + 1 = a, pertanto f è suriettiva. Possiamo così concludere che f è un isomorfismo tra i monoidi ( A , ◦ ) e ( A , · ) . c) Sa ppiamo per ipotesi che ( A, +, · ) è un anello quindi ( A, + ) è un gruppo commutativo. Abbiamo già dimostrato che ( A, ◦ ) è un monoide quindi per vedere se ( A, +, ◦ ) è un anello resta da provare che valgono le proprietà distributive di ◦ rispetto a +. Siano , allora: (a + b ) ◦ c = a + b + c + (a + b) · c = a + b + c + a · c + b ∙ c a ◦ c + b ◦ c = a + c + a · c + b + c + b · c = a + 2c + a · c + b + b · c Poiché ( a + b ) ◦ c ≠ a ◦ c + b ◦ c si ha che non valgono le proprietà dist ributive di ◦ rispetto a + e quindi ( A, +, ◦ ) non è un anello . A c b a  , , A a A b a  , A b a  , A a A c b a  , , LOGICA E ALGEBRA 2 febbraio 2015 PARTE DI LOGICA Esercizio 1 Data 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 0 0 1 1 1 0 1 0 1 0 0 1 0 0 0 0 0 a) Scrivere una formula f (A,B,C) che ammetta la tavola di verità data e contenga solo i connettivi  e  . b) Scrivere una formula g(A,B ,C) che non sia una tautologia, che sia deducibile da f (A,B,C) ma non ad essa equivalente. c) Dire se le due f. b. f. seguenti B  (f (A,B,C)  g(A,B,C)) (g(A,B,C)  f (A,B,C))  B sono teoremi di L. Esercizio 2 Si consideri la seguente formula A di un opportuno linguaggio del primo ordine. a) Si dica se l a formula A è vera, falsa, soddisfacibile ma non vera nell’interpretazion e che ha come dominio l’insieme Z dei numeri interi ed in cui la costante a sia da interpretare come lo 0, la costante b come 1 , la lettera predicativa sia da interpretare come l’uguaglianza e la lettera funzionale come l’ordinaria operazione di moltiplicazione . b) Si dica se A è una formula logicamente valida o logicamente contraddittoria. c) Si considerino la chiusura esistenziale e quella universale della formula A e se ne discuta la verità nella interpretazio ne data. d) Si porti la chiusura universale della formu la data in forma normale prenessa e poi in forma di Skolem. GIUSTIFICARE OGNI RISPOSTA )), ( , ( ))) , ( ), , ( ( ) , ( ) , ( ( 21 21 21 21 21 21 21 t n f x At h n f y x f A by A a y A h y        21A 21f Traccia di soluzione della parte di Logica Esercizio 1 a) Essendoci solo tre 1 nella tavola di verità di f (A,B,C) co nviene scrivere la forma normale disgiuntiva di f (A,B,C): f (A,B,C)  (A  B  C) (A  B  C) (A  B  C)  B  ((A  C)  (A  C)  (A  C))  B  ((A  C)  (A  (C  C)) )  B  ((A  C)  A )  B  ((A  A)  (C  A))  B  (C  A)  (B   (C  A))   (B  (A  C)) b) Affinché g(A,B,C) sia deducibile da f(A,B,C) è necessario che ogni modello di f(A,B,C) lo sia anche per g(A,B,C). Pertanto g(A,B,C) deve valere 1 nelle interpretazioni prima, terza, quarta, settima e ottava ass egnate nella tavola di verità di f(A,B,C) e può assumere un valore arbitrario sulle altre tre purché almeno uno sia non nullo (in quanto g(A,B,C) non può essere equivalente a f(A,B,C)). Una possibile formula g(A,B,C) allora è quella che vale 0 solo nella seconda interpretazione, cioè g(A,B,C)  A  B  C. c) Per il teorema di correttezza e completezza, le due formule assegnate sono teoremi della teoria L se e solo se sono tautologie. Il conseguente della formula B  (f (A,B,C)  g(A,B,C)) è sempre vero (in quanto g( A,B,C ) è conseg uenza semantica di f (A,B,C) ) e quindi si ha subito che la prima formula B  (f (A,B,C)  g(A,B,C)) è una tautologia e quindi un teorema della teoria L. La seconda formula (g(A,B,C)  f (A,B,C))  B non è invece una tautologia . Infatti l’antecedente è sempre vero (è la contronominale di f (A,B,C)  g(A,B,C) che è sempre vera) mentre il conseguente è falso in alcune interpretazioni. Pertanto (g(A,B,C)  f (A,B,C))  B non è un teorema della teoria L. Esercizio 2 a) Traduciamo la formula nell’interpretazione data: “Se esistono y, h ϵ Z tali che da y ≠ 0 e y ≠ 1 segue x ∙ y = n ∙ h , allora esiste t ϵ Z tale che x = n ∙ t ”. La sottoformula tradotta da “ esiste t ϵ Z tale che x = n ∙ t ” è soddisfacibile ma non vera in quanto è soddisfatta ad esempio prendendo x = 6, n = 3 e t = 2 ma non è soddisfatta ad esempio se x è minore di n. La sottoformula è soddisfacibile in quanto è soddisfatta, ad esempio, ponendo y = 0 in quanto il suo antecedente risul ta falso per tale assegnamento. Pertanto la formula è vera. Segue che la formula ha un antecedente vero e un conseguente solo soddisfacibile quindi riusulta essere soddisfacibile ma non vera . )) , ( ), , ( ( ) , ( ) , ( 21 21 21 21 21 h n f y x f A by A a y A    ))) , ( ), , ( ( ) , ( ) , ( ( 21 21 21 21 21 h n f y x f A by A a y A h y      )), ( , ( ))) , ( ), , ( ( ) , ( ) , ( ( 21 21 21 21 21 21 21 t n f x At h n f y x f A by A a y A h y        b) La formula non è né logicamente valida né logicamente contraddittoria in quanto nell’interpretazione assegnata è soddisfacibile ma non vera. c) La chiusura esistenziale della formula data è la seguente : e risulta vera nell’interpretazione data in quanto chiusura esistenziale di una formula soddisfacibile. La chiusura universale della formula data è la seguente : e risulta falsa nell’interpretazione data in quanto chiusura universale di una formula soddisfacibile. d) Portiamo la chiusura universale seguente in forma normale prenessa : Per scriverla i n forma di Skolem eliminiamo il quantificatore esistenziale e sostituiamo l’occorrenza di t con il termine : ))), ( , ( ))) , ( ), , ( ( ) , ( ) , ( ( ( 21 21 21 21 21 21 21 t n f x At h n f y x f A by A a y A h y n x          ))), ( , ( ))) , ( ), , ( ( ) , ( ) , ( ( ( 21 21 21 21 21 21 21 t n f x At h n f y x f A by A a y A h y n x          ))), ( , ( ))) , ( ), , ( ( ) , ( ) , ( ( ( 21 21 21 21 21 21 21 t n f x At h n f y x f A by A a y A h y n x          ))), ( , ( ))) , ( ), , ( ( ) , ( ) , ( (( 21 21 21 21 21 21 21 t n f x A h n f y x f A by A a y A t h y n x          t ) , , , (41 h y n x f )))). , , , ( , ( , ( ))) , ( ), , ( ( ) , ( ) , ( (( 41 21 21 21 21 21 21 21 h y n x f n f x A h n f y x f A by A a y A h y n x        