Varios apuntes de Matemáticas discretas y Lógica



Hola amigos de taringa, actualmente ando cursando mi segundo semestre de ing. de sistemas y pues vi estos apuntes en Internet, y me dije WOW!! esto es exactamente lo que estoy viendo en mi curso y son muy buenos ya que te explican los conceptos de forma resumida pero entendible, bueno sin mas que decir les dejo el contenido, espero que les sirva 



Lógica Matemática Elemental


Lección 1 - Lógica de Proposiciones
Contenido
1.1 Proposiciones y Tablas de Verdad . . . . . . . . . . . . . . . . . . . . .. . . 2
1.1.1 Proposición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 2
1.1.2 Valor de Verdad . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . 3
1.1.3 Proposición Compuesta . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 3
1.1.4 Variables de Enunciado . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . 3
1.1.5 Tablas de Verdad . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 4
1.2 Conexión entre Proposiciones . . . . . . . . . . . . . . . . . . . . . . .. . . . 4
1.2.1 Conjunción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 4
1.2.2 Disyunción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 5
1.2.3 Disyunción Exclusiva . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 5
1.2.4 Negación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 5
1.2.5 Tautologias y Contradicciones . . . . . . . . . . . . . . . . . . . . . .. . . . . . 7
1.2.6 Proposición Condicional . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . 7
1.2.7 Proposición Reciproca . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . 10
1.2.8 Proposición Contrarreciproca . . . . . . . . . . . . . . . . . . . . . .. . . . . . 11
1.2.9 Proposición bicondicional . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . 12
1.3 Implicación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . 15
1.3.1 Implicación Lógica . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 15
1.3.2 Implicación Lógica y Proposición Condicional . . . . . . . . . . . . . .. . . . . 16
1.3.3 Implicaciones Lógicas mas Comunes . . . . . . . . . . . . . . . . . . . .. . . . 17
1.4 Equivalencia Lógica . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 18
1.4.1 Proposiciones Lógicamente Equivalentes . . . . . . . . . . . . . . . . .. . . . . 18
1.4.2 Equivalencia Lógica y Proposición Bicondicional . . . . . . . . . . . . .. . . . 19
1.4.3 Equivalencias Lógicas mas Comunes . . . . . . . . . . . . . . . . . . . .. . . . 21


Lección 2
Lógica de Predicados
 

Contenido
2.1 Definiciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.1.1 Predicado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.1.2 Universo del Discurso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.1.3 Predicados y Proposiciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.2 Cuantificadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.2.1 Cuantificador Universal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.2.2 Valor de Verdad del Cuantificador Universal . . . . . . . . . . . . . . . . . . . . 37
2.2.3 Cuantificador Existencial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.2.4 Valor de Verdad del Cuantificador Existencial . . . . . . . . . . . . . . . . . . . 37
2.2.5 Alcance de un Cuantificador . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.3 Calculo de Predicados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.3.1 Implicación Lógica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.3.2 Equivalencia Lógica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.3.3 Leyes de De Morgan Generalizadas . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.3.4 Regla general . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
2.3.5 Proposiciones al Alcance de un Cuantificador . . . . . . . . . . . . . . . . . . . 49
2.3.6 Predicados al Alcance de un Cuantificador . . . . . . . . . . . . . . . . . . . . . 52
2.3.7 Asociatividad y Distributividad . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

Lección 3
Razonamientos y Demostraciones 


Contenido
3.1 Razonamientos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.1.1 Razonamiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.1.2 Razonamiento Valido . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.1.3 Falacia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.2 Inferencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.2.1 Regla de Inferencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.2.2 Reglas de Inferencia mas Usuales . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.3 Demostraciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.3.1 Teorema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.3.2 Corolario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.3.3 Lema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.3.4 Demostración . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
3.4 Razonamientos y Cuantificadores . . . . . . . . . . . . . . . . . . . . . . . . . 69
3.4.1 Definiciones Matemáticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
3.4.2 Regla de Particularizacion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
3.4.3 Regla de Generalización . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
3.5 Metodos de Demostración . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
3.5.1 Demostración Vacia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
3.5.2 Demostración Trivial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
3.5.3 Demostración Directa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
3.5.4 Demostracion por la Contrarrecıproca . . . . . . . . . . . . . . . . . . . . . . . 76
3.5.5 Demostración por Contradicción . . . . . . . . . . . . . . . . . . . . . . . . . . 77
3.5.6 Búsqueda de Contra-ejemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
logica

Matemática Discreta
Lección 1

Conjuntos y Subconjuntos 

Contenido
1.1 Generalidades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.1 Conjuntos y Elementos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.2 Determinación por Extensión . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.3 Determinación por Comprensión . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.4 Conjunto Universal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.5 Conjunto vacío . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.6 Axioma de Extensión . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Inclusión de conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.1 Subconjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.2 Inclusión Estricta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.3 Proposición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.4 Proposición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.5 Caracterización de la Igualdad . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2.6 Corolario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.2.7 Transitividad de la Inclusión . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3 Diagramas de Venn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

Lección 2
Operaciones con Conjuntos 


Contenido
2.1 Definiciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.1.1 Unión . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.1.2 Intersección . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.1.3 Diferencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.1.4 Complementario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.1.5 Diferencia Simétrica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2 Álgebra de conjuntos. Dualidad . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2.1 Leyes Idempotentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2.2 Leyes Conmutativas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2.3 Leyes Asociativas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2.4 Leyes Distributivas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2.5 Leyes de Identidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2.6 Ley Involutiva . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2.7 Leyes del Complementario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2.8 Leyes de De Morgan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.3 Conjunto de las Partes de un Conjunto . . . . . . . . . . . . . . . . . . . . . 28
2.3.1 Definicion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.4 Producto cartesiano de conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.4.1 n-tupla ordenada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.4.2 Igualdad de n-tuplas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.4.3 Producto cartesiano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.4.4 Propiedades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
Lección 3
Principios Básicos de Conteo 


Contenido
3.1 Partición de un Conjunto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.1.1 Definicion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.1.2 Recubrimiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.1.3 Cardinal de un conjunto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.2 Principio de Adición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.2.1 Teorema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.2.2 Regla de la Suma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.3 Principio de Multiplicación . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.3.1 Teorema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.3.2 Regla del Producto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.4 Principio de Inclusion-Exclusion . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.4.1 Teorema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.4.2 Teorema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.4.3 Generalizacion del Principio de Inclusión-Exclusion . . . . . . . . . . . . . . . . 59
3.5 Principio de Distribución . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
3.5.1 Teorema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
3.5.2 Corolario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

Lección 4
Permutaciones y Variaciones


Contenido
4.1 Permutaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
4.1.1 Definicion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
4.1.2 Numero de Permutaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
4.2 Permutaciones con Repetición . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
4.2.1 Definicion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
4.2.2 Numero de Permutaciones con Repetición . . . . . . . . . . . . . . . . . . . . . 82
4.3 Variaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
4.3.1 Definicion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
4.3.2 Formación y Numero de Variaciones . . . . . . . . . . . . . . . . . . . . . . . . 94
4.4 Variaciones con Repetición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
4.4.1 Definicion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
4.4.2 Formación y Numero de las Variaciones con Repetición . . . . . . . . . . . . . 97

Lección 5
Combinaciones. Teorema del Binomio 


Contenido
5.1 Combinaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
5.1.1 Definicion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
5.1.2 Formación y numero de combinaciones . . . . . . . . . . . . . . . . . . . . . . . 106
5.2 Teorema del Binomio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
5.2.1 Proposición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
5.2.2 Formula de Pascal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
5.2.3 Triangulo de Pascal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
5.3 Combinaciones con Repetición . . . . . . . . . . . . . . . . . . . . . . . . . . 121
5.3.1 Definicion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
5.3.2 Numero de combinaciones con repetición . . . . . . . . . . . . . . . . . . . . . . 123

Lección 6
Relaciones 


Contenido
6.1 Generalidades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
6.1.1 Relación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
6.1.2 Igualdad de Relaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
6.2 Relaciones Binarias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
6.2.1 Dominio e Imagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
6.3 Matriz de una Relación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
6.3.1 Definicion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
6.4 Grafo Dirigido de una Relación . . . . . . . . . . . . . . . . . . . . . . . . . . 136
6.4.1 Definicion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
6.4.2 Representación Ara de un Grafo Dirigido . . . . . . . . . . . . . . . . . . . 136
6.5 Propiedades de las Relaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
6.5.1 Reflexividad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
6.5.2 Simetría . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
6.5.3 Asimetria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
6.5.4 Antisimetrıa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
6.5.5 Transitividad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145

Lección 7
Relaciones de Orden 


Contenido
7.1 Generalidades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
7.1.1 Relacion de Orden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
7.1.2 Relación de Orden Estricto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
7.1.3 Proposición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
7.1.4 Proposición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
7.2 Conjuntos Ordenados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
7.2.1 Elementos Comparables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
7.2.2 Orden Parcial y Total . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
7.2.3 Conjuntos Ordenados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
7.3 Producto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
7.3.1 Orden del Producto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
7.3.2 Orden Lexicografico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
7.4 Representación Grafica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
7.4.1 Diagrama de Hasse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
7.5 Ordenación Topologica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
7.6 Elementos Caracterısticos de un Conjunto Ordenado . . . . . . . . . . . . . 177
7.6.1 Elemento Maximal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
7.6.2 Elemento Minimal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
7.6.3 Existencia del Maximal y Minimal . . . . . . . . . . . . . . . . . . . . . . . . . 178
7.6.4 Algoritmo para la Ordenación Topologica . . . . . . . . . . . . . . . . . . . . . 178
7.6.5 Elemento Máximo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
7.6.6 Elemento Mínimo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
7.6.7 Unicidad del Maximo y el Mínimo . . . . . . . . . . . . . . . . . . . . . . . . . 183
7.6.8 Cota Superior . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
7.6.9 Cota Inferior . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
7.6.10 Conjunto Acotado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
7.6.11 Supremo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
7.6.12 ´ Infimo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
7.6.13 Unicidad del ´ Infimo y el Supremo . . . . . . . . . . . . . . . . . . . . . . . . . . 185

Lección 8
Relaciones de Equivalencia 


Contenido
8.1 Generalidades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
8.1.1 Definicion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
8.1.2 Digrafo asociado a una Relacion de Equivalencia . . . . . . . . . . . . . . . . . 201
8.2 Clases de Equivalencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
8.2.1 Definicion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
8.2.2 Lema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
8.3 Conjunto Cociente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
8.3.1 Teorema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
8.3.2 Definicion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
8.3.3 Teorema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208

Lección 9
Funciones


Contenido
9.1 Definiciones y Generalidades . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
9.1.1 Funcion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
9.1.2 Dominio e Imagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
9.1.3 Igualdad de Funciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
9.1.4 Funcion Identidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
9.2 Composicion de Funciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
9.2.1 Definicion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232
9.2.2 Proposicion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232
9.2.3 Asociatividad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
9.3 Tipos de Funciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241
9.3.1 Funcion Inyectiva . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241
9.3.2 Funcion Suprayectiva . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
9.3.3 Funcion Biyectiva . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244
9.3.4 Composicion y Tipos de Funciones . . . . . . . . . . . . . . . . . . . . . . . . . 253
9.4 Funcion Inversa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255
9.4.1 Funcion Invertible . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255
9.4.2 Caracterizacion de una Funcion Invertible . . . . . . . . . . . . . . . . . . . . . 255
9.5 Composicion de Funciones e Inversa de una Funcion . . . . . . . . . . . . . 258
9.5.1 Proposicion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258
9.5.2 Unicidad de la Inversa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260
9.5.3 Inversa de la Composicion de Funciones . . . . . . . . . . . . . . . . . . . . . . 260

Lección 10
Divisibilidad. Algoritmo de la División 


Contenido
10.1 Algoritmo de la Division . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266
10.1.1 Existencia y Unicidad de Cociente y Resto . . . . . . . . . . . . . . . . . . . . 266
10.1.2 Corolario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267
10.2 Sistemas de Numeracion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271
10.2.1 Descomposicion Polinomica de un Numero . . . . . . . . . . . . . . . . . . . . . 271
10.2.2 Representacion Hexadecimal de un Octeto . . . . . . . . . . . . . . . . . . . . . 276
10.2.3 Representacion Binaria de un Hexadecimal de Cuatro D´ıgitos . . . . . . . . . . 277
10.3 El principio del Buen Orden . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278
10.3.1 Conjunto Bien Ordenado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278
10.4 Divisibilidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279
10.4.1 Definicion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279
10.4.2 Propiedades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280
10.5 Criterios de Divisibilidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285
10.5.1 Criterio General de Divisibilidad . . . . . . . . . . . . . . . . . . . . . . . . . . 285
10.6 Maximo Comun Divisor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289
10.6.1 Divisor Comun . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289
10.6.2 Maximo Com´un Divisor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290
10.6.3 Propiedades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291
10.6.4 Maximo Comun Divisor de Varios Números . . . . . . . . . . . . . . . . . . . . 292
10.6.5 Existencia y Unicidad del m.c.d. . . . . . . . . . . . . . . . . . . . . . . . . . . 292
10.6.6 Corolario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294
10.6.7 Proposición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294
10.6.8 Corolario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294
10.6.9 Mas Propiedades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295
10.7 Algoritmo de Euclides . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
10.7.1 Teorema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300
10.7.2 Algoritmo de Euclides . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300
10.8 Mínimo Común Multiplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306
10.8.1 Múltiplo Común . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306
10.8.2 Mínimo Comun Multiplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306
10.8.3 Minimo Comun Multiplo de Varios Numeros . . . . . . . . . . . . . . . . . . . 307
10.8.4 Proposicion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307
10.8.5 Proposicion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308

Lección 11
Teorema Fundamental de la Aritmética 


Contenido
11.1 Números Primos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316
11.1.1 Definicion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316
11.1.2 Números Primos entre s´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316
11.1.3 Proposición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317
11.1.4 Teorema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318
11.2 Criba de Eratostenes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323
11.2.1 Teorema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323
11.3 Teorema Fundamental de la Aritmética . . . . . . . . . . . . . . . . . . . . . 325
11.3.1 Lema de Euclides . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325
11.3.2 Corolario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325
11.3.3 Corolario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326
11.3.4 Teorema Fundamental de la Aritmética . . . . . . . . . . . . . . . . . . . . . . 329
11.3.5 Corolario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331
11.4 Divisores de un N´umero . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332
11.4.1 Criterio General de Divisibilidad . . . . . . . . . . . . . . . . . . . . . . . . . . 332
11.4.2 Obtención de todos los Divisores de un Numero . . . . . . . . . . . . . . . . . . 332
11.4.3 Numero de Divisores de un Numero Compuesto . . . . . . . . . . . . . . . . . . 333
11.4.4 Suma de los Divisores de un Numero Compuesto . . . . . . . . . . . . . . . . . 335
11.5 Metodo para el Calculo del Maximo Comun Divisor y el Mínimo Común Múltiplo . . 339
11.5.1 Lema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340
11.5.2 Teorema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340
11.5.3 Teorema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341

Lección 12
Ecuaciones Diofánticas
 


Contenido
12.1 Generalidades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343
12.1.1 Definicion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343
12.2 Solución de una Ecuación Diofántica . . . . . . . . . . . . . . . . . . . . . . . 343
12.2.1 Solución Particular . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344
12.2.2 Solución General . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345

Lección 13
Clases de restos modulo m
 


Contenido
13.1 Conceptos Básicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356
13.1.1 Definicion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356
13.1.2 Teorema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356
13.2 Propiedades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359
13.2.1 Teorema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359
13.2.2 Teorema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359
13.2.3 Corolario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361
13.3 Conjunto de las Clases de Restos Modulo m . . . . . . . . . . . . . . . . . . 366
13.3.1 Relación de Equivalencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367
13.3.2 Clases de Equivalencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367
13.3.3 Conjunto Cociente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 368
13.4 Aritmética en Zm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 369
13.4.1 Suma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 369
13.4.2 Bien Definida . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370
13.4.3 Elemento Neutro para la Suma . . . . . . . . . . . . . . . . . . . . . . . . . . . 370
13.4.4 Elemento Opuesto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370
13.4.5 Producto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 371
13.4.6 Bien Definido . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 371
13.4.7 Elemento Neutro para el Producto . . . . . . . . . . . . . . . . . . . . . . . . . 371
13.4.8 Elemento Inverso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 371
13.5 Euler, Fermat y Wilson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383
13.5.1 Función φ de Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383
13.5.2 Teorema de Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384
13.5.3 Corolario (Fermat) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385
13.5.4 Teorema de Wilson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 389
13.6 Teorema Chino del Resto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 390
13.6.1 Teorema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391

Grafos


Contenido
14.1 Generalidades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 396
14.1.1 Definicion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 396
14.1.2 Vértices Adyacentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 397
14.1.3 Representación Grafica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 397
14.1.4 Multigrafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 398
14.1.5 Pseudografo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 398
14.1.6 Digrafo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 399
14.2 Grados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 399
14.2.1 Grado de un Vértice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 399
14.2.2 Vértice Aislado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 399
14.2.3 Grafo Regular . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 399
14.2.4 Suma de los Grados de un Grafo . . . . . . . . . . . . . . . . . . . . . . . . . . 400
14.2.5 Grado de Entrada y de Salida . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402
14.3 Isomorfismo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403
14.3.1 Isomorfismo de Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403
14.3.2 Invariante de un Grafo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404
14.3.3 Invariancia del Grado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404
14.4 Subgrafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 406
14.4.1 Definicion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 406
14.4.2 Subgrafo Expandido . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407
14.4.3 Subgrafo Inducido . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407
14.4.4 Eliminación de Aristas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408
14.4.5 Eliminación de Vértices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408
14.4.6 Grafos Completos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 409
14.4.7 Complemento de un Grafo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 410
14.5 Caminos y Ciclos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411
14.5.1 Camino . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411
14.5.2 Ciclo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411
14.5.3 Teorema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413
14.6 Grafos Conexos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414
14.6.1 Vértices Conectados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414
14.6.2 Grafos Conexos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414
14.6.3 Proposición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415
14.6.4 Componentes Conexas de un Grafo . . . . . . . . . . . . . . . . . . . . . . . . . 416
14.6.5 Puntos de Corte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 418
14.6.6 Puentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 418
14.7 Caminos y Ciclos de Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 420
14.7.1 Ciclo de Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 421
14.7.2 Grafo Euleriano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 422
14.7.3 Primer Lema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 422
14.7.4 Camino de Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423
14.7.5 Segundo Lema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423
14.7.6 Problema de los Puentes de Konisgberg . . . . . . . . . . . . . . . . . . . . . . 424
14.7.7 Tercer Lema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424
14.7.8 Teorema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 425
14.7.9 Corolario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 431
14.8 Caminos y Ciclos de Hamilton . . . . . . . . . . . . . . . . . . . . . . . . . . 443
14.8.1 Ciclo de Hamilton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 443
14.8.2 Grafo Hamiltoniano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 444
14.8.3 Camino de Hamilton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 444
14.8.4 Metodo desarrollado por Hamilton . . . . . . . . . . . . . . . . . . . . . . . . . 444
14.8.5 Teorema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 449
14.9 Representación de Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456
14.9.1 Matriz de Adyacencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456
14.9.2 Teorema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460
14.9.3 Corolario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 461
14.9.4 Caracterización de un Grafo Conexo . . . . . . . . . . . . . . . . . . . . . . . . 461
14.9.5 Matriz de Incidencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462



https://www.dropbox.com/s/1rljvvnie6mkalu/Apuntes%20Logica%20Y%20Mates%20Discretas.rar?dl=0




Gracias por visitar mi post y mas adelante traeré mas apuntes extraídos de la web y de los de mi U