relacion binaria

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
.
a ..
.
⎛
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝

b
.
1
.
.

Matemática discreta. Relaciones binarias

c
.
0
.
.

.
.

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

.
.

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. Relacionesbinarias

•d
4

Matriz de adyacencia
• Matriz booleana MR=(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

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

0 0 10

Matemática discreta. Relaciones binarias

5

Operaciones con relaciones 1
Dadas R1 y R2 sobre 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 ° R

Matemá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

Matemática discreta. Relaciones binarias

⊗
0
1

0
0
0

1
0
1
7

Operaciones con...