UNIDAD 2 - CONJUNTOS Y RELACIONES.pdf

Apuntes sobre conjuntos y relaciones

Matematicas discretas

1. Unidad 2: Conjuntos y
relaciones
Docente: Juan Francisco Castillo León

2. Contenido
2.1 Características de los conjuntos y subconjuntos
2.2 Operaciones con conjuntos
2.3 Propiedades y aplicaciones de los conjuntos
2.4 Conceptos básicos: producto cartesiano y relación binaria
2.5 Representación de las relaciones
2.6 Propiedades de las relaciones
2.7 Relaciones de equivalencia
2.8 Funciones
2.9 Aplicaciones de las relaciones y las funciones en la computación

3. 2.1 Características de los conjuntos y subconjuntos
Concepto de conjunto:
Un conjunto es una colección bien definida de objetos llamados
elementos o miembros del conjunto.

4. 2.1 Características de los conjuntos y subconjuntos
Los conjuntos se indican por medio de una letra mayúscula y los elementos
por medio de letras minúsculas, números o combinaciones de ambos. Todos
los elementos se colocan entre llaves { -}, separados por comas.
Notación abstracta.
Se lee como A es el conjunto de las x, tal que cumple con la condición (o
condiciones) P(x)

5. 2.1 Características de los conjuntos y subconjuntos
Conjuntos de números .
N: Conjunto de los números naturales
Z+ : Conjunto de los números enteros no negativos.
Z: Conjunto de los números enteros
Q: Conjunto de los números racionales
R: Conjunto de los números reales
C: Conjunto de los números complejos.
U: Conjunto Universo
∅: Conjunto vacío.

6. 2.1 Características de los conjuntos y subconjuntos
Subconjuntos
Si todos los elementos de Atambién son elementos de B, se dice que A
es subconjunto de B, o que Aesta contenido en B.
Si A no es un subconjunto de Bse escribe:

7. 2.1 Características de los conjuntos y subconjuntos
Subconjuntos

8. 2.1 Características de los conjuntos y subconjuntos
APLICANDO LA DEFINICON DE SUBCONJUNT TENEMOS:
1.Todo conjunto A es un subconjunto de si mismo
2.El conjunto vacío es un subconjunto de todos los conjuntos y en
particular de si mismo.
3.Todos los conjuntos son subconjuntos del conjunto universo.

9. 2.1 Características de los conjuntos y subconjuntos
Conjunto potencia de A
Por otro lado, si A es un conjunto entonces al conjunto de todos los
subconjuntos de A se le llama conjunto potencia de A y se indica como
P(A)

10. 2.1 Características de los conjuntos y subconjuntos
Diagrama de Venn

11. 2.2 Operaciones con conjuntos
Union (A∪�)

12. 2.2 Operaciones con conjuntos
Union (A∪�)

13. 2.2 Operaciones con conjuntos
Union (A∪�)

14. 2.2 Operaciones con conjuntos
Intersección (A∩�)

15. 2.2 Operaciones con conjuntos
Intersección (A∩�)

16. 2.2 Operaciones con conjuntos
Intersección (A∩�)

17. 2.2 Operaciones con conjuntos
Ley distributiva

18. 2.2 Operaciones con conjuntos
Ley distributiva

19. 2.2 Operaciones con conjuntos
Complemento ( A’ →ҧ�)

20. 2.2 Operaciones con conjuntos
Complemento ( A’ →ҧ�)

21. Ley de Morgan
El matemático ingles AugustusDe Morgan demostró que:
1.La negación de la intersección de dos o mas conjuntos es
equivalente a la unión de los conjuntos negados separadamente.
2.La negación de la unión de dos o mas conjuntos es igual a la
intersección de los conjuntos negados por separado.

22. Ley de Morgan
Sean los conjuntos :
Aplicando las definiciones correspondientes se tiene que:
Por otro lado también se tiene que:

23. Ley de Morgan
Usando diagramas de Vennse tiene que:
Por lo tanto se puede afirmar que:
De acuerdo a la ley de Morgan también se puede aplicar a la intersección de
la siguiente manera:

24. Ley de Morgan
Las operaciones de unión e intersección, así como la ley de Morgan, se
pueden extender a mas de dos conjuntos.

25. 2.2 Operaciones con conjuntos
Diferencia (A-B)

26. 2.2 Operaciones con conjuntos
Diferencia (A-B)

27. 2.2 Operaciones con conjuntos
Diferencia simétrica

28. 2.2 Operaciones con conjuntos
Diferencia simétrica

29. 2.2 Operaciones con conjuntos (a)
Ejemplos

30. 2.2 Operaciones con conjuntos (b)
Ejemplos

31. 2.2 Operaciones con conjuntos (b)
Ejemplos

32. 2.2 Operaciones con conjuntos (c)
Ejemplos

33. 2.2 Operaciones con conjuntos (d)
Ejemplos

34. 2.2 Operaciones con conjuntos (d)
Ejemplos

35. 2.2 Operaciones con conjuntos (d)
Ejemplos

36. 2.3 Propiedades y aplicaciones de los
conjuntos

37. 2.3 Propiedades y aplicaciones de los
conjuntos

38. 2.3 Propiedades y aplicaciones de los
conjuntos

39. 2.3 Propiedades y aplicaciones de los
conjuntos

40. Conjuntos finitos
Sean A y B dos conjuntos finitos, entonces:

41. Conjuntos finitos
Ejemplo 3.17
De 34 programas revisados en programación “C++”, 23 marcaron error
en la compilación, 12 tuvieron fallas en lógica y 5 en lógica y
compilación. ¿Cuántos programas tuvieron al menos un tipo de error?
Aquí se tiene que

42. Conjuntos finitos
Ejemplo 3.18
En la biblioteca existen 103 libros de ciencias de la computación que tratan en
cierta medida los siguientes temas:
•Compiladores
•Estructura de datos
•Redes
Del total de 50 libros tienen información sobre compiladores, 54 sobre estructuras
de datos, 51 sobre redes, 30 sobre compiladores y estructuras de datos, 32 sobre
compiladores y redes, 35 sobre estructuras de datos y redes, 19 sobre los tres
temas.
a)¿Cuántos libros contienen material exactamente sobre uno de los tres temas?
b)¿Cuántos no tienen material de redes?
c)¿Cuántos no tienen material sobre ninguno de los temas?
d)¿Cuántos libros contienen material de compiladores y redes pero no de estructuras de
datos?

43. Conjuntos finitos
Ejemplo 3.18
Solución:

44. 2.3 Propiedades y aplicaciones de los
conjuntos
Aplicaciones:
•Una relación es un conjunto y en base de datos es posible llevar a cabo operaciones
entre relaciones, de la misma manera en que se hacen en teoría de conjuntos de forma
que los conceptos de unión, intersección, complementación, así como otras reglas
lógicas que resultan de mezclar estas tres operaciones básicas de conjuntos dan origen a
lo que se conoce como algebra relacional, misma que a su ves proporciona los elementos
necesarios con los que se manejan las bases de datos relacionales y que permiten
obtener la información en forma organizada y concreta.
•Los lenguajes de programación se definen como un conjunto de conjuntos, y dentro de
ellos se pueden mencionar el conjunto de símbolos (alfabeto) con los cuales se forman
las palabras de un lenguaje, el conjunto de símbolos no terminales que permiten
multiplicar y mezclar organizadamente los símbolos del alfabeto, el conjunto de
composiciones o reglas que se deben usar para la estructuración de las palabras validas
en el lenguaje y el conjunto de símbolos terminales que marcan el limite de esas
palabras validas de un lenguaje. Por lo tanto, si un lenguaje es un conjunto de conjuntos,
es claro que obedece también a las leyes y reglas de la teoría de conjuntos.

45. 2.3 Propiedades y aplicaciones de los
conjuntos
Aplicaciones:
•Las redes de teléfonos, eléctricas, carreteras, de agua potable o de
computadoras son relaciones y por lo tanto son conjuntos a los cuales
se les puede aplicar también las operaciones de unión, intersección,
complementación, composición y ley de Morgan, de la misma manera
que se hace en teoría de conjuntos, por lo tanto también es una
aplicación practica de la teoría de conjuntos. Esta representación
grafica de los conjuntos se conoce en computación como teoría de
grafos y será objeto de estudio posteriormente en este libro.

46. TAREAS –PARTE 1

47. TAREAS –PARTE 1

48. TAREAS –PARTE 1

49. TAREAS –PARTE 1
Resolver los problemas siguientes, usando
conjuntos finitos.
1.-La compañía “desarrollo de sistemas” necesita contratar 18
personas que programen en Access y 12 personas que programen en
java. De estos programadores se considera que 10 personas saben
programar tanto en Access como en java. ¿Cuántos programadores
deberá contratar la compañía?

50. TAREAS –PARTE 1
Resolver los problemas siguientes, usando
conjuntos finitos.
2.-De una muestra de 42 estudiantes de la carrera de informática se obtuvo el siguiente
numero de reprobados por materia:
•28 matemáticas
•26 fundamentos de programación
•17 administración
•16 matemáticas y fundamentos de programación
•12 fundamentos de programación y administración
•8 matemáticas y administración
•4 matemáticas, fundamentos de programación y administración
a)¿Cuántos estudiantes no reprobaron ninguna materia de las antes mencionadas?
b)¿Cuántos estudiantes reprobaron solamente fundamentos de programación?
c)¿Cuántos estudiantes reprobaron solamente alguna de las tres materias?
d)¿Cuántos reprobaron matemáticas y fundamentos para programación, pero no
administración?

51. TAREAS –PARTE 1
Resolver los problemas siguientes, usando
conjuntos finitos.
3.-De un grupo de 40 alumnos del TEC, algunos están estudiando para
presentar examen como se indica a continuación:
•28 Teoría de la computación
•8 redes de computadoras
•20 inteligencia artificial
•13 Teoría de la computación y redes de computadora
•8 Redes de computadoras e inteligencia artificial
•10 Teoría de la computación e inteligencia artificial
•4 estudian las tres asignaturas.
a)¿Cuántos de ellos no estudian para ninguna de las tres asignaturas?
b)¿Cuántos de ellos estudian únicamente para inteligencia artificial?
c)¿Cuántos están estudiando teoría de la computación y redes pero no
inteligencia artificial?

52. TAREAS –PARTE 1
Resolver los problemas siguientes, usando
conjuntos finitos.
4.-Se aplico una encuesta entre los 714 jóvenes que estudian la carrera de
ingeniería en sistemas computacionales de una universidad, para conocer las
preferencias de especialidad de su carrera. Los resultados obtenidos son:
•206 prefieren ingeniería de software
•291 prefieren sistemas distribuidos
•215 prefieren inteligencia artificial
•59 prefieren ingeniería del software y sistemas distribuidos
•68 prefieren ingeniería del software e inteligencia artificial
•80 prefieren sistemas distribuidos e inteligencia artificial
•28 se inclinan por las tres especialidades al mismo tiempo.
a)¿Cuántos prefieren únicamente sistemas distribuidos como especialidad?
b)¿Cuántos se inclinan por ingeniería del software e inteligencia artificial, pero no
por ingeniería del software?
c)¿Cuántos no pusieron preferencia de especialidad?

53. Relaciones
•Una relación es una correspondencia entre dos elementos de dos
conjuntos con ciertas propiedades.
•En computación las relaciones se utilizan en bases de datos, estructuras de
datos, redes, autómatas y lenguajes.
•Para relacionar datos de un archivo con otra información se establece el
campo relación y las reglas que permitan la búsqueda y asignación de
información.
•Un autómata es un conjunto de estados, y algunos de ellos se consideran
de aceptación y otros no pero la finalidad es el reconocimiento de la
palabra de un lenguaje; se puede considerar a los autómatas como una
relación. (Un uso es su aplicación los compiladores).
•Una red (de computadoras, eléctrica, telefónica, de agua, etc.) también se
puede ver como una relación.

54. Elementos de una relación
Relación
Dados dos conjuntos no vacíos A y B, una relación R es un conjunto de
pares ordenados en donde el primer elemento “a” esta relacionado con
el segundo elemento “b” por medio de cierta propiedad o
característica. La relación de indica como aRb:

55. Elementos de una relación
Una relación es una tabla que muestra la correspondencia de unos
elementos respecto a otros. Por ejemplo:
En este caso se tiene que:

56. Ejemplo 6.1

57. Relaciones
Si los elementos de un conjunto se pueden relacionar, se dice que los
conjuntos que integran la relación están ordenados y a la relación se le
llama “relación de orden” en el conjunto. Sin embargo, existen muchos
conjuntos cuyos elementos no son comparables.
Por ejemplo, en el conjunto de los boxeadores profesionales no seria
posible tener una pelea entre Julio Cesar Chávez y Mike Tyson
(suponiendo que estuvieran activos) debido a que no son del mismo
peso, por lo tanto el conjunto de peleas posibles entre boxeadores
profesionales es un conjunto parcialmente ordenado para todos sus
pesos, pero no entre la mismas categorías.

58. 2.4 Conceptos básicos: producto cartesiano y
relación binaria
El producto cartesiano de los conjuntos A y B, que se denota como
AxB, es la combinación de todos los elementos del conjunto A con
todos los elementos del conjunto B. en teoría de conjuntos equivale al
conjunto universo.
Una relación R de A en B (R: A →B) es un subconjunto del producto
cartesiano AXB. Si R ⊆AxBy (a,b) ∈R, entonces a su vez el producto
cartesiano también es una relación.

60. 2.4 Conceptos básicos: producto cartesiano y
relación binaria
No siempre los elementos de la relación son pares ordenados, ya que
pueden tener mas de dos elementos como en el siguiente caso:
Aquí la relación esta formada por tercias de elementos pertenecientes a los
conjuntos A = {a,b,c}, B = {1,2,3} y c = {∎,∆}. En este caso se trata de una
relación terciaria y no binaria, ya que los elementos no son pares ordenados
si no tercias.
Una de las relaciones mas importantes en la computación es la relación
binaria, ya que se puede representar por medio de una matriz, tabla o
grafica. Además de ser mas fácil de manejar, se le llama relación binaria por
que sus elementos son pares ordenados que se forman a partir de dos
conjuntos

61. 2.4 Conceptos básicos: producto cartesiano y
relación binaria
En toda relación de pares ordenados no vacía se tienen dos conjuntos:
el dominio de R(Dom(R)), que es el conjunto de todos los primeros
elementos de los pares de una relación el cual es un subconjunto del
conjunto A (Dom(R) ⊆A), y el codominiode R (Cod(R)), conjunto que
esta formado por los segundos elementos de los pares de la relación R
y que también es un subconjunto de B (Cod(R) ⊆B)

62. 2.4 Conceptos básicos: producto cartesiano y
relación binaria

63. 2.5 Representación de las relaciones
Matriz de una relación
Si a y B son dos conjuntos finitos con m y n elementos,
respectivamente, y R es una relación de A en B, entonces es posible
representar a R como una matriz M
R= [m
ij] cuyos elementos se definen
como:

64. 2.5 Representación de las relaciones

65. 2.5 Representación de las relaciones
Grafo de una relación
Es posible representar una relación por medio de una grafica integrada
por nodos y flecha, y a este tipo de grafica se le conoce como “grafo
dirigido” de R.
Para hacer un grafo solo se tienen que colocar los elementos de los
conjuntos A y B como nodos, y la relación que existe entre los
elementos se indica por medio de una flecha que va del elemento del
conjunto A al elemento del conjunto B con el que esta relacionado.

66. 2.5 Representación de las relaciones

67. 2.5 Representación de las relaciones
Los grafos pueden ser de dos tipos: “dirigidos ”, en el que los nodos
están relacionados por medio de una flecha que indica la relación, o
“No dirigidos”, como el siguiente grafo en el que no existe
direccionamiento.

68. 2.5 Representación de las relaciones
Los grafos no dirigidos tienen mucha aplicación tanto en el área de la
computación como en los sistemas de comunicación, ya que por medio
de un grafo no dirigido es posible representar una red carretera, una
red telefónica, una red de computadoras, una red de redes y un árbol,
entre otros.
En un grafo no dirigido la relación es en ambos sentidos (se considera
que las líneas tienen cabezas de flecha en ambos extremos), por lo que
no es necesaria la flecha.

70. Tipos de relaciones
Las relaciones y funciones deben cumplir con ciertos requisitos para
que sean consideradas como tales, y como cada una de ellas tiene sus
características propias es posible establecer cierta clasificación.
Relación reflexiva
Una relación es reflexiva cuando todo elemento de un conjunto A esta
relacionado consigo mismo, esto es, cuando se cumple que aRapara
todo elemento de A. Una característica de este tipo de relación es que
su matriz correspondiente contiene unos en toda su diagonal principal
y los elementos restantes de la matriz pueden ser unos o ceros, como
se muestra en el siguiente ejemplo:

71. Tipos de relaciones
Relación reflexiva

72. Tipos de relaciones
Relación irreflexiva
Se dice que una relación es
irreflexiva cuando ningún
elemento del conjunto A
esta relacionado consigo
mismo (�,�∉R). En este
caso la matriz de la relación
deberá contener
únicamente ceros en la
diagonal.

73. Tipos de relaciones
Relación irreflexiva
Se dice que una relación R:A→B es simétrica
cuando �,�????????????y �,�????????????.Si (a,b) esta en la
relación pero (b,a) no, entonces la relación no es
simétrica.
Una forma rápida de saber si la relación es
simétrica, consiste en comparar la matriz de la
relación con su transpuesta: si son iguales
entonces se concluye que la relación R es
simétrica.
En la segunda matriz se tiene que ??????
??????≠??????
??????
−1
, por
lo que se concluye que la relación R no es
simétrica.

74. Tipos de relaciones
Relación asimétrica
Una relación R de a en B es asimétrica
cuando �,�????????????entonces �,�????????????,
además de que ningún elemento
deberá estar relacionado consigo
mismo; esto significa que la diagonal
de la matriz de la relación deberá
contener solamente ceros.

75. Tipos de relaciones
Relación asintimétrica
Una relación de este tipo se da cuando
uno de los pares colocados
simétricamente no esytaen la relación,
lo cual significa que �,�∉R o bien
�,�∉R). En este caso la diagnalde la
matriz no es importante, ya que
pueden estar o no relacionados los
elementos con ellos mismos.

76. Tipos de relaciones
Relación transitiva
Una relación de A en B tiene la
propiedad de ser transitiva si cuando
aRby bRcentonces existe el par aRc.
En la matriz de la siguiente relación se
tiene (2,3) y (3,4), entonces existe (2,4).
También se tiene (3,1) y (1,3), entonces
(3,3). De esta forma se deben de
revisar todos los posibles pares para
ver si se cumple la transitividad.

77. Tipos de relaciones
Relación transitiva
Luego de llevar a cabo la tabulación correspondiente se concluye
que la relación anterior no es transitiva, ya que debe tener los
pares ordenados encontrados a continuación:
Sin embargo, faltan 5 elementos marcados con (*).
Se recomienda que se desarrolle un algoritmo para multiplicar la
matriz booleana ??????
??????por ella misma, para obtener ??????
??????
2
. Si ??????
??????=
??????
??????+??????
??????
2
se dice que la relación R es transitiva.

78. Tipos de relaciones
Relación transitiva
Los elementos de la matriz resultante se obtuvieron multiplicando las filas
de la primera matriz, por cada una de las columnas de la segunda.

79. 2.6 Propiedades de las relaciones

80. 2.6 Propiedades de las relaciones

81. 2.6 Propiedades de las relaciones

82. 2.6 Propiedades de las relaciones

83. 2.6 Propiedades de las relaciones

84. 2.7 Relaciones de equivalencia
Una relación de equivalencia es aquella que tiene las tres propiedades:
Reflexiva, simétrica y transitiva.
Por otro lado, una relación de equivalencia tiene clases de equivalencia
y estas forman particiones. Una participación es un subgrafo completo.
Las clases de equivalencia son conjuntos que contienen a todos los
elementos �∈�y que están relacionados con a∈�.Los elementos
del primer conjunto se encierran entre corchetes, de forma que una
clase de equivalencia se puede indicar como

85. 2.7 Relaciones de equivalencia
Una partición es un conjunto de clases de equivalencia (conjunto de
conjuntos) con las siguientes propiedades:
a)Deberán estarcontenidostodosloselementosdelconjuntoA.
b)La intersección entre las clases de equivalencia deberá ser vacía.
Masformalmentesepuedeindicarcomo:

86. 2.7 Relaciones de equivalencia

87. 2.7 Relaciones de equivalencia

88. 2.7 Relaciones de equivalencia

89. 2.7 Relaciones de equivalencia

90. Cerraduras

91. Cerraduras

92. Operaciones entre relaciones
Así como se pueden realizar operaciones con números también e
posible realizar operaciones entre relaciones. Las operaciones que se
pueden llevar a cabo con relaciones son:

93. Operaciones entre relaciones

94. 2.9 Aplicaciones de las relaciones y las
funciones en la computación

95. 2.9 Aplicaciones de las relaciones y las
funciones en la computación

96. 2.8 Funciones
Los lenguajes de programación tradicionales se fundamentan en el
concepto de función, y lo mismo ocurre en el caso de los visuales ya
que por ejemplo para dibujar una ventana es necesario proporcionar
los parámetros que no son otra cosa mas que las propiedades del
dibujo que al final se obtiene como resultado.

97. 2.8 Funciones

98. 2.8 Funciones
Se puede decir que todas las funciones son relaciones, pero no todas
las relaciones son funciones. Para que una relación sea considerada
como una función deberá cumplir con las siguientes condiciones:

99. 2.8 Funciones

100. Anexo