PDF de programación - Lógica Computacional

Lógica Computacional

José Luis Fernández Vindel
Ángeles Manjarrés Riesco
Francisco Javier Díez Vegas

Dpto. Inteligencia Artificial

E.T.S.I. Informática

UNED
2007

Presentación

Estos apuntes se facilitan como material de estudio de la asignatura Lógica Computacional, impartida
por los autores en cuarto curso de Ingeniería Informática en la UNED.

Los alumnos de este curso encontrarán, en su grupo de tutorización en la Red, otros documentos

con ejemplos, actividades, ampliaciones o exámenes previos resueltos.

Los capítulos 1-2 y 5-6 han sido desarrollados por José Luis Fernández Vindel, el capítulo 3 por
Ángeles Manjarrés Riesco y el capítulo 4 por Francisco Javier Díez Vegas, todos ellos profesores del
Departamento de Inteligencia Artificial de la UNED.

Agradeceríamos sinceramente cualquier comunicación sobre erratas así como sugerencias sobre
los contenidos y su exposición. En particular nos preocupa cómo mantener un tono expositivo amiga-
ble sin renunciar al rigor: hasta qué punto facilitar demostraciones formales (y dónde situarlas), cómo
reubicar ejemplos y ejercicios para no entorpecer la exposición, etc.

Estas aportaciones se están canalizado a través del grupo de tutorización en la Red. La página
www.ia.uned.asignaturas/logica4 resume los detalles de planificación de este curso y facilita la
dirección electrónica del grupo.

Los autores
UNED, Madrid, 1 de octubre de 2007

Sobre esta edición 2007

Esta edición, de Octubre de 2007, difiere de la utilizada el pasado curso 06-07 en dos puntos:

1. algunas actualizaciones menores en los apartados sobre el uso de los apuntes (presentación,

localización de ejercicios, direcciones de la asignatura, etc.)

2. una variación sustancial en el capítulo 6: se ha sustituido íntegramente su contenido. El nue-
vo capítulo 6 corresponde al contenido del artículo sobre lógica temporal CTL que se facilitó
separadamente el pasado curso.

Si el estudiante dispone de la versión impresa previa de estos apuntes y del citado artículo, no es
necesario que imprima esta nueva versión. Cualquier duda puede consultarse en los Foros habilitados
en el grupo de tutorización telemática.

II

Índice general

Introducción

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Objetivos y contenidos
Motivación para los alumnos de Ingeniería Informática . . . . . . . . . . . . . . . . . . .
Bibliografía recomendada .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. .

.

.

.

.

Parte I. LÓGICA DE PREDICADOS

1 LÓGICA DE PROPOSICIONES

.
.

Resumen .
.
.
Objetivos
.
.
Metodología .
.
1.1 Sintaxis .

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

1.1.1 El lenguaje de la Lógica de Proposiciones . . . . . .
1.1.2
1.1.3 Derivación de conceptos sintácticos . . . . . . . .
1.1.4 Eliminación de paréntesis
. . . . . . . . . . . . .

Sobre la estructura inductiva del lenguaje . . . . . . .
. .
. .

1.2 Semántica . .

.
.

.
.

. .

. .

. .

Semántica de las conectivas

.
Introducción .

. . . . . . . . . . . . . .
. .
1.2.1
. . . . . . . . . . . . . . . . . .
1.2.2 Valores de verdad de fórmulas atómicas . . . . . . .
. . . . . . . . . . . . .
1.2.3
1.2.4 Valores de verdad de fórmulas complejas
. . . . . .
1.2.5 Tablas de verdad . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . .
1.2.6 Tautologías y contradicciones
. .

. . . . . . . . . . . .

. .

1.3 Conceptos semánticos básicos

. .

. .

. .

. .

. .

. .

. .

. .

. .

. .

. .

. .

. .

. .

. .
. .
. .

. .
. .
. .

. .
. .
. .

. .
. .
. .

. .
. .
. .

. .
. .
. .

. .
. .
. .

. .
. .
. .

. . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . .
.
. .
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. .

.
. .
. .
. .
.
. .
. .
. .
.
.
.
.
.
.
.
.
. .
. .
.
.
.
.
. .
.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
.
.
. . . . . . . . . . . . . .
. .
. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. .
. .
. .
. .
. .
. .
. .
. .

. .
. .
. .
. .
. .
. .
. .
. .

. .
. .
. .
. .
. .
. .
. .
. .

. .
. .
. .
. .
. .
. .
. .
. .

. .
. .
. .
. .
. .
. .
. .
. .

. .
. .
. .
. .
. .
. .
. .
. .

. .
. .
. .
. .

. .
. .
. .
. .

. .
. .
. .
. .

. .
. .
. .
. .

. .
. .
. .
. .

. .
. .
. .
. .

. .

. .

. .

. .
. .

. .

. .

. .

. .
. .

. .

. .

. .

. .

. .

. .

. .
. .

. .
. .

. .
. .

.

.

.

1.3.1
Satisfacibilidad .
1.3.2 Validez .
.
1.3.3 Consecuencia . .
.
1.3.4 Equivalencia .
.
.
1.4.1 Deducción natural
1.4.2 Resolución .
.
1.4.3 Tablas semánticas .

.

1.4 Sistemas deductivos .

Bibliografía complementaria .
Actividades y evaluación .
.

.

1
1
2
3

5

7
7
7
8
8
9
12
15
19
20
20
22
22
24
25
26
26
26
29
30
36
42
43
51
57
61
61

2 LÓGICA DE PREDICADOS DE PRIMER ORDEN

.
.

Resumen .
.
.
Objetivos
.
.
Metodología .
.
2.1 Sintaxis .

2.2 Semántica .

. .

. .

. .

. .

. .

. .

.
.
.
.

.
.
.
.

.

. .

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.

.
.
.
.
.
.
.

Satisfacción .

.
. .
Sustituciones .
.
.
. .
.
.
Introducción .
.
Interpretaciones .
. .
.
.

63
63
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.
63
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
64
. . . . . . . . . . . . . . . . . . . . .
.
64
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.
64
2.1.1 Lenguajes de primer orden . . . . . . . . . . . . . . . . . . . . . . . . . . .
67
Inducción y recursión . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.2
68
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.3
Subfórmulas
69
2.1.4 Eliminación de paréntesis
. . . . . . . . . . . . . . . . . . . . . . . . . . .
70
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.5 Variables libres .
72
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.6
77
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
77
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.1
79
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.2
80
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.3 Asignaciones .
80
2.2.4
.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.
81
2.2.5 Ejemplos de interpretación . . . . . . . . . . . . . . . . . . . . . . . . . . .
87
2.2.6 Conceptos semánticos básicos . . . . . . . . . . . . . . . . . . . . . . . . .
88
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
88
2.3.1 Consideraciones previas . . . . . . . . . . . . . . . . . . . . . . . . . . . .
90
2.3.2 Cuantificadores universales . . . . . . . . . . . . . . . . . . . . . . . . . . .
92
2.3.3 Cuantificadores existenciales . . . . . . . . . . . . . . . . . . . . . . . . . .
93
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
93
. . . . . . . . . . . . . . . . . . . . . . . . . . .
2.4.1
94
2.4.2 Notación uniforme .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.4.3 Reglas de expansión γ y δ . . . . . . . . . . . . . . . . . . . . . . . . . . .
96
.
2.4.4 Ejemplos .
97
. . . . . . . . . . . . . . . . .
.
. 100
.
. . . . . . . . . . . . .
. .
.
. . 100
Forma prenexa .
.
. . 103
Funciones de Skolem .
. . 104
.
Forma clausulada .
. 106
.
. . . . . . . . . . . . . . . . .
. 110
. . . . . . . . . . . . . . . . .
.
.
.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
.

2.5.1
2.5.2
2.5.3
2.5.4 Unificación .
2.5.5 Resolución .

. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .

Fórmulas proposicionales

. .
. .
. .

. .
. .
. .

. .
. .
. .

. .
. .
. .

. .
. .
. .

. .
. .
. .

. .
. .

. .
. .

. .
. .

. .
. .

. .
. .

. .
. .

. .
. .

. .
. .

. .
. .

.
.
.

.
.
.
.
.

. .
. .

. .
. .

. .
. .

.

.

.

. .

.

.
.
Bibliografía complementaria .
Actividades y evaluación .
.

.
.

.

2.5 Resolución .

.

.

.
.

.
.

.
.
.

2.3 Deducción Natural

.

.

2.4 Tablas semánticas .

.

.

.

.

.

Parte II. FORMALISMOS PARA PROGRAMACIÓN

113

.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

3 PROGRAMACIÓN LÓGICA
.
.
.

Resumen .
.
Objetivos
.
Metodología .
3.1 Cómo interpretar una fórmula lógica como un programa

115
.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
. . . . . . . . . . . . . . . . . . . . .
. 115
. . . . . . . . . . . . . . . 116
3.1.1 Declaración de programa versus algoritmo de solución . . . . . . . . . . . . 116
3.1.2 La resolución como algoritmo para la solución de problemas . . . . . . . . . 119
3.1.3
Programación lógica versus programación algorítmica . . . . . . . . . . . . 121
3.2 Formalismo lógico para la representación de problemas . . . . . . . . . . . . . . . . 123

. .

. .

. .

. .

.
.
.

IV

.

.

.
.

.
.

3.3 Resolución SLD .
.
3.4 El lenguaje PROLOG .

3.4.1 Definición de predicados recursivos. Reglas de computación y búsqueda . .
3.4.2 Usos procedimentales del PROLOG . . . . . . . . . .
3.4.3 Ventajas de la programación en PROLOG. Principales aplicaciones.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
. 128
. . 133
. . 140
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
.

Bibliografía complementaria .
Actividades y evaluación .
.

.

. .
. .

. .
.

. .

. .

. .

4 VERIFICACIÓN DE PROGRAMAS SECUENCIALES

.

.
.

.
.
.

.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

4.3 Semántica de los programas

.
.
.
Introducción .
.

Resumen .
.
Objetivos
.