1 Introducción

1.1 Objetivos del seminario

• Lógica como:
  • sistema de especificación y
  • lenguaje de programación
• Principios:
  • Programas = Teorías
  • Ejecución = Búsqueda de pruebas
  • Programación = Modelización

• Prolog = Programming in logic

• Relaciones con otros campos:
  • Inteligencia artificial
  • Sistemas basados en el conocimiento
  • Procesamiento del lenguaje natural

1.2 Declarativo vs. imperativo

• Paradigmas
  • Imperativo: Se describe cómo resolver el problema
  • Declarativo: Se describe qué es el problema
• Programas
  • Imperativo: Una sucesión de instrucciones
  • Declarativo: Un conjunto de sentencias
• Lenguajes
  • Imperativo: Pascal, C, Fortran, Java, Python
  • Declarativo: Prolog, Lisp puro, ML, Haskell
• Ventajas
  • Imperativo: Programas rápidos y especializados
  • Declarativo: Programas generales, cortos y legibles

1.3 Historia de la programación lógica

• 1960: Demostración automática de teoremas
• 1965: Resolución y unificación (Robinson)
• 1969: QA3, obtención de respuesta (Green)
• 1972: Implementación de Prolog (Colmerauer)
• 1974: Programación lógica (Kowalski)
• 1977: Prolog de Edimburgo (Warren)
• 1981: Proyecto japonés de Quinta Generación
• 1986: Programación lógica con restricciones
• 1995: Estándar ISO de Prolog

2 Deducción Prolog

2.1 Deducción Prolog en lógica proposicional

• Base de conocimiento y objetivo:
  • Base de conocimiento:
    • Regla 1: Si un animal es ungulado y tiene rayas negras, entonces es una cebra.
    • Regla 2: Si un animal rumia y es mamífero, entonces es ungulado.
    • Regla 3: Si un animal es mamífero y tiene pezuñas, entonces es ungulado.
    • Hecho 1: El animal es mamífero.
    • Hecho 2: El animal tiene pezuñas.
    • Hecho 3: El animal tiene rayas negras.
  • Objetivo: Demostrar a partir de la base de conocimientos que el animal es una cebra.
• Programa:

es_cebra :- es_ungulado, tiene_rayas_negras.
es_ungulado :- rumia, es_mamífero.
es_ungulado :- es_mamífero, tiene_pezuñas.
es_mamífero.
tiene_pezuñas.
tiene_rayas_negras.

• Sesión:

/home/SLC2015/tema-1> prolog
Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 6.6.4)
Copyright (c) 1990-2013 University of Amsterdam, VU Amsterdam
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to redistribute it under certain conditions.
Please visit http://www.swi-prolog.org for details.

For help, use ?- help(Topic). or ?- apropos(Word).

?- [animales].
% animales compiled 0.00 sec, 7 clauses
true.

?- es_cebra.
true.

?- trace.
true.

[trace]  ?- es_cebra.
   Call: (6) es_cebra ? 
   Call: (7) es_ungulado ? 
   Call: (8) rumia ? 
   Fail: (8) rumia ? 
   Redo: (7) es_ungulado ? 
   Call: (8) es_mamifero ? 
   Exit: (8) es_mamifero ? 
   Call: (8) tiene_pezuñas ? 
   Exit: (8) tiene_pezuñas ? 
   Exit: (7) es_ungulado ? 
   Call: (7) tiene_rayas_negras ? 
   Exit: (7) tiene_rayas_negras ? 
   Exit: (6) es_cebra ? 
true.

[trace]  ?- nodebug.
true.

• Árbol de deducción:

• Demostración por resolución SLD:

2.2 Deducción Prolog en lógica relacional

• Base de conocimiento:
  • Hechos 1-4: 6 y 12 son divisibles por 2 y por 3.
  • Hecho 5: 4 es divisible por 2.
  • Regla 1: Los números divisibles por 2 y por 3 son divisibles por 6.
• Programa:

divide(2,6).
divide(2,4).
divide(2,12).
divide(3,6).
divide(3,12).
divide(6,X) :- divide(2,X), divide(3,X).

• Símbolos:
  • Constantes: 2, 3, 4, 6, 12
  • Relación binaria: divide
  • Variable: X
• Interpretaciones de la Regla 1:
  • Interpretación procedimental. divide(6,X) :- divide(2,X), divide(3,X).
  • Interpretación declarativa: (∀X)[divide(2,X) ∧ divide(3, X) → divide(6, X)]
• Consulta: ¿Cuáles son los múltiplos de 6?

?- divide(6,X).
X = 6 ;
X = 12 ;
No

• Árbol de deducción:

• Comentarios:
  • Unificación.
  • Cálculo de respuestas.
  • Respuestas múltiples.

2.3 Deducción Prolog en lógica funcional

Suma de números naturales

• Representación de los números naturales:

0, s(0), s(s(0)), ...

• Definición de la suma:

0 + Y = Y
s(X) + Y = s(X+Y)

• Programa

suma(0,Y,Y).
suma(s(X),Y,s(Z)) :- suma(X,Y,Z).

Cálculo de sumas

• Consulta: ¿Cuál es la suma de s(0) y s(s(0))?

• Sesión

?- suma(s(0),s(s(0)),X).
X = s(s(s(0)))

• Árbol de deducción:

Cálculo de restas

• Consulta: ¿Cuál es la resta de s(s(s(0))) y s(s(0))?

• Sesión

?- suma(X,s(s(0)),s(s(s(0)))).
X = s(0) ;
false.

• Árbol de deducción:

Descomposiciones en dos sumandos

• Consulta: ¿Cuáles son las soluciones de la ecuación X + Y = s(s(0))?

• Sesión

?- suma(X,Y,s(s(0))).
X = 0       Y = s(s(0)) ;
X = s(0)    Y = s(0) ;
X = s(s(0)) Y = 0 ;
false.

• Árbol de deducción:

Soluciones de sistemas de ecuaciones

• Consulta: ¿Cuáles son las soluciones del sistema de ecuaciones

1 + X = Y
X + Y = 1

• Sesión:

?- suma(s(0),X,Y), suma(X,Y,s(0)).
X = 0 Y = s(0) ;
false.

• Árbol de deducción:

3 Bibliografía

1. J.A. Alonso (2006) Introducción a la programación lógica con Prolog.
   • Cap. 0: “Introducción”.
2. I. Bratko (1990) Prolog Programming for Artificial Intelligence (2nd ed.)
   • Cap. 1: “An overview of Prolog”.
   • Cap. 2: “Syntax and meaning of Prolog programs”.
3. W.F. Clocksin y C.S. Mellish (1994) Programming in Prolog (Fourth Edition).
   • Cap. 1: “Tutorial introduction”.
   • Cap. 2: “A closer look”.

4. R.A. Kowalski (2006) La lógica computacional y el pensamiento humano: cómo ser artificialmente inteligente.

5. SWISH: SWI-Prolog for SHaring (a SWI-Prolog web IDE).