Computer Engineering - Logica e Algebra

Full exam

Logica ed algebra 27/7/2016 Parte di algebra Esercizio 1 Sia X = {a, b, c, d, e, f} e sia R  X  X la relazione con la seguente matrice di incidenza: 1. Determinare le proprietà di R. 2. Trovare la relazione di equivalenza  generata da R e determinarne le -classi. 3. Dire se esiste la minima relazione d’ordine T contenente R e in caso affermativo trovare , se esistono sup(c,d), inf(c,d), gli elementi massimali, minimali, massimi e minimi di X rispetto a T . 4. Dire se esistono funzioni contenute in R e funzioni c ontenute in T e , in caso affermativo , calcolare il loro numero. Esercizio 2 Sia A = {p (x) Z[ x] | p (2) = 0} , dove Z[x] è l’anello dei polinomi nell’indeterminata x. 1. Mostrare che A è un anello rispetto alle usuali operazioni di addizione e moltiplicazion e di polinomi. 2. Si provi che l’applicazione f : A  Z che manda ogni polinomio p(x) nel suo termine noto p0 è un omomorfismo fra anelli. E’ un epimorfismo? 3. Mostrare che la relazione   A  A definita da  p(x), q(x)  A (p(x), q(x))   se e solo se il te rmine noto di p(x) - q(x) è nullo è una relazio ne di congruenza su A e che A/  è isomorfo all’anello degli interi pari. MOTIVARE OGNI RISPOSTA TRACCIA DI SOLUZIONE Esercizio 1 1. R non soddisfa la proprietà seriale in quanto sulle ultime due righe no n è presente alcun 1, non soddisfa la proprietà riflessiva poiché sulla diagonale principale ci sono alcuni zeri, non soddisfa la proprietà simm etrica essendo la matrice di incidenza non simmetrica rispetto alla diagonale principale e non soddisfa l a propr ietà transitiva in quanto , ad esempio, (a, c) ϵ R, (c, e) ϵ R ma (a, e)  R. R invece soddisfa la proprietà anti simmetrica poiché, sommando la matrice di incidenza alla sua trasposta, gli unici elementi uguali a 2 che si ottengono si trovano sulla diagona le principale. 2. La chiusura riflessiva e simmetrica di R ha la seguente matrice d’incidenza: mentre la chiusura transitiva della chiusura riflessiva e simmetrica di R ha la seguente matrice d’incidenza: Pert anto la relazione di equivalenza  generata da R è la relazione universale su X e quindi vi è un’unica -class e che coincide con tutto l’insieme X. 3. Osserviamo che R è antisimmetrica quindi può esistere la minima relazione d’ordine T contene nte R. Calcoli amo le potenze di R:                   1 0 1 1 0 0 0 1 1 1 0 0 1 1 1 0 1 0 1 1 0 1 0 1 0 0 1 0 1 1 0 0 0 1 1 1                   1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 MR2 = = M R3 quindi la chiusura riflessiva e transitiva di R è data da I X  R  R2 ed ha la seguente matrice d’incidenza: Tale relazione è ancora antisimmetrica quindi corrisponde alla mi nima relazione d’ordine T contenente R. Dal diagramma di Hasse di T si deduce che: a) non esiste sup(c,d) in quanto l’insieme dei maggioranti di {c, d} è {e, f} che non ammette minimo rispetto a T; b) inf (c, d) = a; c) a è l’unico minimale di X rispetto a T e qui ndi è anche il minimo di X; d) e, f sono i massimali di X rispetto a T e quindi non esiste il massimo di X. 4. Non esistono funzioni contenute in R in quanto le ultime due righe di R non contengono alcun 1. T invece contiene fu nzioni in quanto su ogni riga della matrice d’incidenza di T c’è almeno un 1, in particolare ci sono n = 6 ∙ 4 ∙ 3 ∙ 3 ∙ 1 ∙ 1 = 216 funzioni contenute in T. Esercizio 2 1. Poiché Z[x] è anello è sufficiente dimostrare che A è sottoanello di (Z[x], +, ∙). Siano p(x), q(x) ϵ A, allora r(x) = p(x) - q(x) ϵ A in quanto r(x) ϵ Z[x] e r(2) = p(2) - q(2) = 0 – 0 = 0. I noltre t(x) = p(x) ∙ q(x) ϵ A in quanto t(x) ϵ Z[x] e t(2) = p(2) ∙ q(2) = 0 ∙ 0 = 0. Dal criterio di caratterizzazione dei sottoanelli segue che A è sottoanello di (Z[x], +, ∙) e quindi (A, +, ∙) è un anello. 2. Siano p(x), q(x) ϵ A av enti termine noto rispettivamente p 0 e q 0, allora il termine noto di p(x) + q(x) è p0 + q 0 mentre quello di p(x) ∙ q(x) è p 0 ∙ q0, pertanto: f (p(x) + q(x)) = p 0 + q 0 = f (p(x) ) + f ( q(x))                   0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 1 1 1 0 1 0 1 1 1 1 1 1                   1 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 1 1 0 1 0 0 1 1 1 0 1 0 1 1 1 1 1 1 f (p(x) ∙ q(x)) = p 0 ∙ q0 = f (p(x) ) ∙ f ( q(x)) f non è un epimo rfismo in quanto i numeri dispari non hanno contro immagine in A tramite f poiché tutti i polinomi p(x) di A hanno termine noto pari. Infatti se p(x) = a n xn + a n-1 xn-1 +…+ a1 x + p 0 è il generico polinomio di A, dovendo essere p(2) = 0, si ha 0 = p(2) = a n ∙ 2n + a n-1 ∙ 2n-1 +…+ a1 ∙ 2 + p 0 e quindi p0 = -an ∙ 2n - an-1 ∙ 2n-1 -… - a1 ∙ 2 = 2( -an ∙ 2n-1 - an-1 ∙ 2n-2 -… - a1), cioè p 0 dev’essere pari. 3. Osserviamo che, per ogni p(x), q(x)  A, indicati con p 0 e q 0 i rispettivi termini noti, si ha (p(x), q(x))    il termine noto di p(x) - q(x) è nullo  p0 - q0 = 0  p0 = q 0  f (p(x)) = f (q(x))   (p(x), q(x))  ker f Pertanto la relazione  coincide con la relazione ker f ed è noto dalla teoria che quest’ultima è una relazione d i congruenza . In alt ernativa si può provare che  è una relazione d i congruenza dimostr ando che è una relazione d’equivalenza e che è compatibile con le operazioni di addizione e moltiplicazione di polinomi. Dal teorema di fattorizzazione degli omomorfismi sappiamo che esiste un monomorfismo g : A / ker f  Z tale che f = π ker f ∙ g, dove = π ker f è la proiezione canonica, in particolare g risulta essere un isomorfismo tra A / kerf e f (A). Al punto precedente abbiamo osservato che f (A) è l’ insieme dei numeri pari essendo i ter mini noti dei polinomi di A pari. Poiché abbiamo dimostrato che  coincide con la relazione ker f, segue che A /  è isomorfo all’anello degli interi pari.