Siguiente: Relaciones binarias en un Subir: RELACIONES Anterior: Conceptos generales sobre relaciones   Índice General

Relaciones binarias

El caso particular de relaciones binarias merece ser tratado aparte, por la riqueza de conceptos y resultados a que da lugar y el tipo de técnicas que pueden utilizarse. En primer lugar, si $R$ es una relación entre $A$ y $B$, el hecho de que un par ordenado $(a,b)$ esté en $R$ suele denotarse

$$a R b$$

Asimismo, el hecho contrario, es decir $(a,b)\notin R$, suele denotarse $a R\!\!\!\!/\;b$, o simplemente $\neg(a R b)$. Una relación binaria admite una representación matricial, siempre que los dominios de la relación sean finitos. En efecto, supongamos que $A=\{a_{1},\ldots,a_{m}\}$ y $B=\{b_{1},\ldots,b_{p}\}$. Entonces la matriz asociada a $R$ es la matriz Booleana con $m$ filas y $p$ columnas

$$M_{R}:=\left[\begin{array}{ccccc} r_{1,1}&\ldots&\ldots&\ldots&r... ...\ldots&\ldots&\ldots\\ r_{m,1}&\ldots&\ldots&\ldots&r_{m,p}\end{array}\right]$$

dada por

$$r_{i,j}:=\left\{\begin{array}{lcl} 1&\mbox{si}&a_{i} R b_{j}\\ 0&\mbox{si}&a_{i} R\!\!\!\!/\;b_{j}\end{array}\right.$$

Ejemplo 3.1   Se consideran los conjuntos $A=\{2,3,5\}$ y $B=\{4,6,9,10\}$, y se define la relación

$$R:=\{(2,4),(2,6),(2,10),(3,6),(3,9),(5,10)\}$$

(es decir, $a R b$ si y sólo si $a\vert b$). Entonces, la matriz asociada a $R$ es

$$M_{R}=\left[\begin{array}{cccc} 1&1&0&1\\ 0&1&1&0\\ 0&0&0&1\end{array}\right]$$

Hacemos observar que las matrices asociadas a las relaciones entre $A$ y $B$ nos permiten realizar fácilmente, en el caso finito, las operaciones conjuntistas básicas mediante operaciones lógicas entre las entradas de las matrices. Efectivamente, supongamos que $A=\{a_{1},\ldots,a_{m}\}$ y $B=\{b_{1},\ldots,b_{p}\}$, y que $M_{R}=[r_{i,j}]$ y $M_{S}=[s_{i,j}]$. Puesto que vamos a operar con valores Booleanos, es decir, valores de verdad con los que podemos hacer las operaciones lógicas de negación, conjunción, disyunción, condicional y bicondicional, vamos a denotar, para simplificar la notación, la disyunción como una suma y la conjunción como un producto. De esta manera, tendríamos las operaciones

$$\begin{array}{cc} \begin{tabular}{\vert c\vert c\vert c\ve... ... \\ 0&1&0 \\ 0&0&0 \hline \end{tabular} \end{array}$$

Con esta notación, es fácil comprobar que:

Proposición 3.2   $\;$

1. La matriz asociada a $R\cup S$ es $M_{R}+M_{S}$, donde la suma de matrices es entendida componente a componente.
2. La matriz asociada a $R\cap S$ es $M_{R}\ast M_{S}$, donde `$\ast$' representa el producto componente a componente de dos matrices.
3. La matriz asociada a $\overline{R}$ es $\neg M_{R}$, en donde se niegan todas las entradas (Booleanas) de la matriz.
4. La matriz asociada a $R\setminus S$ es $M_{R}\ast(\neg M_{S})$.
5. $R\subseteq S$ si y sólo si $M_{R}\Rightarrow M_{S}$, es decir:
   $$\forall i,\forall j, \;\; r_{i,j}\rightarrow s_{i,j}$$

6. $R=S$ si y sólo si $(M_{R}\Rightarrow M_{S})\wedge(M_{S}\Rightarrow M_{R})$, es decir, si y sólo si $M_{R}=M_{S}$.

Además de la operaciones usuales, las relaciones binarias admiten algunas operaciones adicionales. En primer lugar, definimos la relación inversa a una dada:

Definición 3.3   Dada una relación $R\subseteq A\times B$, se llama relación inversa de $A$, y se denota $R^{-1}$, a la relación $R^{-1}\subseteq B\times A$ definida por

$$\forall a\in A,\forall b\in B, \;\; (b,a)\in R^{-1}\Leftrightarrow(a,b)\in R$$

Es decir, $R^{-1}$ consiste en intercambiar los elementos de los pares ordenados que pertenecen a $R$. Es evidente que, en el caso finito, la matriz asociada a la relación inversa es justamente la traspuesta de la matriz de $R$, es decir

$$M_{R^{-1}}=M_{R}^{t}$$

En segundo lugar, se define lo que se entiende por composición de relaciones:

Definición 3.4   Sean dos relaciones $R\subseteq A\times B$ y $S\subseteq B\times C$. Se llama composición de $R$ y $S$, y se denota $R\circ S$, a la relación $T\subseteq A\times C$ definida por

$$\forall a\in A,\forall c\in C, \;\; a T c \Leftrightarrow \exists b\in C \;\;$$tal que$$\;\; (a R b)\wedge(b S c)$$

La pregunta natural en este momento es cómo calcular (en el caso finito) la matriz asociada a la composición $T=R\circ S$ a partir de las matrices de $R$ y de $S$. Para ello, se tiene el siguiente

Teorema 3.5   La matriz asociada a la relación $R\circ S$ es $M_{R}\cdot M_{S}$.

Ejemplo 3.6   Sean $A=\{1,2\}$, $B=\{a,b,c\}$ y $C=\{x,y\}$, y se consideran las relaciones $R\subseteq A\times B$ dada por

$$R=\{(1,b),(1,c),(2,a)\}$$

y $S\subseteq B\times C$ dada por

$$S=\{(b,x),(c,x),(c,y)\}$$

Las matrices asociadas a $R$ y $S$ son

$$\begin{array}{ccc} M_{R}= \left[\begin{array}{ccc} 0&1&1\\... ...rray}{cc} 0&0\\ 1&0\\ 1&1 \end{array}\right] \end{array}$$

y por tanto la matriz asociada a $R\circ S$ es

$$\left[\begin{array}{ccc} 0&1&1\\ 1&0&0 \end{array}\right] \c... ...nd{array}\right] = \left[\begin{array}{cc} 1&1\\ 0&0 \end{array}\right]$$

Es decir, $R\circ S=\{(1,x),(1,y)\}$.

Siguiente: Relaciones binarias en un Subir: RELACIONES Anterior: Conceptos generales sobre relaciones   Índice General