Download Introducción

TALF 2
Introducción
Roberto Moriyón
Objetivo general del curso
• Estudiar los límites de los algoritmos:
– Hay más algoritmos de los que conocemos?
• Estudiar los límites algorítmicos del
razonamiento:
– Se puede algoritmizar el razonamiento?
– Se puede razonar todo?
– Hay axiomáticas razonables en las que todo sea
cierto o falso?
Objetivo I
• Qué cálculos (algoritmos) son posibles?
– Los que se pueden implementar con los
lenguajes de programación habituales.
– No son todas las funciones.
No es una afirmación que se pueda
demostrar, pues el concepto de algoritmo no
tiene una definición universal.
Objetivo II
• El razonamiento es un proceso
algorítmico?
– Se pueden definir algoritmos que emulan el
razonamiento.
– Razonamiento proposicional: Tablas de
verdad.
– Razonamiento con objetos: Reglas de
deducción.
Objetivo III
• Todas las afirmaciones ciertas se pueden
demostrar?
– Qué es una afirmación cierta? Tautologías
– Teorema de completitud de Gödel: Toda
tautología se puede demostrar que lo es.
Objetivo IV
• Hay afirmaciones que no son ciertas ni
falsas?
– Paradoja: Esta afirmación no es cierta.
Irreproducible en la Lógica Matemática.
Del mismo modo que los lenguajes de
programación no pueden calcular todas las
funciones, el lenguaje de la Lógica no puede
representar todas las afirmaciones.
– En Lógica se pueden hacer afirmaciones
sobre fórmulas lógicas. Ej: True(“1+1=2”)
Objetivo V
• Hay afirmaciones que no se pueden
demostrar, y su negación tampoco?
Afirmaciones que dependen de su
interpretación:
– “Todos los objetos son amarillos”
Las afirmaciones se pueden contextualizar:
– “Todos los números son primos”
(utilización de axiomas)
Objetivo V, bis
• Hay afirmaciones que no se pueden
demostrar, y su negación tampoco?
Paradoja: Esta afirmación no tiene
demostración.
Teorema de incompletitud de Gödel: La
paradoja anterior es reproducible en
algunos sistemas lógicos, incluyendo la
Aritmética.
Objetivo VI
• Hay un conjunto universal de axiomas
lógicos que representen un contexto
universal de razonamiento y de los que se
deduzcan todas las verdades?
Teorema de incompletitud de Gödel:
Cualquier sistema lógico que contenga a la
Aritmética tiene afirmaciones indemostrables
cuya negación también lo es.
“Esta afirmación no tiene demostración en el
sistema lógico X”
Material de trabajo
•
•
•
•
Material esencial:
Transparencias en la web
Algún material adicional fotocopiado
Material de apoyo:
En algunos temas: Libro de E. Alfonseca,
M. Alfonseca y R. Moriyón
Lógica: Libro D. Hofstadter: Gödel,
Escher, Bach
Organización de las clases
• Clases de teoría:
– Exposición de los temas por el profesor y de
trabajos de alumnos y resolución de ejercicios
seleccionados
• Clases de prácticas:
– Resolución de ejercicios prácticos
– Prácticas reducidas en el laboratorio
(complejidad algorítmica)
Evaluación continua
• Abarca la teoría y las clases de problemas
• Presentación (en clase o en papel) de
trabajos voluntarios y obligatorios
• Pueden contar hasta tres puntos de la
nota final
• Precisa un 90 por ciento de asistencia en
teoría (hasta 4 faltas) y problemas (hasta
una falta)
• Exige un 3 en el examen final y ningún 0
en preguntas del mismo
Mantenimiento de calificaciones
• Las notas de teoría y prácticas se guardan
para el curso siguiente.
• La nota de evaluación continua no se
guarda para septiembre.
Evaluación normal
• Examenes teóricos: parcial (hasta 30 %
de nota de teoría) y final
• Requisitos para aprobar: Mínimo 5 en nota
final de teoría y en prácticas
• Calificación final: 80% nota de teoría +
20% nota prácticas
• Ver el algoritmo detallado en la ficha de la
asignatura