Informatica - Matematica discreta

Raccolta temi d'esame anni passati

Other

PROVA SCRITTA DI MATEMATICA DISCRETA C.L. Informatica- Sede di Brindisi Brindisi, 13 Febbraio 2012 Esercizio 1. Date le seguenti funzioni g:N ! R,g (n)= pn 4 e h:R ! R h(x)= x3+5 , stabilire se sono iniettive, suriettive o biettive. Inoltre calcolare, ove possibile, le funzioni inverse g1eh1, e le composizioni hgegh. Esercizio 2. Risolvere, se possibile, il seguente sistema di congruenze lineari 8< : 3x⌘ 6 (mod 33) 7x⌘ 21 (mod 5) 5x⌘ 5 (mod 30) . Esercizio 3. Quanti sono i numeri primi, finiti o infiniti? Dare una dimostrazione della risposta. Esercizio 4. Dati i seguenti numeri complessi: z1= p2i 1,z 2=5 5i. (1) Determinare il modulo di z1ez2. (2) Scrivere in forma algebrica i numeri complessi z1ez2. (3) Scrivere in forma algebrica i numeri complessi z1z2, 1 z2ez2 z1. Esercizio 5. Determinare gli elementi invertibili e i divisori dello zero nell’anello ( Z18,+,·). Per ogni elemento invertibile determinarne l’inverso. Esercizio 6. (1) Stabilire se esiste un albero con 8 vertici, dei quali 2 di ordine 3, 4 di ordine 2 e i restanti di ordine 1. Se esiste disegnare un grafico di un tale albero. (2) Stabilire se esiste un grafo con 8 vertici, dei quali 2 di ordine 3, 4 di ordine 2 e i restanti di ordine 1. 1 2 ATTENZIONE: Qui di seguito riportiamo un accenno alle soluzione degli esercizi, solo un accenno mancano dettagli. Contengono tutte le risposte anche se spesso non motivate o senza tutti i dettagli necessari. Piu’ che soluzioni vere e proprie, sono da considerarsi come linee guide per lo svolgi- mento. Non sono su cienti a prendere il massimo punteggio dell’esercizio, proprio perch´e non sono complete. Inoltre, Sono state inserite come EXTRA per questo appello, in via del tutto eccezionale Esercizio. 1 Date le seguenti funzioni g:N ! R,g (n)= pn 4 e h:R ! R h(x)= x3+5 , stabilire se sono iniettive, suriettive o biettive. Inoltre calcolare, ove possibile, le funzioni inverse g1eh1, e le composizioni hgegh. Soluzione 1. Per quanto riguarda g:N ! R,g (n)= pn 4 g non e’ suriettiva, ad esempio perche’ assume solo valori maggiori di -4 (quindi g1(10) = insieme vuoto. Quindi gnon e’ suriettiva. (quale e’ la definizione?) g e’ iniettiva in quanto soddisfa la definizione di giniettiva (che e’ ?): pn4= pm 4 se e solo se pn= pm se e solo se n= ±m, ma il dominio di gsono i numeri naturali e quindi n= ±m se e solo se n=m quindi ge’ iniettiva. g non e’ biettiva, perche’ non e’ suriettiva (quale e’ la definizione di funzione biettiva?). Quindi non si puo’ calcolare g1. Per quanto riguarda h h:R ! R h(x)= x3+5 , h e’ iniettiva: x3+5 = y3+ 5 se e solo se x3= y3se e solo se y= x. h e’ suriettiva, infatti per ogni y fissato in R, l’equazione y = x3+ 5 ha soluzione: x3= y 5, ovvero x= 3py 5. Quindi l’insieme contro immagine di ogni elemento del codominio R e’ diverso dall’insieme vuoto. Quindi he’ suriettiva. Quindi he’ biettiva (perche’ ?) e l’inversa e’ data dalla funzione h1:R ! R,h 1(y)= 3p y 5, Infine ghnon si puo’ calcolare in quanto ge’ definita solo sui naturali (ad esempio dovremmo fare radici di cose negative) hgsi puo’ calcolare: hg:N ! R ! R, h (g(n)) = h(pn 4) = ( pn 4)3+5 Esercizio. 2 Risolvere, se possibile, il seguente sistema di congruenze lineari 8< : 3x⌘ 6 (mod 33) 7x⌘ 21 (mod 5) 5x⌘ 5 (mod 30) . Soluzione 2. Riduciamo il sistema al seguente sistema equivalente, 8< : x⌘ 2 (mod 11) x⌘ 3 (mod 5) x⌘ 1 (mod 6) . dividendo la prima per 3, la seconda per 7 e la terza congruenza per 5. Perche’ lo possiamo fare: ovvero otteniamo un sistema equivalente? Si, perche’ ? 3 Perche’ abbiamo fatto questa riduzione? Controllare le ipotesi del teorema cinese dei resti, (non potevamo applicarlo subito, perche’ ?) Applichiamo il teorema cinese dei resti, cosa dice? cosa dobbiamo fare? Studiamo le singole congruenze (notare ora non e’ piu’ un sistema, niente parentesi gra ↵e!!) - 30 x ⌘ 2 (mod 11) ovvero 8 x ⌘ 2 (mod 11); inoltre MCD (8,11) = 1 |2,unica soluzione modulo 11 che e’ 3. - 66 x⌘ 3 (mod 5) ovvero x⌘ 3 (mod 5) unica soluzione modulo 5 e’ 3 ( perche’ ?) -55 x⌘ 1 (mod 6), ovvero x⌘ 1 (mod 6) unica soluzione modulo 6 e’ 1 11 ⇤6⇤5 = 330, quindi teorema cinese dei resti, soluzione unica modulo 330 e’ 3⇤30 + 66 ⇤3 + 55 ⇤1 = 90 + 198 + 55 = 288 + 55 = 343 ⌘ 13(mod 330). Perche’ e’ unica? Esercizio. 3 Quanti sono i numeri primi, finiti o infiniti? Dare una dimostrazione della risposta. Soluzione 3. Per fortuna sono infiniti, come dimostrato da Euclide. Vedere un qualsiasi libro, ad esempio pag 84 del libro Matematica Discreta, Piacentini-Cattaneo. Esercizio. 4 Dati i seguenti numeri complessi: z1= p2i 1,z 2=5 5i. (1) Determinare il modulo di z1ez2. (2) Scrivere in forma algebrica i numeri complessi z1ez2. (3) Scrivere in forma algebrica i numeri complessi z1z2, 1 z2ez2 z1. Soluzione 4. quale e’ la definizione di modulo? |z1|= p2+1 = p3, |z2|= p25 + 25 = p50 Quale e’ la definizione di coniugato? z1= p2i 1, z2=5+5 i Quale e’ la regola per il prodotto? z1z2=( p2i1)(5 5i)= 5+5 p (2) + i(5p2 + 5), 1 z2= 1 5 5i= 5+5 i 50 = 1 10 + i 10 z2 z1= 5 5i p2i 1= (p2i 1)(5 5i) 3 = 5 5p2+ i(5p2 + 5) 3 . Esercizio. 5 Determinare gli elementi invertibili e i divisori dello zero nell’anello ( Z18,+,·). Per ogni elemento invertibile determinarne l’inverso. Soluzione 5. Quale e’ la definizione di elemento invertibile? e di divisore dello zero? Un elemento puo’ essere invertibile e divisore dello zero contemporaneamente? Abbiamo che 18 = 3 2⇤2. Quindi : [2] 18,[3] 18,[4] 18,[6] 18,[8] 18,[9] 18,[10] 18,[12] 18,[14] 18,[15] 18,[16] 18. sono divisori dello zero (ovviamenti diversi da zero!!!) Perche’ sono loro? Come li abbiamo determinati? Gli invertibili sono [1] 18,[5] 18,[7] 18,[11] 18,[13] 18,[17] 18.perche? (Solo per facilitare i conti, controlliamo che sono congrui ad 1 modulo 18 i seguenti numeri 1,19,37,55,73, 91,109,127....) INVERSI: [1] 18 inverso se stesso, [5] 18 ha inverso [11] 18 (55) [7] 18 ha inverso [13] 18 (91) [11] 18 ha inverso [5] 18 [13] 18 ha inverso [7] 18 [17] 18 ha inverso [17] 18 (obbligato ad essere inverso di se stesso) Infatti 17*17=289=1+288=1+18*16. Esercizio. 6 4 (1) Stabilire se esiste un albero con 8 vertici, dei quali 2 di ordine 3, 4 di ordine 2 e i restanti di ordine 1. Se esiste disegnare un grafico di un tale albero. (2) Stabilire se esiste un grafo con 8 vertici, dei quali 2 di ordine 3, 4 di ordine 2 e i restanti di ordine 1. Soluzione 6. Abbiamo 2 veritici ordine 3, 4 ordine 2 e quindi 2 di ordine 1. I vertici dispari sono in numeri pari, ok. Perche’ faccimao questa verifica? se non fosse stata soddisfatta? Nei grafi abbiamo 2|l|= P vd(v)=2 ⇤3+4 ⇤2+2 ⇤1 = 6 + 8 + 2 = 16 . Quindi |l|= 8. Risposta 1) Quindi un tale albero non esiste perche un tale albero dovrebbe avere |L|= |V| 1 = 7. giusto? Risposta 2) Esistono tali grafi ad esempio 3 2 22 2 3 ⌘⌘⌘⌘ llll QQQQ ,,,, • • • • • • • • OPPURE 2 1 2 22 3 3 1 • • • • •• • • PROVA SCRITTA DI MATEMATICA DISCRETA C.L. Informatica- Sede di Brindisi Brindisi, 12 Aprile 2012 Esercizio 1. Dimostrare con il principio di induzione che, per ogni n∈ N,siha n+1! k=0 3 (2 + k) 1 (3 + k)= n+1 n+4 + 1 2. Esercizio 2. Risolvere, se possibile, il seguente sistema di congruenze linear i ⎧⎨ ⎩ 10 x≡ 9 (mod 7) 7x≡ 14 (mod 35) 10 x≡ 10 (mod 30) . Esercizio 3. Si consideri in S7la seguente permutazione f= %1234567 3452761 & . (1) Scrivere f come prodotto di cicli disgiunti e stabilire se f e’ pari o dispari. (2) Calcolare f−1e l’ordine di f in S7. (3) Calcolare l’ordine del sottogruppo H generato da f e scrivere esplicitamente tutti gli elementi. (4) Calcolare l’ordine degli elementi del sottogruppo H. Esercizio 4. Siano A ∈ Mat 2×5(C)e B ∈ Mat 5×2(C) A = %0 i 2 −11 31 i 22 & ,B = ⎛ ⎜⎜⎜⎜⎝ 0 −43 1 i 1 −1 1 −1 −14 ⎞ ⎟⎟⎟⎟⎠ . (1) Calcolare se possibile AB ,BB eAA . (2) Calcolare se possibile il determinante di A,B eAB . (3) Calcolare se possibile le matrice inverse di A eAB . Esercizio 5. Sia G il grafo seguente. !! !! !! • • • • • • • • (1) Stabilire se il grafo G e’ planare e determinare la valenza dei sui vertici. (2) Stabilire se il grafo G ammette cammini euleriani e/o cammini hamiltoniani. (3) Stabilire se esiste un albero con lo stesso numero di vertici e le stesse valenze. 1 PROVA SCRITTA DI MATEMATICA DISCRETA C.L. Informatica- Sede di Brindisi Brindisi, 2 Luglio 2012 Esercizio 1. Assegnata su Z la relazione R = {(a, b )∈ Z× Z |15 |4b+ 11 a}, (ovvero aR b⇐⇒ 15 |4b+ 11 a), verificare che R definisce una relazione di equivalenza su Z e scrivere la classe di equivalenza di 0. Esercizio 2. Calcolare il massimo comun divisore tra i numeri 5775 e 1120 ed esprimerlo come combinazione di 5775 e 1120. Esercizio 3. Sia A un insieme finito di cardinalita’ n (ovvero A possiede n elementi). Quale e’ la cardinalita’ dell’insieme P(A) della parti di A? Dare una dimostrazione della risposta. Esercizio 4. Determinare gli elementi invertibili e i divisori dello zero ne ll’anello ( Z21,+,·). Per ogni elemento invertibile determinarne l’inverso. Esercizio 5. Dati i seguenti numeri complessi: z1= √2− 3i, z 2=4 i− 2. (1) Determinare il modulo di z1ez2. (2) Scrivere in forma algebrica i numeri complessi z1ez2. (3) Scrivere in forma algebrica i numeri complessi z1z2, 1 z2ez2 z1. Esercizio 6. Sia assegnato il reticolo ( R, ≤), dove R = {a, b, c, d, e, f , g }e la relazione ≤ e’ descritta dal seguente diagramma di Hasse: e g a d c b f ✑✑✑✑ ✑✑✑✑ ❅❅❅❅ ❍❍❍❍ ✪✪✪✪✪ • • • • • • • (1) Determinare gli eventuali complementi di tutti gli elementi di R. (2) Stabilire se il reticolo R e’ distributivo. (3) Stabilire se il reticolo R e’ di Boole. 1 2 ATTENZIONE: Qui di seguito riportiamo un accenno alle soluzione degli esercizi, spesso mancano dettagl spesso le risposte non sono motivate o non contengono tutti i dettagli necessari. Piu’ che soluzioni vere e proprie, sono da considerarsi linee guide per lo svolgimento. Pertanto, non sono su cienti ad avere il massimo punteggio. Inoltre, Sono state inserite come EXTRA per questo appello, in via del tutto eccezionale Esercizio. 1 Assegnata su Z la relazione R = {(a, b )2 Z⇥ Z |15 |4b+ 11 a}, (ovvero aR b() 15 |4b+ 11 a), verificare che R definisce una relazione di equivalenza su Z e scrivere la classe di equivalenza di 0. Soluzione 1. Quale e’ la definizione di relazione di equivalenza su un insieme? Quali sono le proprieta’ che deve soddisfare la relazione? La relazione e’ riflessiva infatti, per ogni a2 A si ha aR adato che 15 |4a+ 11 a= 15 a La relazione e’ simmetrica infatti se aR ballora 15 |4b+ 11 a. Inoltre, per ogni aeb si ha che 15 |15 b+ 15 a. Quindi 15 |15 b+ 15 a 4b 11 a=4 a+ 11 b. Perche’ possiamo fare la somma? Ne segue che bR a. La relazione e’ transitiva, infatti supponiamo aR bebR c. Dato che aR ballora si ha 15 |4b+ 11 a. Da bR csi ha che 15 |4c+ 11 b Quindi, facendo la somma si ha che 15 |4b+ 11 a+4 c+ 11 b. Di nuovo, siamo sicuri che 15 divide la somma? Quindi 15 |11 a+4 cequindi aR c. La classe di zero e’: aR 0() 15 |11 aovvero i multipli di 15. Esercizio. 2 Calcolare il massimo comun divisore tra i numeri 5775 e 1120 ed esprimerlo come combinazione di 5775 e 1120. Soluzione 2. Osserviamo che 5775 = 5 2⇤3⇤11 ⇤7 1120 = 5 ⇤25⇤7 Quindi MCD= 35=5 ⇤7 Procediamo comunque con l’algoritmo dele divisioni per determinare il MCD. 5775 = 5 ⇤1120 + 175 1120 = 175 ⇤6 + 70 175 = 70 ⇤2 + 35 70 = 35 ⇤2. Quindi 35 e’ e ↵ettivamente MCD. Perche’ ? Quale e’ l’ultimo resto non nullo? Inoltre, 35 = 175 70 ⇤2 70 = 1120 6⇤175 35 = 175 2⇤1120 + 12 ⇤175 = 13 ⇤175 2⇤1120 175 = 5775 5⇤1120 quindi 35 = 13 ⇤5775 65 ⇤1120 2⇤1120 = 13 ⇤5775 67 ⇤1120 = 75075 75040 Esercizio. 3 Sia A un insieme finito di cardinalita’ n (ovvero A possiede n elementi). Quale e’ la cardinalita’ dell’insieme P(A) della parti di A? Dare una dimostrazione della risposta. Soluzione 3. Se |A |= n, allora |P (A)|=2 n. A lezione sono state date tre di- mostrazioni. Ne bastava scrivere una corretta. Vedere un qualsiasi libro di testo. Esercizio. 4 Determinare gli elementi invertibili e i divisori dello zero nell’anello ( Z21,+,·). Per ogni elemento invertibile determinarne l’inverso 3 Soluzione 4. Quale e’ la definizione di elemento invertibile? e di divisore dello zero? Un elemento puo’ essere invertibile e divisore dello zero contemporaneamente? Un elemento ammette piu’ di un inverso? Abbiamo che 21 = 3 ⇤7. Quindi : [3] 21,[6] 21,[7] 21,[9] 21,[12] 21,[14] 21,[15] 21,[18] 21. sono divisori dello zero (ovviamenti diversi da zero!!!) Perche’ sono loro? Come li abbiamo determinati? Gli invertibili [1] 21,[2] 21,[4] 21,[5] 21,[8] 21,[10] 21,[11] 21,[13] 21,[16] 21,[17] 21,[19] 21,[20] 21. (Solo per facilitare i conti, controlliamo che sono congrui ad 1 modulo 18 i seguenti numeri 22,43,64,85, 106,127,148, 169, 190, 211 , 399=21*19....) Quindi [1] 21 inverso se stesso, [2] 21 ha inverso [11] 21 (22) e viceversa [4] 21 ha inverso [16] 21 (64) [5] 21 ha inverso [17] 21 (85) [8] 21 ha inverso [8] 21 (64) [10] 21 ha inverso [19] 21 (190) [13] 21 ha inverso [13] 21 (169) [20] 21 ha inverso [20] 21 (400=1+399 Esercizio. 5 Dati i seguenti numeri complessi: z1= p2 3i, z 2=4 i 2. (1) Determinare il modulo di z1ez2. (2) Scrivere in forma algebrica i numeri complessi z1ez2. (3) Scrivere in forma algebrica i numeri complessi z1z2, 1 z2ez2 z1. Soluzione 5. quale e’ la definizione di modulo? |z1|= p2+9 = p11 , |z2|= p16 + 4 = p20 = 2 p5 Quale e’ la definizione di coniugato? z1= p2+3 i, z2= 2 4i Quale e’ la regola per il prodotto? z1z2=( p2 3i)(4 i 2) = ( 2p2 + 12) + i(4p (2) + 6). Come si calcola l’inverso?1 z2= 1 4i 2= 2 4i 20 = 1 10 1 5i z2 z1= 4i 2 p2 3i= (p2+3 i)(4 i 2) 11 = (2p2 12) + i(4p (2) 6) 11 . Esercizio. 6 Sia assegnato il reticolo ( R, ), dove R = {a, b, c, d, e, f , g }e la relazione  e’ descritta dal seguente diagramma di Hasse: e g a d c b f ⌘⌘⌘⌘ ⌘⌘⌘⌘ @@@@ HHHH %%%%% •• • • • • • (1) Determinare gli eventuali complementi di tutti gli elementi di R. (2) Stabilire se il reticolo R e’ distributivo. 4 (3) Stabilire se il reticolo R e’ di Boole. Soluzione 6. Quale e’ la definizione di complemento? a parte i complementi banali ovvero ged e.Sihache f edsono complementari. a, b, c non hanno complemento. Quale e’ la definizione di reticolo distributivo? Il reticolo non e’ distributivo perche’ contiene un sottoreticolo isomorfo al reticolo pentagonale N 5. Quale e’ ? Oppure si poteva applicare la definizione di distributivita’ ? a quali vertici? Quale e’ la definizione di reticolo di Boole? Il reticolo non e’ di Boole perche’ non distributivo. Oppure esistono elementi senza complemento? Quindi? PROVA SCRITTA DI MATEMATICA DISCRETA C.L. Informatica- Sede di Brindisi Brindisi, 4 Settembre 2012 Esercizio 1. Date le seguenti funzioni f:R → R,f (x)= √2x− 1 e h:Z → R h(x)=2 x2+1 , stabilire se sono iniettive, suriettive o biettive. Inoltre cal colare, ove possibile, le funzioni inverse f−1eh−1, e le composizioni h◦f ef◦h. Esercizio 2. Date due proposizioni P eQ scrivere la tabella di verit`a di P ∨Q,dove Q indica la negazione di Q. Inoltre, stabilire se la proposizione &x∈ R ∃n∈ Z tale che x2= n2+1 `e vera o falsa e scrivere la sua negazione. Esercizio 3. Si considerino 3 studenti di Informatica, 4 studenti di Matematica e5 studenti di Fisica. Gli studenti di Informatica e Matematica sono t utti maschi, gli studenti di Fisica sono 3 maschi e due femmine. a) In quanti modi diversi si puo’ formare un comitato di 4 studenti? b) In quanti modi diversi si puo’ formare un comitato di 3 studenti, c on un rapp- resentante per ogni materia? c) In quanti modi diversi si puo’ formare un comitato di 3 studenti, c on un rapp- resentante per ogni materia ed almeno una donna? Esercizio 4. Scrivere la definizione di anello commutativo unitario e descrive re almeno un esempio. Esercizio 5. Si consideri in S8la seguente permutazione g= !12345678 14765832 " . (1) Scrivere gcome prodotto di cicli disgiunti e stabilire se ge’ pari o dispari. (2) Calcolare g−1e l’ordine di gin S8. (3) Calcolare l’ordine del sottogruppo H generato da ge scrivere esplicitamente tutti gli elementi. (4) Calcolare l’ordine degli elementi del sottogruppo H. Esercizio 6. Sia G il grafo seguente. ❆❆❆❆ ◗◗◗◗◗◗◗ ✁✁✁✁ ❆❆❆❆ ✑✑✑✑✑✑✑ ✁✁✁✁ •• • • • (1) Stabilire se il grafo G e’ planare e determinare la valenza dei sui vertici. (2) Stabilire se il grafo G ammette cammini euleriani e/o cammini hamiltoniani. 1 PROVA SCRITTA DI MATEMATICA DISCRETA C.L. Informatica- Sede di Brindisi Brindisi, 19 Novembre 2012 Esercizio 1. Dimostrare con il principio di induzione che, per ogni n∈ N,siha n+1! i=−1 (3 i+ 1) = 3 2(n+ 1)( n+ 2) + n. Esercizio 2. Date le seguenti funzioni g:N → Q g(n)= 1− n 2n+2 , e f:Q → Q,f (z)= 7 5z+ 11 stabilire se sono iniettive, suriettive o biettive. Inoltre cal colare, ove possibile, le funzioni inverse f−1eg−1, e le composizioni f◦geg◦f. Esercizio 3. Risolvere se possibile la seguente equazione diofantea indicandone t utte le soluzioni 396 x+ 156 y= 12 . Esercizio 4. a) Scrivere la definizione di relazione di ordine parziale su un insie me. b) Sia assegnata su Z la relazione R = {(c, d )∈ Z× Z |cd ≥ 0}, (ovvero cR d ⇐⇒ il prodotto cd e’ maggiore o uguale a zero). Stabilire se R e’ rif- lessiva, simmetrica, transitiva, antisimmetrica, d’ordine, d’eq uivalenza. Esercizio 5. Scrivere la definizione di gruppo e di gruppo abeliano. Dare un esempi o di entrambe le definizioni. Esercizio 6. Dati i seguenti numeri complessi: z1=4 i− 1,z 2=3 − √3i. (1) Determinare il modulo di z1ez2. (2) Scrivere in forma algebrica i numeri complessi z1ez2. (3) Scrivere in forma algebrica i numeri complessi z1z2, 1 z2ez2 z1. 1 PROVA SCRITTA DI MATEMATICA DISCRETA C.L. Informatica- Sede di Brindisi Brindisi, 15 Gennaio 2013 Traccia 1 Esercizio 1. Siano assegnate le seguenti leggi f:Q {5}! Q {0},f (n)= 1 5n 1 e h:Q {0}! Q h(z)= 3 z+2 . Stabilire se sono funzioni, ed in tal caso se sono iniettive, suriettive o biettive. Inoltre calcolare, ove possibile, le funzioni inverse f1eh1, e le composizioni hf efh. Esercizio 2. Verificare che la seguente successione definita per ricorrenza {an}n= 8< : a0=0 a1=1 an= an1+ an2 n 2. ammette come formula chiusa la successione {bn}ncon bn= 1p5 " 1+ p5 2 !n 1 p5 2 !n# 8n 0. Esercizio 3. Risolvere, se possibile, il seguente sistema di congruenze lineari 8< : 10 x⌘ 50 (mod 70) 11 x⌘ 22 (mod 66) 131 x⌘ 132 (mod 13) . Esercizio 4. Scrivere la definizione di elemento invertibile in un anello commutativo unitario e dimostrare che ogni elemento in ( Z⇤p,+,·), con p primo, e’ invertibile. Esercizio 5. Siano A 2 Mat 2⇥3(C)e C 2 Mat 3⇥3(C) A = ✓i 2 i 3 i 0 ◆ ,C = 0 @ 102 10 1 13 1 1 A . (1) Calcolare, se possibile, AC eCA . (2) Calcolare, se possibile, il determinante di A edi C. (3) Calcolare, se possibile, le matrici inverse di A edi C. Esercizio 6. (1) Stabilire se esiste un albero con 13 vertici, dei quali 1 ha ordine 6 e gli altri hanno ordine 2. Se esiste un tale albero disegnare un grafico. (2) Stabilire se esiste un grafo con 13 vertici, dei quali 1 ha ordine 6 e gli altri hanno ordine 2. Se esiste un tale grafo disegnare un grafico. 1 PROVA SCRITTA DI MATEMATICA DISCRETA C.L. Informatica- Sede di Brindisi Brindisi, 15 Gennaio 2013: Traccia A Esercizio 1. Siano E 2 Mat 2⇥3(C)e F 2 Mat 3⇥3(C) E = ✓3 i 0 i 2 i ◆ ,F = 0 @ 301 10 1 12 1 1 A . (1) Calcolare, se possibile, EF eFE . (2) Calcolare, se possibile, il determinante di E edi F. (3) Calcolare, se possibile, le matrici inverse di E edi F. Esercizio 2. Scrivere la definizione di elemento invertibile in un anello commutativo unitario e dimostrare che ogni elemento in ( Z⇤p,+,·), con p primo, e’ invertibile. Esercizio 3. (1) Stabilire se esiste un albero con 17 vertici, dei quali 1 ha ordine 6 e gli altri hanno ordine 2. Se esiste un tale albero disegnare un grafico. (2) Stabilire se esiste un grafo con 17 vertici, dei quali 1 ha ordine 6 e gli altri hanno ordine 2. Se esiste un tale grafo disegnare un grafico. Esercizio 4. Siano assegnate le seguenti leggi g:Q {2}! Q,g (t)= 1 2 t 1 e f:Q {4}! Q {2} f(y)= 3 4y 1. Stabilire se sono funzioni, ed in tal caso se sono iniettive, suriettive o biettive. Inoltre calcolare, ove possibile, le funzioni inverse g1ef1, e le composizioni gf efg. Esercizio 5. Verificare che la seguente successione definita per ricorrenza {bn}n= 8< : b0=0 b1=1 bn= bn1+ bn2 n 2. ammette come formula chiusa la successione {an}ncon an= 1p5 " 1+ p5 2 !n 1 p5 2 !n# 8n 0. Esercizio 6. Risolvere, se possibile, il seguente sistema di congruenze lineari 8< : 10 x⌘ 20 (mod 130) 71 x⌘ 75 (mod 7) 7x⌘ 14 (mod 42) . 1 PROVA SCRITTA DI MATEMATICA DISCRETA C.L. Informatica- Sede di Brindisi Brindisi, 25 Gennaio 2013 Traccia 1 Esercizio 1. Risolvere se possibile la seguente equazione diofantea indicandone tutte le soluzioni 682 x+ 374 y= 22 . Esercizio 2. In una classe ci sono 18 studenti. a) In quanti modi distinti si possono scegliere 4 studenti? b) In quanti modi distinti si possono assegnare un 3 e un 8 a due studenti diversi? c) In quanti modi diversi si possono formare 3 gruppi di 6 studenti? Esercizio 3. Date tre proposizioni P,Q ed R, scrivere la tabella di verit`a di P ^(Q =) R). Inoltre, stabilire se la proposizione 8x2 Z 9c2 N tale che 8y2 R si ha x=2 yc 2+ x 3cy 2. `e vera o falsa e scrivere la sua negazione. Esercizio 4. Sia assegnata sull’insieme A = Z⇥ Z, la seguente operazione ⇤ :A⇥ A ! A, tale che 8(a, b ),(x, y )2 A (a, b )⇤(x, y )=(2 ax, 3+ b+ y). (1) Stabilire se l’operazione ⇤verifica la propriet`a associativa e commutativa. (2) Determinare, se esiste, l’elemento neutro. (3) Determinare, se esistono, gli elementi invertibili. Esercizio 5. Sia ( A, +,·) un anello commutativo unitario. Dimostrare che se ae’ un elemento invertibile allora anon e’ un divisore dello zero. Esercizio 6. Sia assegato il reticolo D132 dei divisori di 132, ordinato per divisibilit`a. (1) Tracciare il diagramma di Hasse di D132 . (2) Determinare gli eventuali complementi di tutti gli elementi di D132 . (3) Stabilire se il reticolo e’ distributivo. (4) Stabilire se il reticolo e’ di Boole. 1 PROVA SCRITTA DI MATEMATICA DISCRETA C.L. Informatica- Sede di Brindisi Brindisi, 25 Gennaio 2013 Traccia A Esercizio 1. Sia assegnato il reticolo D140 dei divisori di 140, ordinato per divisibilit`a. (1) Tracciare il diagramma di Hasse di D140 . (2) Determinare gli eventuali complementi di tutti gli elementi di D140 . (3) Stabilire se il reticolo e’ distributivo. (4) Stabilire se il reticolo e’ di Boole. Esercizio 2. Sia ( A, +,·) un anello commutativo unitario. Dimostrare che se x e’ un elemento invertibile allora xnon e’ un divisore dello zero. Esercizio 3. In una classe ci sono 15 studenti. 1) In quanti modi distinti si possono scegliere 5 studenti? 2) In quanti modi distinti si possono assegnare un 5 e un 7 a due studenti diversi? 3) In quanti modi diversi si possono formare 3 gruppi di 5 studenti? Esercizio 4. Date tre proposizioni P,Q ed R, scrivere la tabella di verit`a di (P =) Q)_R. Inoltre, stabilire se la proposizione 8a2 Z 9b2 N tale che 8z2 R si ha 5 zb 2+ a 4bz 2= a. `e vera o falsa e scrivere la sua negazione. Esercizio 5. Sia assegnata sull’insieme A = Z⇥ Z, la seguente operazione ⇤ :A⇥ A ! A, tale che 8(x, y ),(s, t )2 A (x, y )⇤(s, t )=(4 xs, y + t+ 1) . a) Stabilire se l’operazione ⇤verifica la propriet`a associativa e commutativa. b) Determinare, se esiste, l’elemento neutro. c) Determinare, se esistono, gli elementi invertibili. Esercizio 6. Risolvere se possibile la seguente equazione Diofantea indicandone tutte le soluzioni 748 x+ 440 y= 44 . 1 PROVA SCRITTA DI MATEMATICA DISCRETA C.L. Informatica- Sede di Brindisi Brindisi, 25 Gennaio 2013 Traccia 3 Esercizio 1. Sia ( A, +,·) un anello commutativo unitario. Dimostrare che se x e’ un elemento invertibile allora xnon e’ un divisore dello zero. Esercizio 2. Date tre proposizioni P,Q ed R, scrivere la tabella di verit`a di (P _Q)= ) R. Inoltre, stabilire se la proposizione 8v2 Z 9u2 N tale che 8t2 R si ha 11 u2t2 2v= u3t3 2v. `e vera o falsa e scrivere la sua negazione. Esercizio 3. Risolvere se possibile la seguente equazione Diofantea indicandone tutte le soluzioni 533 x+ 377 y= 13 . Esercizio 4. Sia assengato il reticolo D220 dei divisori di 220, ordinato per divisibilit`a. (1) Tracciare il diagramma di Hasse di D220 . (2) Determinare gli eventuali complementi di tutti gli elementi di D220 . (3) Stabilire se il reticolo e’ distributivo. (4) Stabilire se il reticolo e’ di Boole. Esercizio 5. In una classe ci sono 21 studenti. i) In quanti modi distinti si possono scegliere 6 studenti? ii) In quanti modi distinti si possono assegnare un 5 e un 7 a due studenti diversi? iii) In quanti modi diversi si possono formare 3 gruppi di 7 studenti? Esercizio 6. Sia assegnata sull’insieme A = Z⇥ Z, la seguente operazione ⇤ :A⇥ A ! A, tale che 8(a, x ),(t, z )2 A (a, x )⇤(t, z )=(3 at, x +2+ z). a) Stabilire se l’operazione ⇤verifica la propriet`a associativa e commutativa. b) Determinare, se esiste, l’elemento neutro. c) Determinare, se esistono, gli elementi invertibili. 1 PROVA SCRITTA DI MATEMATICA DISCRETA C.L. Informatica- Sede di Brindisi Brindisi, 8 Febbraio 2013 Traccia 1 Esercizio 1. Sia dato il gruppo ( Z⇤11,·). (1) Stabilire l’ordine del gruppo. (2) Stabilire se il gruppo `e ciclico (3) Se il gruppo e’ ciclico determinare tutti i generatori. Esercizio 2. Dati i seguenti numeri complessi: z1= i 5,z 2= p6 2i. i) Determinare la parte reale e la parte complessa di z1ez2. ii) Scrivere in forma algebrica il coniugato di z1ez2. iii) Determinare il modulo di z1ez2. iv) Scrivere in forma algebrica i numeri complessi z1z2,z1 z2e 1 z1. Esercizio 3. Siano A eB due insieme finiti della stessa cardinalit`a ed h:A ! B una funzione da A aB. Dimostrare che h `e una funzione iniettiva se e solo se h `e suriettiva. Esercizio 4. Sia assegnata sull’insieme Z la relazione R = {(c, z )2 Z⇥ Z |18 |10 c+8 z}, (ovvero cR z() 18 |10 c+8 z). Verificare che R definisce una relazione di equivalenza su Z e scrivere la classe di equivalenza di 0. Esercizio 5. Dimostrare con il principio di induzione, che per ogni n2 N si ha 3|4n+2 . Esercizio 6. Si consideri in S9la seguente permutazione f= ✓123456789 876235491 ◆ . (1) Scrivere f come prodotto di cicli disgiunti. (2) Stabilire se f`e pari o dispari. (3) Calcolare l’ordine di f in S9. (4) Calcolare f1. (5) Calcolare esplicitamente gli elementi del sottogruppo F generato da f ed il loro ordine. 1 PROVA SCRITTA DI MATEMATICA DISCRETA C.L. Informatica- Sede di Brindisi Brindisi, 8 Febbraio 2013 Traccia A Esercizio 1. Dimostrare con il principio di induzione, che per ogni n2 N si ha 3|4n+2 . Esercizio 2. Siano A eB due insieme finiti della stessa cardinalit`a ed f:A ! B una funzione da A aB. Dimostrare che f`e una funzione iniettiva se e solo se f`e suriettiva. Esercizio 3. Sia assegnata sull’insieme Z la relazione R = {(a, x )2 Z⇥ Z |14 |4a+ 10 x}, (ovvero aR x() 14 |4a+ 10 x). Verificare che R definisce una relazione di equivalenza su Z e scrivere la classe di equivalenza di 0. Esercizio 4. Sia dato il gruppo ( Z⇤13,·). Stabilire l’ordine del gruppo e stabilire se il gruppo `e ciclico. Inoltre, determinare l’ordine di tutti i suoi elementi. Esercizio 5. Si consideri in S7la seguente permutazione h= ✓1234567 7652341 ◆ . (1) Scrivere hcome prodotto di cicli disgiunti. (2) Stabilire se h`e pari o dispari. (3) Calcolare l’ordine di hin S7. (4) Calcolare h1. (5) Calcolare l’ordine degli elementi del sottogruppo H generato da h. Esercizio 6. Dati i seguenti numeri complessi: z1= p5i 2,z 2=3 4i. a) Determinare la parte reale e la parte immaginaria di z1ez2. b) Scrivere in forma algebrica il coniugato di z1ez2. c) Determinare il modulo di z1ez2. d) Scrivere in forma algebrica i numeri complessi z1z2, 1 z1ez1 z2. 1 PROVA SCRITTA DI MATEMATICA DISCRETA C.L. Informatica- Sede di Brindisi Brindisi, 8 Febbraio 2013 Traccia B Esercizio 1. Si consideri in S8la seguente permutazione g= ✓12345678 87623541 ◆ . a) Scrivere gcome prodotto di cicli disgiunti. b) Stabilire se g`e pari o dispari. c) Calcolare l’ordine di gin S8. d) Calcolare g1. e) Calcolare l’ordine degli elementi del sottogruppo G generato da g. Esercizio 2. Sia assegnata sull’insieme Z la relazione R = {(y, b )2 Z⇥ Z |16 |12 y+4 b}, (ovvero yR b() 16 |12 y+4 b). Verificare che R definisce una relazione di equivalenza su Z e scrivere la classe di equivalenza di 0. Esercizio 3. Dati i seguenti numeri complessi: z1=3 i 4,z 2=3 p7i. (1) Determinare la parte reale e la parte immaginaria di z1ez2. (2) Scrivere in forma algebrica il coniugato di z1ez2. (3) Determinare il modulo di z1ez2. (4) Scrivere in forma algebrica i numeri complessi 1 z1,z1z2ez1 z2. Esercizio 4. Dimostrare con il principio di induzione, che per ogni n2 N si ha 3|4n+2 . Esercizio 5. Sia dato il gruppo ( Z⇤11,·). Stabilire l’ordine del gruppo e stabilire se il gruppo `e ciclico. Inoltre, determinare l’ordine di tutti i suoi elementi. Esercizio 6. Siano A eB due insieme finiti della stessa cardinalit`a ed g:A ! B una funzione da A aB. Dimostrare che g`e una funzione iniettiva se e solo se g`e suriettiva. 1 PROVA SCRITTA DI MATEMATICA DISCRETA C.L. Informatica- Sede di Brindisi Brindisi, 27 Marzo 2013 Esercizio 1. Date tre proposizioni P,Q ed R, scrivere la tabella di verit`a di P ^(Q _ ¯R), dove ¯R indica la negazione di R. Inoltre, stabilire se la proposizione 8a2 R 9c2 R tale che 8b2 R si ha a=2 c2+4 b4 `e vera o falsa e scrivere la sua negazione. Esercizio 2. Verificare che la seguente successione {an}ndefinita per ricorrenza {an}n= ⇢ a0=0 an=2 an1+1 n 1. ammette come formula chiusa la successione {bn}ncon bn=2 n 1. Esercizio 3. Risolvere se possibile la seguente equazione Diofantea indicandone tutte le soluzioni 434 x+ 308 y= 14 . Esercizio 4. Determinare gli elementi invertibili e i divisori dello zero nell’anello ( Z20,+,·). Per ogni elemento invertibile determinarne l’inverso. Esercizio 5. Scrivere la definizione di cammino hamiltoniano in un grafo. Descrivere un esempio di un grafo che ammette un cammino hamiltoniano. Esercizio 6. Sia assegnato il reticolo ( R, ), dove R = {a, b, c, d, e, f , g }e la relazione  e’ descritta dal seguente diagramma di Hasse: c d a e f b g CCC ⇧⇧⇧⇧ ⌘⌘⌘⌘ @@@@ HHHH %%%%% ◆◆◆◆◆◆ •• • • • • • (1) Determinare gli eventuali complementi di tutti gli elementi di R. (2) Stabilire se il reticolo R e’ distributivo. (3) Stabilire se il reticolo R e’ di Boole. 1 PROVA SCRITTA DI MATEMATICA DISCRETA C.L. Informatica- Sede di Brindisi Brindisi, 1 Luglio 2013 Esercizio 1. Si considerino 7 studenti di Biologia, 4 studenti di Lettere e 4 studenti di Architettura. a) In quanti modi diversi si pu`o formare un comitato di 5 studenti? b) In quanti modi diversi si possono assegnare un 25 e un 27 a due studenti distinti? c) In quanti modi diversi si pu`o formare un comitato di 5 studenti, con un rappre- sentante per ogni materia? d) In quanti modi diversi si possono formare 3 gruppi di 5 studenti? Esercizio 2. Stabilire con il principio di induzione se la seguente a ↵ermazione `e falsa o vera: 8n2 N si ha 5 |6n+4 . Esercizio 3. Risolvere, se possibile, il seguente sistema di congruenze lineari 8< : 11 x⌘ 9 (mod 8) 71 x⌘ 142 (mod 7) 88 x⌘ 3 (mod 5) . Esercizio 4. Dati i seguenti numeri complessi: z1= p2 i, z 2=2 i 4. (1) Determinare il modulo di z1ez2. (2) Scrivere in forma algebrica i numeri complessi z1ez2. (3) Scrivere in forma algebrica i numeri complessi z1z2, 1 z2ez2 z1. Esercizio 5. Sia assegnato il seguente grafo G HHHHHHHHH •• • • •• ••• (1) Stabilire se il grafo G `e planare e determinare la valenza dei suoi vertici. (2) Stabilire se il grafo G ammette cammini euleriani e/o cammini hamiltoniani. (3) Stabilire se esiste un albero con lo stesso numero di vertici e le stesse valenze. Esercizio 6. Sia assegnato il reticolo algebrico ( R, ^,_,ˆ0,ˆ1), dove ˆ0e ˆ1 denotano gli elementi neutri. Dare la definizione di complemento di un elemento e dimostrare che se R `e un reticolo distributivo allora il complemento se esiste `e unico. 1 PROVA SCRITTA DI MATEMATICA DISCRETA C.L. Informatica- Sede di Brindisi Brindisi, 11 Settembre 2013 Esercizio 1. Risolvere se possibile la seguente equazione Diofantea indicandone tutte le soluzioni 945 x+ 240 y= 15 . Esercizio 2. Dimostrare con il principio di induzione che, per ogni n2 N,siha 1 2 nX i=0 3i= 3n+1 1 4 . Esercizio 3. Date tre proposizioni P,Q ed R, scrivere la tabella di verit`a di (P =) R)^(P _Q). Inoltre, stabilire se la proposizione 9v2 Z tale che 8t2 Z 9c2 N tale che c v2+ t=0 `e vera o falsa e scrivere la sua negazione. Esercizio 4. (1) Stabilire se esiste un grafo con 9 vertici, dei quali 1 di ordine 5, 1 di ordine 4, 3 di ordine 3, 2 di ordine 2 e i restanti di ordine 1. Se esiste disegnare un grafico di un tale grafo. (2) Stabilire se esiste un albero con 9 vertici, dei quali 1 di ordine 5, 1 di ordine 4, 3 di ordine 3, 2 di ordine 2 e i restanti di ordine 1. Se esiste disegnare un grafico di un tale albero. Esercizio 5. Sia ( A, +,·) un anello commutativo unitario. Dimostrare che se x e’ un elemento invertibile allora xnon e’ un divisore dello zero. Esercizio 6. Sia assengato il reticolo D198 dei divisori di 198 ordinato per divisibilit`a. (1) Tracciare il diagramma di Hasse di D198 . (2) Determinare gli eventuali complementi di tutti gli elementi di D198 . (3) Stabilire se il reticolo e’ distributivo. (4) Stabilire se il reticolo e’ di Boole. 1 PROVA SCRITTA DI MATEMATICA DISCRETA C.L. Informatica- Sede di Brindisi Brindisi, 25 Settembre 2013 Esercizio 1. Sia assegnata su Z la seguente relazione R = {(a, b )2 Z⇥ Z |f(a)= f(b)}, dove f e’ la seguente funzione f:Z ! Z f(x)= x2+3 (ovvero aR b() f(a)= f(b)). Stabilire se R e’ una relazione riflessiva, simmetrica, transitiva, d’ordine o di equivalenza. Nel caso in cui sia una relazione di equivalenza, determinare la classe di equivalenza di 1. Esercizio 2. Date le seguenti funzioni g:N ! R {0},g (n)= | 2n| 1 3 e h:R {0}! R {2} h(z)=2 z5, stabilire se sono iniettive, suriettive o biettive. Inoltre calcolare, ove possibile, le funzioni inverse g1eh1, e le composizioni hgegh. Esercizio 3. Quanti sono i numeri primi? Finiti o infiniti? Dare una dimostrazione della risposta. Esercizio 4. Sia assegnata sull’insieme Q la seguente operazione ⇤ :Q ⇥ Q ! Q, tale che 8x, y 2 Q x⇤y= xy + 1 2x+ 1 2y. (1) Determinare se l’operazione e’ associativa, commutativa. (2) Determinare, se esiste, l’elemento neutro della struttura algebrica ( Q,⇤). (3) Determinare, se esiste, l’inverso di 1 e di -1 in ( Q,⇤). Esercizio 5. Siano D 2 Mat 3⇥3(C)e C 2 Mat 3⇥2(C): D = 0 @ 20 1 22 0 10 1 1 A ,C = 0 @ 2 i 20 1 i 1 A . (1) Calcolare, se possibile, DC eCD . (2) Calcolare, se possibile, il determinante di D edi C. (3) Calcolare, se possibile, le matrici inverse di D edi C. Esercizio 6. Si consideri in S9la seguente permutazione g= ✓123456789 163924758 ◆ . a) Scrivere gcome prodotto di cicli disgiunti e stabilire se g`e pari o dispari. b) Calcolare l’ordine di gin S9. c) Calcolare g1. d) Calcolare l’ordine degli elementi del sottogruppo G generato da g. 1 PROVA SCRITTA DI MATEMATICA DISCRETA C.L. Informatica- Sede di Brindisi Brindisi, 20 Novembre 2013 Esercizio 1. Dimostrare con il principio di induzione, che per ogni n2 N si ha 3|4n+2 . Esercizio 2. Date tre proposizioni T,Q ed S, scrivere la tabella di verit`a di T ^(Q _ ¯S), dove ¯S indica la negazione di S. Inoltre, stabilire se la proposizione 8x2 R 9y2 R tale che 8a2 R si ha x=5 y2+3 a4 `e vera o falsa e scrivere la sua negazione. Esercizio 3. Risolvere se possibile la seguente equazione Diofantea indicandone tutte le soluzioni 945 x+ 240 y= 15 . Esercizio 4. Sia assegnato il seguente grafo G HHHHHHHHH •• • • •• ••• (1) Stabilire se il grafo G `e planare e determinare la valenza dei suoi vertici. (2) Stabilire se il grafo G ammette cammini euleriani e/o cammini hamiltoniani. (3) Stabilire se esiste un albero con lo stesso numero di vertici e le stesse valenze. Esercizio 5. Sia ( A, +,·) un anello commutativo unitario. Dimostrare che se a`e u n elemento invertibile allora anon `e un divisore dello zero. Esercizio 6. Dati i seguenti numeri complessi: z1= p2 i, z 2=2 i 4. (1) Determinare il modulo di z1ez2. (2) Scrivere in forma algebrica i numeri complessi z1ez2. (3) Scrivere in forma algebrica i numeri complessi z1z2, 1 z2ez2 z1. 1 PROVA SCRITTA DI MATEMATICA DISCRETA C.L. Informatica- Sede di Brindisi Brindisi, 24 Febbraio 2014 Esercizio 1. Siano assegnate le seguenti leggi h:Z ! R,h (a)=1 2 3a e g:R ! R g(n)=1 n3. Stabilire se sono funzioni, ed in tal caso se sono iniettive, suriettive o biettive. Inoltre calcolare, ove possibile, le funzioni inverse g1eh1, e le composizioni hgegh. Esercizio 2. Verificare che la seguente successione {an}ndefinita per ricorrenza {an}n= ⇢ a0=0 an=2 an1+1 n 1. ammette come formula chiusa la successione {bn}ncon bn=2 n 1. Esercizio 3. Risolvere, se possibile, il seguente sistema di congruenze lineari 8< : 11 x⌘ 22 (mod 33) x⌘ 39 (mod 7) 4x⌘ 16 (mod 5) . Esercizio 4. Sia dato il gruppo ( Z⇤13,·). (1) Stabilire l’ordine del gruppo. (2) Stabilire se il gruppo `e ciclico (3) Se il gruppo `e ciclico determinare tutti i generatori. Esercizio 5. Dati i seguenti numeri complessi: z1= 1 2+ i, z 2= 2 2i. (1) Determinare il modulo di z1ez2. (2) Scrivere in forma algebrica i numeri complessi z1,z2ez1+ z2. (3) Scrivere in forma algebrica i numeri complessi z1z2, 1 z2ez2 z1. Esercizio 6. Sia assegnato il reticolo algebrico ( R, ^,_,ˆ0,ˆ1), dove ˆ0e ˆ1 denotano gli elementi neutri. Dare la definizione di complemento di un elemento e dimostrare che se R `e un reticolo distributivo allora il complemento se esiste `e unico. 1 PROVA SCRITTA DI MATEMATICA DISCRETA C.L. Informatica- Sede di Brindisi Brindisi, 9 Giugno 2014 Esercizio 1. Dimostrare con il principio di induzione, che per ogni n2 N si ha 6|7n+5 . Esercizio 2. Sia A un insieme finito di cardinalit`a n. Qual’`e la cardinalit`a dell’insieme P(A) della parti di A? Dare una dimostrazione della risposta. Esercizio 3. Sia assegnata su Z la relazione R = {(a, b )2 Z⇥ Z |17 |6b+ 11 a}, (ovvero aR b() 17 |6b+ 11 a). Stabilire se R definisce una relazione d’ordine o di equivalenza su Z. Se `e di equivalenza, scrivere la classe di equivalenza di 0. Esercizio 4. Sia G il grafo seguente. AAAA QQQQQQQ AAAA ⌘⌘⌘⌘⌘⌘⌘ •• •• • (1) Stabilire se il grafo G `e planare e determinare la valenza dei sui vertici. (2) Stabilire se il grafo G ammette cammini euleriani e/o cammini hamiltoniani. (3) Stabilire se esiste un albero con lo stesso numero di vertici e le stesse valenze. Esercizio 5. Dati i seguenti numeri complessi: z1=1+ 1 2i, z 2= 3 3i. (1) Determinare il modulo di z1ez2. (2) Scrivere in forma algebrica i numeri complessi z1,z2ez1+ z2. (3) Scrivere in forma algebrica i numeri complessi z1z2, 1 z2ez2 z1. Esercizio 6. Si consideri in S9la seguente permutazione f= ✓123456789 238456179 ◆ . (1) Scrivere f come prodotto di cicli disgiunti. (2) Stabilire se f`e pari o dispari. (3) Calcolare l’ordine di f in S9. (4) Scrivere esplicitamente gli elementi del sottogruppo generato da f. 1 PROVA SCRITTA DI MATEMATICA DISCRETA C.L. Informatica- Sede di Brindisi Brindisi, 23 Giugno 2014 Esercizio 1. Date le seguenti leggi f:Z ! R f(n)=2 |n|+1 2, e g:R ! R,g (x)=1 3 4x5 stabilire se sono funzioni. In tal caso, stabilire se sono iniettive, suriettive o biettive. Inoltre calcolare, ove possibile, le funzioni inverse f1eg1, e le composizioni fge gf. Esercizio 2. Date tre proposizioni R,S ed T, scrivere la tabella di verit`a di ( R =) S)^(R =) T). Inoltre, stabilire se la proposizione 8a2 R 9t2 R tale che 8c2 N a c= t2. `e vera o falsa e scrivere la sua negazione. Esercizio 3. Risolvere se possibile la seguente equazione diofantea indicandone tutte le soluzioni 132 x+ 140 y= 16 . Esercizio 4. Determinare gli elementi invertibili e i divisori dello zero nell’anello ( Z21,+,·). Calcolare esplicitamente l’inverso degli elementi invertibili. Esercizio 5. (1) Stabilire se esiste un albero con 8 vertici, dei quali: 4 di valenza 2, 2 di valenza 3 e 2 di valenza 1. Se esiste, disegnare un grafico di un tale albero. (2) Stabilire se esiste un grafo con 8 vertici, dei quali: 4 di valenza 2, 2 di valenza 3 e 2 di valenza 1. Se esiste, disegnare un grafico di un tale grafo. Esercizio 6. Sia assegnato il reticolo algebrico ( R, ^,_,ˆ0,ˆ1), dove ˆ0e ˆ1 denotano gli elementi neutri. Dare la definizione di complemento di un elemento e dimostrare che se R `e un reticolo distributivo allora il complemento se esiste `e unico. 1 PROVA SCRITTA DI MATEMATICA DISCRETA C.L. Informatica- Sede di Brindisi Brindisi, 7 Luglio 2014 Esercizio 1. Verificare che la seguente successione {an}ndefinita per ricorrenza {an}n= ⇢ a0=0 an=2 an1+1 n 1. ammette come formula chiusa la successione {bn}ncon bn=2 n 1, 8n 0. Esercizio 2. Risolvere, se possibile, il seguente sistema di congruenze lineari 8< : 17 x⌘ 5 (mod 8) 4x⌘ 16 (mod 44) 5x⌘ 10 (mod 7) . Esercizio 3. Sia assegnata sull’insieme Z la seguente operazione ⇤ :Z⇥ Z ! Z, tale che 8x, y 2 Z x⇤y= xy +2 x. (1) Determinare se l’operazione `e associativa, commutativa. (2) Determinare, se esiste, l’elemento neutro della struttura algebrica ( Z,⇤). (3) Determinare, se esiste, l’inverso di 1 e di -1 in ( Z,⇤). Esercizio 4. Sia ( A, +,·) un anello commutativo unitario. Dimostrare che se x `e u n elemento invertibile allora xnon `e un divisore dello zero. Esercizio 5. Si considerino 4 studenti di Chimica, 5 studenti di Fisica e 3 studenti di Matematica. a) In quanti modi diversi si pu`o formare un comitato di 5 studenti? b) In quanti modi diversi si possono assegnare un 20 e un 29 a due studenti distinti? c) In quanti modi diversi si pu`o formare un comitato di 3 studenti, con un rappre- sentante per ogni materia? d) In quanti modi diversi si possono formare 2 gruppi di 6 studenti? Esercizio 6. Siano D 2 Mat 2⇥3(R)e C 2 Mat 3⇥3(R) D = ✓02 0 11 1 ◆ ,C = 0 @ 12 2 00 12 2 2 2 1 A . (1) Calcolare, se possibile, DC eCD . (2) Calcolare, se possibile, il determinante di D edi C. (3) Calcolare, se possibile, le matrici inverse di D edi C. 1 PROVA SCRITTA DI MATEMATICA DISCRETA C.L. Informatica- Sede di Brindisi Brindisi, 10 Settembre 2014 Esercizio 1. Dimostrare con il principio di induzione che, per ogni n2 N,siha 1 3 n+1X i=0 3i= 3n+2 1 6 . Esercizio 2. Sia assegnata sull’insieme Z la relazione R = {(x, y )2 Z⇥ Z |11 |4x+7 y}, (ovvero xR y() 11 |4x+7 y). Verificare che R definisce una relazione di equivalenza su Z e scrivere la classe di equivalenza di 0. Esercizio 3. Sia A un insieme finito di cardinalit`a n. Qual’`e la cardinalit`a dell’insieme P(A) della parti di A? Dare una dimostrazione della risposta. Esercizio 4. Sia G il grafo seguente. AAAA QQQQQQQ AAAA ⌘⌘⌘⌘⌘⌘⌘ • •• • •• • (1) Stabilire se il grafo G `e planare e determinare i gradi dei suoi vertici. (2) Stabilire se il grafo G ammette cammini euleriani e/o cammini hamiltoniani. (3) Stabilire se esiste un albero con lo stesso numero di vertici e gli stessi gradi. Esercizio 5. Siano D 2 Mat 3⇥3(C)e E 2 Mat 3⇥2(C) D = 0 @ 10 1 2 1 12 1 1 1 1 A ,E = 0 @ i 0 1 i i 1 1 A . (1) Calcolare, se possibile, DE ed ED . (2) Calcolare, se possibile, il determinante di D edi E. (3) Calcolare, se possibile, le matrici inverse di D edi E. Esercizio 6. Sia assengato il reticolo D126 dei divisori di 126 ordinato per divisibilit`a. (1) Tracciare il diagramma di Hasse di D126 . (2) Determinare gli eventuali complementi di tutti gli elementi di D126 . (3) Stabilire se il reticolo `e distributivo. (4) Stabilire se il reticolo `e di Boole. 1 PROVA SCRITTA DI MATEMATICA DISCRETA C.L. Informatica- Sede di Brindisi Brindisi, 22 Settembre 2014 Esercizio 1. Date tre proposizioni P,S ed Q, scrivere la tabella di verit`a di ( PQ)= ⇥ S. Inoltre, stabilire se la proposizione ⇤x⌅ Z ⇧t⌅ R e ⇧y⌅ N x= ⌃ t2+ y. `e vera o falsa e scrivere la sua negazione. Esercizio 2. Risolvere se possibile la seguente equazione diofantea indicandone tutte le soluzioni 170 x+ 55 y= 15 . Esercizio 3. Scrivere la de finizione di gruppo e di gruppo abeliano. Descrivere un esempio di gruppo e di gruppo abeliano. Esercizio 4. Siano assegnate le seguenti leggi h:Z ⌥ Q h(a)= 1 2+2 a2, e g:Q ⌥ Q g(x)=2 4 3x. Stabilire se sono funzioni, ed in tal caso se sono iniettive, suriettive o biettive. Inoltre calcolare, ove possibile, le funzioni inverse g1eh1, e le composizioni h geg h. Esercizio 5. Dati i seguenti numeri complessi: z1= 1 3 i, z 2= 3+3 i. (1) Determinare il modulo di z1ez2. (2) Scrivere in forma algebrica i numeri complessi z1ez2. (3) Scrivere in forma algebrica i numeri complessi z1z2, 1 z2ez2 z1. Esercizio 6. Si consideri in S8la seguente permutazione f= 12345678 15863472 ⇥ . (1) Scrivere f come prodotto di cicli disgiunti. (2) Stabilire se f`e pari o dispari. (3) Calcolare l’ordine di f in S8. (4) Scrivere esplicitamente gli elementi del sottogruppo generato da f. 1 PROVA SCRITTA DI MATEMATICA DISCRETA C.L. Informatica- Sede di Brindisi Brindisi, 21 Novembre 2014 Esercizio 1. Risolvere se possibile la seguente equazione Diofantea indicandone tutte le soluzioni 135 x+ 260 y= 25 . Esercizio 2. Dimostrare con il principio di induzione, che per ogni n2 N si ha 7|8n+6 . Esercizio 3. In una classe ci sono 20 studenti. a) In quanti modi distinti si possono scegliere 3 studenti? b) In quanti modi distinti si possono assegnare un 20 e un 22 e un 24 a tre studenti diversi? c) In quanti modi diversi si possono formare 4 gruppi di 5 studenti? Esercizio 4. Sia assegnata sull’insieme A = Z⇥ Z, la seguente operazione ⇤ :A⇥ A ! A, tale che 8(s, t ),(x, y )2 A (s, t )⇤(x, y )=(3 xs, t +5+ y). (1) Stabilire se l’operazione ⇤verifica la propriet`a associativa e commutativa. (2) Determinare, se esiste, l’elemento neutro. (3) Determinare, se esistono, gli elementi invertibili. Esercizio 5. Sia ( A, +,·) un anello commutativo unitario. Dimostrare che se a`e u n elemento invertibile allora anon `e un divisore dello zero. Esercizio 6. Dati i seguenti numeri complessi: z1=2 1 5i, z 2= 3i. (1) Determinare il modulo di z1ez2. (2) Scrivere in forma algebrica i numeri complessi z1,z2ez1+ z2. (3) Scrivere in forma algebrica i numeri complessi z1z2, 1 z2ez2 z1. 1 PROVA SCRITTA DI MATEMATCA DISCRETA C.L. Informatica Bari, 26 Gennaio 2015 Traccia: 1 Esercizio 1. Consideriamo le seguenti leggi h:R ! R,h (a)= a5 2 e g:Q ! R g(n)=2 n2. Stabilire se sono funzioni, ed in tal caso se sono iniettive, suriettive o biettive. Inoltre calcolare, ove possibile, le funzioni inverse g1eh1, e le composizioni hgegh. Esercizio 2. Usando il principio di induzione verificare che la seguente successione {bn}n2Ndefinita per ricorrenza bn= ⇢ b0=0 n=0 bn= bn1+6 nn 1. ammette come formula chiusa la successione {an}n2Ncon an=3 n(n+ 1), 8n 0. Esercizio 3. Se possibile, risolvere la seguente equazione diofantea indicandone tutte le soluzioni 200 x+ 325 y= 75 . Esercizio 4. In S10, sia assegnata la seguente permutazione g= ✓1 2 3 4 5 6 7 8 9 10 5 10 2 7 1 3 4 8 9 6 ◆ . (1) Descrivere l’elmento gcome prodotto di cicli disgiunti. (2) Individuare l’ordine di gnel gruppo S10. (3) Determinare esplicitamente gli elementi del sottogruppo generato da g. (4) Indicare se l’elemento g`e pari o dispari. Esercizio 5. (1) Stabilire se esiste un grafo con 13 vertici, dei quali: 1 di valenza 5, 2 di valenza 4, 5 di valenza 2 e nessuno di valenza maggiore. Se esiste, disegnare il grafico di un tale grafo. (2) Stabilire se esiste un albero con 13 vertici, dei quali: 1 di valenza 5, 2 di valenza 4, 5 di valenza 2 e nessuno di valenza maggiore. Se esiste, disegnare il grafico di un tale albero. Esercizio 6. Scrivere la definizione di monoide e dimostrare l’unicita dell’inverso di un elemento. 1 PROVA SCRITTA DI MATEMATCA DISCRETA C.L. Informatica Bari, 26 Gennaio 2015 Traccia: 4 Esercizio 1. Si consideri in S7la seguente permutazione h= ✓1234567 6524731 ◆ . (1) Scrivere hcome prodotto di cicli disgiunti. (2) Stabilire se l’elemento h`e dispari o pari. (3) Calcolare l’ordine dell’elemento hnel gruppo S7. (4) Scrivere esplicitamente gli elementi del sottogruppo generato da h. Esercizio 2. Dare la definizione di ( A, +,·) anello commutativo unitario e dimostrare che se a`e un elemento invertibile allora anon `e un divisore dello zero. Esercizio 3. (1) Determinare se esiste un grafo con 14 vertici, dei quali: 2 di valenza 4, 5 di valenza 3, 2 di valenza 2 e nessuno di valenza maggiore. Se esiste, disegnare un grafico di un tale grafo. (2) Determinare se esiste un albero con 14 vertici, dei quali: 2 di valenza 4, 5 di valenza 3, 2 di valenza 2 e nessuno di valenza maggiore. Se esiste, disegnare un grafico di un tale albero. Esercizio 4. Siano assegnate le seguenti leggi f:Q ! Q,f (s)= 1 3s 3 4 e g:Z ! Q g(b)= |b|2. Stabilire se sono funzioni, ed in tal caso se sono iniettive, suriettive o biettive. Inoltre calcolare, ove possibile, le funzioni inverse f1eg1, e le composizioni fgegf. Esercizio 5. Risolvere se possibile la seguente equazione diofantea indicandone tutte le soluzioni 144 x+ 198 y= 90 . Esercizio 6. Provare col principio di induzione che la seguente successione {an}n2N definita per ricorrenza an= ⇢ a0=1 n=0 an=6 n+ an1 n 1. ammette come formula chiusa la successione {bn}n2Ncon bn= 3( n+ 12)2+ 14,8n 0. 1 PROVA SCRITTA DI MATEMATCA DISCRETA C.L. Informatica Bari, 26 Gennaio 2015 Traccia: C Esercizio 1. Verificare, usando il principio di induzione, che la seguente successione {an}n2Ndefinita per ricorrenza an= ⇢ a0= 12 n=0 an= an1+ 34(2n 1) n 1. ammette come formula chiusa la successione {bn}n2Ncon bn= 34(23+ n2), 8n 0. Esercizio 2. Date le seguenti leggi h:N ! R h(x)= 1+ x x+5 , e f:R ! R,f (z)= 1 4z3+7 . Stabilire se sono funzioni, ed in tal caso se sono iniettive, suriettive o biettive. Inoltre calcolare, ove possibile, le funzioni inverse h1ef1, e le composizioni hf efh. Esercizio 3. Sia assegnata la seguente equazione diofantea 162 x+ 225 y= 18 . Risolverla se possibile, indicandone tutte le soluzioni. Esercizio 4. Scrivere la definizione di gruppo e dimostrare le leggi di cancellazione. Esercizio 5. (1) Determinare se esiste un albero con 11 vertici, dei quali: 1 di valenza 4, 4 di valenza 3, 2 di valenza 2 e nessuno di valenza maggiore. Se esiste, disegnare il grafico di un tale albero. (2) Stabilire se esiste un grafo con 11 vertici, dei quali: 1 di valenza 4, 4 di valenza 3, 2 di valenza 2 e nessuno di valenza maggiore. Se esiste, disegnare il grafico di un tale grafo. Esercizio 6. Consideriamo in S9la seguente permutazione f= ✓123456789 137256984 ◆ . (1) Esprimere f come prodotto di cicli disgiunti. (2) Determinare l’ordine di f in S9. (3) Stabilire se f`e pari o dispari. (4) Scrivere esplicitamente gli elementi del sottogruppo generato da f. 1 PROVA SCRITTA DI MATEMATCA DISCRETA C.L. Informatica Bari, 26 Gennaio 2015 Traccia: A Esercizio 1. Scrivere la definizione di elemento invertibile in un anello commutativo unitario e dimostrare che ogni elemento in ( Z⇤p,+,·)`einvertibile. Esercizio 2. (1) Stabilire se esiste un albero con 15 vertici, dei quali: 2 di valenza 4, 2 di valenza 3 e 5 di valenza 2 e nessuno di valenza maggiore. Se esiste, disegnare un grafico di un tale albero. (2) Determinare se esiste un grafo con 15 vertici, dei quali: 2 di valenza 4, 2 di valenza 3 e 5 di valenza 2 e nessuno di valenza maggiore. Se esiste, disegnare un grafico di un tale grafo. Esercizio 3. Sia assegnata in S8la seguente permutazione h= ✓12345678 32146875 ◆ . (1) Determinare hcome prodotto di cicli disgiunti. (2) Determinare l’ordine dell’elemento hin S8. (3) Determinare esplicitamente gli elementi del sottogruppo generato da h. (4) Determinare se h`e dispari o pari. Esercizio 4. Si consideri la seguente equazione diofantea 144 x+ 200 y= 56 . Risolverla se possibile, indicandone tutte le soluzioni. Esercizio 5. Applicando il principio di induzione, dimostrare che la seguente successione {bn}n2Ndefinita per ricorrenza bn= ⇢ b0= 12 n=0 bn= bn1+ 32n 34 n 1. ammette come formula chiusa la successione {an}n2Ncon an= 34n2 12,8n 0. Esercizio 6. Stabilire se le seguenti leggi g:Z ! R g(t)= 3p t4, e h:R ! R,h (y)= 4 13 17 y sono funzioni, ed in tal caso se sono iniettive, suriettive o biettive. Inoltre calcolare, ove possibile, le funzioni inverse h1,g1, e le composizioni ghehg. 1 PROVA SCRITTA DI MATEMATCA DISCRETA C.L. Informatica Bari, 10 Febbraio 2015 Traccia: 1 Esercizio 1. Dati i seguenti numeri complessi: z1= 1+ 2 3i, z 2= p2p3i. (1) Calcolare il modulo dei numeri complessi z1ez2. (2) Scrivere z1,z2in forma algebrica. (3) Scrivere z1z2,1 z1ez1 z2in forma algebrica. Esercizio 2. Sia assegnato il reticolo ( R, ), dove R = {a, b, c, d, e, f , g }e la relazione  `e descritta dal seguente diagramma di Hasse: !!!!! llllll c d a e f b g• • • • • • • (1) Scrivere esplicitamente gli eventuali complementi di tutti gli elementi di R. (2) Stabilire se il reticolo R `e distributivo. (3) Stabilire se il reticolo R `e di Boole. Esercizio 3. Sia assegnata sull’insieme A = Q⇥Q la seguente operazione ⇤:A⇥A ! A, tale che 8(a, b ),(s, t )2A (a, b )⇤(s, t )=( a+s+2 ,3bt). (1) Stabilire se l’operazione `e commutativa. (2) Stabilire se l’operazione `e associativa. (3) Se esiste, stabilire l’elemento neutro della struttura algebrica ( A, ⇤). (4) Se esiste, determinare in modo esplicito l’inverso di (1 ,1) in ( A, ⇤). Esercizio 4. Sia assegnata sull’insieme dei numeri interi Zla relazione R = {(s, t )2Z⇥Z |16 |7t+9 s}, (ovvero 8s, t 2Z,sR t() 16 |7t+9 s). Stabilire se R definisce una relazione di equivalenza o d’ordine sull’insieme dei numeri interi Z.Se R `e di equivalenza, determinare la classe di equivalenza di 0. Esercizio 5. Sia assegnato il seguente sistema di congruenze lineari 8< : 14x⌘ 7 (mod 35) 20x⌘ 8 (mod 18) 30x⌘ 20 (mod 70) . Se possibile, risolverlo determinandone tutte le soluzioni. Esercizio 6. Sia A un insieme finito di cardinalit`a n. Dare la definizione di insieme P (A)della parti di A. Inoltre stabilire la cardinalit`a di P (A) dare una dimostrazione dettagliata della risposta. 1 PROVA SCRITTA DI MATEMATCA DISCRETA C.L. Informatica Bari, 10 Febbraio 2015 Traccia: B Esercizio 1. Dare la definizione di numero primo. Inoltre stabilire se la cardinalit`a dell’insieme dei numeri primi `e finita o infinta e fornire una dimostrazione dettagliata. Esercizio 2. Si consideri su Zla seguente relazione R = {(c, d )2Z⇥Z |14 |9c+5 d}, (ovvero 8c, d 2Z,cR d() 14 |9c+5 d). Determinare se R definisce una relazione d’ordine o di equivalenza su Z. Inoltre, se tale relazione `e di equivalenza, descrivere la classe di equivalenza di 0. Esercizio 3. Risolvere, se possibile, e indicare tutte le soluzioni del seguente sistema di con- gruenze lineari 8< : 78x⌘ 10 (mod 7) 102 x⌘ 16 (mod 5) 20x⌘ 170 (mod 90) . Esercizio 4. Consideriamo sull’insieme B = Q⇥Q la seguente operazione ⇤:B⇥B ! B, tale che 8(x, y ),(c, d )2B (x, y )⇤(c, d )=( x3+ c,2yd ). (1) Determinare se l’operazione `e associativa (2) Determinare se l’operazione `e commutativa. (3) Determinare se, nella struttura algebrica ( B, ⇤), esiste l’elemento neutro. (4) Scrivere esplicitamente l’inverso di ( 1,1) in ( B, ⇤), se esiste. Esercizio 5. Sia assegnato il reticolo ( R, ), dove R = {a, b, c, d, e, f , g }e la relazione  `e descritta dal seguente diagramma di Hasse: AAAAAAAA ⌘⌘⌘⌘ c d a e f b g• • • • • • • (1) Determinare in modo esplicito gli eventuali complementi di tutti gli elementi. (2) Determinare se il reticolo R `e distributivo. (3) Determinare se il reticolo R `e di Boole. Esercizio 6. Si considerino i seguenti numeri complessi: z1=2+ p5i, z 2= p3 5 3i. (1) Determinare il modulo di z2ez1. (2) Determinare la forma algebrica dei numeri complessi z2,z1. (3) Determinare la forma algebrica dei numeri complessi z2z1,1 z2ez2 z1. 1 PROVA SCRITTA DI MATEMATCA DISCRETA C.L. Informatica- Sede di Brindisi Brindisi, 16 Febbraio 2015 Esercizio 1. Usando il principio di induzione verificare che la seguente successione {bn}n2N definita per ricorrenza bn= ⇢ b0=0 n=0 bn= bn1+6 nn 1. ammette come formula chiusa la successione {an}n2Ncon an=3 n(n+ 1), 8n 0. Esercizio 2. Si consideri la seguente equazione diofantea 144 x+ 200 y= 56 . Risolverla se possibile, indicandone tutte le soluzioni. Esercizio 3. Siano assegnate le seguenti leggi f:Q ! Q,f (s)= 1 5s 3 4 e g:Z! Q g(b)= |b|4. Stabilire se sono funzioni, ed in tal caso se sono iniettive, suriettive o biettive. Inoltre calcolare, ove possibile, le funzioni inverse f1eg1, e le composizioni fgegf. Esercizio 4. Dati i seguenti numeri complessi: z1= 1+ 2 3i, z 2= p2p3i. (1) Calcolare il modulo dei numeri complessi z1ez2. (2) Scrivere z1,z2in forma algebrica. (3) Scrivere z1z2,1 z1ez1 z2in forma algebrica. Esercizio 5. Consideriamo sull’insieme B = Q⇥Q la seguente operazione ⇤:B⇥B ! B, tale che 8(x, y ),(c, d )2B (x, y )⇤(c, d )=( x3+ c,2yd ). (1) Determinare se l’operazione `e associativa (2) Determinare se l’operazione `e commutativa. (3) Determinare se, nella struttura algebrica ( B, ⇤), esiste l’elemento neutro. (4) Scrivere esplicitamente l’inverso di ( 1,1) in ( B, ⇤), se esiste. Esercizio 6. Sia assegnato il reticolo algebrico ( R, ^,_,ˆ0,ˆ1), dove ˆ0e ˆ1 denotano gli elementi neutri. Dare la definizione di complemento di un elemento e dimostrare che se R `e un reticolo distributivo allora il complemento se esiste `e unico. 1 PROVA SCRITTA DI MATEMATCA DISCRETA C.L. Informatica Bari, 24 Febbraio 2015 Traccia: A Esercizio 1. Siano B 2 Mat 3⇥3(R)e D 2 Mat 2⇥3(R) B = 0 @ 23 3 1 20 1 1 12 1 A ,D = ✓ 41 2 11 3 ◆ . (1) Calcolare, se possibile, DB eBD . (2) Calcolare, se possibile, il determinante di B edi D. (3) Calcolare, se possibile, le matrici inverse di B edi D. Esercizio 2. Si considerino 5 Inglesi, 6 Francesi e 8 Spagnoli. I Francesi sono tutte Donne, tra gli Spagnoli ci sono 3 Donne e tra gli Inglesi ci sono 2 Donne. a) In quanti modi diversi si pu`o formare un comitato di 4 persone? b) In quanti modi diversi possiamo formare un comitato con un rappresentate per ogni nazionalit`a? c) In quanti modi diversi possiamo formare un comitato con un rappresentate per ogni nazionalit`a ed esattamente un uomo? d) In quanti modi diversi possiamo formare un comitato con un rappresentate per ogni nazionalit`a ed almeno un uomo? Esercizio 3. Date tre proposizioni R,S eT, scrivere la tabella di verit`a di ( R _S)^ (R =) T). Inoltre, stabilire se la proposizione 8x2 Z 9y2 N tale che 8a2 R a= x+ y. `e vera o falsa, motivandone la risposta, e scriverne la sua negazione. Esercizio 4. Sia G un grafo. Sia dia la definizione di grafo connesso, di cammino eule- riano, di circuito euleriano e di cammino hamiltoniano. Si diano esempi e controesempi delle varie definizioni. Esercizio 5. Sia assegnata la seguente equazione diofantea 63 x+ 162 y= 99 . Risolverla se possibile, indicandone tutte le soluzioni. Esercizio 6. Determinare gli elementi invertibili e i divisori dello zero nell’anello ( Z24,+,·). Calcolare esplicitamente l’inverso degli elementi invertibili. 1 PROVA SCRITTA DI MATEMATCA DISCRETA C.L. Informatica Bari, 24 Febbraio 2015 Traccia: 2 Esercizio 1. Se possibile, risolvere la seguente equazione diofantea indicandone tutte le soluzioni 72 x+ 243 y= 45 . Esercizio 2. Si considerino tre proposizioni P,R eQ. Scrivere la tabella di verit`a di (P =) Q)_(P ^R). Determinare, motivando la risposta, se la proposizione 9s2 N tale che 8b2 Z, 9q2 R con b+ s q=0 `e vera o falsa e scriverne la sua negazione. Esercizio 3. Si consideri l’anello ( Z22,+,·). Scrivere quali elementi sono invertibili e quali sono divisori dello zero. Inoltre, determinare esplicitamente l’inverso degli eve