Relaciones Binarias

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 es una relación entre y , el hecho de que un par ordenado esté en suele denotarse

Asimismo, el hecho contrario, es decir , suele denotarse , o simplemente . Una relación binaria admite una representación matricial, siempre que los dominios de la relación sean finitos. En efecto, supongamos que y . Entonces la matriz asociada a es la matriz Booleana con filas y columnas

dada por

Ejemplo 3.1 Se consideran los conjuntos y , y se define la relación

(es decir, si y sólo si ). Entonces, la matriz asociada a es

Hacemos observar que las matrices asociadas a las relaciones entre y 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 y , y que y . 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

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

Proposición 3.2

1. La matriz asociada a es , donde la suma de matrices es entendida componente a componente.

2. La matriz asociada a es , donde ` ' representa el producto componente a componente de dos matrices.

3. La matriz asociada a es , en donde se niegan todas las entradas (Booleanas) de la matriz.

4. La matriz asociada a es .

5. si y sólo si , es decir:

6. si y sólo si , es decir, si y sólo si .

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 , se llama relación inversa de , y se denota , a la relación definida por

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

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

Definición 3.4 Sean dos relaciones y . Se llama composición de y , y se denota , a la relación definida por

tal que

La pregunta natural en este momento es cómo calcular (en el caso finito) la matriz asociada a la composición a partir de las matrices de y de . Para ello,

...