Notas matemáticas discretas

Notas de Matem´ticas Discretas a
Luis Eduardo Gamboa Guzm´n a
1

Universidad Michoacana de San Nicol´s de Hidalgo a Facultad de Ingenier´ El´ctrica ıa e 08 de julio de 2008

1

http://lc.fie.umich.mx/~legg/

2

´ Indice general
1. Sobre este documento 2. M´todos de demostraci´n e o 2.1. L´gica proposicional . . . . . . . . . . . . . . . . . . . . . . . . o 2.1.1. Proposicionescompuestas . . . . . . . . . . . . . . . . . 2.1.2. Tablas de verdad . . . . . . . . . . . . . . . . . . . . . . 2.1.3. F´rmulas, Tautolog´ y Contradicciones . . . . . . . . . o ıas 2.1.4. Simplificaci´n . . . . . . . . . . . . . . . . . . . . . . . . o 2.1.5. Obtenci´n de f´rmulas . . . . . . . . . . . . . . . . . . . o o 2.1.6. Forma Normal Conjuntiva . . . . . . . . . . . . . . . . . 2.1.7. FormaNormal Disyuntiva . . . . . . . . . . . . . . . . . 2.2. Inferencia L´gica . . . . . . . . . . . . . . . . . . . . . . . . . . o 2.3. Argumentos v´lidos . . . . . . . . . . . . . . . . . . . . . . . . a 2.4. Prueba directa . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5. Prueba indirecta . . . . . . . . . . . . . . . . . . . . . . . . . . 2.6. Pruebas vacuas . . . . . . . . . . . . . . . .. . . . . . . . . . . 2.7. Pruebas triviales . . . . . . . . . . . . . . . . . . . . . . . . . . 2.8. Prueba por contradicci´n . . . . . . . . . . . . . . . . . . . . . o 2.9. Prueba por casos . . . . . . . . . . . . . . . . . . . . . . . . . . 2.10. Prueba por equivalencia . . . . . . . . . . . . . . . . . . . . . . 2.11. L´gica de predicados . . . . . . . . . . . . . . . . . . . . . . . . o2.11.1. Cuantificador universal . . . . . . . . . . . . . . . . . . 2.11.2. Cuantificador existencial . . . . . . . . . . . . . . . . . . 2.11.3. Escritura de declaraciones . . . . . . . . . . . . . . . . . 2.11.4. Propiedades de los cuantificadores . . . . . . . . . . . . 2.11.5. Instanciaci´n e Interpretaci´n . . . . . . . . . . . . . . . o o 2.11.6. Principio de resoluci´n y procesamiento deinterrogantes o 2.12. Errores en las demostraciones . . . . . . . . . . . . . . . . . . . 7 9 9 9 9 12 14 14 15 16 16 18 18 19 19 20 20 21 21 21 22 22 22 23 24 27 28

. . . . . . . . . . . . . . . . . . . . . . . . .

3. Inducci´n Matem´tica o a 29 3.1. Inducci´n simple . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 o 3.2. Inducci´n completa . . . . . . . . . . . . . . . . . . . . . . . . .. 32 o 3

4 4. Conjuntos 4.1. Definici´n y operaciones . . . . . . . . . . o 4.1.1. Subconjuntos . . . . . . . . . . . . 4.1.2. Definici´n Recursiva de Conjuntos o 4.1.3. Conjunto potencia . . . . . . . . . 4.1.4. Algebra de Conjuntos . . . . . . . 4.2. Conjuntos contables e incontables . . . . . 4.2.1. Producto . . . . . . . . . . . . . . 5. Relaciones 5.1. Relaci´n Inversa . . . . . . o 5.2.Relaciones Reflexivas . . . . 5.3. Relaciones Irreflexivas . . . 5.4. Relaciones Sim´tricas . . . . e 5.5. Relaciones Antisim´trica . . e 5.6. Relaciones Transitivas . . . 5.7. Composici´n . . . . . . . . o 5.8. Ordenes Parciales . . . . . . 5.9. Relaciones de Equivalencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . .

´ INDICE GENERAL 35 35 36 36 36 36 38 38 41 42 42 42 42 42 43 43 43 43 45 45 45 46 46 46 46 47 47 47 47 49 49 49 51 51 53 53 53 53 53 53 53

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . ..

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6. Funciones 6.1. Propiedades . . . . . . . . . . . . . . . . ....