Relazioni binarie

 

Una relazione binaria fra due insiemi A e B è un sottoinsieme del prodotto cartesiano AxB ; ogni coppia della relazione è caratterizzata dal fatto di rendere vera una determinata e caratteristica affermazione in cui sono coinvolti un generico elemento di A ed un generico elemento di B. Tale affermazione costituisce il criterio con cui sono associati, nella relazione considerata, gli elementi di A con gli elementi di B.

 

Una relazione fra gli insiemi A e B è rappresentata sinteticamente nel seguente  modo:

x R y  - oppure R(x ;y) – con : x Î A e y Î B

 

Ad esempio, consideriamo gli insiemi di amici A ={ Alda, Bruno, Chiara, Ernesto, Giacomo, Lisa } e B = { Antonio, Beatrice, Carlo, Emma, Maria, Nicola}

     Consideriamo la relazione per cui sia vero che: “x è parente di y” ove x Î A e y Î B. In tal caso R : è parente di

 

     Sapendo che:

     Antonio è fratello di Lisa, Bruno e Carlo sono cugini, Chiara e Maria sono sorelle, Ernesto è lo zio di Nicola

     Possiamo rappresentare la relazione nel modo seguente (evidenziando le coppie del prodotto cartesiano che appartengono alla relazione):

AxB

Alda

Bruno

Chiara

Ernesto

Giacomo

Lisa

Antonio

Alda ; Antonio

Bruno; Antonio

Chiara ;   Antonio

Ernesto  ;  Antonio

Giacomo ;   Antonio

Lisa ;   Antonio

Beatrice

Alda ; Beatrice

Bruno; Beatrice

Chiara  ;  Beatrice

Ernesto  ;  Beatrice

Giacomo  ;  Beatrice

Lisa ;   Beatrice

Carlo

Alda ; Carlo

Bruno; Carlo

Chiara  ;  Carlo

Ernesto; Carlo

Giacomo  ;  Carlo

Lisa; Carlo

Emma

Alda ;   Emma

Bruno ;   Emma

Chiara ;   Emma

Ernesto  ;  Emma

Giacomo  ;  Emma

Lisa ;   Emma

Maria

Alda ;   Maria

Bruno ;   Maria

Chiara; Maria

Ernesto ;   Maria

Giacomo ;   Maria

Lisa  ;  Maria

Nicola

Alda ;   Nicola

Bruno ;   Nicola

Chiara  ;  Nicola

Ernesto  ;  Nicola

Giacomo ;   Nicola

Lisa  ; Nicola

 

 

Si chiama Dominio della relazione (fra l’insieme A e l’insieme B) l’insieme formato dagli elementi di A che appartengono alla relazione (evidenziati in bianco nell’esempio precedente).

Si chiama Codominio della relazione (fra l’insieme A e l’insieme B) l’insieme formato dagli elementi di B che appartengono alla relazione (evidenziati in azzurro nell’esempio precedente).

 

Nota: una volta definito il criterio con cui associare gli elementi dei due insiemi, è identificato anche il sottoinsieme del loro prodotto cartesiano costituente la relazione; pertanto si può considerare come definizione di relazione il criterio di associazione: legge (o regola) che permette di associare gli elementi del primo insieme al secondo.

 

Tipi di relazioni

Uno ad uno: associa ad un elemento di A un solo elemento di B.

Uno a molti: associa ad un elemento di A diversi elementi di B

Molti ad uno: associa a diversi elementi di A un solo elemento di B

Molti a molti: associa a diversi elementi di A diversi elementi di B.

 

L’esempio che abbiamo considerato prima è del tipo “uno ad uno”.

Ciò può essere visto meglio rappresentando la relazione in modo grafico ( vai )

 

Una particolare relazione è quella gerarchica: relazione uno a molti fra più insiemi (livelli della gerarchia) che è rappresentata generalmente mediante un organigramma  ( vai )

 

Relazioni di un insieme in se stesso : si ha quando i due insiemi associati nella relazione sono il medesimo insieme.

Ad esempio consideriamo l’insieme A = {  1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }

      E la relazione x R y :  la divisione di x con y dà come risultato un valore appartenente all’insieme A

      Cioè: “x : y  Î A ” ove x Î A e y Î A.

      Usando la rappresentazione tabellare si ha :

AxA

1

2

3

4

5

6

7

8

9

10

1

1 ; 1

2 ; 1

3 ; 1

4 ; 1

5 ; 1

6 ; 1

7 ; 1

8 ; 1

9 ; 1

10 ; 1

2

1 ; 2

2 ; 2

3 ; 2

4 ; 2

5 ; 2

6 ; 2

7 ; 2

8 ; 2

9 ; 2

10 ; 2

3

1 ; 3

2 ; 3

3 ; 3

4 ; 3

5 ; 3

6 ; 3

7 ; 3

8 ; 3

9 ; 3

10 ; 3

4

1 ; 4

2 ; 4

3 ; 4

4 ; 4

5 ; 4

6 ; 4

7 ; 4

8 ; 4

9 ; 4

10 ; 4

5

1 ; 5

2 ; 5

3 ; 5

4 ; 5

5 ; 5

6 ; 5

7 ; 5

8 ; 5

9 ; 5

10 ; 5

6

1 ; 6

2 ; 6

3 ; 6

4 ; 6

5 ; 6

6 ; 6

7 ; 6

8 ; 6

9 ; 6

10 ; 6

7

1 ; 7

2 ; 7

3 ; 7

4 ; 7

5 ; 7

6 ; 7

7 ; 7

8 ; 7

9 ; 7

10 ; 7

8

1 ; 8

2 ; 8

3 ; 8

4 ; 8

5 ; 8

6 ; 8

7 ; 8

8 ; 8

9 ; 8

10 ; 8

9

1 ; 9

2 ; 9

3 ; 9

4 ; 9

5 ; 9

6 ; 9

7 ; 9

8 ; 9

9 ; 9

10 ; 9

10

1 ; 10

2 ; 10

3 ; 10

4 ; 10

5 ; 10

6 ; 10

7 ; 10

8 ; 10

9 ; 10

10 ; 10

    Come si vede, relazione è prevalentemente del tipo Uno a Molti.

 

Proprietà delle relazioni di un insieme ( A ) in se stesso

Riflessiva:  x R x per ogni x Î A

Antiriflessiva: per ogni x Î A si ha che x non è in relazione con se stesso.

Simmetrica: Se x R y à y R x

Antisimmetrica : Se x R y e y R x à x = y

Transitiva : Se x R y e y R z à x R z

 

Ad esempio: la relazione considerata in precedenza gode delle proprietà Riflessiva, Antisimmetri ca e Transitiva

 

Nota: rappresentando la relazione in forma tabellare si può affermare subito se la relazione è:

Riflessiva: se appartengono alla relazione le celle della diagonale principale (vedi l’esempio precedente)

Antiriflessiva: se alla relazione non appartengono le celle della diagonale principale.

Simmetrica: se appartengono alla relazione le celle disposte in modo simmetrico rispetto alla diagonale principale (celle bordate nell’esempio seguente).

AxA

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Relazioni di equivalenza: relazioni che godono delle proprietà Riflessiva, Simmetrica e Transitiva.

Le relazioni di equivalenza permettono di determinare una particolare partizione dell’insieme considerato : l’insieme quoziente.

Ogni sottoinsieme dell’insieme quoziente è detto classe di equivalenza. Ogni classe di equivalenza è formata da elementi che sono in relazione solo fra loro ( non con elementi di altre classi di equivalenza).

Tale caratteristica delle classi di equivalenza permette di identificare tutti gli elementi appartenenti ad essa una volta che sia noto un elemento; gli altri, infatti, possono essere ricavati applicando la relazione di equivalenza. Pertanto si dice che gli elementi di una classe di equivalenza sono equivalenti fra loro e sono rappresentabili mediante uno solo di essi ( o, come indicato nell’esempio, da un particolare attributo).

 

Ad esempio consideriamo un insieme di persone: A = { Alda, Anna, Bruno, Carlo, Chiara, Elisa, Ernesto, Franco, Giobbe, Luigi, Mario, Sandra }

      Consideriamo la relazione  x R y :  “x e y appartengono alla stessa famiglia”   con x Î A e y Î A.

      La relazione gode delle proprietà:

      Riflessiva : ovviamente una persona appartiene alla famiglia di se stesso.

      Simmetrica: se x è della famiglia di y, ovviamente anche y è della famiglia di x.

      Transitiva: se x e y appartengono alla stessa famiglia e y e z appartengono alla stessa famiglia,  ovviamente anche x e z appartengono alla stessa famiglia.

      La relazione considerata è una relazione d’equivalenza.

 

Rappresentando in forma tabellare la relazione otteniamo ( omettiamo di indicare esplicitamente le coppie di ogni cella del prodotto cartesiano e utilizziamo un colore diverso per le persone che appartengono alla stessa famiglia) :

 

AxA

Alda
Anna
Bruno

Carlo
Chiara

Elisa

Ernesto
Franco

Giobbe

Luigi

Mario
Sandra

Alda

 

 

 

 

 

 

 

 

 

 

 

 
Anna

 

 

 

 

 

 

 

 

 

 

 

 

Bruno

 

 

 

 

 

 

 

 

 

 

 

 

Carlo

 

 

 

 

 

 

 

 

 

 

 

 
Chiara

 

 

 

 

 

 

 

 

 

 

 

 

Elisa

 

 

 

 

 

 

 

 

 

 

 

 

Ernesto

 

 

 

 

 

 

 

 

 

 

 

 
Franco

 

 

 

 

 

 

 

 

 

 

 

 

Giobbe

 

 

 

 

 

 

 

 

 

 

 

 

Luigi

 

 

 

 

 

 

 

 

 

 

 

 

Mario

 

 

 

 

 

 

 

 

 

 

 

 
Sandra

 

 

 

 

 

 

 

 

 

 

 

 

 

Si riconoscono subito le classi di equivalenza (i sottoinsiemi della relazione costituiti dagli elementi in relazione fra loro):

Classe 1 (Bianchi) = { Alda, Carlo, Ernesto, Luigi }

Classe 2 (Rossi) =  { Anna, Chiara, Franco, Sandra }

Classe 3 (Neri) = { Bruno, Elisa, Giobbe, Mario }

Nota: ogni classe (ed ogni elemento della classe) può essere identificato mediante un attributo; nel nostro caso può essere il cognome della famiglia (il colore).

 

 

 

 

Rappresentazione grafica dei tipi di relazione.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


Gli altri tipi di relazione possono essere rappresentati graficamente nel seguente modo:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


Torna su

 

 

 

Organigramma
 
 


 

Torna su