Matematicas discretas propiedades de las relaciones

Matemáticas Discretas

UNIDAD 1.- RELACIONES
OBJETIVO: El alumno identificará cuando una relación es de equivalencia, distinguirá las clases de orden, construirá y aplicará las matrices de incidencia y el algoritmo de Warshall para encontrar cerraduras transitivas. Una relación R de un conjunto A sobre otro conjunto B ⊆ AXB, donde los elementos de cada pareja ordenada están ligados a lascondiciones que establece la relación R. De este modo una relación R consiste en lo siguiente A) Un conjunto A B) Un conjunto B(Que puede ser el mismo conjunto A) C) Proposición o enunciado que indica como están relacionados los elementos de los conjuntos. DEFINICIÓN: Sea R una relación y sean los conjuntos A y B, se dice que R es una relación sobre A siempre y cuando R ⊆ AXA y se dice que R es unrelación de A a B, siempre y cuando R ⊆ de AXB .

PRODUCTO CRUZ A = {1, 2, 3, 4} Y B = {3, 4}

El producto cruz de A a B se realiza de la siguiente manera: AXB = {(1, 3), (1, 4), (2, 3), (2, 4), (3, 3), (3, 4), (4, 3), (4, 4)} EJERCICIO: Sean A = {1, 2, 3, 4} y B = {3, 4}, encontrar que relación son (AXA, de AXB, BXA, BXB o ninguna) R1={(1, 1), (2, 2), (3, 3), (4, 4)} R2={(1, 2), (3, 2)} R3={(1,4), (1, 5), (4, 7)} R4={(4, 4), (5, 2), (6, 2), (7, 3)} R5={(1, 7), (7, 1)} R = relación de AXA R = relación de AXA R = relación de AXB R = relación de BXA R = ninguna
Página 1

Lic. Christian Carlos Delgado Elizondo

Matemáticas Discretas

EJERCICIO: Sea A = {1,2,3,4} Encontrar la relación R (menor que) en A: donde a R b si y sólo si a < b Respuesta R = {(1, 2), (1, 3), (1, 4), (2, 3), (2,4), (3, 4)}

EJERCICIO. Sea A = R el conjunto de todos los números reales, se define la siguiente relación, R en A: x R y si y sólo si. x y y satisfacen la ecuación x2 +y2 = 1 4 9 (0, 3)

(-2, 0)

(2, 0)

(0, -3)

Respuesta: Son todos los puntos de la línea roja.

Lic. Christian Carlos Delgado Elizondo

Página 2

Matemáticas Discretas

REPRESENTACION DE LAS RELACIONES Existencuatro formas de representar gráficamente las relaciones: 1. 2. 3. 4. Diagrama cartesiana Diagrama de Venn. Matriz Booleana. Digrafos.

EJEMPLO Sean los conjuntos A = {1, 2, 3, 4} y B = {x, y, z} y la relación R = {(1, x) (2, y), (3, x), (4, z)}. Representar la relación R mediante las cuatro formas ya mencionadas. a) Representación Cartesiana de R.

z

.

y

.

x

.

.

1

23

4

b) Representación de Diagrama de Venn. A B

1 x 2 y 3 z 4

Lic. Christian Carlos Delgado Elizondo

Página 3

Matemáticas Discretas

c) Representación de Matriz Booleana. 1  0 MR =  1  0  0 0  1 0 0 0  0 1 

d) Representación por gráficos.

1 x 2 y 3 z 4

PROPIEDADES DE LAS RELACIONES Una relación R sobre un conjunto A se dice que es reflexiva si ∀ a Є A →(a, a) Є R, es decir, a R a. 1) Una relación reflexiva está caracterizada gráficamente porque: a) Contiene bucles en cada vértice de su dígrafo. b) En su matriz booleana contiene 1 en su diagonal principal. c) En su presentación cartesiana contiene los elementos (i, i) EJEMPLO: Sea A = {1, 2, 3, 4} y R = {(1, 1), (2, 2), (3, 3)} Por definición se sabe que ∀ a Є A → (a, a) Є R ∴ (1,1) Є R, (2,2) ЄR. (3,3) Є R y (4,4) ∉ R

Lic. Christian Carlos Delgado Elizondo

Página 4

Matemáticas Discretas

Por lo tanto R no cumple con la propiedad reflexiva sobre el conjunto A ya que (4,4) no pertenece a la relación. 2) Una Relación R sobre A es simétrica, si ∀ a, b ∈ A se cumple que si a R b → bRa a. Gráficamente una relación simétrica contiene en su dígrafo por cada arco de ida tiene otro deregreso para cada par de vértices i, j. b. Su matriz booleana pose los elementos 1 dispuestos simétricamente respecto a su diagonal principal dicho de otra manera la transpuesta de A = At. EJEMPLO: Sea A = {1, 2, 3} y R = {(1, 1), (2, 3), (3, 2)} (1,1) ∈ R → (1, 1) ∈ R (2, 3) ∈R → (3, 2) ∈ R (3, 2) ∈ R → (2, 2) ∈ R Por lo tanto R es una relación simétrica sobre A. 3) Una relación R sobre A es...