Fondamenti di informatica - Laurea triennale Informatica/Relazioni

Le relazioni tra insiemi sono un modo generale per descrivere quando un elemento di un insieme è “collegato” a un elemento di un altro insieme. Una relazione viene definita formalmente come un insieme di coppie ordinate ed è quindi un sottoinsieme del prodotto cartesiano tra due insiemi. Per esempio, una tabella che associa studenti ai corsi frequentati può essere vista come una relazione: se Bill frequenta Informatica, allora la coppia (Bill, Informatica) appartiene alla relazione.

Relazioni e funzioni

Una relazione da un insieme X a un insieme Y è un sottoinsieme di X × Y.

Se (x, y) appartiene alla relazione R, si scrive:

x R y

e si legge: “x è in relazione con y”.

Una funzione è un caso particolare di relazione: ogni elemento del dominio deve essere associato a uno e un solo elemento del codominio.

Relazioni su un insieme

Quando una relazione va da un insieme X a sé stesso, si parla di relazione su X.

Per rappresentare una relazione su un insieme si può usare un digrafo, cioè un grafo orientato:

• ogni elemento dell’insieme è rappresentato da un punto, detto vertice;
• se (x, y) appartiene alla relazione, si disegna una freccia da x a y;
• se (x, x) appartiene alla relazione, si disegna un loop sul vertice x.

Proprietà delle relazioni

1. Relazione riflessiva

Una relazione R su un insieme X è riflessiva se ogni elemento è in relazione con sé stesso.

Formalmente:

(x, x) ∈ R per ogni x ∈ X

Nel digrafo, questo significa che ogni vertice ha un loop.

Esempio: la relazione ≤ sui numeri è riflessiva, perché per ogni numero x vale x ≤ x.

Una relazione non è riflessiva se esiste almeno un elemento x tale che (x, x) non appartiene alla relazione.

---

2. Relazione simmetrica

Una relazione è simmetrica se, ogni volta che x è in relazione con y, allora anche y è in relazione con x.

Formalmente:

se (x, y) ∈ R, allora (y, x) ∈ R

Nel digrafo, se c’è una freccia da x a y, deve esserci anche una freccia da y a x.

Esempio: “essere fratello/sorella di” è simmetrica: se Maria è sorella di Mario, allora Mario è fratello di Maria.

Una relazione non è simmetrica se esistono x e y tali che (x, y) ∈ R, ma (y, x) ∉ R.

---

3. Relazione antisimmetrica

Una relazione è antisimmetrica se, quando x è in relazione con y e y è in relazione con x, allora necessariamente x = y.

Formalmente:

se (x, y) ∈ R e (y, x) ∈ R, allora x = y

Un modo equivalente per capirla è questo: tra due elementi distinti non possono esserci frecce in entrambe le direzioni.

Esempio: la relazione ≤ è antisimmetrica, perché se x ≤ y e y ≤ x, allora x = y.

Attenzione: antisimmetrica non significa “non simmetrica”. Una relazione può essere sia simmetrica sia antisimmetrica, per esempio una relazione che contiene solo coppie del tipo (x, x).

Una relazione non è antisimmetrica se esistono due elementi distinti x e y tali che sia (x, y) sia (y, x) appartengono alla relazione.

---

4. Relazione transitiva

Una relazione è transitiva se, quando x è in relazione con y e y è in relazione con z, allora x è in relazione con z.

Formalmente:

se (x, y) ∈ R e (y, z) ∈ R, allora (x, z) ∈ R

Esempio: la relazione ≤ è transitiva, perché se x ≤ y e y ≤ z, allora x ≤ z.

Nel digrafo, se c’è una freccia da x a y e una da y a z, allora deve esserci anche una freccia da x a z.

Una relazione non è transitiva se esistono x, y, z tali che (x, y) e (y, z) appartengono alla relazione, ma (x, z) no.

Ordini parziali

Una relazione è un ordine parziale se è contemporaneamente:

1. riflessiva;
2. antisimmetrica;
3. transitiva.

Un esempio importante è la relazione ≤ sui numeri interi positivi.

Un altro esempio è la relazione “divide” sui numeri positivi:

a divide b

se esiste un intero k tale che b = ak.

Questa relazione è un ordine parziale perché:

• ogni numero divide sé stesso;
• se a divide b e b divide a, allora a = b;
• se a divide b e b divide c, allora a divide c.

Elementi confrontabili e non confrontabili

In un ordine parziale, due elementi x e y sono confrontabili se:

x R y oppure y R x

Se invece nessuna delle due relazioni vale, gli elementi sono non confrontabili.

Un ordine parziale diventa un ordine totale quando ogni coppia di elementi è confrontabile.

Per esempio, ≤ sui numeri è un ordine totale, perché dati due numeri qualsiasi a e b, vale sempre a ≤ b oppure b ≤ a.

La relazione “divide”, invece, è solo un ordine parziale: per esempio 2 e 3 non sono confrontabili, perché 2 non divide 3 e 3 non divide 2.

Applicazione: pianificazione di attività

Le relazioni possono essere usate per ordinare attività. Per esempio, per scattare una foto con una macchina fotografica, alcune azioni devono avvenire prima di altre:

• togliere il copriobiettivo;
• mettere a fuoco;
• accendere il flash;
• premere il pulsante.

La relazione “deve essere fatto prima di” crea un ordine parziale tra le attività. Alcune azioni hanno un ordine obbligato, mentre altre possono essere scambiate.

Una soluzione consiste nel trovare un ordine totale compatibile con l’ordine parziale.

Relazione inversa

Data una relazione R da X a Y, la sua relazione inversa R⁻¹ si ottiene invertendo ogni coppia ordinata.

Se:

(x, y) ∈ R

allora:

(y, x) ∈ R⁻¹

Per esempio, se R rappresenta “divide”, allora R⁻¹ può essere interpretata come “è divisibile da”.

Composizione di relazioni

Se R è una relazione da X a Y e S è una relazione da Y a Z, la loro composizione S ∘ R è una relazione da X a Z.

La coppia (x, z) appartiene a S ∘ R se esiste un elemento intermedio y tale che:

(x, y) ∈ R e (y, z) ∈ S

In pratica, si applica prima R e poi S.