Lógica y Computabilidad

Esta página es sobre la materia del plan de estudios 1993.

Lógica y Computabilidad es una materia que estudia formalmente la lógica proposicional y la lógica de primer orden, e introduce la teoría de la computabilidad. La materia es dictada por el Departamento de Matemática en el primer cuatrimestre de cada año y por el Departamento de Computación en el verano y segundo cuatrimestre de cada año. Según el plan de la carrera, es una materia a ser cursada en tercer año. Es correlativa de Algoritmos y Estructuras de Datos II, y es requerida para cursar Paradigmas de Lenguajes de Programación y Teoría de Lenguajes.

Durante el año, la materia se cursa los miércoles y viernes a partir de las 17:00.

Programa

Abarca los temas de los capítulos 1 al 4 del libro "Computability, Complexity, and Languages" de Davis, Sigal y Weyuker

• Computabilidad: Lenguajes de programación. Macros. Recursión. Funciones primitivas recursivas. Predicados, operadores lógicos. Minimización. Codificación de Godel. Halting Problem, universalidad. Conjuntos recursivamente enumerables. Teoremas de la recursión, del punto fijo y de Rice.
• Lógica proposicional: Lenguaje. Semántica. Mecanismo Deductivo. Metateoremas para SP. Compacidad.
• Lógica de primer orden: Lenguaje. Semántica. Sistema axiomático. Metateoremas para SQ. Indecidibilidad.

Contenidos

Algunos teoremas vistos en la parte de lógica:

• Teorema de Completitud
• Teorema de Compacidad
• Resumen de definiciones y teoremas varios

Prácticas

Departamento de Computación

Computabilidad

• 2do Cuatrimestre 2017
  • Práctica 1 - Funciones primitivas recursivas y clases PRC

• Verano
  • Práctica 1 - Funciones computables
  • Práctica 2 - Funciones primitivas recursivas
  • Práctica 3 - Teoría de Computabilidad

Lógica

• 2do Cuatrimestre 2017
  • Práctica 5 - Sistemas Deductivos y Compacidad
• Verano
  • Práctica 4 - Logica Proposicional
  • Práctica 5 - Sistemas Deductivos y Compacidad
  • Práctica 6 - Logica de Primer Orden
  • Práctica 7 - Sistemas Deductivos, Completitud y Compacidad (1º Orden)

Departamento de Matemática

Lógica

• Práctica 1: Lógica Proposicional
• Práctica 2: Semántica del Cálculo Proposicional
• Práctica 3: Consecuencia Lógica y Árboles
• Práctica 4: Compacidad
• Práctica 5: Cálculo de Predicados
• Práctica 6: Árboles del Cálculo de Predicados

Computabilidad

• Práctica 7: Computabilidad y Programas
• Práctica 8: Funciones Primitivas Recursivas
• Práctica 9: Recursividad

Parciales

Departamento de Computación

Computabilidad

Año	Cuatrimestre	Fecha	Instancia	Links
2023	Primer Cuatrimestre	30/06/2023	Recuperatorio	enunciado + resolución (pdf)
2023	Primer Cuatrimestre	x/06/2023	Parcial	enunciado
2023	Verano	17/02/2023	Parcial	enunciado, resolucion
2022	Segundo Cuatrimestre	25/11/2022	Recuperatorio	enunciado (pdf)
2020	Segundo Cuatrimestre	23/10/2020	Parcial	enunciado (pdf)
2020	Primer Cuatrimestre	24/07/2020	Recuperatorio	enunciado (pdf)
2020	Primer Cuatrimestre	29/05/2020	Parcial	enunciado + resolución (pdf)
2020	Verano	19/02/2020	Parcial	enunciado, resolución
2019	Segundo cuatrimestre	11/10/2019	Parcial	solución por Manu Giménez (video)
2018	Segundo cuatrimestre	23/11/2018	Recuperatorio	enunciado
2018	Segundo cuatrimestre	05/10/2018	Parcial	enunciado, resolución
2018	Verano	15/03/2018	Recuperatorio	enunciado con resolución
2018	Verano	22/02/2018	Parcial	enunciado + resolución (pdf)
2017	Segundo cuatrimestre	29/09/2017	Parcial	enunciado
2017	Verano	18/03/2017	Recuperatorio	enunciado
2017	Verano	21/02/2017	Parcial	enunciado, resolución (pdf), resolución2 (pdf)
2016	Verano	13/02/2016	Parcial	enunciado, enunciado + resolución (pdf)
2015	Segundo cuatrimestre		Parcial	enunciado (pdf)
2015	Verano		Recuperatorio	enunciado (jpg)
2015	Verano	14/02/2015	Parcial	enunciado (jpg), resolución (jpg): ej 1, ej 2, solución por Manu Giménez (video)
2014	Segundo cuatrimestre	03/12/2014	Recuperatorio	enunciado (jpg), resolución (jpg): ej 2, ej 3, ej 4
2014	Segundo cuatrimestre	26/09/2014	Parcial	enunciado (pdf)
2014	Verano	15/02/2014	Parcial	enunciado (jpg)
2012	Segundo cuatrimestre		Recuperatorio	enunciado (jpg)
2011	Segundo cuatrimestre	07/10/2011	Parcial	enunciado + resolución (pdf)

Lógica

Año	Cuatrimestre	Fecha	Instancia	Links
2023	Verano	13/03/2023	Parcial	enunciado, resolucion
2022	Segundo Cuatrimestre	18/11/2022	Parcial	enunciado + resolución (pdf)
2021	Verano	18/03/2021	Parcial	enunciado + resolución (pdf)
2020	Segundo Cuatrimestre	04/10/2020	Parcial	enunciado (pdf)
2020	Primer Cuatrimestre	17/07/2020	Parcial	enunciado, enunciado + resolución (pdf)
2020	Primer Cuatrimestre	31/07/2020	Recuperatorio	enunciado, enunciado + resolución (pdf)
2019	Verano	29/03/2019	Recuperatorio	enunciado (pdf)
2018	Segundo Cuatrimestre	16/11/2018	Parcial	enunciado (pdf), resolución (pdf)
2018	Verano	15/03/2018	Parcial	enunciado (pdf), resolución (pdf)
2017	Segundo Cuatrimestre	17/11/2017	Parcial	enunciado, resolución
2017	Verano	25/03/2017	Recuperatorio	enunciado
2017	Verano	16/03/2017	Parcial	enunciado, resolución 1, resolución 2
2016	Segundo cuatrimestre		Parcial	enunciado (jpg), resolución (jpg/pdf): ej 1, ej 2, ej 3, ej 4
2016	Verano	03/03/2016	Parcial	enunciado, enunciado + resolución (pdf)
2015	Segundo cuatrimestre		Parcial	enunciado (pdf), resolución (pdf): ej 1, ej 2
2015	Verano		Recuperatorio	enunciado (jpg)
2015	Verano	07/02/2015	Parcial	enunciado (jpg), resolución (jpg): ej 2, ej 3
2014	Segundo cuatrimestre	14/11/2014	Parcial	enunciado (pdf), resolución (jpg): ej 1, ej 2, ej4

Departamento de Matemática

Lógica

Año	Cuatrimestre	Fecha	Instancia	Links
2024	Primer cuatrimestre	12/07/2024	Recuperatorio	Enunciado (jpg)
2024	Primer cuatrimestre	10/05/2024	Parcial	Enunciado (jpg)
2023	Primer cuatrimestre	07/07/2023	Recuperatorio	Enunciado + Resolución (pdf)
2018	Primer cuatrimestre		recuperatorio	Enunciado+resolucion
2018	Primer cuatrimestre		Parcial	enunciado + resolución (pdf)
2016	Primer cuatrimestre		Parcial	enunciado + resolución (pdf)
2015	Primer cuatrimestre	15/05/2015	Parcial	enunciado (jpg)

Computabilidad

Año	Cuatrimestre	Fecha	Instancia	Links
2024	Primer cuatrimestre	05/07/2024	Parcial	Enunciado (jpg)
2018	Primer cuatrimestre	20/07/2018	Recuperatorio	enunciado (pdf), enunciado + resolución (pdf), Resolucion
2018	Primer cuatrimestre	06/06/2018	Parcial	enunciado + resolución (pdf)
2015	Primer cuatrimestre	03/07/2015	Parcial	enunciado (pdf)

Finales

Departamento de Computación

En general toma Santiago Figueira. Santiago toma todos los teoremas que aparecen en las diapositivas. No se confíen si algún teorema no aparece en los finales a continuación, se toman todos.

• Preguntas de finales resueltas (Source): Tomadas por Santiago Figueira.
• Final del 17/03/07: Tomado por Santiago Figueira (Escrito)
• Final del 23/02/10: Tomado por Santiago Figueira (Oral)
• Final del 16/03/10: Tomado por Santiago Figueira (Escrito)
• Final del 28/12/10: Tomado por Santiago Figueira (Escrito)
• Final del 26/12/12: Tomado por Santiago Figueira (Escrito)
• Final del 05/08/13: Tomado por Santiago Figueira (Escrito)
• Final del 20/02/14: Tomado por Santiago Figueira (Escrito)
• Final del 07/03/14: Tomado por Santiago Figueira (Escrito)
• Final del 11/12/14: Tomado por Santiago Figueira (Oral)
• Final del 22/12/14: Tomado por Santiago Figueira (Escrito)
• Final del 13/04/15: Tomado por Santiago Figueira (Escrito)
• Final del 21/12/15: Tomado por Santiago Figueira (Escrito)
• Final del 09/05/16: Tomado por Santiago Figueira (Escrito)
• Final del 10/03/17: Tomado por Santiago Figueira (Escrito)
• Final del 22/06/17: Tomado por Santiago Figueira (Escrito)
• Final del 21/12/17: Tomado por Santiago Figueira (Escrito)
• Final del 22/02/18: Tomado por Santiago Figueira (Escrito)
• Final del 17/05/18: Tomado por Santiago Figueira (Escrito)
• Final del 07/03/19: Tomado por Santiago Figueira (Escrito)
• Final del 24/04/19: Tomado por Santiago Figueira (Escrito)
• Final del 12/05/19: Tomado por Santiago Figueira (Escrito)
• Final del 06/12/19: Tomado por Santiago Figueira (Escrito)
• Final del 20/02/20: Tomado por Santiago Figueira (Escrito)
• Final del 05/03/20: Tomado por Santiago Figueira (Escrito)
• Final del 20/12/20: Tomado por Santiago Figueira (Virtual) + resolución
• Final del 07/12/22: Tomado por (Oral)
• Final del 22/12/22: Tomado por Ariel (Oral)
• Final del 22/02/23: Tomado por Sergio Abriola (Escrito)
• Final del 08/03/23: Tomado por Sergio Abriola (Escrito)
• Final del 11/04/23: Tomado por Sergio Abriola (Escrito)

Departamento de Matemática

• Final del 16/07/13: Tomado por Alejandro Petrovich (Escrito)
• Final del 10/09/14: Tomado por Alejandro Petrovich (Escrito)
• Final del 21/10/14: Tomado por Alejandro Petrovich (Escrito) (resuelto)
• Final del 23/10/18: Tomado por Alejandro Petrovich (Escrito)
• Final del 13/11/18: Tomado por Alejandro Petrovich (Escrito) (resuelto 50%)
• Final del 22/10/19: Tomado por Juan José Guccione (Escrito) (resuelto 25%)
• Final del 11/08/21: Tomado por Ariel Bendersky (Oral)
• Final del 20/10/21: Tomado por Alejandro Petrovich (Escrito)

Recursos

Prácticas

• Prácticas resueltas de LyC Verano 2021.

Apuntes

• Apunte de Computabilidad(Repositorio de fuentes), hecho por Leopoldo Taravilse, durante la cursada del segundo cuatrimestre de 2012.
• Apunte de clases teóricas, hecho por Lucas Di Salvo.

Videos

• Video explicando resolución de un parcial de Computabilidad (por Manu Gimenez)

• Playlist con más videos explicando cosas (por Manu Gimenez)

Bibliografía recomendada

• Davis, Martin D.; Sigal, Ron y Weyuker, Elaine J., Computability, complexity and languages: fundamentals of theoretical computer science, San Diego: Academic Press, 1994 (Circulante 681 334 Davis en la Biblioteca Central)
• Mendelson, Elliot, Introduction to mathematical logic, Princeton, N.J.: Van Nostrand, c1964 (Circulante 510 600 Mendelson en la Biblioteca Central)

Enlaces externos

• Pagina Oficial de la Materia (DM)