Agencia de Gobierno Electrónico y Sociedad de la Información y del Conocimiento

C. Programa de Matemática Discreta y Lógica 2

1. Datos de la Actividad Curricular

• Nombre: Matemática Discreta y Lógica 2
• Área de formación: Matemática
• Créditos: 6

2. Objetivos

El objetivo de esta actividad curricular es que el estudiante comprenda la Lógica de Predicados desde el punto de vista formal y como mecanismo de especificación y verificación. Asimismo, que sepa utilizar elementos relevantes de matemática discreta y de lógica matemática para formalizar elementos de la realidad.

A nivel de los objetivos de aprendizaje el estudiante será capaz de:

• Reconocer los componentes de un sistema formal.
• Interpretar y distinguir las nociones de verdad, juicio y fórmula lógica en Lógica de Primer Orden.
• Interpretar y distinguir elementos sintácticos de la Lógica de Primer Orden.
• Interpretar la noción de estructura de primer orden.
• Interpretar y diferenciar los juicios que involucran fórmulas, términos y estructuras.
• Construir estructuras y lenguajes de primer orden adecuados para representar una realidad determinada.
• Identificar y probar propiedades sintácticas de los lenguajes de primer orden.
• Identificar y probar propiedades algebraicas de la Lógica de Primer Orden.
• Interpretar las reglas de inferencia de Deducción Natural como esquemas de razonamiento típicos de las matemáticas.
• Construir pruebas usando las  reglas  de  Deducción  Natural. Interpretar y aplicar las ideas de axioma, teorema, teoría lógica, consistencia.
• Interpretar las nociones de corrección y completitud de la lógica clásica de primer orden.

3. Metodología de enseñanza

• Horas clase (teórico): 30
• Horas clase (práctico y laboratorio): 30
• Horas evaluación: 6
• Horas estudio: 24

Total de horas de dedicación del estudiante: 90

4. Temario

1. Sintaxis de la Lógica de Primer Orden (LPO)
   1. Definición de estructura de primer orden
   2. Definición recursiva de términos y fórmulas sobre un alfabeto
   3. Definición de variables libres, ligadas, sustituciones
2. Semántica de la LPO
   1. Interpretaciones sobre estructuras. Definición recursiva de funciones de interpretación
   2. Interpretación recursiva de fórmulas proposicionales. Definición de Tautología, Contingencia y Contradicción
   3. Interpretación de fórmulas de primer orden. Clausura Universal. Definición de juicios: Satisfactible, Lógicamente Válido y Consecuencia Lógica
   4. ) Propiedades algebraicas básicas, equivalencia, teoremas de cambios de variables y de sustitución. Identidad
   5. Formalización y análisis de propiedades sobre distintas realidades
3. Deducción Natural en LPO
   1. Reglas de derivación y heurísticas
   2. Definición inductiva del lenguaje de las derivaciones
   3. Análisis de casos de estudio
4. Corrección y Completitud de la LPO
   1. Nociones de corrección y completitud del sistema de pruebas
   2. Corrección del sistema
   3. Conjuntos consistentes e inconsistentes. Definición de teoría
   4. ) Noción de conjunto completo y consistencia maximal

5. Bibliografía Básica

1. D. van Dalen: Logic and Structure. Springer London, 5th Edition, (2013).

Complementaria

1. H. B. Curry: Foundations of mathematical logic. Dover Publications, 2nd Edition, (2010).
2. E. Lehman, F. Thomson Leighton, A. R. Meyer: Mathematics for Computer Science, (2017).

6. Conocimientos Recomendados

Conocimientos Previos Exigidos Curso Matemática Discreta y Lógica 1 (MDL1)

Conocimientos Previos Recomendados Inducción y Recursión (MDL1). Significado intuitivo de los conectivos y cuantificadores de Lógica de Primer Orden (MDL1). De acuerdo a los conocimientos previos necesarios, el curso podría desarrollarse en el segundo semestre.