Logica y programación

Programaci´n L´gica
o o

Programaci´n L´gica
o
o
I

Lenguajes Formales: Conceptos Fundamentales

1 Gram´ticas y Lenguajes
a
1.1 Gram´ticas . . . . . . . . . . . . . . . . . . . . .
a
1.2 Lenguaje generado por una gram´tica . . . . . . .
a

1
3
3
7

2 An´lisis Sint´ctico
a
a
11
2.1 T´cnicas descendentes . . . . . . . . . . . . . . . 15
e
2.2 T´cnicas ascendentes . . .. . . . . . . . . . . . . 17
e
2.3 Eliminaci´n de ambig¨ edades . . . . . . . . . . . 20
o
u

II

L´gica: Conceptos Fundamentales
o

3 C´lculo de Proposiciones
a
3.1 Evaluaci´n de proposiciones: tablas de verdad . .
o
3.1.1 Evaluaci´n de proposiciones constantes . .
o
3.1.2 Evaluaci´n de proposiciones en estados . .
o
3.1.3 Evaluaci´n de proposiciones sin par´ntesis
o
e
3.1.4Tautolog´
ıas . . . . . . . . . . . . . . . . .
3.2 Reglas de reescritura . . . . . . . . . . . . . . . .
3.2.1 Leyes de equivalencia . . . . . . . . . . . .
3.2.2 Reglas de sustituci´n, resoluci´n y
o
o
transitividad . . . . . . . . . . . . . . . . .
3.2.3 Axiomas y teoremas . . . . . . . . . . . .
i

23
25
27
28
29
30
33
35
36
37
41

ii

Programaci´n L´gica
o o

4C´lculo de Predicados
a
4.1 Extensi´n del concepto de estado . . . . . .
o
4.2 Los operadores cand y cor . . . . . . . . . .
4.3 Cuantificadores . . . . . . . . . . . . . . . .
4.3.1 El cuantificador universal . . . . . .
4.3.2 El cuantificador existencial . . . . . .
4.3.3 El cuantificador num´rico . . . . . .
e
4.3.4 Equivalencias entre cuantificadores .
4.3.5 Cuantificaci´n sobre rangosinfinitos
o
4.4 Identificadores libres y ligados . . . . . . . .
4.5 Sustituci´n textual . . . . . . . . . . . . . .
o
4.6 Sustituci´n simult´nea . . . . . . . . . . . .
o
a

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

43
44
46
48
48
49
50
51
53
54
56
59

5 Prolog y C´lculo de Predicados
a
5.1 Regla de resoluci´n . . . .. . .
o
5.2 El proceso de resoluci´n . . . .
o
5.2.1 Un ejemplo simple . . .
5.2.2 Un ejemplo completo . .

.
.
.
.

.
.
.
.

.
.
.
.

61
61
63
64
68

III

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

El Int´rprete L´gico
e
o

79

6 Conceptos Fundamentales
81
6.1 Objetos en programaci´n l´gica . . . . . . .. . . 81
o o
6.2 Programas l´gicos, cl´usulas y preguntas . . . . . 83
o
a
6.3 Concepto de unificaci´n: sustituciones e instancias 85
o
6.4 Un int´rprete l´gico simple . . . . . . . . . . . . . 89
e
o
6.5 El concepto de retroceso . . . . . . . . . . . . . . 94
6.6 Significado de un programa l´gico . . . . . . . . . 100
o
6.6.1 El orden de tratamiento de los objetivos . 105
6.6.2 Elorden de aplicaci´n de las cl´usulas . . 107
o
a
7 Control en Prolog: el Corte
7.1 Sem´ntica operacional . . . . . . . . . . . . . .
a
7.2 Tipos de cortes . . . . . . . . . . . . . . . . . .
7.2.1 El corte verde . . . . . . . . . . . . . . .

111
. 111
. 122
. 123

iii

Programaci´n L´gica
o o

7.3

7.2.2 El corte rojo . . . . . . . . . . . . . . . . . 123
Las variablesan´nimas . . . . . . . . . . . . . . . 124
o

8 La Negaci´n
o
127
8.1 El predicado fail . . . . . . . . . . . . . . . . . . 127
8.2 La negaci´n por fallo . . . . . . . . . . . . . . . . 130
o
8.3 Anomal´ de la negaci´n por fallo . . . . . . . . 132
ıas
o
9 Control de la Evaluaci´n
o
139
9.1 La primitiva freeze . . . . . . . . . . . . . . . . 139
9.2 La declaraci´n wait . . . . . . . . . .. . . . . . . 142
o
IV

Programaci´n L´gica
o
o

10 Las
10.1
10.2
10.3

145

Listas
Definici´n del tipo lista . . . . . . . . .
o
Operaciones fundamentales sobre listas
Operaciones sobre conjuntos . . . . . .
10.3.1 El tipo conjunto . . . . . . . . .
10.3.2 La uni´n . . . . . . . . . . . . .
o
10.3.3 La inclusi´n . . . . . . . . . . .
o
10.3.4 La intersecci´n . . . ....