Computer Engineering - Logica e Algebra

Full exam

LOGICA E ALGEBRA 5 luglio 2018 Esercizio 1 Sia R la relazione binaria sull’insieme {a; b; c; d; e; f} definita nel seguente modo: R = {( b, a); ( b, d); ( c, d); ( c, e); ( c, f); ( d, a); ( d, e); ( f, a)} a) Stabilire se R è antisimmetrica e se è una relazione d'ordine. b) Verificare se esiste una relazione d'ordine che contiene R. c) Sia S la più piccola relazione d'ordine contene nte R. Costruire il diagramma di Hasse di S e determinare se S ammette massimo e/o minimo , elementi massimali e/o elem enti minimali . d) Determinare il diagramma di Hasse di una relazione d'ordine totale contenente S. e) Dimostrare che non es istono funzioni contenute in R né funzioni contenenti R. Esercizio 2 Sia f(A,B,C) una f.b.f che assume i seguenti valori di verità: A B C f (A, B, C ) ___________________________________ 1 1 0 0 1 0 1 1 0 1 1 1 0 1 0 1 0 0 1 1 0 0 0 1 a) Si completi la tavola di verità di f(A,B,C) in modo tale che dall’insieme di f.b.f. { AB, B C} non si deduca f(A,B,C) ma da f(A,B,C) si deduca A  C. b) Si scriva la formula ottenuta f(A ,B,C) utilizzando solo i connettivi e  . c) Si verifichi usando la risoluzione che da { AB, B C} non si deduce f(A,B,C) . Esercizio 3 Sia f : N → N la funzione così definita: dove N è l’insie me dei numeri naturali. a) Dimost rare che f è un m onomorfismo di (N, +) in (N , ·). E’ anche un isomorfismo? b) Tradurre in un opportuno linguaggio del primo ordine la seguente frase: “Se g è un omomorfismo da (N, +) ad (N, +) , allora la funzione composta g · f è un omomorfismo da (N, +) ad (N, ·) ” Il dominio da considerare dev’essere l’insieme dei numeri naturali N e le due funzioni f e g devono essere interpretate da due lettere funzionali di arità 1. c) Si porti la formula trovata in forma normale prenessa e po i in forma di Skolem. d) Si stabilisca se la formula trovata è logicamente valida. GIUSTIFICARE OGNI RISPOSTA    x x f N x 2 ) (    TRACCIA DI SOLUZIONE Esercizio 1 a) La relazione R è antisimmetrica in quanto, presi due generici elementi x, y dell’insieme {a; b; c; d; e; f} , se allora non accade mai che anche . R non è una relazione d’ordine in quanto non è né riflessiva (ad esempio ) né transitiva (ad esempio ma ). b) Essendo R antisimmetrica potrebbe esistere una relazione d’ordine contenente R. Costruiamo la chiusura riflessiva R’ di R: R’ = R  {(a, a); (b, b); (c, c); (d, d); ( e, e); (f, f)} e la chiusura transitiva T di R’: S = R’  {(b, e); (c , a)}. S risulta essere ancora antisimmetrica e quindi è una relazione d’ordine (la minima) contenente R. c) La relazione S costruita al passo precedente è la minima relazione d’ordine contenente R ed è definita nel seguente modo: S = {(b, a);(b, d);(c, d); (c, e);(c, f);(d, a);(d, e); (f, a);(a, a);(b, b); (c, c);(d, d);(e, e);(f, f);(b, e);(c, a)}. Il diagramma di Hasse di S è quello rappresentato a lato dal quale si evince che l’insieme degli elementi minimali è {b; c}, quello degli elementi mass imali è {a; e} mentre non esistono massimo né minimo. d) Un esempio di relazione d’ordine totale contenente R è quella avente come diagramma di Ha sse quello rappresentato a lato con tutti gli elementi allineati. e) Non esistono funzioni contenute in R perché, ad esempio, non c’è nessuna coppia del tipo (a, x) che appartiene ad R, al variare di x in {a; b; c; d; e; f} . Non esistono funzioni contenenti R perché, ad esempio, e quindi ogni altra relazione contenente R co nterrebbe queste due coppie, non rispettando così la definizione di funzione. Esercizio 2 a) Affinché dall’insieme di f.b.f. { AB, B C} non si deduca f(A,B,C) è necessario che almeno un modello dell’insieme di f.b.f. non sia modello pe r f(A,B,C). I modelli di { AB, B C} sono le interpretazioni v e v’ tali che v(A) = v(B) = v(C) = 1 e v’(A) = 0, v’(B) = v’(C) = 1. Osserviamo che v’(f(A,B,C )) = 1, quindi bisogna imporre la condizione che v(f(A,B,C )) = 0. Affinché da f(A,B,C) si possa dedu rre A  C è necessario che tutti i modelli di f(A,B,C) siano modelli per A  C. Le uniche interpretazioni che non sono modelli per A  C sono w e w’ tali che w(A) = R y x ) , ( R x y ) , ( R a a ) , ( , ) , ( R d b  R e d ), ( R e b ),( , ) , ( R a b  R d b ) ,(   = w(B) = 1, w(C) = 0 e w’ (A) = 1, w’ (B) = w’ (C) = 0. Poiché vale già che w(f(A,B,C )) = 0, è sufficiente imporre la condizione che w’ (f(A,B,C )) = 0. Pertanto la tavola di verità di f(A,B,C ) è la seguente: A B C f (A, B, C ) ___________________________________ 1 1 1 0 1 1 0 0 1 0 1 1 1 0 0 0 0 1 1 1 0 1 0 1 0 0 1 1 0 0 0 1 b) c) Trasformiamo in forma a clausole le formule dell ’insieme { AB, B C} e la negazione di f(A,B,C) :  da AB si ottiene la clausola { A,B};  da BC si ot tengono le clausole {B}, { C};  Da si ottengono le clausole . L’insieme delle clausole di input è S ={ { A,B};{B};{C}; } e si verifica subito che Ris( S) = S . Poiché la clausola v uota non appartiene a Ris( S) segue che da { AB, B C} non si può dedu rre f(A,B,C) . Esercizio 2 a) Dimostriamo innanzitutto che f è un om omorfismo di (N, +) in (N , ·) cioè che , per ogni vale Risulta che: e pertanto f è un omomorfismo. f risulta essere un mon omo rfismo se è anche iniettiva. Siano tali che Allora e quindi x = y . Segue che f è in iettiva e pertanto è un monomorfismo. f risulta essere un isomo rfismo se è un omomorfismo iniettiv o e suriettivo. Ma f non è un ’applicazione suriettiva in quanto, ad esempio, non esiste alcun tale che Pertanto f non è un isomorfismo.              ) ( ) ( ) ( ) , , ( C B A C B A C B A C B A f ) ( ) ( ) ( )) ( )) (( )) ( ( )) ( )) ( (( )) ( ) ( ) (( B C A C B A C B A C B B B A C B B A C B C C B A C B C B C B A                                                 ) , , ( C B A f ) ( ) ( )) ( ( C B A C B A C B A             ) , , ( C B A f  } , { }, { C B A   } , { }; { C B A   , , N y x  ). ( ) ( ) ( y f x f y x f    ) ( ) ( 2 2 2 ) ( y f x f y x f y x yx        N y x  , ). ( ) ( y f x f  y x 2 2  N x .3 ) (  x f b) Sia la lettera predicativa che inte rpreta la relazione di uguaglianza e siano la lettera funzional e che interpreta la funzione f, la lettera funzion ale che interpreta la funzione g , la lettera funzion ale che interpreta l ’operazione di addizione e la lettera funzion ale che interpreta l ’operazione di moltiplicazione. La f.b.f. F della logica del primo ordine che traduce la frase assegnata è la seguente: c) La forma normale prenessa della f.b.f. F trovata al punto b) è la se guente: La forma di Skolem di F è la seguente: dove a, b sono costanti. d) La formula F trovata al punto b) non è logicamente valida. Infatti l ’affermazione “se g è un omomorfismo da (N, +) ad (N, +) , allora la funzione composta g · f è un omomorfismo da (N, +) ad (N, ·)” risulta vera quindi la F risulta vera nell ’interpretazione assegnata all ’inizio. La f.b.f. F risulta falsa invece nell ’interpretazione in cui la lettera predicativa inte rpreta sempre la relazione di uguaglianza, la lettera funzional e interpreta ancora la funzione f assegnata all ’inizio ma la lettera funziona le interpreta una funzione h che risu lta essere un omomorfismo di (N, ·) in (N, ·) , la lettera funzionale interpreta l ’operazione di moltiplicazione e la lettera funzion ale interpreta l’operazione di addizione . Infatti l ’anteceden te di F risulta vero in questa nuova interpretazione in quanto si traduce in “per ogni ”, affermazione vera essendo h un omomorfismo di (N, ·) in (N, ·) . Il cons egu ente di F invece r isulta falso in questa nuova interpretazione in quanto si traduce in “per ogni ”, cioè “per ogni vale ”. Quest ’ultima affermazione è falsa poiché in generale . Pertanto la f.b.f. F risulta falsa nella nuova interpretazione e quindi non può essere logicamente valida. 21A 11f 12f 21f 22f )))). ( ( )), ( ( ( ))), , ( ( ( ( ))) ( ), ( ( )), , ( ( ( 12 11 12 11 22 21 12 11 21 12 12 21 21 12 21 y f f x f f f y x f f f Ay x y f x f f y x f f Ay x      ))))).( ( )), ( ( ( ))),,( ( ( ( ))) ( ), ( ( )), , ( ( ( ( 12 11 12 11 22 21 12 11 21 12 12 21 21 12 21 t f f z f f f tz f f f A y f x f f y x f f A t z y x      ))))),( ( )), ( ( ( ))),,( ( ( ( ))) ( ), ( ( )), , ( ( ( ( 12 11 12 11 22 21 12 11 21 12 12 21 21 12 21 t f f z f f f tz f f f A b f a f f b a f f A t z    21A 11f 12f 21f 22f , , N y x  ) ( ) ( ) ( y h x h y x h    , , N y x  )) ( ( )) ( ( )) ( ( y h f x h f y x h f    , , N y x  )( )( ) ( 2 2 2 yh xh yxh      )( )( )( )( )()( ) ( 2 2 2 2 2 yh xh yh xh yhxh yxh      