Matemáticas discretas con aplicaciones (4a. ed.).

Matemáticas discretas con aplicaciones
CONTENIDO
PREFACIO
Capítulo 1 Hablando matemáticamente
	1.1 Variables
		Algunos tipos importantes de enunciados matemáticos
			Enunciados universales condicionales
			Enunciados universales existenciales
			Enunciados universales existenciales
		Autoexamen
			Conjunto de ejercicios 1.1
			Respuestas del autoexamen
	1.2 El lenguaje de los conjuntos
		Subconjuntos
		Productos cartesianos
		Autoexamen
			Conjunto de ejercicios 1.2
			Respuestas del autoexamen
	1.3 El lenguaje de las relaciones y funciones
		Diagrama de flechas de una relación
		Funciones
		Máquinas de funciones
		Autoexamen
			Conjunto de ejercicios 1.3
			Respuestas del autoexamen
Capítulo 2 La lógica de los enunciados compuestos
	2.1 Forma lógica y equivalencia lógica
		Enunciados
		Enunciados compuestos
		Valores de verdad
		Evaluando la verdad de los enunciados compuestos más generales
		Equivalencia lógica
		Tautologías y contradicciones
		Resumen de las equivalencias lógicas
		Autoexamen
			Conjunto de ejercicios 2.1
			Respuestas del autoexamen
	2.2 Enunciados condicionales
		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 la contraria de un enunciado condicional
		Sólo si y el bicondicional
		Condiciones necesarias y suficientes
		Observaciones
		Autoexamen
			Conjunto de ejercicios 2.2
			Respuestas del autoexamen
	2.3 Argumentos válidos y no válidos
		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
		Autoexamen
			Conjunto de ejercicios 2.3
			Respuestas del autoexamen
	2.4 Aplicación: circuitos lógicos digitales
		Cajas negras y puertas
		Reglas para un circuito combinacional
		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 corresponde a una tabla dada de entrada/salida
		Simplificación de circuitos combinacionales
		Puertas NAND y NOR
		Autoexamen
			Conjunto de ejercicios 2.4
			Respuestas del autoexamen
	2.5 Aplicación: sistemas numéricos y circuitos para suma
		Representación binaria de números
		Suma y resta binaria
		Circuitos para el cálculo de sumas
		Complementos de dos y la representación en computadora de enteros negativos
		Representación 8 bits de un número
		Suma en computadora con enteros negativos
		Notación hexadecimal
		Autoexamen
			Conjunto de ejercicios 2.5
			Respuestas del autoexamen
Capítulo 3 La lógica de enunciados cuantificados
	3.1 Predicados y enunciados cuantificados I
		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
		Autoexamen
			Conjunto de ejercicios 3.1*
			Respuestas del autoexamen
	3.2 Predicados y enunciados cuantificados II
		Negaciones de enunciados cuantificados
		Negaciones de enunciados condicionales universales
		La relación entre ∀, 3, Λ y V
		Verdad vacía de los enunciados universales
		Variantes de los enunciados condicionales universales
		Condiciones necesarias y suficientes, sólo si
		Autoexamen
			Conjunto de ejercicios 3.2
			Respuestas del autoexamen
	3.3 Enunciados con cuantificadores múltiples
		Traducción del lenguaje informal al formal
		Lenguaje ambiguo
		Negaciones de enunciados con cuantificadores múltiples
		Orden de cuantificadores
		Notación lógica formal
		Prologo
		Autoexamen
			Conjunto de ejercicios 3.3
			Respuestas del autoexamen
	3.4 Argumentos con enunciados cuantificados
		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 acerca de los errores converso y contrario
		Autoexamen
			Conjunto de ejercicios 3.4
			Respuestas del autoexamen
Capítulo 4 Teoría elemental de números y métodos de demostración
	4.1 Demostración directa y contraejemplo I: introducción
		Definiciones
		Prueba de enunciados existenciales
		Refutación de un enunciado universal con un contraejemplo
		Prueba de enunciados universales
		Instrucciones para escribir demostraciones de enunciados universales
		Variación entre demostraciones
		Errores comunes
		Obtención del inicio de demostraciones
		Mostrando que un enunciado existencial es falso
		Conjetura, demostración y refutación
		Autoexamen
			Conjuntos de ejercicios 4.1*
			Respuestas del autoexamen
	4.2 Demostración directa y contraejemplo II: números racionales
		Más de la generalización de lo general a lo particular
		Demostración de propiedades de números racionales
		Deducción de nuevas Matemáticas a partir de las viejas
		Autoexamen
			Conjunto de ejercicios 4.2
			Respuestas del autoexamen
	4.3 Demostración directa y contraejemplo III: divisibilidad
		Demostración de propiedades de la divisibilidad
		Contraejemplos y divisibilidad
		Teorema de factorización única de enteros
		Autoexamen
			Conjunto de ejercicios 4.3
			Respuestas del autoexamen
	4.4 Demostración directa y contraejemplo IV: división en casos y el teorema del cociente-residuo
		div y mod
		Representaciones de enteros
		Valor absoluto y la desigualdad del triángulo
		Autoexamen
			Conjunto de ejercicios 4.4
			Respuestas del autoexamen
	4.5 Demostración directa y contraejemplo V: piso y techo
		Autoexamen
			Conjunto de ejercicios 4.5
			Respuestas del autoexamen
	4.6 Argumento indirecto: contradicción y contraposición
		Argumentos por contraposición
		Relación entre demostración por contradicción y demostración por contraposición
		La demostración como herramienta para resolver problemas
		Autoexamen
			Conjunto de ejercicios 4.6
			Respuestas del autoexamen
	4.7 Argumento indirecto: dos teoremas clásicos
		La irracionalidad de √2
		¿Hay un infinito de números primos?
		Cuándo usar una demostración indirecta
		Preguntas abiertas de la Teoría de números
		Autoexamen
			Conjunto de ejercicios 4.7
			Respuestas del autoexamen
	4.8 Aplicación: algoritmos
		Un lenguaje algorítmico
		Una notación de algoritmos
		El algoritmo de la división
		El algoritmo euclidiano
		Autoexamen
			Conjunto de ejercicios 4.8
			Respuestas del autoexamen
Capítulo 5 Sucesiones, inducción matemática y recurrencia
	5.1 Sucesiones
		Notación de suma
		Notación de producto
		Propiedades de sumas y productos
		Cambio de variable
		Notación factorial y de “n se selecciona r”
		Sucesiones en un programa de cómputo
		Aplicación: algoritmo para convertir de la base 10 a la base 2 usando división repetida por 2
		Autoexamen
			Conjunto de ejercicios 5.1*
			Respuestas del autoexamen
	5.2 Inducción matemática I
		Demostración de una igualdad
		Deducción de fórmulas adicionales
		Autoexamen
			Conjunto de ejercicios 5.2
			Respuestas del autoexamen
	5.3 Inducción matemática II
		Un problema con trominos
		Autoexamen
			Conjunto de ejercicios 5.3
			Respuestas del autoexamen
	5.4 Inducción matemática fuerte y el principio del buen orden de los números enteros
		Aplicación de la inducción matemática fuerte
		Autoexamen
			Conjunto de ejercicios 5.4
			Respuestas del autoexamen
	5.5 Aplicación: exactitud de algoritmos
		Afirmaciones
		Invariantes de bucle
		Exactitud del algoritmo de división
		Exactitud del teorema de Euclides
		Autoexamen
			Conjunto de ejercicios 5.5
			Respuestas del autoexamen
	5.6 Definición de sucesión recursiva
		Ejemplos de sucesiones definidas recursivamente
		Definiciones recursivas de suma y producto
		Autoexamen
			Conjunto de ejercicios 5.6
			Respuestas del autoexamen
	5.7 Solución por iteración de las relaciones de recurrencia
		El método de iteración
		Uso de fórmulas para simplificar soluciones obtenidas por iteración
		Comprobación de lo exacto de una fórmula con inducción matemática
		Descubriendo que una fórmula explícita es incorrecta
		Autoexamen
			Conjunto de ejercicios 5.7
			Respuestas del autoexamen
	5.8 Relaciones lineales de recurrencia de segundo orden con coeficientes constantes
		El caso de raíces distintas
		El caso de una sola raíz
		Autoexamen
			Conjunto de ejercicios 5.8
			Respuestas del autoexamen
	5.9 Definiciones generales recursivas e inducción estructural
		Conjuntos definidos recursivamente
		Demostración de propiedades respecto de conjuntos definidos recursivamente
		Funciones recursivas
		Autoexamen
			Conjunto de ejercicios 5.9
			Respuestas del autoexamen
Capítulo 6 Teoría de conjuntos
	6.1 Teoría de conjuntos: definiciones y el método del elemento de demostración
		Subconjuntos: demostración y refutación
		Igualdad de conjuntos
		Diagramas de Venn
		Operaciones con conjuntos
		Conjunto vacío
		Particiones de conjuntos
		Conjunto potencia
		Productos cartesianos
		Un algoritmo para comprobar si un conjunto es un subconjunto de otro (opcional)
		Autoexamen
			Conjunto de ejercicios 6.1*
			Respuestas del autoexamen
	6.2 Propiedades de conjuntos
		Identidades de conjuntos
		Demostración de identidades de conjunto
		Conjunto vacío
		Autoexamen
			Conjunto de ejercicios 6.2
			Respuestas del autoexamen
	6.3 Refutaciones, demostraciones algebraicas y álgebra booleana
		Refutación de una supuesta propiedad de un conjunto
		Estrategia de solución de problemas
		El número de subconjuntos de un conjunto
		Demostraciones “algebraicas” de identidades de conjuntos
		Autoexamen
			Conjunto de ejercicios 6.3
			Respuestas del autoexamen
	6.4 Álgebra booleana, paradoja de Russell y el problema del paro
		Paradoja de Russell
		El problema del paro
		Autoexamen
			Conjunto de ejercicios 6.4
			Respuestas del autoexamen
Capítulo 7 Funciones
	7.1 Funciones definidas sobre conjuntos generales
		Diagramas de flechas
		Ejemplos de funciones
		Funciones booleanas
		Verificación de si una función está bien definida
		Funciones actuando sobre conjuntos
		Autoexamen
			Conjuntos de ejercicios 7.1*
			Respuestas del autoexamen
	7.2 Inyectiva y sobreyectiva, funciones inversas
		Funciones inyectivas
		Funciones inyectivas sobre conjuntos infinitos
		Aplicación: Funciones Hash
		Funciones sobreyectivas
		Funciones sobreyectivas sobre conjuntos infinitos
		Relaciones entre las funciones exponenciales y logarítmicas
		Correspondencias inyectivas
		Funciones inversas
		Autoexamen
			Conjunto de ejercicios 7.2
			Respuestas del autoexamen
	7.3 Composición de funciones
		Composición de funciones inyectivas
		Composición de funciones sobreyectivas
		Autoexamen
			Conjunto de ejercicios 7.3
			Respuestas del autoexamen
	7.4 Cardinalidad con aplicaciones a la computabilidad
		Conjuntos contables
		La búsqueda de grandes infinitos: el proceso de diagonalización de Cantor
		Aplicación: cardinalidad y computabilidad
		Autoexamen
			Conjunto de ejercicios 7.4
			Respuestas del autoexamen
Capítulo 8 Relaciones
	8.1 Relaciones sobre conjuntos
		La inversa de una relación
		Grafo dirigido de una relación
		Relaciones n-arias y Bases de datos relacionales
		Autoexamen
			Conjunto de ejercicios 8.1*
			Respuestas del autoexamen
	8.2 Reflexividad, simetría y transitividad
		Propiedades de las relaciones sobre conjuntos infinitos
		La cerradura transitiva de una relación
		Autoexamen
			Conjunto de ejercicios 8.2
			Respuestas del autoexamen
	8.3 Relaciones de equivalencia
		La relación inducida por una partición
		Definición de una relación de equivalencia
		Clases de equiva lencia de una relación de equivalencia
		Congruencia módulo n
		Una definición de números racionales
		Autoexamen
			Conjunto de ejercicios 8.3
			Respuestas del autoexamen
	8.4 Aritmética modular con aplicaciones a la criptografía
		Propiedades de congruencia módulo n
		Aritmética modular
		Extensión del algoritmo de Euclides
		Determinación de un inverso módulo n
		Criptografía RSA
		Lema de Euclides
		Pequeño teorema de Fermat
		¿Por qué funciona el cifrado RSA?
		Observaciones adicionales de la teoría de números y de la criptografía
		Autoexamen
			Conjunto de ejercicios 8.4
			Respuestas del autoexamen
	8.5 Relaciones de orden parcial
		Antisimetría
		Relaciones de orden parcial
			Orden lexicográfico
			Diagramas de Hasse
			Conjuntos ordenados parcial y totalmente
			Ordenamiento topológico
			Una aplicación
		PERT y CPM
		Autoexamen
			Conjunto de ejercicios 8.5
			Respuestas del autoexamen
Capítulo 9 Conteo y probabilidad
	9.1 Introducción
		Conteo de los elementos de una lista
		Autoexamen
			Conjunto de ejercicios 9.1*
			Respuestas del autoexamen
	9.2 Árbol de probabilidad y la regla de multiplicación
		La regla de la multiplicación
		Cuando la regla de la multiplicación es difícil o imposible de aplicar
		Permutaciones
		Permutaciones de elementos seleccionados
		Autoexamen
			Conjunto de ejercicios 9.2
			Respuestas del autoexamen
	9.3 Conteo de elementos de conjuntos disjuntos: la regla de la suma
		La regla de la diferencia
		La regla de inclusión/exclusión
		Autoexamen
			Conjunto de ejercicios 9.3
			Respuestas del autoexamen
	9.4 El principio de las casillas
		Aplicación a expansiones decimales de fracciones
		Principio generalizado de las casillas
		Demostración del principio de las casillas
		Autoexamen
			Conjunto de ejercicios 9.4
			Respuestas del autoexamen
	9.5 Conteo de subconjuntos de un conjunto: combinaciones
		Algunos consejos acerca del conteo
		El número de particiones de un conjunto en r subconjuntos
		Autoexamen
			Conjunto de ejercicios 9.5.
			Respuestas del autoexamen
	9.6 r-combinaciones con repetición permitida
		¿Qué fórmula usar?
		Autoexamen
			Conjunto de ejercicios 9.6
			Respuestas del autoexamen
	9.7 Fórmula de Pascal y el teorema del binomio
		Fórmula de Pascal
		El teorema binomial
		Autoexamen
			Conjunto de ejercicios 9.7
			Respuestas del autoexamen
	9.8 Axiomas de probabilidad y valor esperado
		Valor esperado
		Autoexamen
			Conjunto de ejercicios 9.8
			Respuestas del autoexamen
	9.9 Probabilidad condicional, fórmula de Bayes y eventos independientes
		Probabilidad condicional
		Teorema de Bayes
		Eventos independientes
		Autoexamen
			Conjunto de ejercicios 9.9
			Respuestas del autoexamen
Capítulo 10 Grafos y árboles
	10.1 Grafos: definiciones y propiedades básicas
		Ejemplos de grafos
		Grafos especiales
		El concepto de grado
		Autoexamen
			Conjunto de ejercicios 10.1*
			Autoexamen
	10.2 Senderos, rutas y circuitos
		Definiciones
		Conectividad
		Circuitos de Euler
		Circuitos hamiltonianos
		Autoexamen
			Conjunto de ejercicios 10.2
			Respuestas del autoexamen
	10.3 Representaciones matriciales de grafos
		Matrices
		Matrices y grafos dirigidos
		Matrices y grafos no dirigidos
		Matrices y componentes conexos
		Multiplicación de matrices
		Conteo de caminos de longitud N
		Autoexamen
			Conjunto de ejercicios 10.3
			Respuestas del autoexamen
	10.4 Isomorfismos de grafos
		Isomorfismo gráfico para grafos simples
		Autoexamen
			Conjunto de ejercicios 10.4
			Respuestas del autoexamen
	10.5 Árboles
		Ejemplos de árboles
		Caracterización de árboles
		Autoexamen
			Conjunto de ejercicios 10.5
			Respuestas del autoexamen
	10.6 Árboles enraizados
		Árboles binarios
		Autoexamen
			Conjunto de ejercicios 10.6
			Respuestas del autoexamen
	10.7 Expansión de árboles y trayectorias más cortas
		Arboles expandidos mínimos
		Algoritmo de Kruskal
		Algoritmo de Prim
		Algoritmo de la trayectoria más corta de Dijkstra
		Autoexamen
			Conjunto de ejercicios 10.7
			Respuestas del autoexamen
Capítulo 11 Análisis de la eficiencia de un algoritmo
	11.1 Funciones de valores reales de una variable real y sus gráficas
		Funciones potencia
		La función piso
		Graficando funciones definidas sobre conjuntos de enteros
		Gráfica de un múltiplo de una función
		Funciones crecientes y decrecientes
		Autoexamen
			Conjunto de ejercicios 11.1*
			Respuestas del autoexamen
	11.2 Notaciones O, Ω y Θ
		Órdenes de funciones potencia
		Órdenes de funciones polinomiales
		Órdenes para funciones de variables enteras
		Extensión a funciones compuestas de funciones potencia racionales
		Autoexamen
			Conjunto de ejercicios 11.2
			Respuestas del autoexamen
	11.3 Aplicación: análisis de la eficiencia del algoritmo I
		El algoritmo de la búsqueda sucesiva
		El algoritmo de ordenamiento por inserción
		Eficiencia temporal de un algoritmo
		Autoexamen
			Conjunto de ejercicios 11.3
			Respuestas del autoexamen
	11.4 Funciones exponenciales y logarítmicas: gráficas y órdenes
		Gráficas de funciones exponenciales
		Gráficas de funciones logarítmicas
		Aplicación: número de bits necesarios para representar a un entero en notación binaria
		Aplicación: uso de logaritmos para resolver relaciones de recurrencia
		Órdenes exponenciales y logarítmicas
		Autoexamen
			Conjunto de ejercicios 11.4
			Respuestas del autoexamen
	11.5 Aplicación: análisis de la eficiencia de un algoritmo II
		Búsqueda binaria
		Eficiencia del algoritmo de búsqueda binaria
		Ordenamiento por mezcla
		Problemas manejables e inmanejables
		Una observación final acerca de la eficiencia de un algoritmo
		Autoexamen
			Conjunto de ejercicios 11.5
			Respuestas del autoexamen
Capítulo 12 Expresiones regulares y autómatas de estado-finito
	12.1 Lenguajes formales y expresiones regulares
		El lenguaje definido por una expresión regular
		Usos prácticos de expresiones regulares
		Autoexamen
			Conjunto de ejercicios 12.1*
			Respuestas del autoexamen
	12.2 Autómatas de estado-finito
		Definición de un autómata de estado-finito
		El lenguaje aceptado por un autómata
		La función de estado-eventual
		Diseño de un autómata de estado-finito
		Simulación de un autómata de estado-finito utilizando software
		Autómatas de estado-finito y expresiones regulares
		Lenguajes regulares
		Autoexamen
			Conjunto de ejercicios 12.2
			Respuestas del autoexamen
	12.3 Simplificando autómatas de estado-finito
		*-Equivalencia de Estados
		k-Equivalencia de estados
		Determinación de las clases de *-equivalencia
		El autómata cociente
		Construcción del autómata cociente
		Autómata equivalente
		Autoexamen
			Conjunto de ejercicios 12.3
			Respuestas del autoexamen
Apéndice A Propiedades de los números reales*
Apéndice B Soluciones y sugerencias para los ejercicios seleccionados
Índice
Lista de símbolos
Fórmulas de referencia