MATERIA:Análisis Lógico

CLAVE:COMP-421

SEMESTRE DE UBICACION:Cuarto.

AREA:Temas Selectos de Computación

OBJETIVOS: Este curso introduce al estudiante en el análisis del lenguaje matemático a través de los lenguajes de primer orden. De éstos, se enfatizan por igual tres aspectos: su estructura formal, su semántica (a través de las estructuras matemáticas) y la teoría de la inferencia lógica.

TEMARIO:

1. Introducción

   Se busca abstraer del lenguaje matemático ordinario (¡.e. tal como éste aparece en un libro de texto, por ejemplo) su estructura lógica. Mostrar ejemplos de cómo un lenguaje como, por ejemplo, el de la teoría de grupos es susceptible de distintas interpretaciones. Introducir los operadores lógicos fundamentales (negación, conjunción, cuantificación, etc.)

   • Análisis del lenguaje de la teoría de los números, el álgebra, etc.

   • Lenguajes y su semántica (por ejemplo, teoría de grupos, geometría)

   • Conectivos lógicos; propiedades y criterios de verdad.

   • Cuantificadores; propiedades y criterios de verdad

2. Lenguajes de primer orden

   Definición del concepto general de promer orden con ejemplos, puntualizando el papel de las variables en sus distintos niveles

   • Definición: símbolos lógicos, de puntuación, símbolos de función, predicados y Constantes

   • Sintaxis. Términos, fórmulas, enunciados

   • Variables libres y acotadas

3. Estructuras de primer orden

   Definir el concepto general de estructura de primer orden dando algunos ejemplos matemáticos. Establecer la relación entre los lenguajes y las estructuras de primer orden mediante las nociones de satisfacción y verdad. Considerar las relaciones que se pueden establecer entre las estructuras a través de la noción de verdad

   • Definición

   • Satisfacción y verdad (definición de Tarski)

   • Modelos

   • Relaciones entre estructuras. Subestructuras, imnersiones, equivalencia elemental, extensiones elementales

4. Validez y equivalencia lógica

   Se introducen las nociones de consecuencia y equivalencia lógica, mostrando su papel protagónico en la teoría de la inferencia lógica. Se estudian las propiedades básicas de los conectivos y los cuantificadores

   • Validez. Ejemplos. Consecuencia lógica

   • Equivalencia lógica. Definición y ejemplos

   • Leyes de la equivalencia lógica. Equivalencia entre fórmulas sin cuantificadores y álgebra de Boole. Tablas de verdad. Formas normales

   • Prenexación; cambio de variables acotadas

5. Teorema de finitud o compacidad

   Se presentan dos teoremas de vital importancia para la teoría: el teorema de finitud y el teorema de Herbrand, considerados por algunos lógicos como el teorema fundamental de la lógica de primer orden. Se muestra su importancia a través de distintos ejemplos. Se introducen las nociones de consistencia, completez y decidibilidad de un conjunto de enunciados

   • Introducción

   • Consistencia y completez

   • Teorema de finitud o de Compacidad

   • Aplicaciones. Análisis no estándar, aritmética no estándar

   • Teorema de Herbrand. Carácter no constructivo del teorema. ¿Es decidible el conjunto de fórmulas válidas en un lenguaje de primer orden? ¿Es decidible la consecuencia lógica?

BIBLIOGRAFIA:

• Delong, H., A Profile Of Mathematical Logic, Addison-Wesley, 1992

• Amor, J. A., Un Curso De Análisis Lógico, (notas en proceso)

BIBLIOGRAFIA COMPLEMENTARIA:

• Polya, G., How To Solve It, Princeton Univ. Press, 1945