Relaciones binarias

Relaciones binariasJVBYUNI-FIIS 2014Relacin binariaDados dos conjuntos A y B, una relacin binaria de A en B es cualquier subconjunto R del producto cartesiano AxB R AxB = { (a, b) / a A, b B} Si (a, b) R, se dice que a esta relacionado con b por R Se escribe aRb.Si (a, b) R, se escribe aRbSi A=B se dice que R es una relacin (binaria) sobre A

EjemploSean A={2, 3, 4} y B={3, 4, 5, 6, 7} R: A B, como (x, y) R, si x divide a y .(x|y)R={(2, 4), (2, 6), (3, 3), (3, 6), (4, 4)}

Relacin binariaDominio y rangoSea R: A B

Dominio de RDom(R)= {x A / (x, y) R para algn y B}

Rango de RRan(R)= {y B /(x, y) R para algn x A}

En el ejemplo anteriorDom(R) = {2, 3, 4} Ran(R) = {3, 4, 6}

Representacin de una relacinUna relacin binaria R, se puede representar mediante

DigrafoMatrizDiagrama sagital

Digrafo de una relacinSea R la relacin sobre A = {1, 2, 3, 4} y R= {(1, 1), (1, 2), (2, 1), (2, 2), (2, 3), (2, 4), (3, 4), (4, 1)}

2134Propiedades de las relacionesSea R una relacin sobre el conjunto A . R: A ARelacin reflexivaR es reflexiva si a A => (a, a) R

Relacin irreflexivaR es irreflexiva si a A => (a, a) R Relacin simtricaR es simtrica si a, b A , si aRb =>bRa

Propiedades de las relacionesRelacin antisimtricaR es antisimtrica si a, b A ,se cumple que si aRb bRa a = b

Relacin transitivaR es transitiva si a, b, c A se cumple queSi aRb bRc aRc

Propiedades de las relacionesSea R la relacin sobre A = {3, 4, 5, 6} definida como (x, y) R si x y

R es:Reflexiva?Simtrica?Transitiva?Antisimtrica?Irreflexiva?

Matriz de una relacinEs posible representar una relacin entre dos conjuntos finitos como una matriz de la siguiente manera.Si A={a1, a2, .am} y B={b1, b2, .bn} son conjuntos finitos que contienen m y n elementos respectivamente. y R una relacin de A a B, se representa por la matriz mxn. MR =(mij), la cual se define por 1, si (ai, bj) R mij= 0, si (ai, bj) R

Matriz de una relacinEjemploSea A={1, 2, 3, 4} R: A A R={(1, 1), (1, 3), (1, 4), (2, 1), (2, 2), (2, 4), (3, 1), (4, 2)}Hallar MR

1 0 1 1MR = 1 1 0 1 1 0 0 0 0 1 0 0Relacin inversa y complementariaSea R: A B

Relacin inversa = {(b, a) / (a, b) R}

Relacin complementaria R: A BTal que a A, b R , aRb (a, b) R

Operaciones con relacionesSean R: A B y S: A BUninR S aRb aSbInterseccinR S aRb aSb

Relacin compuestaSean los conjuntos: A, B y CLas relaciones: R: A B S: B CLa relacin compuesta R y S: S0R a A, c CS0R={(a, c)/ b B tal que ((a, b) R (b, c) S)}

Ejemplos