Lógica para Informáticos

Descripción

Este libro proporciona al lector fundamentos de lógica, para las ciencias de la computación, sólo se asumen conocimientos previos muy básicos de matemáticas, conocimientos que además se revisan brevemente.

El libro inicia con un capítulo de preliminares matemáticos donde se repasan: Conjuntos, Relaciones y funciones, Combinatoria, Demostración de propiedades.

Continúa con la definición de la lógica proposicional y de las técnicas de deducción en esta lógica y sus aplicaciones. En la segunda parte del libro define la lógica de primer orden, explica los métodos de deducción e incluye algunas aplicaciones. Dedica un capítulo a la programación lógica.

Ventajas Competitivas

• Escrito de forma amena y cercana, simplificando al máximo la carga rotacional, con numerosos ejemplos que ilustran los conceptos explicados.
• Más de 200 ejercicios acompañados de su correspondiente solución, desarrollada en todo detalle.

Conozca

• La lógica como una herramienta formal de apoyo en diversas áreas de las ciencias de la computación.
• La lógica de primer orden, sus métodos de deducción y aplicaciones.
• Las estructuras de datos más adecuadas a la resolución de problemas de la lógica computacional.
• Cómo analizar, diseñar y construir sistemas de lógica computacional utilizando técnicas propias de los sistemas inteligentes.
• Cómo formalizar y representar el conocimiento humano en una forma computable para la resolución de problemas mediante un sistema informático.
• Cómo solucionar problemas lógicos que puedan plantearse en la ingeniería.
• Las propiedades fundamentales de los cálculos lógicos, tales como adecuación y completitud.

Aprenda

• Las técnicas de deducción de la lógica proposicional y sus aplicaciones.
• Cómo construir aplicaciones de lógica computacional eligiendo el paradigma y lenguaje de programación más adecuado.
• Cómo construir y desarrollar argumentos lógicos, identificando claramente las hipótesis y las conclusiones.
• Cómo presentar argumentos y conclusiones con claridad y exactitud.
• Cómo usar la lógica para especificar, verificar y razonar sobre programas informáticos.
• Cómo identificar problemas que pueden expresarse como problemas lógicos, traducirlo a la forma apropiada.

Índice

Prologo ix
1. Preliminares 1
1.1. Conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1. Inclusión e igualdad de conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.2. Operaciones sobre conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.3. Propiedades de las operaciones sobre conjuntos . . . . . . . . . . . . . . . . . . . 2
1.1.4. Partes de un conjunto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.5. Cadenas sobre un conjunto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2. Relaciones y funciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1. Relación de equivalencia y conjunto cociente . . . . . . . . . . . . . . . . . . . . 4
1.2.2. Relaciones de orden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3. Combinatoria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4. Demostración de propiedades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4.1. Inducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4.2. Contrarrecíproco . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4.3. Reducción al absurdo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2. Definición de la lógica proposicional ´ 7
2.1. ¿Qué es una lógica? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2. Lógica proposicional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3. Explicaciones sobre la definición de la lógica proposicional . . . . . . . . . . . . . . . . . 8
2.4. Satis factibilidad, tautología, consecuencia y equivalencia . . . . . . . . . . . . . . . . . . 9
3. Deducción en la lógica proposicional ´ 19
3.1. Formas normales y clausulas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2. Nociones informales de decidibilidad y complejidad . . . . . . . . . . . . . . . . . . . . . 21
3.2.1. Lo importante es el coste como función del tamaño de la entrada . . . . . . . . . . 22
3.3. Resolución. Corrección y completitud . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.4. Resolver problemas prácticos con la lógica proposicional . . . . . . . . . . . . . . . . . . 27
3.5. El procedimiento DPLL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4. Definición de la lógica de primer orden ´ 35
4.1. Lógica de primer orden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.1.1. Sintaxis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.1.2. Interpretación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.1.3. Satisfacción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.1.4. Formulas cerradas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.2. Explicaciones sobre la definición de la lógica de primer orden . . . . . . . . . . . . . . . 37
4.3. Lógica de primer orden con igualdad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.4. Formalización del lenguaje natural . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
5. Deducción en la lógica de primer orden ´ 51
5.1. Formas normales y clausulas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
5.2. Transformación a forma clausal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
5.3. Unificación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
5.4. Resolución y factorización . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
6. Fundamentos de la programación lógica ´ 61
6.1. Calculo de respuestas mediante resolución . . . . . . . . . . . . . . . . . . . . . . . . . . 61
6.1.1. Bases de datos deductivas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
6.1.2. Programas lógicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
6.1.3. Completitud . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
6.2. La ejecución de programas Prolog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
6.2.1. La resolución SLD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
6.2.2. Ejemplos de Prolog. Unificación, listas . . . . . . . . . . . . . . . . . . . . . . . 66
6.2.3. La programación recursiva y la inducción . . . . . . . . . . . . . . . . . . . . . . 68
6.2.4. Los aspectos extra-lógicos de Prolog . . . . . . . . . . . . . . . . . . . . . . . . 69
7. Ejercicios resueltos 79
7.1. Ejercicios de definición de la lógica proposicional . . . . . . . . . . . . . . . . . . . . . . 79
7.2. Ejercicios de deducción en la lógica proposicional . . . . . . . . . . . . . . . . . . . . . . 114
7.2.1. Formas normales y clausulas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
7.2.2. Nociones informales de decidibilidad y complejidad . . . . . . . . . . . . . . . . 123
7.2.3. Resolución. Corrección y completitud . . . . . . . . . . . . . . . . . . . . . . . . 124
7.2.4. Resolver problemas prácticos con la lógica proposicional . . . . . . . . . . . . . . 132
7.2.5. El procedimiento DPLL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
7.3. Ejercicios de definición de la lógica de primer orden . . . . . . . . . . . . . . . . . . . . . 153
7.3.1. Lógica de primer orden con igualdad . . . . . . . . . . . . . . . . . . . . . . . . 169
7.3.2. Formalización del lenguaje natural . . . . . . . . . . . . . . . . . . . . . . . . . . 176
7.4. Ejercicios de deducción en la lógica de primer orden . . . . . . . . . . . . . . . . . . . . 177
7.5. Ejercicios de fundamentos de la programación lógica . . . . . . . . . . . . . . . . . . . . 194