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

$\displaystyle 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

$\displaystyle 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

$\displaystyle 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

$\displaystyle 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

$\displaystyle 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{displaymath}
\begin{array}{cc}
\begin{tabular}{\vert c\vert c\vert c\ve...
... \\
0&1&0 \\
0&0&0  \hline
\end{tabular}
\end{array}
\end{displaymath}

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:

    $\displaystyle \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

$\displaystyle \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

$\displaystyle 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

$\displaystyle \forall a\in A,\forall c\in C, \;\;
a T c \Leftrightarrow \exists b\in C \;\;$tal que$\displaystyle \;\;
(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

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

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

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

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

\begin{displaymath}\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}\end{displaymath}

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

$\displaystyle \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
Jose Ignacio Farran Martin 2003-07-16