Metologias de programacion

Metodolog´as de Programaci´ n I ı o
Programaci´ n L´ gica o o
5 de noviembre de 2009

Departamento de Inteligencia Artificial Sebasti´ n Camacho No. 5, Xalapa, Ver., a M´ xico 91000 e

´ Indice general

1.

Introducci´ n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 o 1.1. Breve historia de la programaci´ n l´ gica. . . . . . .. . . . . . . . . . . . . . . . . 1 o o 1.2. Una breve introducci´ n a Prolog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 o 1.2.1. Hechos y relaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2.2. Reglas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2.3. Definici´ n de reglas recursivas . . . . . . . .. . . . . . . . . . . . . . . . . 11 o 1.3. ¿C´ mo computa Prolog una soluci´ n? . . . . . . . . . . . . . . . . . . . . . . . . . 13 o o 1.4. Organizaci´ n del curso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 o

Parte I Formalismos 2. L´ gica de Primer Orden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . o 2.1. Introducci´ n .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . o 2.2. Sistemas formales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3. El lenguaje de la l´ gica de primer orden . . . . . . . . . . . . . . . . . . . . . . . . o 2.3.1. Sintaxis de la l´ gica de primer orden . . . . . . . . . . . . . . . . . . . . o 2.4. La sem´ntica de la l´ gica de primer orden . . . . . . . . . . . . . . . . . . . . . . a o 2.4.1. Teor´a de modelo de la l´ gica de primer orden . . . . . . . . . . . . ı o 2.5. Inferencia en la l´ gica de primer orden . . . . . . . . . . . . . . . . . . . . . . . . . o 2.6. Substituciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Cl´ usulas y ProgramasDefinitivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . a 3.1. Cl´ usulas definitivas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . a 3.2. Programas definitivos y Metas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3. El modelo m´nimo de Herbrand . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ı 3.3.1. Resultadosconcernientes a los modelos de Herbrand . . . . . . 3.3.2. Construcci´ n del modelo m´nimo de Herbrand . . . . . . . . . . . . o ı 21 21 23 23 25 26 27 29 31 33 33 35 37 39 41

3.

4.

Principio de Resoluci´ n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 o 4.1. Introducci´ n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 43 o 4.2. ¿Qu´ es un procedimiento de prueba? . . . . . . . . . . . . . . . . . . . . . . . . . . 44 e

V

VI

´ Indice general

4.3. 4.4. 4.5. 4.6. 5.

Pruebas y programas l´ gicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . o Substituci´ n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . o Unificaci´ n . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . o Resoluci´ n-SLD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . o 4.6.1. Propiedades de la resoluci´ n-SLD . . . . . . . . . . . . . . . . . . . . . . o

45 48 50 52 55 57 57 59 62 65 67

Negaci´ n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . o 5.1. Introducci´ n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . o 5.2. La compleci´ n de un programa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . o 5.3. Resoluci´ n SLDNF para programas definitivos . . . . . . . . . . . . . . . . . . o 5.4. Programas L´ gicos Generales . . . . . . . . . . . ....