Libro De Apuntes Y Problemas De Lógica Matemática De Alessandra Gallinari

LÓGICA MATEMÁTICA
APUNTES
Ingeniería en Informática ESCET Alessandra Gallinari 20052006

2

Prólogo
El contenido de esta publicación es un guión de la asignatura de Lógica Matemática para la titulación de Ingeniería en Informática de la Escuela Superior de Ciencias Experimentales y Tecnología (ESCET). Los principales objetivos de la asignatura son:

• Introducir herramientas yconceptos básicos de la Lógica Matemática y sus aplicaciones. • Ayudar al alumno a aprender a razonar y formalizar correctamente. • Junto con la asignatura Lógica Informática del próximo cuatrimestre, dar una formación global acerca de los procedimientos formales y algorítmicos de razonamiento automático y resolución formal de problemas.
Con estas notas de clase se intenta presentar de forma organizadael material que se expondrá en las clases teóricas. Por la naturaleza de estos apuntes, la exposición no es completa y es fundamental que el alumno consulte también los libros recomendados en la bibliografía relativa a la asignatura. Las principales referencias bibliográcas empleadas en estos apuntes son [A], [HLR], [MH] y las notas de clase de los profesores Ana Pradera y Luis Solá. La primeraparte de la publicación trata la lógica proposicional y la segunda la lógica de predicados. Las dos partes tienen la misma estructura y están divididas en tres capítulos que introducen la sintaxis, la semántica y la teoría de la demostración, respectivamente. Cada capítulo contiene un apartado de ejercicios.

Índice General
1 Introducción
1.1 1.2 El lenguaje de la lógica . . . . . . . Resumende la historia de la lógica 1.2.1 Lógica y losofía . . . . . . 1.2.2 Lógica y matemáticas . . . . 1.2.3 Lógica e informática . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7
7 10 10 10 11

I Lógica de proposiciones
2 Sintaxis de la lógica proposicional
2.1 2.2 Alfabeto dellenguaje formal de la lógica proposicional . . . Denición recursiva de las expresiones bien construidas: fórmulas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.1 El principio de inducción estructural para fórmulas proposicionales . . . . . . . . . . . . . . . . . . . . . . . Representación de las fórmulas bien construidas . . . . . . . 2.3.1 Fórmulas en forma usual y abreviada . . . .. . . . . 2.3.2 Principio de unicidad de estructura para fórmulas proposicionales . . . . . . . . . . . . . . . . . . . . . . . 2.3.3 Fórmulas en forma de árbol estructural . . . . . . . . 2.3.4 El principio de recursión estructural para fórmulas proposicionales . . . . . . . . . . . . . . . . . . . . . . . 2.3.5 Fórmulas en forma de Lukasiewicz . . . . . . . . . . Formalización del lenguajenatural . . . . . . . . . . . . . . Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

13
15
. 16 . 17 . 18 . 20 . 20 . 21 . 22 . . . . 25 26 26 27

2.3

2.4 2.5

4

3 Semántica de la lógica proposicional. Teoría interpretativa
3.1 3.2 3.3 3.4 3.5 3.6 4.1 4.2 4.3 4.4 Valoraciones de un lenguaje formal . . . . . . . . . . . . . . Evaluación semántica de fórmulas . . . .. . . . . . . . . . . 3.2.1 Tablas de verdad . . . . . . . . . . . . . . . . . . . . Modelos y contraejemplos de una fórmula bien construida. Tautologías, contingencias y contradicciones . . . . . . . . . Evaluación semántica de deducciones . . . . . . . . . . . . . Equivalencia de fórmulas . . . . . . . . . . . . . . . . . . . . Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . .Denición de sistema formal axiomático . . El sistema de Kleene . . . . . . . . . . . . . El sistema de deducción natural de Gentzen Métodos de refutación. Tableaux . . . . . . 4.4.1 Refutación . . . . . . . . . . . . . . . 4.4.2 Denición de los tableaux . . . . . . 4.4.3 Aplicaciones de los tableaux . . . . . Corrección, completitud y decidibilidad . . . Ejercicios . . . . . . . . . . . . . . ....