Esercizi sulle relazioni (superiori)

I seguenti esercizi riguardano Le Relazioni studiati nella Lezione 7. Essi sono divisi per paragrafi in modo tale da favorire la scelta degli esercizi specifici.

Proposizioni e predicati

ESERCIZIO 1. Completa la tabella come suggerito nella prima riga, individuando, per ciascuna proposizione, il predicato e gli argomenti a cui esso si riferisce:

Relazioni in un insieme

ESERCIZIO 2. Nell'insieme A = {3, 5, 6, 9, 30} considera il predicato “essere minore di”; con esso forma proposizioni vere aventi come soggetto e come complemento due elementi di A.

Esempio: p1: 9 è minore di 30.

ESERCIZIO 3. Nell'insieme A rappresentato con il diagramma di Eulero-Venn di FIGURA 10 introduciamo il predicato R: “avere una sola lettera diversa”. Costruisci l'insieme GR.

Traccia di soluzione: Per costruire l'insieme GR devo formare le coppie ordinate ricordando che per qualunque a e b appartenenti ad A, aRb se e solo se “a ha una sola lettera diversa da b”, ad esempio preteRprese.

ESERCIZIO 4. Nell'insieme C = {Como, Milano, Venezia, Parma, Brescia, Aosta, Torino, Genova, Imperia, Arezzo, Firenze, Grosseto, Napoli, Campobasso, Catanzaro, Bologna, Vercelli, Salerno} è definita la relazione R: “essere nella stessa regione”. Costruisci l'insieme GR.

ESERCIZIO 5. Nell'insieme S = {x | x è il nome di un giorno della settimana} è definita la relazioneR: x € S, y € S, xRy se e solo se “x ha lo stesso numero di sillabe di y”. Costruisci l'insieme GR.

ESERCIZIO 6. Nell'insieme F = {1, 3, 4, 6, 5, 9, 0, 2} è definita la relazione R: “essere consecutivi”. Costruisci l'insieme GR.

ESERCIZIO 7. Considera l'insieme S = {x | x è il nome di un giorno della settimana}, completa la rappresentazione grafica di FIGURA 11, dell'insieme S X S, evidenzia poi con una crocetta gli elementi dell'insieme GR determinato dalla relazione “x ha lo stesso numero di sillabe di y”.

ESERCIZIO 8. Considera l'insieme F = {1, 3, 4, 6, 5, 9, 0, 2}; fai la rappresentazione grafica dell'insieme F X F e metti in evidenza con una crocetta gli elementi dell'insieme GR determinato dalla relazione “essere consecutivi”.

ESERCIZIO 9. Considera nell'insieme A = {-1, +3, -7, +5, -2, +4, +10} la relazione R: x € A, y € A, xRy se e solo se “x è concorde con y”. Costruiamo una tabella a doppia entrata (FIGURA 12) riportando in orizzontale e in verticale gli elementi dell'insieme A. Fissa l'attenzione su una cella e segui le istruzioni:

• Se aRb metti 1 nella cella (a; b).
• Altrimenti metti 0 nella cella (a; b).

Prosegui tu seguendo l'esempio.

OSSERVAZIONE. Alla fine tutte le celle sono riempite: compare zero se gli elementi della coppia ordinata non sono in relazione, compare 1 al contrario. La relazione R è completamente rappresentata. La tabella costruita si chiama matrice della relazione. Una relazione può sempre essere rappresentata attraverso una matrice.

ESERCIZIO 10. Nell'insieme S = {x | x è il nome di un giorno della settimana} è introdotta la relazione R: x € S, y € S, xRy se e solo se “x ha lo stesso numero di sillabe di y”. Rappresenta la relazione con una matrice.

ESERCIZIO 11. Assegnato il predicato R: “essere divisibile per” introdotto nell'insieme A = {12, 4, 2, 8, 3, 21, 5, 60}, rappresenta con una matrice la relazione R.

ESERCIZIO 12. Completa la rappresentazione di FIGURA 13 con le frecce relative alla relazione R: x € A, y € A, xRy se e solo se “x è concorde con y” nell'insieme A = {-1, +3, -7, +5, -2, +4, +10}.

ESERCIZIO 13. Nell'insieme A = {1, 2, 3, 4, 5, 6, 7, 8, 9} è introdotto il predicato R: “essere il doppio di”; costruisci l'insieme GR, rappresenta la relazione nei tre modi descritti sopra: con un grafico cartesiano, con una matrice e con un grafo.

ESERCIZIO 14. Sono assegnati i grafi di tre relazioni R1, R2, R3 definite in altrettanti insiemi A, B, C (FIGURA 14); deduci da essi gli elementi di ciascun insieme e costruisci, per ciascuna relazione, l'insieme GR.

ESERCIZIO 15. Rappresenta nei tre modi che sono stati descritti (con un grafico cartesiano, con una matrice, con un grafo) la relazione R: “essere nati nello stesso mese” introdotta nell'insieme C degli alunni della tua classe.

ESERCIZIO 16. Nell'insieme H = {x € N | 21 < x < 40}, xRy se e solo se “la somma delle cifre di x è uguale alla somma delle cifre di y”. Costruisci GR e rappresenta la relazione con una matrice.

ESERCIZIO 17. Rappresenta con un grafo la relazione R indicata dal grafico cartesiano riportato nella FIGURA 15.

Proprietà delle relazioni

ESERCIZIO 18. Quali relazioni sono riflessive?

ESERCIZIO 19. Quali delle seguenti relazioni sono antiriflessive?

ESERCIZIO 20. Riconosci le relazioni simmetriche:

Le relazioni degli ultimi due casi non godono della proprietà simmetrica. Infatti:

• La proposizione “Il Ticino è un affluente del Po” è vera, ma non lo è la proposizione che da essa si ottiene scambiando il soggetto con il complemento.
• Se un numero intero è il quadrato di un altro (ad esempio +25 è il quadrato di +5), non è vero il contrario (infatti +5 non è il quadrato di +25).

ESERCIZIO 21. Riconosci le relazioni antisimmetriche:

ESERCIZIO 22. Verifica se, nell'insieme N dei numeri naturali, la relazione R: “avere lo stesso numero di cifre” gode della proprietà transitiva. Completa le proposizioni e rappresenta R con un grafo:

• A. Da 18R50 e 50R ... segue ... R ....
• B. Da ... R555 e ... R267 segue ... R ....

ESERCIZIO 23. Indica quale tra le seguenti relazioni è transitiva:

ESERCIZIO 24. Dai una rappresentazione tabulare dell'insieme H = {x € N | 0 ≤ x ≤ 12}; determina il resto della divisione di ciascun numero di H con 4, compila la tabella come suggerito nell'esempio:

Introduciamo in H la relazione xRy se e solo se “x e y hanno lo stesso resto nella divisione per 4”. Costruisci il grafo della relazione e stabilisci se gode della proprietà transitiva. La stessa relazione R, introdotta nell'insieme dei numeri naturali N è una relazione transitiva?

'ESERCIZIO 25. Indica le proprietà che verificano le seguenti relazioni.

Relazioni di equivalenza

ESERCIZIO 26. Quali delle seguenti sono relazioni di equivalenza?

ESERCIZIO 27. Fissa l'attenzione sulla relazione R: “frequentare la stessa classe” introdotta nell'insieme S degli alunni iscritti nella tua scuola. Verifica che R è una relazione d'equivalenza. Costruisci le classi d'equivalenza. Quante ne hai potute formare? Come sono indicate nella realtà che vivi quotidianamente? Determina la partizione P(S) in classi d'equivalenza e infine l'insieme quoziente S/R.

ESERCIZIO 28. Studia in N la relazione R: “avere la stessa cifra delle unità”. Verifica se è una relazione d'equivalenza, costruisci l'insieme quoziente dopo aver risposto alle seguenti domande:

• Quanti numeri naturali sono tra loro equivalenti?
• Da quanti elementi è costituito l'insieme N/R?
• Qual è l'elemento che sceglieresti come rappresentante di ciascuna classe?

ESERCIZIO 29. Considera la relazione R: “avere lo stesso resto nella divisione per due” introdotta nell'insieme N e studiane le proprietà.

• È una relazione d'equivalenza? Se la risposta è affermativa, costruisci l'insieme quoziente N/R.
• Quante classi d'equivalenza hai formato?
• Puoi sfruttare quanto ottenuto per enunciare le definizioni di numero pari e di numero dispari?
• Giustifica, in base allo svolgimento dell'esercizio, l'affermazione: “L'insieme dei numeri pari è il complementare in N dell'insieme dei numeri dispari”.

ESERCIZIO 30. Considera l'insieme A = {x € N | 1 ≤ x ≤ 20} e i suoi sottoinsiemi: A₁ = {1, 5, 9, 13, 17}, A₂ = {2, 6, 10, 14, 18}, A₃ = {3, 7, 11, 15, 19}, A₄ = {4, 8, 12, 16, 20}.

• A. Rappresenta gli insiemi con un diagramma di Eulero-Venn.
• B. Si può affermare che quei sottoinsiemi costituiscono una partizione dell'insieme A?
• C. È vero che a ciascuno dei suddetti sottoinsiemi appartengono i numeri di A aventi lo stesso resto nella divisione per 4?
• D. Quei sottoinsiemi sono dunque classi d'equivalenza? Qual è il predicato della relazione che le determina?

ESERCIZIO 31. Nell'insieme N dei numeri naturali stabilisci se è d'equivalenza la relazione R: “xRy se e solo se x ha le stesse cifre di y”.

ESERCIZIO 32. Nell'insieme C degli alunni della tua classe, verifica se la relazione R: “xRy se e solo se il cognome di x ha la stessa lettera iniziale del cognome di y” è d'equivalenza; determina in caso affermativo la partizione dell'insieme C e l'insieme quoziente C/R.

ESERCIZIO 33. Nell'insieme delle parole della lingua italiana verifica se la relazione “xRy se e solo se x ha lo stesso numero di lettere di y” è una relazione di equivalenza. In caso affermativo individua alcune classi di equivalenza.

ESERCIZIO 34. Nell'insieme dei nomi dei giorni della settimana considera la relazione “xRy se e solo se x e y scritti in lettere, hanno almeno tre lettere in comune”. Verifica se è una relazione di equivalenza e in caso affermativo individua le classi di equivalenza.

ESERCIZIO 35. Nell'insieme dei numeri naturali da 1 a 100, verifica se la relazione “xRy se e solo se x e y hanno lo stesso numero di lettere” è una relazione di equivalenza. Individua quante sono le classi di equivalenza. Scrivi tutti gli elementi delle classi di equivalenza [1] e [10].

ESERCIZIO 36. Nell'insieme dei numeri naturali da 1 a 100, verifica se la relazione “xRy se e solo se x + y è dispari” è una relazione di equivalenza.

ESERCIZIO 37. Nell'insieme dei nomi dei mesi dell'anno verifica se la relazione “xRy se e solo se x e y hanno lo stesso numero di giorni” è una relazione di equivalenza. Eventualmente individua le classi di equivalenza.

Relazioni di ordine

ESERCIZIO 38. Nell'insieme M = {1, 8, 3, 4, 10, 2, 7, 0, 5, 9, 6} viene introdotta la relazione R così definita: “xRy se e solo se y - x appartiene a N”. La relazione è riflessiva? La relazione è antisimmetrica? La relazione è transitiva? È vero che due elementi distinti sono sempre confrontabili?

ESERCIZIO 39. Verifica che la relazione R: “essere divisore” introdotta nell'insieme J = {3, 6, 10, 15, 21} è una relazione d'ordine parziale in senso largo.

ESERCIZIO 40. Perché la relazione R rappresentata dal grafico cartesiano riportato nella figura, pur essendo una relazione d'ordine non può essere classificata in nessuna delle tipologie studiate? Dai una breve motivazione indicando quali proprietà non sono soddisfatte dalla relazione rappresentata.

ESERCIZIO 41. Nell'insieme degli studenti della tua classe determina le proprietà della relazione R: “xRy se e solo se l'altezza di x non supera l'altezza di y”. È una relazione d'ordine? Di quale tipo?

ESERCIZIO 42. Nell'insieme A = {12, 4, 2, 8, 3, 21, 5, 60} la relazione R: “essere divisibile” è una relazione d'ordine? Se lo è, di che tipo di relazione si tratta? Totale, parziale, in senso largo, in senso stretto?

ESERCIZIO 43. Nell'insieme N - {0} la relazione “essere divisibile” è d'ordine totale in senso largo?

Relazioni tra due insiemi diversi

ESERCIZIO 44. Rappresenta con un grafico cartesiano la relazione R: "essere nato nell'anno" di dominio l'insieme A = {Galileo, Napoleone, Einstein, Fermi, Obama} e codominio l'insieme B ={1901, 1564, 1961, 1879, 1769, 1920, 1768}. Rappresenta per elencazione il sottoinsieme GR del prodotto cartesiano A X B. Stabilisci infine gli elementi dell'immagine IM..

ESERCIZIO 45. L'insieme S = {casa, volume, strada, ufficio, clavicembalo, cantautore, assicurazione} è il codominio della relazione R: "essere il numero di sillabe di" il cui dominio è X = {x € N/0 < x < 10}. Rappresenta con un grafico cartesiano la relazione assegnata, evidenzia come nel primo esempio di questo paragrafo l'insieme GR, scrivi per elencazione l'insieme IM..

ESERCIZIO 46. Completa la rappresentazione con grafico sagittale della relazione "essere capitale di". La freccia che collega gli elementi del dominio con quelli del codominio rappresenta il predicato R: "essere la capitale di".

ESERCIZIO 47. È univoca la relazione R definita tra l'insieme P = {parola del proverbio "rosso di sera, bel tempo si spera"} e l'insieme A ={lettere dell'alfabeto italiano} che associa ad ogni parola la sua iniziale? Ti sembra corretto affermare che dominio e insieme di definizione coincidono? Completa con il simbolo corretto la relazione tra insieme immagine e codominio: IM....C. Fai il grafico sagittale della relazione.

ESERCIZIO 48. R è la relazione tra l'insieme N dei naturali e l'insieme degli interi relativi Z espressa dal predicato "essere il quadrato di". Ti sembra corretto affermare che dominio e insieme di definizione coincidono? Perché IM. = C? La relazione è univoca?

ESERCIZIO 49. Una relazione R è assegnata con il suo grafico cartesiano.

Completa e rispondi alle domande:

• A. D ={................................................................................}.
• B. C ={................................................................................}.
• C. I.D. ={................................................................................}.
• D. IM. ={................................................................................}.
• E. La relazione è biunivoca?
• F. 2 è l'immagine di quali elementi dell'insieme di definizione?
• G. Quale elemento del codominio è l'immagine di M?

ESERCIZIO 50. I tre grafici sagittali rappresentano altrettante corrispondenze, R₁, R₂, R₃. Completa per ciascuna di esse la descrizione schematizzata nel riquadro sottostante:

Esercizi riepilogativi

ESERCIZIO 51. L'insieme GR di una relazione introdotta nell'insieme A = {a, b, c, d, e} è GR = [(a; a), (a; b), (b; b), (d; d), (c; d), (d; e), (e; e)}. Quale delle seguenti affermazioni è vera

• A. R è una relazione antiriflessiva.
• B. R è una relazione solo antisimmetrica.
• C. R è una relazione riflessiva.
• D. R è una relazione transitiva e antisimmetrica.

ESERCIZIO 52. La relazione R: “essere vicini di banco” inserita nell'insieme degli alunni della tua classe è una relazione d'equivalenza? È una relazione d'ordine?

ESERCIZIO 53. I tre sottoinsiemi A₁ = {36, 135, 432}, A₂ = {65} e A₃ = {66, 3522, 93, 435} dell'insieme A = {36, 65, 66, 93, 135, 432, 435, 3522} costituiscono una partizione dell'insieme A? Sapresti trovare una caratteristica per gli elementi di ciascun sottoinsieme? A₁, A₂, A₃ sono classi d'equivalenza?

ESERCIZIO 54. La relazioneR: “xRy se e solo se x sta nella stessa nazione di y” nell'insieme K = {Parigi, Madrid, Milano, Siviglia, Bari, Granada, Venezia, Lione} è d'equivalenza? Costruisci A/R.

ESERCIZIO 55. Verifica se la relazione R assegnata con la matrice rappresentata sotto è d'equivalenza. In caso positivo determina la partizione dell'insieme A = {[], ♦, ∞, V} e l'insieme quoziente A/R.

ESERCIZIO 56. Associa a ciascun grafo della figura la corretta relazione d'ordine:

• A. Ordine totale in senso largo.
• B. Ordine totale in senso stretto.
• C. Ordine parziale in senso largo.
• D. Ordine parziale in senso stretto.

ESERCIZIO 57. In un torneo di pallavolo gareggiano quattro squadre A, B, C, D; rappresenta con un grafo a frecce le seguenti informazioni, relative alle prime tre giornate:

• 1^a giornata: A vince contro B. C vince contro D.
• 2^a giornata: D vince contro A. B vince contro C.
• 3^a giornata: A vince contro C. B vince contro D.

Il 4^o giorno si gioca la semifinale tra le prime due classificate e le altre due. Se per ogni vittoria si ottiene un punteggio di 10 punti e per ogni sconfitta un punteggio di 2 punti, quale squadra gioca la semifinale con B? Il torneo è vinto dalla squadra C. Rappresenta con un grafo a frecce la situazione della semifinale e quella della finale. È unica la risposta a quest'ultimo quesito?

ESERCIZIO 58. Analizza le proprietà delle seguenti relazione e stabilisci se sono relazioni di equivalenza o di ordine e in questo caso di che tipo sono.

ESERCIZIO 59. Andrea, insegnante di grafica, ha chiesto ai suoi alunni di usare il minimo numero di colori per colorare il modello della figura sottostante in modo che poligoni confinanti non risultino con lo stesso colore. Come si può risolvere il problema? [Risposta: 3 colori]

Traccia di soluzione: Nell'insieme Z = {1, 2, 3, 4, 5, 6, 7, 8, 9} studia la relazione R: “confinare con”, rappresentandola con un grafico cartesiano e sfrutta i risultati trovati per risolvere il problema. La soluzione può essere trovata fissando un punto interno a ciascuna regione: due punti sono uniti se e solo se le regioni confinano, il segmento che li congiunge deve attraversare solo il loro confine comune; i punti che non sono congiunti indicano regioni che avranno lo stesso colore.