5678 1234

Facultad de Matemática, Astronomía, Física y Computación - FaMaF - UNC

Wiki

PROGRAMA DE ASIGNATURA

ASIGNATURA: Introducción a la Lógica y la Computación

AÑO: 2022

CARACTER: Obligatoria, optativa

UBICACIÓN EN LA CARRERA: 2° año 2° cuatrimestre

CARRERA: Profesorado en Matemática, Licenciatura en Ciencias de la Computación

REGIMEN: Cuatrimestral

CARGA HORARIA: 120 horas (Lic. en Ciencias de la Computación) / 165 horas (Prof. en Matemática)

FUNDAMENTACIÓN Y OBJETIVOS

Fundamentación:

Se han definido para esta materia tres grandes ejes de contenidos teóricos que contribuirán a lograr los objetivos propuestos.

El primer eje trata de estructuras ordenadas, que constituyen la base para la definición de modelos matemáticos, tanto de los lenguajes de programación como de las lógicas que se utilizan para razonar sobre los programas.

El segundo eje aborda la lógica proposicional a través de una presentación diferente a la ofrecida en materias anteriores, que no pone énfasis en el cálculo, sino en el concepto de demostración. Este abordaje establece las bases para conectar la lógica con otras áreas fundamentales de las Ciencias de la Computación, como el cálculo lambda (a través del isomorfismo de Curry-Howard), y la inteligencia artificial.

Por último, el tercer eje trata sobre mecanismos de computación y formas de definición de lenguajes formales, con aplicaciones directas en el desarrollo de los lenguajes de programación, por ejemplo mediante las técnicas de parsing.

OBJETIVOS

En esta materia se abordan contenidos que constituyen algunos de los pilares teóricos de las Ciencias de la Computación. El objetivo general es proveer un marco teórico que tenga aplicaciones tanto en la práctica profesional como en la investigación científica.

Entre los objetivos específicos se espera que las y los estudiantes adquieran destrezas relativas a:

1. La aplicación de los diversos algoritmos que involucran estructuras matemáticas surgidas de las teorías del orden, de los autómatas y lenguajes formales y de la lógica.
2. Manejo de los conceptos de inducción y recursión estructural.
3. Desarrollo de demostraciones matemáticas y formales involucrando los conceptos de la materia.

CONTENIDO

Relaciones y orden

Noción de Relación y propiedades. Relaciones de Equivalencia y Particiones. Órdenes Parciales. Conjuntos Parcialmente Ordenados (“posets”). Máximos, mínimos, elementos maximales y minimales, ínfimos y supremos. Diagramas de Hasse. Isomorfismo de posets y sus propiedades.

Reticulados y Álgebras de Boole

Posets reticulados. Versión algebraica: retículos. Equivalencia de dichas definiciones. Isomorfismo de retículos. Equivalencia con isomorfismo de posets. Pruebas de desigualdades en reticulados. Reticulados acotados y complementos. Reticulados distributivos. Álgebras de Boole y sus propiedades. Teoremas de Representación. Representación de las álgebras de Boole finitas como álgebras de conjuntos. Teorema de Birkhoff de Representación de reticulados distributivos finitos. Caracterizaciones de la distributividad en reticulados.

Cálculo Proposicional: Sintaxis y Semántica

La sintaxis de las proposiciones (PROP). Definición inductiva de PROP como un conjunto de cadenas. La inducción estructural; recursión sobre PROP. Noción de verdad: Asignaciones y valuaciones. Tautologías y la relación de consecuencia. Lema de coincidencia y tablas de verdad.

Cálculo Proposicional: Deducción Natural

Noción de demostración: el sistema de deducción natural de Gentzen-Prawitz. Caso intuicionista y clásico: la reducción al absurdo. Inducción estructural en derivaciones. Conjuntos consistentes, maximales. Teoremas de Corrección y Completitud del cálculo proposicional. Álgebra de Lindenbaum.

Autómatas Finitos y Lenguajes Regulares

Alfabetos, Cadenas y Lenguajes. Codificación de problemas con lenguajes. Autómatas finitos deterministas (DFA). Trazas. Lenguajes regulares como los aceptados por un DFA. Autómatas no deterministas (NFA) y con movimientos silenciosos (ε-NFA). Determinización de ε-NFAs. Expresiones regulares y propiedades de clausura de los lenguajes regulares. Teorema de Kleene. Lema de bombeo (“Pumping”) como método para ver no regularidad.

Gramáticas

Gramáticas Libre de Contextos (CFG). Derivación. Lenguajes Libres de Contexto. Gramáticas Regulares; equivalencia con lenguajes regulares. Ejemplo de autómata a pila. Lenguajes contextuales (CSL). Introducción a la computabilidad y la Jerarquía de Chomsky.

BIBLIOGRAFÍA

BIBLIOGRAFÍA BÁSICA

Apunte de Cátedra: “Lenguajes y Autómatas”, Alejandro Tiraboschi y colaboradores.

Apunte de Cátedra: “Lógica Proposicional”, Pedro Sánchez Terraf.

Apunte de Cátedra: “Reticulados y Álgebras de Boole”, Alejandro Tiraboschi y Héctor Gramaglia.

BIBLIOGRAFÍA COMPLEMENTARIA

B. Davey, H. Priestley, "Introduction to Lattices and Order", Cambridge University Press.

Jeffrey Ullman; John Hopcroft; Rajeev Motwani. ''Introducción a la teoría de autómatas, lenguajes y computación''. Prentice Hall, 2002.

D. Van Dalen, "Logic and Structure". Springer Verlag, Berlin.

EVALUACIÓN

FORMAS DE EVALUACIÓN

Se tomarán 3 (tres) exámenes parciales. Las evaluaciones parciales serán sobre contenidos teórico-prácticos.

Si la cátedra lo considera necesario se podrán incorporar otras instancias de evaluación formativa.

REGULARIDAD

Aprobar al menos dos evaluaciones parciales de las tres evaluaciones parciales.