Matem ticas discretas

MATEMÁTICAS
DISCRETAS

ÍNDICE
1.Conceptos y fundamentos
1.1Teoria de los conjuntos
1.2. Suseciones
1.3 Operaciones con conjuntos
1.4 Análisis combinatorio
1.5 Algoritmos y seudocódigo

2. Relaciones
2.1
2.2
2.3
2.4

Relación binaria
Trayectorias de las relaciones
Propiedades de las relaciones
Manipulación de las relaciones

3. Funciones
3.1 Funciones
3.2 Permutaciones

• 4. Lógicaproposicional
4.1 Lenguaje de la lógica proposional
4.2 Inferencia en la lógica proposicional
4.3 Lógica de primer orden
4.4 Matrices
5 Teoría de grafos
5.1 Clasificación de grafos
5.2 Topología de grafos
5.3 Árboles y arborescentes
6. Algoritmos de grafos
6.1 Problemas de rutas
6.2 Problemas de flujos

CONCEPTOS Y
FUNDAMENTOS

• Teoría de conjuntos
• Sucesiones
• Operaciones con conjuntos
• Análisiscombinario
• Algoritmos y seudocódigo
• Inducción y recursion

TEORÍA DE CONJUNTOS
• DEFINICIÓN
• Un conjunto queda perfectamente definido si se conocen con exactitud los
elementos que lo integran o que pertenecen a él; es decir, si se nombran
todos sus elementos o bien si se usa un enunciado o propiedad que lo
identifique. Independientemente de la forma en que se lo represente, siempre
se usa una letramayúscula que lo define. Esta letra mayúscula representa a
un conjunto específico de elementos.
• Existen dos maneras de definir un conjunto dado:
• a) Por extensión o enumeración: se define nombrando a cada elemento
del conjunto.
• b) Por comprensión: se define mediante un enunciado o atributo que
representa al conjunto (se busca una frase que represente a la totalidad de
elementos sin nombrar aninguno en particular).

RELACIONES DE
CONJUNTOS
Sean los conjuntos

A =  { 5, 7 }
B = { 3, 5, 7, 9 }
Los elementos 5 y 7 forman parte del conjunto A
En otras palabras,
conjunto A.

los

elementos 5 y 7 pertenecen (Є) al

 

 

                                5  Є  A     y    7  Є  A
Los elementos 3, 5, 7, 9 forman parte del conjunto B, es
decir, pertenecen al conjunto B
         3  Є  B                 5  Є B                  7  Є B                  9 

 

Є  B
Se puede observar, además, en el diagrama, que los elementos
del conjunto A están incluidos dentro del conjunto B; por lo tanto,
dichos elementos también pertenecen al conjunto B.
En otras palabras, A es subconjunto de B.
                                                 A Є B

SUCESIONES
• Definición
Una sucesión es un conjunto de cosas(normalmente números ) una detrás de otra, en un
cierto orden.

Finita o infinita
Si la sucesión sigue para siempre, es una sucesión infinita,
si no es una sucesión finita
Ejemplos:
{1, 2, 3, 4 ,...} es una sucesión muy simple (y es una sucesión infinita)
{20, 25, 30, 35, ...} también es una sucesión infinita
{1, 3, 5, 7} es la sucesión de los 4 primeros números impares (y es una sucesióninfinita)
{4, 3, 2, 1} va de 4 a 1 hacia atrás
En orden
Cuando decimos que los términos están "en orden", ¡nosotros somos los que decimos qué
orden! Podría ser adelante, atrás... o alternando... ¡o el que quieras!
Una sucesión es muy parecida a un conjunto, pero con los términos en orden (y el mismo
valor sí puede aparecer muchas veces).
Ejemplo: {0, 1, 0, 1, 0, 1, ...} es la sucesión que alterna 0s y 1s.El conjunto sería sólo
{0,1}

OPERACIONES DE
CONJUNTOS
•

INTERSECCION (л)

•

La intersección entre dos o más conjuntos es otro conjunto formado por los elementos comunes
a ellos; es decir, a los elementos comunes o repetidos de ambos conjuntos A y B.

•

La intersección se simboliza con el signo л y se coloca entre las letras que representan a cada
conjunto.

•
•

Conjunto A = {3, 8, 24}Conjunto B = {13, 7, 8, 12}

•

Los elementos que se repiten entre A y B son: 3 y 8. Estos elementos se anotan en la parte de
color amarillo pues representa el lugar común entre ambos conjuntos.

•

LA UNIÓN

La unión se representa por el símbolo (U)  Si un elemento está repetido, se coloca una sola vez.
Cuando no hay elementos comunes o repetidos (esquema 1) se anotan todos los elementos...