• Author / Uploaded
• Kevin Manchego Salazar

• Categories
• Número natural
• Conceptos matemáticos
• Análisis matemático
• Relaciones matemáticas
• Lógica matemática

Citation preview

RELACIONES BINARIAS

Par ordenado: Llamaremos par ordenado a un ente matemático que consiste de un par de elementos que están ordenados.

a es la primera componente y b es la segunda componente . Observación:

( a, b ) ≠ ( b, a )

( a , b ) = ( c, d )

⇒ a = c ∧b = d

Producto Cartesiano Sean A y B dos conjuntos diferentes del vacío.

A × B = {( a, b ) / a ∈ A ∧ b ∈ B} Ejemplos: Sean A ={1,2,3} y B={3,4}, hallar a) A×B b) B×A c) A×A Solución

A × B = {(1,3) , (1,4 ) , ( 2,3) , ( 2,4 ) , ( 3,3) , ( 3,4 )}

Propiedades 1. En general A×B ≠ B×A. 2. A × ( B ∪ C ) = ( A × B ) ∪ ( A × C )

A× (B ∩ C ) = ( A× B) ∩ ( A×C )

3. Si A ⊂ B y D ⊂ E ⇒ A × D ⊂ B × E En particular:

4.

A× B ⊂ B × B Si A ⊂ B ⇒  A× A ⊂ A× B

A× (B − C ) = ( A× B) − ( A× C )

Nota:

Si A = ℝ entonces A n =  A × A × ... × A = ℝn = ℝ × ℝ × ... × ℝ  n veces

n veces

R es una relación(binaria) de A en B ⇔ R ⊂ A × B; A ≠ φ , B ≠ φ Ejemplo: Dados los conjuntos:

A = {x ∈ ℕ / . x 2 − 4 = 0}

B = {x ∈ ℝ / . x − 4 = 3}

Hallar todas las relaciones de A en B

Solución:

Para A : x − 4 = 0 ⇔ x = 2 ∨ x = −2 2

pero x ∈ ℕ ⇒ A = {2} Para B :

x − 4 = 3 ⇔ {x − 4 = 3 ∨ x − 4 = −3} ⇔ {x = 7 ∨ x = 1}

como x ∈ ℝ ⇒ B = {1,7}

Luego A × B = {( 2,1) , ( 2,7 )}

Ahora como la relación R es un subconjunto cualquiera de A×B, tendremos que todas las relaciones R de A en B son:

R1 = {( 2,1)} R2 = {( 2,7 )} R3 = {( 2,1) , ( 2,7 )}

R4 = φ

Observaciones: 1. A×B tiene

2

# ( A× B )

elementos.

2. Si un elemento (x,y) pertenece a una relación R, entonces lo simbolizaremos

( x, y ) ∈ R

⇔ xRy ⇔ y = R ( x )

3. Si el conjunto de partida A fuese igual al conjunto de llegada B, entonces decimos que R es una relación de A en A o simplemente R es una relación en A.

Dominio y Rango de una Relación Dominio de R: Llamaremos dominio de una relación R al conjunto formado por todas las primeras componentes de los pares ordenados de R.

Dom ( R ) = {x /

( x, y ) ∈ R }

Rango de R: Llamaremos rango de una relación R al conjunto formado por todas las segundas componentes de los pares ordenados de R.

Rang ( R ) = { y /

( x, y ) ∈ R }

Relación inversa Toda relación R de A en B tiene una relación inversa (recíproca) de B a A, que se define por

R −1 = {( b, a ) /

( a, b ) ∈ R} R −1

Es decir, la relación inversa consta de los pares ordenados que al ser invertidos, es decir, permutados, pertenecen a R.

Ejemplo:

Sean A={1,2,3} y B= {a, b} entonces

R = {(1, a ) , (1, b ) , ( 3, a )} La relación inversa es

R −1 = {( a,1) , ( b,1) , ( a,3)}

Propiedades Dadas las relaciones

R1

y

1).

( R1 ∪ R2 )

2).

( R1 ∩ R2 )

3).

( R1 − R2 ) = R1−1 − R2−1

−1

= R1−1 ∪ R2−1

−1

= R1−1 ∩ R2−1

−1

R2

de A en B, decimos que:

Relación reflexiva Sea R una relación binaria R en A, (A ≠ ∅). Definición: Diremos que R es reflexiva si ∀a∈A, a R a ⇔ (a,a)∈R Ejemplo: 1) En

ℕ

la relación R definida por: “x R y ⇔ x divide a y”

es reflexiva ya que ∀x∈

ℕ,

xRx

porque x divide a x.

2) En ℕ la relación R definida por: “a R b

⇔

a es el doble de b”.

no es reflexiva ya que (1, 1) ∉R puesto que 1 no es el doble de 1

Relación reflexiva

Representación Cartesiana

Si la relación R es reflexiva entonces la diagonal pertenece a la relación.

A

A Representación Sagital:

A

Si la relación R es reflexiva entonces todo elemento tiene una flecha que comienza y termina en sí mismo (un bucle).

Relación simétrica Definición: Diremos que R es simétrica si ∀ a, b ∈A: a R b ⇒ b R a Ejemplo: 1) En

ℤ

la relación R definida por: “a R b

⇔

a – b es múltiplo de 2”.

es simétrica ya que si a R b ⇒ hay p∈ ℤ tal que a – b = 2p ⇒ b – a = 2(-p) con -p ∈ 2) En

ℕ

ℤ

⇒ bRa

la relación R definida por: “x R y ⇔ x divide a y”

no es simétrica ya que 2 R 4 porque 2 divide a 4 pero 4 no divide a 2 por lo tanto (4,2) ∉R.

relación simétrica

Representación Cartesiana Si la relación R es simétrica sobre A entonces los pares relacionados se reflejan respecto a la diagonal principal.

A

A

Representación Sagital:

A

Si la relación R es simétrica entonces todo par de elementos que tiene una flecha la tiene en las dos direcciones

Relación anti simétrica Definición: Diremos que R es antisimétrica si ∀ a, b ∈A: [a R b ∧ b R a] ⇒ a = b Otra manera de expresarlo: Si a≠b ⇒ [ (a,b) ∉ R ∨ (b,a) ∉ R ] Ejemplo: 1) En

ℕ

la relación R definida por: “x R y ⇔ x divide a y” es antisimétrica

Ya que si a R b y b R a entonces existen n, m ∈ b = an y a = bm. Combinándolas,

ℕ tales que:

a = bm = (a.n).m ⇒ n.m = 1

⇒

n = m = 1 ⇒ a = b. 2) En ℤ la relación R definida por: “a R b ⇔ a – b es múltiplo de 2”. no es antisimétrica ya que 2R4 y 4R2, pero 2≠4

Relación antisimétrica

Representación Cartesiana

A Si la relación R es antisimétrica pueden existir pares por encima o por debajo de la diagonal pero ningún par tiene reflejo respecto a la diagonal principal excepto la diagonal misma.

A

Representación Sagital:

A

La relación R es antisimétrica si para cada par de elementos distintos relacionados la flecha está solo en un sentido

Relación Tansitiva Definición: Diremos que R es transitiva si ∀ a, b, c ∈A: [a R b ∧ b R c] ⇒ a R c Ejemplo: 1) En

ℕ

la relación R definida por: “x R y ⇔ x divide a y”

es transitiva ya que si a R b y b R c entonces existen n, m ∈ ℕ tales que: b = an y c = bm. Combinándolas, c = bm = (a.n).m= a(n.m) con n.m ∈ ℕ ⇒ b R c. 2) En

ℕ

la relación R definida por: “a R b

⇔

a es el doble de b”.

no es transitiva ya que (4, 2) ∈ R y (2, 1) ∈ R puesto que 4 es el doble de 2 y 2 es el doble de 1, sin embargo 4 no es el doble de 1, de donde (4,1)∉ R

Relación Transitiva

Representación Sagital: La relación R es transitiva si cada vez que hay un camino entre tres elementos, también está la flecha que comienza en el principio del camino y va al elemento que es final del camino.

A

Cuadro Resumen

Completa la siguiente tabla: Propiedad R

Se satisface sii

Reflexiva

∀a∈A a R a

Simétrica

∀ a, b ∈A: aRb⇒bRa

Antisimétrica

∀ a, b ∈A: [a R b ∧ b R a] ⇒ a = b

Transitiva

∀ a, b, c ∈A: [a R b ∧ b R c] ⇒ a R c

No se satisface sii

Cuadro Resumen

Verifique: Propiedad R

Se satisface sii

No se satisface sii

Reflexiva

∀a∈A a R a

∃ a∈A (a,a)∉R

Simétrica

∀ a, b ∈A: aRb⇒bRa

∃ a, b ∈A: (a, b) ∈ R ∧ (b, a) ∉ R

Antisimétrica

∀ a, b ∈A: [a R b ∧ b R a] ⇒ a = b

∃ a, b ∈A: (a, b) ∈ R ∧ (b, a) ∈ R ∧ a ≠ b

Transitiva

∀ a, b, c ∈A: [a R b ∧ b R c] ⇒ a R c

∃ a, b, c ∈A: (a, b) ∈ R ∧ (b, c) ∈ R ∧ (a, c) ∉ R

Ejercicios

Ejercicio 1: Sea A = {1, 2, 3, 4}. i) Represente gráficamente las relaciones (b) y (d) en forma cartesiana y sagital. ii) Determine las propiedades que satisfacen las siguientes relaciones en A y verifíquelas (demuéstrelas) a)

R = { (1,1) , (2,2) , (3,3)}.

b) c) d) e)

R = { (1,1) , (2,2) , (3,3), (4,4) , (1,2) , (1,4) , (2,1), (3,2) , (4,3) }. R = { (1,1) , (2,2) , (3,3), (4,4)}. R = { (1,1) , (2,2) , (3,3), (1,2), (3,2) , (2,3) }. R = { (1,1) , (1,2) , (1,4) , (2,3), (4,3) }.

Ejercicios

Ejercicio 2: Sea A = {1, 2, 3, 4}. Construya tres relaciones binarias en A con las siguientes propiedades: i) Reflexiva, simétrica y no transitiva ii) Reflexiva, no simétrica y transitiva iii) No reflexiva, simétrica y transitiva

Ejercicios

Ejercicio 3: Sea A = {1, 2, 3, 4}. Considere las siguientes relaciones binarias en A:

(a) 1

(b)

2

A 3

4

1

2

A 3

4

a) Exprese las relaciones anteriores por extensión b) Determine las propiedades que satisfacen las relaciones en A anteriores y pruébelas!

Ejercicios

Ejercicio 4: Sea A = {1, 2, 3, 4, 5}. Considere las siguientes relaciones binarias en A:

(c)

(d)

1

2

1

2

A 5

A

3 4

3

5 4

i) Determine las propiedades que satisfacen las relaciones en A anteriores y pruébelas!

Ejercicios

Ejercicio 5: Definimos en ℜ, el conjunto de los números reales, la relación R : xRy

⇔

x–y∈Ζ

Determina las propiedades que cumple R y demuestra, usando la definición, que efectivamente las verifica!

Tipos de relaciones

Relación de equivalencia Diremos que una relación binaria sobre A, es una relación de equivalencia si satisface las tres propiedades:


R es reflexiva




R es simétrica




R es transitiva

Ejemplos: 1)

En Z la relación R definida por: a R b

2)

Dado un conjunto D⊆ U, la relación: ARB

⇔

⇔

a – b es múltiplo de 3.

A ∩ D = B ∩D

Demuestra que estas son relaciones de equivalencia

Tipos de relaciones Sea

R ⊂ A2

Relación de orden R es una relación de orden en A, si y sólo si


R es reflexiva

a ∈ A ⇒ ( a, a ) ∈ R




R es antisimétrica

{( a, b ) ∈ R

∧ ( b, a ) ∈ R} ⇒ a = b




R es transitiva

{( a, b ) ∈ R

∧ ( b, c ) ∈ R} ⇒ ( a, c ) ∈ R

Relación de orden parcial Sea R una relación de orden en A 

R es de orden parcial si y sólo si (existen pares de elementos incomparables)

∃a , ∃b / ( a, b ) ∉ R ∧ ( b, a ) ∉ R

Relación de orden total Sea R una relación de orden en A 

R es de orden total si

a ≠ b ⇒ {( a , b ) ∈ R ∨

( b, a ) ∈ R}

Ejemplo: En

ℕ

definimos la relación de divisor, es decir

n a ⇔ ∃k ∈ ℕ / a = nk Esta relación es de orden y parcial . En efecto: i) Reflexiva:

a ∈ ℕ : a = a.1 ⇒ a a

ii) Antisimétrica:

Sean a b ∧ b a

⇒ ∃n k1 y k2 ∈ ℕ / b = ak1 ∧ a = bk2

⇒ ab = ( ak1 ) . ( bk2 ) ⇒ 1 = k1k2 ⇒ k1 = 1 = k2 luego a = b

iii) Transitiva: Sean

{a

b ∧ b c} ⇒ {b = ak1 ∧ c = bk2 , k1 , k2 ∈ ℕ}

entonces b.c = ak1.bk2 ⇒ c = a ( k1.k2 )

⇒ c = ak k = k1.k2 ∈ ℕ

⇒a c También es una relación de orden parcial, pues

∃ 2 y ∃ 3: