30/08/2022

MATEMATICA DISCRETA

UNIDAD 4

A B

a 1
b
c 2

Autor: Ing. María Alicia Piñeiro

RELACION:
Dados dos conjuntos A y B, llamamos relación de A en B a cualquier
subconjunto de A X B.

R :A B R es una relación de A en B ( R  AX B )

Ejemplo: Algunas relaciones de A en B:

siendo A = { m, p, h } y B = { 1, 2 }

R1: A  B / R1 = {(m;1), (m;2), (h;1) }

R2: A  B / R2 = {(m;2), (p;1) }

R3: A  B / R3 = {(m;1), (p;1), (h;1) }

¿Cuál es la relación más pequeña que puedes escribir?

R4: A  B / R4 = { }

¿Cuál es la relación más grande que puedes escribir?

R5: A  B / R5 = {(m;1), (m;2), (p;1), (p;2), (h;1), (h;2) }
 30/08/2022

¿Cómo se representan las relaciones?

 Conjuntos de pares ordenados: R = { (p;1) (m;1) (m;2) }

 Diagramas de Venn mediante flechas.

A B

m 1
p
h 2
 Tablas.

A B  Gráficos cartesianos.
m 1
m 2
p 1

DOMINIO DE UNA RELACIÓN:

Sea R: A  B Dom (R) = { x  A /  y  B  (x;y)  R }

Ejemplo: Halla el dominio de la relación R = { (p;1) (m;1) (m;2) }

Dom (R) = { p, m }

IMAGEN DE UNA RELACIÓN:

Sea R: A  B Im (R) = { y  B /  x  A  (x;y)  R }

Ejemplo: Halla la imagen de la relación R = { (p;1) (m;1) (m;2) }

Im (R) = { 1, 2 }
 30/08/2022

RELACIÓN INVERSA O RECIPROCA:

Sea R: A  B R-1 = { (y;x)  B X A / (x;y)  R }

Ejemplo: Halla la inversa de la relación R = { (p;1) (m;1) (m;2) }

R-1 = { (1;p), (1;m), (2;m) }

IMAGEN DE UN ELEMENTO:

Sea a  A Im (a) = { y  B / (a;y)  R }

Ejemplo: Halla las imágenes de los elementos

R(m) = { 1, 2 } R(p) = {1} R(h) = { }

RELACIÓN COMPLEMENTARIA:

Sea R: A  B R = { (x;y)  A X B / (x;y)  R } = A X B - R

Ejemplo: Halla el complemento de R = { (p;1) (m;1) (m;2) }

R = { (p;2), (h;1), (h;2) }

30/08/2022
 30/08/2022

Ejemplo: Dados los siguientes conjuntos:

A = { 1, 2, 3 } B = { x, y, z } C = { m, n } D = {a, b, c, d }

Indica si las siguientes relaciones son funciones. En ese caso, clasifícalas:

R1 : A  B / R1 = { (1;x) , (2;x) , (3;y) }

R2 : A  B / R2 = { (1;z) , (2;x) , (3;y) }

R3 : A  B / R3 = { (1;x) , (1;y) , (2;x) , (3;z) }
R4 : A  C / R4 = { (1,m) , (2;n) }
R5 : A  C / R5 = { (1;n) , (2;n) , (3;n) }
R6 : A  C / R6 = { (1;m) , (2;m) , (3;n) }
R7 : A  D / R7 = { (1;a) , (2;b) , (3;c) }
R8 : A  D / R8 = { (1;a) , (2;b) , (3;c), (3;d) }

Completa: Para que exista una función biyectiva entre dos

conjuntos finitos, sus cardinales deben ser ....IG...U..A.L..E..S.........
 30/08/2022

SOLUCION:
 30/08/2022

MATRICES

 11 a12
a ... a1 m 
MATRIZ 
 a21 a22 ... a2 m 
A =  ... ... FILAS
 ... ... 
 an1 an2 ... anm 

A = (( aij ))
COLUMNAS
A  Knxm

Ejemplo:  4  2 1
A =  3  A  R2x3
 0 6

MATRICES BOOLEANAS
Son aquellas cuyos elementos pertenecen al conjunto { 0, 1 }

Ejemplos:

1 0 0
  A  {0,1}3x3
A= 0 1 0
 1 
1 1 cuadradas

 1 1  B  {0,1}2x2
B=
0 0

 1 1 0
C=   C  {0,1}2x3
 0 1 0 
 30/08/2022

OPERACIONES ENTRE MATRICES BOOLEANAS:

1) SUMA LOGICA o DISYUNCION : 

A B = C cij = aij  bij

 i: 1 ... n  j: 1 ... m

 {0,1}nxm  {0,1}nxm  {0,1}nxm

Ejemplos:

 1 1   0 1 =  1 1

 0 0   0 1  0 1

 1 1 0   0 0 1 1 1 1
   =  

 0 1 0   0 1 1  0 1 1

2) PRODUCTO LOGICO o CONJUNCION : 

A B = C cij = aij  bij

 i: 1 ... n  j: 1 ... m

 {0,1}nxm  {0,1}nxm  {0,1}nxm

Ejemplos:

 1 1   0 1 =  0 1 

 0 0   0 1  0 0 

 1 1 0  0 0 1  0 0 0
    = 
 0 1 0  0 1 1  0 1 0
 30/08/2022

3) PRODUCTO MATRICIAL BOOLEANO: 

m

A B = C cij = V
k=1
aik  bkj

 i: 1 ... n  j: 1 ... m
 {0,1}nxm  {0,1}mxp  {0,1}nxp

 1 0  0 1
 0 1  
 1 0   
Otro ejemplo =  0 1
   1 1   
 0 1  1 1
 30/08/2022

4) TRASPUESTA DE UNA MATRIZ:

(A)t = B
bij = aji

 i: 1 ... n  j: 1 ... m
 {0,1}nxm  {0,1}mxn

Ejemplo:
 1 1 0 t  1 0 
 
 0 1 0
= 1 1
 0 0
 
2x3
3x2

 1 0 0  t 1 0 1
 
Calcula:  0 1 0 =  0 1 1
   
1 1 1   0 0 1

5) COMPLEMENTO DE UNA MATRIZ:

A = B
bij = aij

 i: 1 ... n  j: 1 ... m
 {0,1}nxm  {0,1}nxm

Ejemplo:
 1 1 0  0 0 1
  =  
 0 1 0  1 0 1

2x3 2x3

 1 0 0   0 1 1
 
Calcula:  0 1 0 = 1 0 1
   0 0 0
1 1 1   
 30/08/2022

PROPIEDADES DE LAS OPERACIONES CON MATRICES:

IDEMPOTENCIA AA =A AA=A

A  B =B A
CONMUTATIVIDAD
AB =B A

A  (B  C) = (A  B)  C
ASOCIATIVIDAD A  (B  C) = (A  B)  C
A  (B  C) = (A  B)  C

DISTRIBUTIVIDAD
A  (B  C) = (A  B)  (A  C)
A  (B  C) = (A  B)  (A  C)
 30/08/2022

MATRIZ DE UNA RELACION

Sea R: A  B tal que A = { a1 , a2 , ..., an } y B = { b1 , b2 , ..., bm }

1 si (ai , bj )  R
MR  {0,1} nxm
mij =
0 si (ai , bj )  R

Ejemplo:

Sean los conjuntos: A = {1, 3, 4} y B = {x, y, z, t }

R = {(1,x) , (1, t) , (3,x) , (3,y) , (3,z) , (4,z)}

x y z t
1 0 0 1
1
 
MR = 3  1 1 1 0 
4 
0 0 1 0

OPERACIONES CON LAS MATRICES DE RELACIONES:

Sean R: A  B y S: A  B

Sea MR la matriz de R y MS la matriz de S.

MR  S = MR  MS

MR  S = MR  MS

M -1 = (M )t
R R

M R = (MR)
 30/08/2022

Ejemplo:

1 1 0 1 1 0 0 0
  
M(R) =  1 0 0 0  M(S) =  1 1 0 1 
   
0 1 0 1 0 1 1 1 

1 1 0 1 1 0 0 0
M(RUS) =  1 1 0 1 M(RS) =  1 0 0 0 
   
 0 1 1 1 0 1 0 1
   

1 1 0
  0 1 1 1
 
M(R-1) =  1 0 1  M( S ) =  0 0 1 0 
 
0 0 0  1 0 0 0
 
1 0 1 

COMPOSICION DE RELACIONES
Dadas R: A  B y S: B  C

SoR = { (x,z)  AXC /  y  B  (x,y)  R  (y,z)  S }

A R B S C

x y z

SoR

MSoR = MR  MS
 30/08/2022

Ejemplo:

Sean A = { a, b } B = { x, y, z, t } C = { 1, 2, 3 }

R = { (a,x) , (a,z) , (b,y) , (b,z) , (b,t) }

S = { (x,2) , (x,3) , (y,1) , (z,2), (t,2) }

A B C

a x 1
y 2
b z
t 3

SoR = { (a;2) , (a;3) , (b;1) , (b;2) }

Ahora lo haremos matricialmente

Ejemplo: A = { a, b } B = { x, y, z, t } C = { 1, 2, 3 }

R = { (a,x) , (a,z) , (b,y) , (b,z) , (b,t) }

S = { (x,2) , (x,3) , (y,1) , (z,2), (t,2) }


0 1 1
 

 1 0 1 0 
1 0 0
M(R) =   M(S) =  

 0 1 1 1 
0 1 0
 

 0 1 0

M(SoR) = M(R)  M(S) = 


0 1 1


1 1 0

 30/08/2022

A
A partir de acá, estudiaremos en
particular las relaciones en las
que tanto el conjunto de partida
como el de llegada sea el mismo.

RELACIÓN en A R: A  A
Se lee relación en A.
Ejemplos: Sea A = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }

R: A  A tal que R = { (x;y)  AXA / y = x2 }

S: A  A tal que S = { (x;y)  AXA / 3  x - y }

T: A  A tal que T = { (x;y)  AXA / x + y = 11 }

DIGRAFO elementos del conjunto: vértices o nodos

Si (x,y)  R : arista (flecha) desde x hasta y.

x
 30/08/2022

Ejemplo: A = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }

R: A  A tal que R = { (x;y)  AXA / y = x2 }

2
1
4
3
5 6

9 7 8
10

Ejemplo: A = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }

S: A  A tal que S = { (x;y)  AXA / 3  x - y }

4
1
10
3
7 2

9 5 8
6
 30/08/2022

Ejemplo: A = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }

T: A  A tal que T = { (x;y)  AXA / x + y = 11 }

10
1
9
3
7 2

8 4 6
5

PROPIEDADES DE LAS RELACIONES

Sea una relación R: A  A

R es Reflexiva  a  A: (a;a)  R

R es A-Reflexiva  a  A: (a;a)  R

R es Simétrica  a,b  A: (a;b)  R  (b;a)  R

R es A-simétrica  a,b  A: (a;b)  R  (b;a)  R

R es Antisimétrica  a,b  A: (a;b)  R  (b;a)  R  a=b

R es Transitiva  a,b,c  A: (a;b) R  (b;c) R  (a;c) R

R es A-transitiva  a,b,c  A: (a;b) R  (b;c) R  (a;c) R

30/08/2022
30/08/2022
30/08/2022
30/08/2022
30/08/2022
30/08/2022
 30/08/2022

Ejemplo:

A = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }

R: A  A tal que

R = { (x;y)  AXA / y = x2 }

Ejemplo:

A = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }

S: A  A tal que

S = { (x;y)  AXA / 3  x - y }
 30/08/2022

Ejemplo:

A = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }

T: A  A tal que

T = { (x;y)  AXA / x + y = 11 }

Resumen: PROPIEDADES en las MATRICES

R es Reflexiva I  M(R)

R es A-Reflexiva I  M(R) = N

R es Simétrica M(R) = M(R)t

R es A-simétrica M(R)  M(R)t = N

R es Antisimétrica M(R)  M(R)t  I

R es Transitiva M(R)  M(R)  M(R)

 30/08/2022

Ejercicio:

Dadas las siguientes relaciones definidas en el conjunto A={1,2,3,4}:

R1 = { (1,1) , (1,2) , (1,3) , (2,3) , (1,4)}

R2 = { (1,1) , (1,2) , (2,1) , (2,3) , (4,4) }
R3= { (2,1) , (1,2) , (1,3) , (3,1), (2,4) , (4,2) }
R4 = { (1,1) , (2,2) , (3,3) , (4,4) }
R5 = { (1,2) , (2,3) , (1,4) }
R6= { (1,1) , (1,2) , (2,1) , (2,2) , (3,3) , (2,4) , (4,2) , (4,4)}

Se pide:
 Construye la matriz de cada una de las relaciones.
 Analiza las propiedades observando las matrices.

RESPUESTAS:
30/08/2022
30/08/2022
 30/08/2022

Ejercicio:

Analiza las propiedades de las siguientes relaciones:

En |R la relación: x R y   x – y  = 1

En Z la relación: x R y  x  y +2
 30/08/2022

SOLUCION:

RELACION DE CONECTIVIDAD

R2 todos los caminos de longitud 2

existentes en la relación original R.

R3 todos los caminos de longitud 3

…
existentes en la relación original R.

Rn todos los caminos de longitud n

existentes en la relación original R.
 30/08/2022

x Rn y  existe un camino de longitud n entre x e y

x R∞ y  existe un camino de cualquier longitud entre x e y

RELACION DE CONECTIVIDAD

R = R U R2 U R3 U R4 U ... U Rn U ...

Matricialmente: M(R) = M(R)  M(R2)  M(R3)  ...  M(Rn)  ...

Y teniendo en cuenta que M(R2) = M(R)  M(R) = [M(R)]2
M(R) = M(R)  [M(R)]2  [M(R)]3  ...  [M(R)]n  ...

En realidad, si hay n elementos en el conjunto A, los caminos de longitudes

mayores a n , no nos aportan pares nuevos, por lo tanto alcanza sólo con
calcular hasta el nivel n.

Ejemplo:

Sea A = { a , b , c , d }

y la relación R dada por el digrafo:

0 1 1 0
 
Escribamos primero MR =  1 0 0 0
0 0 0 1 

0 0 1 1

Ahora calculamos MR2

0 1 1 0 0 1 1 0 1 0 0 1
     
 1 0 0 0   1 0 0 0 0 1 1 0
MR2 =  = 0
1 0 1  0 1 1 
0 0 0   0 0 
0 0 1 1 0 0 1 1 0 0 1 1
 30/08/2022

Ahora calculamos MR3

0 1 1 0 1 0 0 1 0 1 1 1
     
1 0 0 0   0 1 1 0 1 0 0 1
MR3 = MR  M R2 =  = 
0 0 0 1   0 0 1 1  0 0 1 1
 
0 0 1 1 0 0 1 1 0 0 1 1

Ahora calculamos MR4

0 1 1 0 0 1 1 1 1 0 1 1
     
MR = MR  M R = 1
4 3  0 0 0   1 0 0 1 0 1 1 1
= 0
0 0 0 1  0 0 1 1 0 1 1
0  
 0 1 1
0 0 1 1 0 0 1 1

Finalmente calculamos MR∞

0 1 1 0 1 0 0 1  0 1 1 1 1 0 1 1 1 1 1 1

      
1 0 0 0 0 1 1 0  1 0  0 1 1 1  = 1 1
MR∞ =  0 1 1 1
0 0 0 1  0 0 1 1    0 0 1 1 
  0 0 1 1
  0 0 1 1  
0 0 1 1 0 0 1 1  0 0 1 1 0 0 1 1
  0 0 1 1