Introduccin
Teora de Conjuntos
Sumario
Matemtica Discreta
Prof. Jos H. Nieto
Departamento de Matemtica
Facultad de Ciencias
Universidad del Zulia
Abril 2005
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Desarrollo del curso
Qu es la matemtica discreta?
Contenido sinptico
Bibliografa
Forma de trabajo
Una conferencia semanal plenaria de dos horas a mi
cargo, con contenidos tericos y asignacin de trabajos
prcticos.
Una clase prctica de 2 horas (cuatro grupos atendidos
por los profesores Alirio Pea y Haller Bracho).
Evaluacin: se realizarn tres exmenes parciales. La nota
nal ser el promedio de esas tres notas parciales.
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Desarrollo del curso
Qu es la matemtica discreta?
Contenido sinptico
Bibliografa
Pgina web del curso
[Link]
Aqu se publicarn las notas de clase, los ejercicios propuestos
y las presentaciones, todo en formato PDF.
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Desarrollo del curso
Qu es la matemtica discreta?
Contenido sinptico
Bibliografa
Qu es la matemtica discreta?
En matemtica discreto signica separado y distinto, es lo
opuesto a continuo.
El par discreto-continuo es la contraparte matemtica del
par digital-analgico en el mundo fsico.
La matemtica discreta estudia las estructuras discretas,
tales como los conjuntos nitos, los nmeros enteros y los
grafos.
La informacin que circula en un computador, sus circuitos
digitales y los programas que ejecuta son de naturaleza
discreta.
La matemtica discreta proporciona la base terica para la
ciencia y la tecnologa de la computacin.
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Desarrollo del curso
Qu es la matemtica discreta?
Contenido sinptico
Bibliografa
Qu es la matemtica discreta?
En matemtica discreto signica separado y distinto, es lo
opuesto a continuo.
El par discreto-continuo es la contraparte matemtica del
par digital-analgico en el mundo fsico.
La matemtica discreta estudia las estructuras discretas,
tales como los conjuntos nitos, los nmeros enteros y los
grafos.
La informacin que circula en un computador, sus circuitos
digitales y los programas que ejecuta son de naturaleza
discreta.
La matemtica discreta proporciona la base terica para la
ciencia y la tecnologa de la computacin.
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Desarrollo del curso
Qu es la matemtica discreta?
Contenido sinptico
Bibliografa
Qu es la matemtica discreta?
En matemtica discreto signica separado y distinto, es lo
opuesto a continuo.
El par discreto-continuo es la contraparte matemtica del
par digital-analgico en el mundo fsico.
La matemtica discreta estudia las estructuras discretas,
tales como los conjuntos nitos, los nmeros enteros y los
grafos.
La informacin que circula en un computador, sus circuitos
digitales y los programas que ejecuta son de naturaleza
discreta.
La matemtica discreta proporciona la base terica para la
ciencia y la tecnologa de la computacin.
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Desarrollo del curso
Qu es la matemtica discreta?
Contenido sinptico
Bibliografa
Qu es la matemtica discreta?
En matemtica discreto signica separado y distinto, es lo
opuesto a continuo.
El par discreto-continuo es la contraparte matemtica del
par digital-analgico en el mundo fsico.
La matemtica discreta estudia las estructuras discretas,
tales como los conjuntos nitos, los nmeros enteros y los
grafos.
La informacin que circula en un computador, sus circuitos
digitales y los programas que ejecuta son de naturaleza
discreta.
La matemtica discreta proporciona la base terica para la
ciencia y la tecnologa de la computacin.
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Desarrollo del curso
Qu es la matemtica discreta?
Contenido sinptico
Bibliografa
Qu es la matemtica discreta?
En matemtica discreto signica separado y distinto, es lo
opuesto a continuo.
El par discreto-continuo es la contraparte matemtica del
par digital-analgico en el mundo fsico.
La matemtica discreta estudia las estructuras discretas,
tales como los conjuntos nitos, los nmeros enteros y los
grafos.
La informacin que circula en un computador, sus circuitos
digitales y los programas que ejecuta son de naturaleza
discreta.
La matemtica discreta proporciona la base terica para la
ciencia y la tecnologa de la computacin.
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Desarrollo del curso
Qu es la matemtica discreta?
Contenido sinptico
Bibliografa
Contenido
Programa sinptico
1
Revisin de Teora de Conjuntos.
2
Principios de la Combinatoria.
3
Coecientes binomiales y multinomiales.
4
Particiones de un conjunto. Permutaciones.
5
Funciones generatrices y relaciones de recurrencia.
6
Conjuntos parcialmente ordenados.
7
Grafos y digrafos. Grafos eulerianos y hamiltonianos.
Coloracin de grafos.
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Desarrollo del curso
Qu es la matemtica discreta?
Contenido sinptico
Bibliografa
Bibliografa
Libros
Nieto, Jos H. Teora combinatoria, EdiLUZ, Maracaibo,
1996.
Kolman, B. et al. Estructuras de matemticas discretas
para la computacin, Prentice Hall, 1997.
Notas de clase
Nieto, Jos H. Conjuntos, Relaciones y Funciones.
Nieto, Jos H. Teora de Grafos.
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Conjuntos
Un conjunto es un agregado o coleccin de entes u
objetos de cualquier naturaleza. A dichos entes se les
llama elementos del conjunto.
Si x es un elemento del conjunto A entonces se dice que x
pertenece a A y se escribe x A.
Si x no es un elemento del conjunto A entonces se dice
que x no pertenece a A y se escribe x A.
Dos conjuntos A y B son iguales si tienen exactamente los
mismos elementos. En ese caso se escribe A = B. De lo
contrario se dice que los conjuntos son diferentes y se
escribe A = B.
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Conjuntos
Un conjunto es un agregado o coleccin de entes u
objetos de cualquier naturaleza. A dichos entes se les
llama elementos del conjunto.
Si x es un elemento del conjunto A entonces se dice que x
pertenece a A y se escribe x A.
Si x no es un elemento del conjunto A entonces se dice
que x no pertenece a A y se escribe x A.
Dos conjuntos A y B son iguales si tienen exactamente los
mismos elementos. En ese caso se escribe A = B. De lo
contrario se dice que los conjuntos son diferentes y se
escribe A = B.
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Conjuntos
Un conjunto es un agregado o coleccin de entes u
objetos de cualquier naturaleza. A dichos entes se les
llama elementos del conjunto.
Si x es un elemento del conjunto A entonces se dice que x
pertenece a A y se escribe x A.
Si x no es un elemento del conjunto A entonces se dice
que x no pertenece a A y se escribe x A.
Dos conjuntos A y B son iguales si tienen exactamente los
mismos elementos. En ese caso se escribe A = B. De lo
contrario se dice que los conjuntos son diferentes y se
escribe A = B.
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Conjuntos
Un conjunto es un agregado o coleccin de entes u
objetos de cualquier naturaleza. A dichos entes se les
llama elementos del conjunto.
Si x es un elemento del conjunto A entonces se dice que x
pertenece a A y se escribe x A.
Si x no es un elemento del conjunto A entonces se dice
que x no pertenece a A y se escribe x A.
Dos conjuntos A y B son iguales si tienen exactamente los
mismos elementos. En ese caso se escribe A = B. De lo
contrario se dice que los conjuntos son diferentes y se
escribe A = B.
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Inclusin
Denicin
Si todo elemento de A es tambin elemento de B se dice que A
est incluido o contenido en B, o que A es un subconjunto de
B y se escribe A B. Tambin se dice que B contiene a A y se
escribe B A.
Si A B y A = B entonces se dice que A es un
subconjunto propio de B y se escribe A B.
A = B si y slo si A B y B A. De hecho para probar
que dos conjuntos A y B son iguales generalmente se
prueba que A B y luego que B A.
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Inclusin
Denicin
Si todo elemento de A es tambin elemento de B se dice que A
est incluido o contenido en B, o que A es un subconjunto de
B y se escribe A B. Tambin se dice que B contiene a A y se
escribe B A.
Si A B y A = B entonces se dice que A es un
subconjunto propio de B y se escribe A B.
A = B si y slo si A B y B A. De hecho para probar
que dos conjuntos A y B son iguales generalmente se
prueba que A B y luego que B A.
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Deniciones por extensin
Un conjunto puede denirse por extensin escribiendo sus
elementos entre llaves, separados por comas.
Ejemplo
{3, 5, 7} es el conjunto formado por los nmeros 3, 5 y 7.
El orden en que se escriben los elementos dentro de las llaves
es irrelevante. Por ejemplo {3, 5, 7} es idntico a {7, 5, 3}, ya
que tienen exactamente los mismos elementos.
Denicin
El conjunto {} no tiene ningn elemento: se le llama conjunto
vaco y se denota con el smbolo .
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Deniciones por extensin
Un conjunto puede denirse por extensin escribiendo sus
elementos entre llaves, separados por comas.
Ejemplo
{3, 5, 7} es el conjunto formado por los nmeros 3, 5 y 7.
El orden en que se escriben los elementos dentro de las llaves
es irrelevante. Por ejemplo {3, 5, 7} es idntico a {7, 5, 3}, ya
que tienen exactamente los mismos elementos.
Denicin
El conjunto {} no tiene ningn elemento: se le llama conjunto
vaco y se denota con el smbolo .
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Deniciones por extensin
Un conjunto puede denirse por extensin escribiendo sus
elementos entre llaves, separados por comas.
Ejemplo
{3, 5, 7} es el conjunto formado por los nmeros 3, 5 y 7.
El orden en que se escriben los elementos dentro de las llaves
es irrelevante. Por ejemplo {3, 5, 7} es idntico a {7, 5, 3}, ya
que tienen exactamente los mismos elementos.
Denicin
El conjunto {} no tiene ningn elemento: se le llama conjunto
vaco y se denota con el smbolo .
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Deniciones por comprensin
Una denicin de un conjunto por comprensin tiene el especto
{x A : P(x)}
y se lee: el conjunto de todos los x de A tales que P(x), siendo
P una condicin que cada elemento de A puede o no cumplir.
Ejemplo
Si N es el conjunto de todos los nmeros naturales, entonces
{x N : 20 < x 25} = {21, 22, 23, 24, 25}
{x N : x
2
5x + 6 = 0} = {2, 3}
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Deniciones por comprensin
Una denicin de un conjunto por comprensin tiene el especto
{x A : P(x)}
y se lee: el conjunto de todos los x de A tales que P(x), siendo
P una condicin que cada elemento de A puede o no cumplir.
Ejemplo
Si N es el conjunto de todos los nmeros naturales, entonces
{x N : 20 < x 25} = {21, 22, 23, 24, 25}
{x N : x
2
5x + 6 = 0} = {2, 3}
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Unin de dos conjuntos
Denicin
La unin de dos conjuntos A y B es el conjunto
A B = {x : x A o x B}
Propiedades
A A = A y A = A, para todo conjunto A.
A B si y slo si A B = B.
Conmutatividad, es decir A B = B A.
Asociatividad, es decir A (B C) = (A B) C.
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Unin de dos conjuntos
Denicin
La unin de dos conjuntos A y B es el conjunto
A B = {x : x A o x B}
Propiedades
A A = A y A = A, para todo conjunto A.
A B si y slo si A B = B.
Conmutatividad, es decir A B = B A.
Asociatividad, es decir A (B C) = (A B) C.
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Interseccin de dos conjuntos
Denicin
La interseccin de dos conjuntos A y B es el conjunto
A B = {x A : x B}
Propiedades
A A = A y A = , para todo conjunto A.
A B si y slo si A B = A.
Conmutatividad: A B = B A.
Asociatividad: A (B C) = (A B) C.
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Interseccin de dos conjuntos
Denicin
La interseccin de dos conjuntos A y B es el conjunto
A B = {x A : x B}
Propiedades
A A = A y A = , para todo conjunto A.
A B si y slo si A B = A.
Conmutatividad: A B = B A.
Asociatividad: A (B C) = (A B) C.
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Diferencia
Denicin
La diferencia de dos conjuntos A y B es el conjunto
A \ B = {x A : x B}
Ejemplo
Si A = {2, 3, 5, 7} y B = {1, 3, 4, 5, 6} entonces A \ B = {2, 7}.
Propiedades
A \ A = y A \ = A.
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Diferencia simtrica
Denicin
La diferencia simtrica de dos conjuntos A y B es el conjunto
A B = (A \ B) (B \ A)
Propiedades
A A = y A = A.
Conmutatividad: A B = B A.
Asociatividad: A (B C) = (A B) C.
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Diferencia simtrica
Denicin
La diferencia simtrica de dos conjuntos A y B es el conjunto
A B = (A \ B) (B \ A)
Propiedades
A A = y A = A.
Conmutatividad: A B = B A.
Asociatividad: A (B C) = (A B) C.
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Ejemplos de operaciones con conjuntos
Sean A = {2, 3, 5, 7} y B = {1, 3, 5, 6, 8}. Entonces:
A B = {1, 2, 3, 5, 6, 7, 8}
A B = {3, 5}
A \ B = {2, 7}
B \ A = {1, 6, 8}
A B = {1, 2, 6, 7, 8}
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Ejemplos de operaciones con conjuntos
Sean A = {2, 3, 5, 7} y B = {1, 3, 5, 6, 8}. Entonces:
A B = {1, 2, 3, 5, 6, 7, 8}
A B = {3, 5}
A \ B = {2, 7}
B \ A = {1, 6, 8}
A B = {1, 2, 6, 7, 8}
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Ejemplos de operaciones con conjuntos
Sean A = {2, 3, 5, 7} y B = {1, 3, 5, 6, 8}. Entonces:
A B = {1, 2, 3, 5, 6, 7, 8}
A B = {3, 5}
A \ B = {2, 7}
B \ A = {1, 6, 8}
A B = {1, 2, 6, 7, 8}
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Ejemplos de operaciones con conjuntos
Sean A = {2, 3, 5, 7} y B = {1, 3, 5, 6, 8}. Entonces:
A B = {1, 2, 3, 5, 6, 7, 8}
A B = {3, 5}
A \ B = {2, 7}
B \ A = {1, 6, 8}
A B = {1, 2, 6, 7, 8}
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Ejemplos de operaciones con conjuntos
Sean A = {2, 3, 5, 7} y B = {1, 3, 5, 6, 8}. Entonces:
A B = {1, 2, 3, 5, 6, 7, 8}
A B = {3, 5}
A \ B = {2, 7}
B \ A = {1, 6, 8}
A B = {1, 2, 6, 7, 8}
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Complemento
Aunque en la teora de conjuntos no se admite un conjunto de
todas las cosas, frecuentemente hay un conjunto que contiene
a todos los dems bajo consideracin en una discusin
determinada. A ese conjunto se le llama conjunto universal
para esa discusin.
Denicin
El complemento de un conjunto A respecto a un conjunto
universal U es el conjunto
A
= U \ A
(A
= A para todo conjunto A.
Tambin es fcil ver que A A
= y A A
= U.
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Complemento
Aunque en la teora de conjuntos no se admite un conjunto de
todas las cosas, frecuentemente hay un conjunto que contiene
a todos los dems bajo consideracin en una discusin
determinada. A ese conjunto se le llama conjunto universal
para esa discusin.
Denicin
El complemento de un conjunto A respecto a un conjunto
universal U es el conjunto
A
= U \ A
(A
= A para todo conjunto A.
Tambin es fcil ver que A A
= y A A
= U.
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Leyes de De Morgan
Para dos conjuntos
(A B)
= A
(A B)
= A
Para n conjuntos A
1
,A
2
,. . . ,A
n
i =1
A
i
=
n
i =1
A
i =1
A
i
=
n
i =1
A
i
.
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Leyes de De Morgan
Para dos conjuntos
(A B)
= A
(A B)
= A
Para n conjuntos A
1
,A
2
,. . . ,A
n
i =1
A
i
=
n
i =1
A
i =1
A
i
=
n
i =1
A
i
.
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Ejemplos de complementos
Sean U = {1, 2, 3, 4, 5, 6, 7, 8, 9}, A = {2, 3, 5, 7} y
B = {1, 3, 5, 6, 8}. Entonces:
A
= {1, 4, 6, 8, 9}
B
= {2, 4, 7, 9}
A
= {1, 2, 4, 6, 7, 8, 9}
A
= {4, 9}
A B = {1, 2, 3, 5, 6, 7, 8}
(A B)
= {4, 9}
A B = {3, 5}
(A B)
= {1, 2, 4, 6, 7, 8, 9}
Observe que (A B)
= A
y (A B)
= A
.
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Diagramas de Venn
A B
A
B
A \ B
A
B
A B
A
B
B \ A
A
B
A B
A
B
A
A
A
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Conjunto potencia
Denicin
El conjunto potencia de un conjunto A es el conjunto de todos
los subconjuntos de A. Se le denota
(A).
Ejemplo
Si A = {3, 5} entonces
(A) = {, {3}, {5}, {3, 5}}.
Observe que X A y X
(A) signican exactamente lo
mismo.
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Conjunto potencia
Denicin
El conjunto potencia de un conjunto A es el conjunto de todos
los subconjuntos de A. Se le denota
(A).
Ejemplo
Si A = {3, 5} entonces
(A) = {, {3}, {5}, {3, 5}}.
Observe que X A y X
(A) signican exactamente lo
mismo.
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Conjunto potencia
Denicin
El conjunto potencia de un conjunto A es el conjunto de todos
los subconjuntos de A. Se le denota
(A).
Ejemplo
Si A = {3, 5} entonces
(A) = {, {3}, {5}, {3, 5}}.
Observe que X A y X
(A) signican exactamente lo
mismo.
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Pares
Denicin
A un conjunto de la forma {a, b} se le llama par no ordenado.
Observe que {a, b} = {b, a}.
Denicin
El par ordenado (a, b) se dene como
(a, b) = {{a}, {a, b}}.
Esta denicin algo articiosa es un recurso tcnico para poder
distinguir el primer elemento de un par del segundo.
Propiedad
(a, b) = (c, d) si y slo si a = c y b = d.
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Pares
Denicin
A un conjunto de la forma {a, b} se le llama par no ordenado.
Observe que {a, b} = {b, a}.
Denicin
El par ordenado (a, b) se dene como
(a, b) = {{a}, {a, b}}.
Esta denicin algo articiosa es un recurso tcnico para poder
distinguir el primer elemento de un par del segundo.
Propiedad
(a, b) = (c, d) si y slo si a = c y b = d.
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Pares
Denicin
A un conjunto de la forma {a, b} se le llama par no ordenado.
Observe que {a, b} = {b, a}.
Denicin
El par ordenado (a, b) se dene como
(a, b) = {{a}, {a, b}}.
Esta denicin algo articiosa es un recurso tcnico para poder
distinguir el primer elemento de un par del segundo.
Propiedad
(a, b) = (c, d) si y slo si a = c y b = d.
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Producto cartesiano
Denicin
El producto cartesiano de dos conjuntos A y B es el conjunto
A B = {(a, b) : a A, b B}
de todos los pares ordenados con el primer elemento en A y el
segundo elemento en B.
Ejemplo
Si A = {a, b} y B = {1, 2, 3} entonces
A B = {(a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3)}
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Producto cartesiano
Denicin
El producto cartesiano de dos conjuntos A y B es el conjunto
A B = {(a, b) : a A, b B}
de todos los pares ordenados con el primer elemento en A y el
segundo elemento en B.
Ejemplo
Si A = {a, b} y B = {1, 2, 3} entonces
A B = {(a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3)}
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Producto cartesiano (2)
Denicin
La denicin de producto cartesiano se puede extender para
ms de dos conjuntos reemplazando los pares ordenados por
ternas, cuaternas, etc. Por ejemplo
A B C = {(a, b, c) : a A, b B, c C}
A
n
= {(a
1
, . . . , a
n
) : a
i
A para i = 1, . . . , n}
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Relaciones
Denicin
Una relacin R de A en B es un subconjunto de A B. Si
(x, y) R entonces se dice que x est relacionado con y y se
escribe x R y o R(x, y).
Ejemplo
Sea F = {Ana, Berta, Carlos, Dora, Eric} una familia en la cual
Ana es la madre de Berta, Berta es la madre de Carlos y Dora,
y Dora es la madre de Eric. Entonces
M = {(Ana, Berta), (Berta, Carlos), (Berta,Dora), (Dora,Eric)}
es una relacin de F en F que corresponde al concepto
intuitivo de la relacin es madre de.
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Relaciones (2)
Denicin
Si R es una relacin de A en B y X A entonces R(X) es el
conjunto denido por
R(X) = {y B : (x, y) R para algn x A}.
Anlogamente si Y B entonces R
1
(Y) se dene como
R
1
(Y) = {x A : (x, y) R para algn y B}.
A R
1
(B) se le llama el dominio y a R(A) el rango de R.
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Diagrama de una Relacin
R = {(a, u), (b, u), (b, w), (d, x)}
A
B
a
u
d
d
d
d
d
d
d
d
d
d
d
d
d
d
b
w f
f
f
f
f
f
f
f
f
f
f
f
f
f
f
f
f
f
f
f
f
f
f
j
j
j
j
j
j
j
j
j
j
j
j
j
j
j
j
j
j
j
j
d
x i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
v
c
e
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Representacin con matrices
Una relacin R de A = {a
1
, . . . , a
m
} en B = {b
1
, . . . , b
n
} se
puede representar con una matriz M
R
= (r
ij
) de mn donde
r
ij
= 1 si (a
i
, b
j
) R y r
ij
= 0 en caso contrario.
Ejemplo
Si A = {a
1
, a
2
, a
3
}, B = {b
1
, b
2
, b
3
, b
4
} y
R = {(a
1
, b
1
), (a
1
, b
3
), (a
2
, b
2
), (a
2
, b
3
), (a
3
, b
4
)} entonces:
M
R
=
1 0 1 0
0 1 1 0
0 0 0 1
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Propiedades de las relaciones
Denicin
Una relacin R en A
reexiva si a R a para todo a A.
irreexiva si para ningn a A se cumple a R a.
simtrica si cada vez que a R b entonces tambin b R a.
asimtrica si a R b y b R a nunca se cumplen
simultneamente.
antisimtrica si a R b y b R a implican a = b.
transitiva si cada vez que a R b y b R c entonces tambin
a R c.
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Inversa de una relacin
Denicin
Si R es una relacin de A en B entonces la inversa de R es la
relacin R
1
de B en A denida por
R
1
= {(b, a) B A : (a, b) R.}
Ejemplo
La inversa de la relacin es progenitor de es es hijo(a) de.
La inversa de la relacin es esposo de es es esposa de.
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Composicin de relaciones
Denicin
Si R es una relacin de A en B y S es una relacin de B en C
entonces la composicin de R y S es la relacin S R de A en
C denida por
SR = {(a, c) AC : (a, b) R y (b, c) S para algn b B}
Esta denicin algo complicada signica sencillamente que
para que un par ordenado (a, c) pertenezca a S R debe
existir algn elemento b en B que haga de puente entre a y c,
es decir que cumpla las dos condiciones a R b y b S c.
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Ejemplos de composicin
Ejemplo
En el conjunto de los seres humanos sean P la relacin
es progenitor de y H es hermano de. Entonces P H
corresponde a la relacin es to de.
En efecto, x P H z signica que para algn y, x es hermano
de y y y es padre o madre de z, es decir que x es to de z.
P
2
= P P es la relacin es abuelo(a) de.
P
1
P
1
es la relacin es nieto(a) de.
P
2
H es es to abuelo de.
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Diagrama de una composicin de relaciones
R = {(a, v), (b, v), (c, w)}, S = {(u, x), (v, x), (w, y)}
A
B
a
v
l
l
l
l
l
l
l
l
l
l
l
l
b
q
q
q
q
q
q
q
q
q
q
q
q
q
q
q
c
w
t
t
t
t
t
t
t
t
t
t
t
t
t
u
x
G
G
G
G
G
G
G
G
G
G
G
Q
Q
Q
Q
Q
Q
Q
Q
Q
Q
Q
Q
Q
Q
Q
C
y
J
J
J
J
J
J
J
J
J
J
J
J
J
d
t
S R = {(a, x), (b, x), (c, y)}
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Diagrama de una composicin de relaciones
R = {(a, v), (b, v), (c, w)}, S = {(u, x), (v, x), (w, y)}
A
B
a
v
l
l
l
l
l
l
l
l
l
l
l
l
b
q
q
q
q
q
q
q
q
q
q
q
q
q
q
q
c
w
t
t
t
t
t
t
t
t
t
t
t
t
t
u
x
G
G
G
G
G
G
G
G
G
G
G
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
Q
Q
Q
Q
Q
Q
Q
Q
Q
Q
Q
Q
Q
Q
Q
C
y
J
J
J
J
J
J
J
J
J
J
J
J
J
d
t
S R = {(a, x), (b, x), (c, y)}
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Funciones
Denicin
Una relacin f de A en B es una funcin si para cada x A
existe un y slo un y B tal que (x, y) f . Ese elemento y se
denomina valor de f en x o imagen de x por f y se denota f (x).
Al conjunto A se le llama dominio de f y al conjunto B
codominio de f .
Notacin
Para indicar que f es una funcin de A en B se escribe
f : A B. Todas las funciones de A en B forman un conjunto
que se denota B
A
.
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Diagrama de una funcin
f : A B
A
B
a
v
d
d
d
d
d
d
d
d
d
d
d
d
d
d
b
w
k
k
k
k
k
k
k
k
k
k
k
k
k
k
k
k
k
k
k
k
c
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
d
x
p
p
p
p
p
p
p
p
p
p
p
p
p
p
p
p
u
f (a) = v, f (b) = v, f (c) = w), f (d) = x
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Imagen y preimagen
Observacin
En el diagrama de una funcin, de cada elemento del dominio
debe salir una y slo una echa. En cambio a cada elemento
del codominio pueden llegar una, varias o ninguna echa.
Denicin
Si f : A B, X A y Y B entonces la imagen de X por f es
f (X) = {y B : y = f (x) para algn x A}
y la preimagen de Y por f es
f
1
(Y) = {x A : f (x) = y}.
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Funcin inyectiva
Denicin
f : A B es inyectiva si elementos diferentes del dominio
tienen imgenes diferentes. En otras palabras, f es inyectiva si
f (x) = f (y) implica x = y. A estas funciones tambin se les
llama uno a uno.
Observacin
En el diagrama de una funcin inyectiva, a cada elemento del
codominio llega a lo sumo una echa.
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Funcin sobreyectiva
Denicin
f : A B es sobreyectiva si f (A) = B, es decir si el recorrido
de f coincide con su codominio. En este caso se dice que f es
una funcin de A sobre B.
Observacin
En el diagrama de una funcin sobreyectiva, a cada elemento
del codominio llega por lo menos una echa.
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Conjuntos
Operaciones con conjuntos
Relaciones
Funciones
Funcin biyectiva
Denicin
f : A B es biyectiva si es tanto inyectiva como sobreyectiva.
En este caso tambin se dice que f es una biyeccin entre A y
B, y que A y B son coordinables.
Observacin
En el diagrama de una funcin biyectiva, a cada elemento del
codominio llega exactamente una echa.
Prof. Jos H. Nieto Matemtica Discreta
Introduccin
Teora de Conjuntos
Sumario
Sumario
Un conjunto es un agregado o coleccin de entes u
objetos de cualquier naturaleza.
Las principales operaciones con conjuntos son: unin,
interseccin, diferencia, complemento, potencia y producto
cartesiano.
Una relacin es un conjunto de pares ordenados.
Una funcin es una relacin en la cual a cada elemento
del dominio le corresponde una y slo una imagen.
Pgina web del curso:
[Link]
Prof. Jos H. Nieto Matemtica Discreta