discretas

Matemáticas Discretas
I. Lógica, conjuntos y clases
1. El método axiomático
2. Teoría axiomática de clases
3. Algebra de clases y conjuntos
4. Conjunto potencia
5. Pares Ordenados y Producto cartesiano
6. Gráficas.
II. Análisis combinatorio
1. Principio de la suma
2. Permutaciones y combinaciones
III. Relaciones y grafos
1. Relaciones y sus propiedades
2. Relaciones de equivalenciay particiones
3. Relaciones de orden parcial y retículos
4. Grafos y su representación
5. Conectividad de grafos
6. Caminos Eulerianos y Hamiltonianos
7. Caminos de longitud mínimo
8. Isomorfismo de grafos
9. Planaridad y coloreado
IV. Estructuras Algebraicas
1. Funciones booleanas
2. Algebra de boole y sus propiedades
3. Representación de funciones booleanas
4. Puertas lógicas
5.Máquinas de estado finito
6. Semigrupos, grupos y anillos
Bibliografía.
1. Pinter, Charles (1971). Set Theory. Reading Mass, Estados Unidos: Addison-Wesley
2. Bernald Kolman Robert C. Busbu Estructuras de matematicas discretas para la computación, Prentice Hall
3. Jose A. Jiménez Murillo, (2009)Matemáticas para la computación, Alfaomega
4. Jean PaulTremblay,(1996) Matemáticas discretas conaplicación a las ciencias de la computación, CECSA.

Evaluación:
Ejercicios ….. 40% Exámenes parciales ….60%

I. Lógica, conjuntos y clases
La teoría de conjuntos es primordial en las matemáticas “modernas” desde el trabajo de George Cantor (1845-1918) al estudiar series trigonométricas donde primero estudio las propiedades de conjuntos en un inicio con conjuntos particulares de númerosreales, posteriormente se da cuenta que su descubrimiento se puede aplicar a conjuntos completamente mas generales, conjuntos infinitos, pero sus contemporáneos no estaban de acuerdo (al trabajar con conjuntos infinitos, no lo comprendían) y cuando finalmente comprendieron su trabajo surgieron contradicciones en su teoría entre 1895 y 1910 y a estas se les llamo paradojas.

Las paradojas de lateoría de los conjuntos son de dos formas.

Paradoja lógica. La clásica es la paradoja de Russell y se describe a continuación.
Si A es un conjunto, sus elementos pueden ser así mismos conjuntos (por ejemplo, el conjunto de líneas donde cada línea es considerada como un conjunto de puntos). Surge un interrogante ¿A puede ser un elemento de sí mismo?.

Considérese el conjunto de todos losconjuntos que tienen la siguiente propiedad. Sea S denota el conjunto de todos los conjuntos que no son elementos de sí mismo. ¿Es S en elemento de sí mismo? Bien si S es un elemento de S, entonces por la propia definición de S, S no es un elemento de S. Por otro lado si S no es un elemento de S, entonces nuevamente por la manera en que S esta definida, S es un elemento de S. Así se ha probado que Ses un elemento de S si y sólo si S no es un elemento de S; lo cual es una contradicción.

Paradoja Semántica. La típica paradoja semántica es la paradoja de Berry.
Para el objeto de nuestro argumento admitamos que todas las palabras del lenguaje Ingles son listadas en algún diccionario estándar. Sea T el conjunto de todos los números naturales que pueden ser descritos a lo más en 20 palabrasdel lenguaje Ingles. Ya que hay solamente finitas maneras de combinar las 20 palabras, esto es, T es un conjunto finito. Bastante obvio entonces que hay números naturales los cuales son más grandes que todos los elementos de T, de aquí que haya un número natural al menos que no puede ser descrito a lo más en 20 palabras del lenguaje Ingles. Por definición este número no esta en T, y este número esdescrito en 16 palabras de aquí que debe de esta en T.


1. El método axiomático
Para muchos de los matemáticos de inicios de 1900 la respuesta al problema de las paradojas fue proporcionar la teoría de clases con base axiomática. En particular los axiomas deberán poder demostrar la teoría de Cantor mientras las paradojas no.
La primera axiomatización de la teoría de clases fue dada en...