MATEMÁTICAS DISCRETAS 2ª Edición

Un conjunto es discreto si sus elementos están separados. Los conjuntos finitos y los subconjuntos infinitos de números enteros son conjuntos discretos, pero el conjunto de los números reales no lo es. La matemática discreta es el estudio de estructuras matemáticas definidas sobre conjuntos discretos. Aunque los orígenes de la matemática discreta se remontan a la antigüedad, no ha sido sino hasta años recientes que ha cobrado importancia, por sus aplicaciones a diversos campos, en particular a las ciencias de la computación y a la investigación de operaciones. Este libro de texto está dirigido a estudiantes de ciencias básicas e ingeniería y en él se exponen los fundamentos de esta área de las matemáticas que es uno de los pilares de la ciencia de la computación.

La obra consta de cuatro partes: Fundamentos, Métodos algebraicos, Enumeración combinatoria y Teoría de grafos. Para esta nueva edición se han agregado nuevas secciones, se ha ampliado el número de problemas propuestos al final de cada capítulo y se han incluido más aplicaciones relacionadas con la ciencia de la computación.

VENTAJAS

• Cada uno de los capítulos inicia con un listado de objetivos del mismo y una introducción, asimismo, al final de cada capítulo se encuentra un resumen y una serie de ejercicios.

• A lo largo del libro hay múltiples ejemplos que contribuyen a la mejor comprensión de los temas.

• Contiene una plataforma virtual de contenidos interactivos.

CONOZCA

• Algunas de las aplicaciones más importantes de las matemáticas discretas como son cambio de base, complejidad computacional, circuitos lógicos, espacios finitos de probabilidad.

• Los axiomas de los números enteros y el método de inducción matemática.

• El mínimo común múltiplo y cómo se relaciona con el máximo común divisor.

• La relación entre la notación binaria y la notación hexadecimal.

APRENDA A

• Identificar las nociones de función recursiva primitiva, función recursiva parcial y función recursiva.

• Definir el producto cartesiano de dos conjuntos y la función de conjunto finito.

• Representar y manipular relaciones binarias finitas por medio de matrices booleanas.

• Identificar las características del álgebra booleana y algunos ejemplos importantes.

DESARROLLE SUS HABILIDADES PARA

• Diferenciar algoritmos computacionales.

• Distinguir las propiedades de congruencias y aplicarlas en la determinación del día de la semana para una fecha cualquiera, así como en el sistema criptográfico RSA.

• Aplicar los polinomios en los campos de Galois.

• Identificar las características de los coeficientes de polinomios y sus implicaciones en las nociones de divisibilidad, del máximo común divisor y el algoritmo de Euclides.

A QUIÉN VA DIRIGIDO

Este libro está dirigido a estudiantes y profesores de ciencias básicas e ingeniería.

CONTENIDO

Prólogo

Parte I

Fundamentos

Capítulo I

Lógica y conjuntos

1.1 Introducción

1.2 Proposiciones y conectivos lógicos

1.3 Implicación y equivalencia lógica

1.4 Reglas de inferencia

1.5 Conjuntos

1.6 Predicados y cuantificadores

1.7 Operaciones con conjuntos

1.8 Resumen

1.9 Ejercicios

Capítulo II

Los enteros

2.1 Introducción

2.2 Axiomas de los números enteros

2.3 Orden en los enteros

2.4 Método de inducción matemática

2.5 El principio del buen orden

2.6 Resumen

2.7 Ejercicios

Capítulo III

Divisibilidad

3.1 Introducción

3.2 Divisibilidad

3.3 Aplicación: cambio de base

3.4 Números primos

3.5 Máximo común divisor

3.6 El teorema fundamental de la aritmética

3.7 Resumen

3.8 Ejercicios

Capítulo IV

Funciones

4.1 Introducción

4.2 Producto cartesiano

4.3 Funciones

4.4 Funciones biyectivas

4.5 Composición de funciones

4.6 Conjuntos finitos

4.7 El principio de la pichonera

4.8 Conjuntos infinitos

4.9 Operaciones binarias

4.10 Resumen

4.11 Ejercicios

Capítulo V

Relaciones binarias

5.1 Introducción

5.2 Tipos de relaciones binarias

5.3 Relaciones de equivalencia

5.4 La matriz de una relación

5.5 Resumen

5.6 Ejercicios

Parte II

Métodos algebraicos

Capítulo VI

Retículos y álgebras booleanas

6.1 Introducción

6.2 Relaciones de orden

6.3 Retículos

6.4 Álgebras booleanas

6.5 Orden en álgebras booleanas

6.6 Expresiones y funciones booleanas

6.7 Simplificación de expresiones booleanas

6.8 Aplicación: circuitos lógicos

6.9 Resumen

6.10 Ejercicios

Capítulo VII

Computabilidad y complejidad computacional

7.1 Introducción

7.2 Funciones recursivas

7.3 Máquinas de Turing

7.4 Complejidad computacional

7.5 Problemas NP-completos

7.6 Resumen

7.7 Ejercicios

Capítulo VIII

Aritmética modular

8.1 Introducción

8.2 Congruencias

8.3 Aplicación: calendario perpetuo

8.4 El teorema chino del residuo

8.5 El teorema de Euler

8.6 El criptosistema RSA

8.7. Los enteros módulo m

8.8 Resumen

8.9 Ejercicios

Capítulo IX

Grupos

9.1 Introducción

9.2 Semigrupos y monoides

9.3 Grupos

9.4 Propiedades de grupos

9.5 Subgrupos

9.6 Códigos de grupo

9.7 Homomorfismos

9.8 Grupos cíclicos

9.9 El teorema de Lagrange

9.10 Resumen

9.11 Ejercicios

Capítulo X

Anillos, campos y polinomios

10.1 Introducción

10.2 Anillos

10.3 Campos

10.4 Polinomios

10.5 Divisibilidad

10.6 Máximo común divisor

10.7 Polinomios irreducibles

10.8 Construcción de campos finitos

10.9 Resumen

10.10 Ejercicios

Parte III

Enumeración combinatoria

Capítulo XI

Conteo

11.1 Introducción

11.2 Permutaciones y combinaciones

11.3 Teorema del binomio

11.4 Coeficientes multinomiales

11.5 Ecuaciones lineales diofantinas

11.6 Espacios finitos de probabilidad

11.7 Resumen

11.8 Ejercicios

Capítulo XII

El principio de inclusión-exclusión

12.1 Introducción

12.2 El principio de inclusión-exclusión

12.3 Aplicaciones especiales

12.4. Extensión del principio

12.5 Resumen

12.6 Ejercicios

Capítulo XIII

Funciones generadoras

13.1 Introducción

13.2 Series de potencias formales

13.3 Funciones generadoras ordinarias

13.4 Particiones de enteros

13.5 Funciones generadoras exponenciales

13.6 Funciones generadoras de probabilidad

13.7 Resumen

13.8 Ejercicios

Capítulo XIV

Relaciones de recurrencia

14.1 Introducción

14.2 Recurrencias lineales de orden uno

14.3 Recurrencias lineales homogéneas de orden dos

14.4 Solución con funciones generadoras

14.5 Resumen

14.6 Ejercicios

Parte IV

Teoría de grafos

Capítulo XV

Grafos

15.1 Introducción

15.2 Grafos y subgrafos

15.3 Caminos y grafos conexos

15.4 Grafos isomorfos

15.5 Paseos eulerianos

15.6 Resumen

15.7 Ejercicios

Capítulo XVI

Árboles

16.1 Introducción

16.2 Propiedades de árboles

16.3 Árboles con raíz

16.4 Contando árboles

16.5 Árboles de búsqueda

16.6 Árbol de recubrimiento mínimo

16.7 Resumen

16.8 Ejercicios

Capítulo XVII

Grafos dirigidos

17.1 Introducción

17.2 Grafos dirigidos

17.3 Grafos orientados y torneos

17.4 Cerradura transitiva

17.5 El problema de la ruta más corta

17.6 Flujo máximo en una red

17.7 Resumen

17.8 Ejercicios

Capítulo XVIII

Temas selectos de grafos

18.1 Introducción

18.2 Ciclos hamiltonianos

18.3 Emparejamientos

18.4 Grafos aplanables

18.5 Coloración de vértices

18.6 El problema de los cuatro colores

18.7 Resumen

18.8 Ejercicios

Bibliografía

Índice analítico

Prólogo