Matemáticas discretas con aplicaciones Susanna S. Epp Cuarta Edición MATEMÁTICAS DISCRETAS CON APLICACIONES CUARTA EDICIÓN SUSANNA S. EPP Universi...

Matemáticas discretas con aplicaciones Susanna S. Epp Cuarta Edición

MATEMÁTICAS DISCRETAS CON APLICACIONES CUARTA EDICIÓN SUSANNA S. EPP Universidad DePaul Omar A. Ramírez Rosas ISBN-13: 978-607-481-757-7 ISBN-10: 607-481-757-x A Jayne y Ernest CONTENIDO Capítulo 1 Hablando matemáticamente 1 1.1 Variables 1 Uso de variables en las presentaciones matemáticas; Introducción a los enunciados universal, existencial y condicional 1.2 El lenguaje de los conjuntos 6 Las notaciones de lista del conjunto y de construcción del conjunto; Subconjuntos; Productos cartesianos 1.3 El lenguaje de las relaciones y funciones 13 Definición de una relación de un conjunto a otro; Diagrama de flechas de una relación; Definición de una función; Máquinas de funciones; Igualdad de funciones Capítulo 2 La lógica de los enunciados compuestos 23 2.1 Forma lógica y equivalencia lógica 23 Enunciados; Enunciados compuestos; Valores verdaderos; Evaluando la verdad de los enunciados compuestos más generales; Equivalencia lógica; Tautologías y contradicciones; Resumen de equivalencias lógicas 2.2 Enunciados condicionales 39 Equivalencias lógicas que involucran ; Representación de Si-Entonces como O; La negación de un enunciado condicional; El contrapositivo de un enunciado condicional; El converso y el contrario de un enunciado condicional; Sólo Si y las condiciones bicondicionales necesaria y suficiente; Observaciones 2.3 Argumentos válidos y no válidos 51 Modus Ponens y Modus Tollens; Formas adicionales de argumento válido: Reglas de inferencia; Falacias; Contradicciones y Argumentos válidos; Resumen de reglas de inferencia 2.4 Aplicación: circuitos lógicos digitales 64 Cajas negras y Puertas; La tabla de entrada/salida para un circuito; La expresión booleana correspondiente a un circuito; El circuito correspondiente a una expresión booleana; Determinación de un circuito que corresponda a una tabla dada de entrada/ salida; Simplificación de circuitos combinacionales; Puertas NAND y NOR 2.5 Aplicación: sistemas numéricos y circuitos para suma 78 Representación binaria de números; Suma y resta binaria; Circuitos para suma en compu- tadoras; Dos complementos y la representación en computadora de enteros negativos; Contenido vii Representación de un número de 8-Bit; Suma en computadora con enteros negativos; Notación hexadecimal Capítulo 3 La lógica de enunciados cuantificados 96 3.1 Predicados y enunciados cuantificados I 96 El cuantificador universal: ; El cuantificador existencial: 3; Lenguaje formal versus lenguaje informal; Enunciados condicionales universales; Formas equivalentes de los enunciados universal y existencial; Cuantificación implícita; mundo de Tarski 3.2 Predicados y enunciados cuantificados II 108 Negaciones de enunciados cuantificados; Negaciones de enunciados condicionales universales; La relación entre , , y ; Verdad vacía de los enunciados universa- les; Variantes de los enunciados condicionales universales; Condiciones necesarias y suficientes, Sólo si 3.3 Enunciados con cuantificadores múltiples 117 Traducción del lenguaje informal al formal; Lenguaje ambiguo; Negaciones de enun- ciados con cuantificadores múltiples; Orden de cuantificadores; Notación lógica formal; Prologo 3.4 Argumentos con enunciados cuantificados 132 Modus ponens universal; Uso del modus ponens universal en una demostración; Modus tollens universal; Prueba de validez de argumentos con enunciados cuantificados; Uso de diagramas para probar validez; Creación de formas adicionales del argumento; Observación de los errores converso y contrario Capítulo 4 Teoría elemental de números y métodos de demostración 145 4.1 Demostración directa y contraejemplo I: introducción 146 Definiciones; Prueba de enunciados existenciales; Refutación de enunciados universales con contraejemplo; Prueba de enunciados universales; Guía para las demostraciones escritas de enunciados universales; Variaciones entre las demostraciones; Errores comu- nes; Iniciando las demostraciones; Demostración de que un enunciado existencial es falso; Suposición, Demostración y Refutación 4.2 Demostración directa y contraejemplo II: números racionales 163 Más de la generalización a partir de lo particular; Prueba de propiedades de números racionales; Deducción de nuevas Matemáticas a partir de las viejas 4.3 Demostración directa y contraejemplo III: divisibilidad 170 Prueba de propiedades de la divisibilidad; Contraejemplos y Divisibilidad; Teorema de factorización única de enteros 4.4 Demostración directa y contraejemplo IV: división en casos y el teorema del cociente-residuo 180 Análisis del teorema del cociente-residuo y ejemplos; div y mod; Representaciones alternativas de enteros y aplicaciones a la teoría de números; Valor absoluto y la des- igualdad del triángulo 4.5 Demostración directa y contraejemplo V: piso y techo 191 Definición y propiedades básicas; El Piso de n 2 4.6 Argumento indirecto: contradicción y contraposición 198 Demostración por contradicción; Argumento por contraposición; Relación entre demos- tración por contradicción y demostración por contraposición; La demostración como una herramienta de solución de problemas 4.7 Argumento indirecto: dos teoremas clásicos 207 La irracionalidad de 2 ; ¿Hay un infinito de números primos?; ¿Cuándo usar una de- mostración indirecta; Preguntas abiertas de la Teoría de números 4.8 Aplicación: algoritmos 214 Un lenguaje algorítmico; Una notación para algoritmos; Tablas de seguimiento; El algoritmo de la división; El algoritmo euclidiano Capítulo 5 Sucesiones, inducción matemática y recurrencia 227 5.1 Sucesiones 227 Fórmulas explicitas para sucesiones; Notación de suma; Notación de producto; Propiedades de sumas y productos; Cambio de variable; Notación factorial y seleccionar r de n; Sucesiones en un programa de cómputo; Aplicación: Algoritmo para convertir de base 10 a base 2 usando división repetida por 2 5.2 Inducción matemática I 244 Principio de inducción matemática; Suma de los primeros n enteros; Demostración de una igualdad; Deducción de fórm