Post on 07-Jul-2015
RELACIONES BINARIAS
Par ordenado: Llamaremos par ordenado a un ente matemtico que consiste de un par de elementos que estn ordenados.
a es la primera componente y b es la segunda componente . Observacin:
( a, b ) ( b, a ) a = c b = d
( a , b ) = ( c, d )
Producto CartesianoSean A y B dos conjuntos diferentes del vaco.
A B = {( a, b ) / a A b B}Ejemplos: Sean A ={1,2,3} y B={3,4}, hallar a) AB b) BA c) AA Solucin
A B = {(1,3) , (1,4 ) , ( 2,3) , ( 2,4 ) , ( 3,3) , ( 3,4 )}
Propiedades1. En general AB BA. 2. A ( B C ) = ( A B ) ( A C )A (B C ) = ( A B) ( AC )
3. Si A B y D E A D B E En particular:
A B B B Si A B A A A B
4.
A (B C ) = ( A B) ( A C )Si A = entonces A n = A A ... A = n = ... n veces n veces
Nota:
R es una relacin(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
Solucin:
Para A : x 4 = 0 x = 2 x = 22
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 relacin R es un subconjunto cualquiera de AB, tendremos que todas las relaciones R de A en B son:
R1 = {( 2,1)} R2 = {( 2,7 )} R3 = {( 2,1) , ( 2,7 )}Observaciones:1. AB tiene
R4 =
2
# ( A B )
elementos.
2. Si un elemento (x,y) pertenece a una relacin 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 relacin de A en A o simplemente R es una relacin en A.
Dominio y Rango de una RelacinDominio de R: Llamaremos dominio de una relacin R al conjunto formado por todas las primeras componentes de los pares ordenados de R.
Dom ( R ) = {x /Rango de R:
( x, y ) R }
Llamaremos rango de una relacin R al conjunto formado por todas las segundas componentes de los pares ordenados de R.
Rang ( R ) = { y /
( x, y ) R }
Relacin inversaToda relacin R de A en B tiene una relacin inversa (recproca) de B a A, que se define por
R 1 = {( b, a ) /
( a, b ) R}R 1
Es decir, la relacin 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 relacin inversa es
R 1 = {( a,1) , ( b,1) , ( a,3)}
PropiedadesDadas las relaciones
R1
y
R2
de A en B, decimos que:
1). 2). 3).
( R1 R2 ) ( R1 R2 )
1
= R11 R2 1 = R11 R2 1
1 1
( R1 R2 ) = R11 R21
Relacin reflexivaSea R una relacin binaria R en A, (A ). Definicin: Diremos que R es reflexiva si aA, a R a (a,a)R Ejemplo:1) En
la relacin R definida por: x R y x divide a y
es reflexiva ya que x
,
xRx
porque x divide a x.
2) En la relacin 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
Relacin reflexiva
Representacin Cartesiana
Si la relacin R es reflexiva entonces la diagonal pertenece a la relacin.
A
ARepresentacin Sagital:Si la relacin R es reflexiva entonces todo elemento tiene una flecha que comienza y termina en s mismo (un bucle).
A
Relacin simtricaDefinicin: Diremos que R es simtrica si a, b A: a R b b R a Ejemplo:1) En
la relacin R definida por: a R b
a b es mltiplo de 2.
es simtrica ya que si a R b hay p tal que a b = 2p b a = 2(-p) con -p 2) En
bRa
la relacin R definida por: x R y x divide a y
no es simtrica ya que 2 R 4 porque 2 divide a 4 pero 4 no divide a 2 por lo tanto (4,2) R.
relacin simtrica
Representacin CartesianaSi la relacin R es simtrica sobre A entonces los pares relacionados se reflejan respecto a la diagonal principal.
A
A
Representacin Sagital:Si la relacin R es simtrica entonces todo par de elementos que tiene una flecha la tiene en las dos direcciones
A
Relacin anti simtricaDefinicin: Diremos que R es antisimtrica si a, b A: [a R b b R a] a = b Otra manera de expresarlo: Si ab [ (a,b) R (b,a) R ] Ejemplo:1) En
la relacin R definida por: x R y x divide a y es antisimtrica
Ya que si a R b y b R a entonces existen n, m b = an y a = bm. Combinndolas, n = m = 1 a = b.
tales que:
a = bm = (a.n).m n.m = 1
2) En la relacin R definida por: a R b a b es mltiplo de 2. no es antisimtrica ya que 2R4 y 4R2, pero 24
Relacin antisimtrica
Representacin Cartesiana
ASi la relacin R es antisimtrica pueden existir pares por encima o por debajo de la diagonal pero ningn par tiene reflejo respecto a la diagonal principal excepto la diagonal misma.
A
Representacin Sagital:La relacin R es antisimtrica si para cada par de elementos distintos relacionados la flecha est solo en un sentido
A
Relacin TansitivaDefinicin: Diremos que R es transitiva si a, b, c A: [a R b b R c] a R c Ejemplo:1) En
la relacin 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. Combinndolas, c = bm = (a.n).m= a(n.m) con n.m b R c. 2) En
la relacin 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
Relacin Transitiva
Representacin Sagital:La relacin R es transitiva si cada vez que hay un camino entre tres elementos, tambin 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 RReflexiva
Se satisface sii aA a R a a, b A: aRbbRa a, b A: [a R b b R a] a = b a, b, c A: [a R b b R c] a R c
No se satisface sii
Simtrica
Antisimtrica
Transitiva
Cuadro Resumen
Verifique:Propiedad RReflexiva
Se satisface sii aA a R a a, b A: aRbbRa a, b A: [a R b b R a] a = b a, b, c A: [a R b b R c] a R c
No se satisface sii aA (a,a)R a, b A: (a, b) R (b, a) R a, b A: (a, b) R (b, a) R a b a, b, c A: (a, b) R (b, c) R (a, c) R
Simtrica
Antisimtrica
Transitiva
Ejercicios
Ejercicio 1:Sea A = {1, 2, 3, 4}. i) Represente grficamente las relaciones (b) y (d) en forma cartesiana y sagital. ii) Determine las propiedades que satisfacen las siguientes relaciones en A y verifquelas (demustrelas) a) b) c) d) e) R = { (1,1) , (2,2) , (3,3)}. 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, simtrica y no transitiva ii) Reflexiva, no simtrica y transitiva iii) No reflexiva, simtrica y transitiva
Ejercicios
Ejercicio 3:Sea A = {1, 2, 3, 4}. Considere las siguientes relaciones binarias en A:
(a)1 3 2 1 3
(b)2
A4
A4
a) Exprese las relaciones anteriores por extensin b) Determine las propiedades que satisfacen las relaciones en A anteriores y prubelas!
Ejercicios
Ejercicio 4:Sea A = {1, 2, 3, 4, 5}. Considere las siguientes relaciones binarias en A:
(c)
(d)
1
2
1
2
A5 4 3 5 4 3
A
i) Determine las propiedades que satisfacen las relaciones en A anteriores y prubelas!
Ejercicios
Ejercicio 5:Definimos en , el conjunto de los nmeros reales, la relacin R : xRy xy
Determina las propiedades que cumple R y demuestra, usando la definicin, que efectivamente las verifica!
Tipos de relaciones
Relacin de equivalenciaDiremos que una relacin binaria sobre A, es una relacin de equivalencia si satisface las tres propiedades: R es reflexiva R es simtrica R es transitiva
Ejemplos:1) 2) En Z la relacin R definida por: a R b Dado un conjunto D U, la relacin: ARB A D = B D a b es mltiplo de 3.
Demuestra que estas son relaciones de equivalencia
Tipos de relacionesSea
R A2
Relacin de ordenR es una relacin de orden en A, si y slo si R es reflexiva R es antisimtrica R es transitivaa A ( a, a ) R
{( a, b ) R{( a, b ) R
( b, a ) R} a = b ( b, c ) R} ( a, c ) R
Relacin de orden parcialSea R una relacin de orden en A R es de orden parcial si y slo si (existen pares de elementos incomparables)
a , b / ( a, b ) R ( b, a ) R
Relacin de orden totalSea R una relacin de orden en A R es de orden total si
a b {( a , b ) R
( b, a ) R}
Ejemplo:En
definimos la relacin de divisor, es decir
n a k / a = nkEsta relacin es de orden y parcial . En efecto: i) Reflexiva: ii) Antisimtrica:
a : a = a.1 a a
Sean a b b a
n k1 y k2 / b = ak1 a = bk2 luego a = b
ab = ( ak1 ) . ( bk2 ) 1 = k1k2 k1 = 1 = k2
iii) Transitiva: Sean
{a
b b c} {b = ak1 c = bk2 , k1 , k2 } c = ak k = k1.k2
entonces b.c = ak1.bk2 c = a ( k1.k2 )
a cTambin es una relacin de orden parcial, pues
2 y 3: