Relazioni binarie

Note

Una relazione binaria è una relazione $R$ tale che:

$$R\subseteq A\times A$$

Proprietà di una relazione binaria

Serialità

La proprietà formale è:

$$\forall a\in A\exists b\in A(a,b)\in R$$

Possiamo dire che nella rappresentazione a grafo di adiacenza ogni vertice ha una freccia uscente, mentre nella matrice di adiacenza ogni riga ha almeno un elemento non nullo.

Riflessività

La proprietà formale è:

$$\forall a\in A(a,a)\in R$$

Nel grafo ogni elemento avrà una relazione con se stesso, mentre nella matrice di adiacenza avremo solo $1$ sulla diagonale ($I=\{(a,a):a\in A\}\subseteq M_R$).

Simmetria

La proprietà formale è:

$$\forall a,b\in A(a,b)\in R⟹(b,a)\in R$$

Nel grafo di adiacenza ogni elemento avrà una relazione con se stesso, inoltre ogni nodo uscente da $a$ a $b$ avrà un nodo rientrante da $b$ ad $a$. Nella matrice di adiacenza equivarrà a dire $M_R=M_R^T$.

Antisimmetria

La proprietà formale è:

$$\forall a,b\in A(a,b)\in R\text{ e }(b,a)\in R⟹a=b$$

Nel grafo di adiacenza ogni elemento avrà una relazione con se stesso. Inoltre ogni nodo uscente da $a$ in $b$ non dovrà avere un nodo rientrante da $b$ ad $a$. Nella matrice di adiacenza equivarrà a dire $R\cap R^{-1}\subseteq I_A$.

Transitività

La proprietà formale è:

$$\forall a,b,c\in A(a,b)\in R\text{ e }(b,c)\in R⟹(a,c)\in R$$

Nella matrice di adiacenza equivarrà a dire

$$R^2\subseteq R$$

Un paio di osservazioni su queste proprietà:

• $\text{Seriale}\text{centernot}⟹\text{Riflessiva}$, tuttavia $\text{Riflessiva}⟹\text{Seriale}$
• $\text{Antisimmetria}\text{centernot}⟹\text{Non simmetrica}$
• $\text{Transitiva}+\text{Simmetrica}\text{centernot}⟹\text{Riflessiva}$
• $\text{Transitiva}+\text{Seriale}+\text{Simmetrica}⟹\text{Riflessiva}$

Comportamento delle proprietà rispetto a delle operazioni

$$R,T\subseteq A\times A$$

|

$$R,T$$

  		   |
  		   $$
  		   R\cap T
  		   $$
  		   	|
  		   	$$
  		   	R\cup T
  		   	$$
  		   		|
  		   		$$
  		   		R\times T
  		   		$$
  		   		  |
  		   		  $$
  		   		  R^{-1}
  		   		  $$
  		   		  	 |
  | ------------------------- | -------------- | -------------- | -------------- | -------------- |

|

$$\text{Seriale}$$

  |
  $$
  \bigtimes
  $$
    |
    $$
    \checkmark
    $$
     |
     $$
     \checkmark
     $$
      |
      $$
      \bigtimes
      $$
        |

|

$$\text{Riflessiva}$$

|

$$✓$$

|
$$
\checkmark
$$
 |
 $$
 \checkmark
 $$
  |
  $$
  \checkmark
  $$
       |

|

$$\text{Simmetrica}$$

|

$$✓$$

|
$$
\checkmark
$$
 |
 $$
 \bigtimes
 $$
   |
   $$
   \checkmark
   $$
        |

|

$$\text{Antisimmetrica}$$

|

$$✓$$

|

$$\text{bigtimes}$$

|

$$\text{bigtimes}$$

 |
 $$
 \checkmark
 $$
         |

|

$$\text{Transitiva}$$

|

$$✓$$

|
$$
\bigtimes
$$
  |
  $$
  \bigtimes
  $$
    |
    $$
    \checkmark
    $$
         |