Relaciones binarias

Relaciones binarias
Matemática discreta

Matemática discreta. Relaciones binarias

1

Relación binaria en A
• Dados dos conjuntos A y B, una relación R binaria es cualquier subconjunto deAxB • Dados a∈A y b∈B, a está relacionado con b por R si (a,b)∈R, aRb. Si a no está relacionado con b, es decir, (a,b)∉R, escribimos aRb. • Si B=A, R es una relación binaria en A.

Matemáticadiscreta. Relaciones binarias

2

Representación de una relación
• Formal: aRb si a y b cumplen una cierta propiedad P. a b • Diagrama sagital: aRb • Matriz de adyacencia: aRb y aRc
b c . . . a . 1 0 .. . . . .
⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝

. .

. .

⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠

Matemática discreta. Relaciones binarias

3

Diagrama sagital
• Representación gráfica con flechas.
– a∈A– aRb •a

a•

•b

ejemplo: A={a,b,c,d} R={(a,c),(a,d),(b,a),(b,b),(b,d),(c,a),(d,c)} a• •b c•
Matemática discreta. Relaciones binarias

•d
4

Matriz de adyacencia
• Matriz booleanaMR=(mij) • A={a1, ..., an} mij=1 si aiRaj mij=0 si aiRaj ejemplo: A={a,b,c,d} R={(a,c),(a,d),(b,a),(b,b),(b,d),(c,a),(d,c)}
MR =
⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝

0 0 1 1 1 1 0 1

1 0 0 0

0 0 1 0⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠

Suponemos un orden en los elementos de A, en este caso el alfabético.

Matemática discreta. Relaciones binarias

5

Operaciones con relaciones 1
Dadas R1 y R2sobre A • Unión: R1∪ R2={(a,b) ∈AxA / aR1b ó aR2b} • Composición o producto: R1°R2={(a,b) ∈AxA / ∃c∈A aR1c y cR2b}
– En general, R1°R2 ≠ R2°R1 – La composición es asociativa: Rn+1=Rn ° RMatemática discreta. Relaciones binarias

6

Operaciones con relaciones 2
• M(R1∪ R2)=MR1 ⊕ MR2 • M(R1°R2)=MR1 ⊗ MR2
– ⊕ suma booleana – ⊗ producto booleano ⊕ 0 1 0 0 1 1 1 1 ⊗ 0 1 0 0 0 1 0 1
7Matemática discreta. Relaciones binarias

Operaciones con relaciones 3
Dada R sobre A={a1,..,an} y MR su matriz de adyacencia: • MR = OR ⇔ R=∅ (matriz nula de orden n) • MR = 1R ⇔ R=AxA (matriz de...