Lógica y Computabilidad

Plantilla:Revisar guías 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
2018	Primer cuatrimestre	20/07/2018	Recuperatorio	enunciado (pdf), enunciado + resolución (pdf)
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)
2010	Segundo cuatrimestre		Recuperatorio	enunciado (pdf)
2010	Segundo cuatrimestre		Parcial	enunciado (pdf)
2009	Verano		Recuperatorio	enunciado (pdf)
2009	Verano		Parcial	enunciado (pdf)
2008	Primer cuatrimestre		Recuperatorio	enunciado (pdf)
2008	Primer cuatrimestre		Parcial	enunciado (pdf)
2008	Verano		Recuperatorio	enunciado (pdf)
2008	Verano		Parcial	enunciado (pdf)
2007	Verano		Recuperatorio	enunciado (pdf)
2007	Verano		Parcial	enunciado (pdf)

Lógica

Año	Cuatrimestre	Fecha	Instancia	Links
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
2010	Segundo cuatrimestre		Recuperatorio (2)	enunciado (pdf)
2010	Segundo cuatrimestre		Recuperatorio	enunciado (pdf)
2010	Segundo cuatrimestre		Parcial	enunciado (pdf)
2009	Verano		Recuperatorio	enunciado (pdf)
2009	Verano		Parcial	enunciado (pdf)
2008	Primer cuatrimestre		Recuperatorio	enunciado (pdf)
2008	Primer cuatrimestre		Parcial	enunciado (pdf)
2008	Verano		Recuperatorio	enunciado (pdf)
2008	Verano		Parcial	enunciado (pdf)
2007	Verano		Recuperatorio	enunciado (pdf)
2007	Verano		Parcial	enunciado (pdf)
2006	Segundo cuatrimestre	13/10/2006	Parcial	enunciado

Departamento de Matemática

Lógica

Año	Cuatrimestre	Fecha	Instancia	Links
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)
2008	Segundo cuatrimestre		Recuperatorio (2)	enunciado (pdf)
2008	Segundo cuatrimestre		Recuperatorio	enunciado (pdf)
2008	Segundo cuatrimestre		Parcial	enunciado (pdf)
2007	Segundo cuatrimestre		Recuperatorio (2)	enunciado (pdf)
2007	Segundo cuatrimestre		Recuperatorio	enunciado (pdf)
2007	Segundo cuatrimestre		Parcial	enunciado (pdf)

Computabilidad

Año	Cuatrimestre	Fecha	Instancia	Links
2018	Primer cuatrimestre	06/06/2018	Parcial	enunciado + resolución (pdf)
2015	Primer cuatrimestre	03/07/2015	Parcial	enunciado (pdf)
2010	Primer cuatrimestre		Parcial	enunciado (pdf), enunciado + resolución (pdf)
2008	Segundo cuatrimestre		Recuperatorio (2)	enunciado (pdf)
2008	Segundo cuatrimestre		Recuperatorio	enunciado (pdf)
2008	Segundo cuatrimestre		Parcial	enunciado (pdf)
2007	Segundo cuatrimestre		Recuperatorio (2)	enunciado (pdf)
2007	Segundo cuatrimestre		Recuperatorio	enunciado (pdf)
2007	Segundo cuatrimestre		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)

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)

Recursos

Clases

• Clase práctica número 2 (computabilidad): Ejemplo de demostraciones de funciones primitivas recursivas.
• Clase práctica número 3 (computabilidad): Esquemas recursivos p.r.
• Clase práctica número 5 (computabilidad): Apunte de clases de funciones y ejercicios de Halt.
• Clase práctica número 6 (computabilidad): Teorema de la recursión, teorema del parámetro, etc.
• Clase práctica número 7 (computabilidad): Conjuntos r.e., Rice.
• Clase práctica número 1 (lógica): Lógica proposicional.
• Clase práctica número 2 (lógica): Conjuntos maximales consistentes.
• Clase práctica número 3 (lógica): Conjuntos maximales consistentes, teorema de la deducción, árboles LP, compacidad.

Prácticas

• Prácticas resueltas de LyC del 2005.

Apuntes

• Apunte de Computabilidad(Repositorio de fuentes), hecho por Leopoldo Taravilse, durante la cursada del segundo cuatrimestre de 2012.

Videos

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

Curiosidades

• Teorema de Cantor

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)