Relazioni

Note

Una relazione su $A_1,\cdots ,A_n$ è un sottoinsieme $R$:

$$R\subseteq A_1\times \cdots \times A_n$$

Ed è detta relazione $n$-aria. In una relazione binaria $A_1$ si dice dominio e $A_2$ si dice codominio:

$$R\subseteq \underset{\text{dominio}}{\underbrace{A_1}}\times \underset{\text{codominio}}{\underbrace{A_2}}$$

Notazione

La notazione $aRb$ può essere usata per rappresentare $(a,b)\in R$.

Proprietà di due relazioni:

$$R\subseteq S⟺\forall (a,b)\in R:\exists (a,b)\in S$$ $$R=S⟺(R\subseteq S)\wedge (S\subseteq R)$$

Metodi di rappresentazione di relazioni finite

Prendiamo in considerazione la relazione $R\subseteq A_1\times A_2$

Elenco di elementi

È possibile rappresentare gli elementi come elenchi:

$$R=\{(a_1,b_1),(a_2,b_2),\cdots \}$$

Grafo di adiacenza

È possibile disegnare un grafo orientato di tutti i vertici in $A_1\cup A_2$ e disegno una freccia da $a$ a $b$ se $(a,b)\in R$.

Matrice di adiacenza

Numerando gli elementi del dominio $(a_1,\cdots ,a_n)$ e gli elementi del codominio $(a_1,\cdots ,a_m)$, possiamo definire la matrice $M_R\in {\mathbb{M}}_{m,n}(\{0,1\})$:

$$(M_R{)}_{ij}=\{\begin{array}{ll}1& \text{se }(a_i,b_j)\in R\\ 0& \text{se }(a_i,b_j)\notin R\end{array}$$

Operazioni su relazioni binarie

Unione

$$R,T\subseteq A_1\times A_2$$ $$R\cup T=\{(a,b):(a,b)\in R\text{ o }(a,b)\in T\}$$

Nel caso della matrice di adiacenza basterà fare un or logico elemento per elemento.

Intersezione

$$R,T\subseteq A_1\times A_2$$ $$R\cap T=\{(a,b):(a,b)\in R\text{ e }(a,b)\in T\}$$

Prodotto di relazioni

$$R\subseteq A_1\times A_{2}T\subseteq A_2\times A_{3}R\cdot T\subseteq A_1\times A_3$$ $$R\cdot T=\{(a,c)\in A_1\times A_3\mid \exists b\in A_2|(a,b)\in R,(b,c)\in T\}$$

Nella rappresentazione della matrice di adiacenza basta fare il prodotto riga per colonna.

$$M_{R\cdot T}=M_R\cdot M_T$$

La matrice risultante rappresenterà il numero di percorsi che connette $i\to j$, e quindi:

$$(M_{R\cdot T}{)}_{ij}=\{\begin{array}{ll}1& \text{ se }(M_R\cdot M_T{)}_{ij}\ne 0\\ 0& \text{ se }(M_R\cdot M_T{)}_{ij}=0\end{array}$$

Inversa di una relazione

$$R\subseteq A_1\times A_2{R}^{-1}\subseteq A_2\times A_1$$ $$R^{-1}=\{(b,a)\in A_2\times A_1\mid (a,b)\in R\}$$