PDF de programación - Tema 13: Introducción a la programación lógica con Prolog - Lógica informática (2015–16)

PD Tema 13: Introducción a la programación lógica con Prolog

Lógica informática (2015–16)

Tema 13: Introducción a la programación lógica con Prolog

José A. Alonso Jiménez
Andrés Cordón Franco
María J. Hidalgo Doblado

Grupo de Lógica Computacional

Departamento de Ciencias de la Computación e I.A.

Universidad de Sevilla

1 / 43

PD Tema 13: Introducción a la programación lógica con Prolog

Tema 13: Introducción a la programación lógica con Prolog

1. El sistema deductivo de Prolog

2. Las listas en Prolog

3. Operadores en Prolog

4. Control mediante corte

5. Negación como fallo

2 / 43

PD Tema 13: Introducción a la programación lógica con Prolog

El sistema deductivo de Prolog

Tema 13: Introducción a la programación lógica con Prolog

1. El sistema deductivo de Prolog

Deducción Prolog en lógica proposicional
Deducción Prolog en lógica relacional
Deducción Prolog en lógica funcional

2. Las listas en Prolog

3. Operadores en Prolog

4. Control mediante corte

5. Negación como fallo

3 / 43

PD Tema 13: Introducción a la programación lógica con Prolog

El sistema deductivo de Prolog

Deducción Prolog en lógica proposicional

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

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

es una cebra.

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.

4 / 43

PD Tema 13: Introducción a la programación lógica con Prolog

El sistema deductivo de Prolog

Deducción Prolog en lógica proposicional

Deducción Prolog en lógica proposicional

Programa:

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

:- es_ungulado, tiene_rayas_negras. %R1
%R2
%R3
%H1
%H2
%H3

Sesión:
> pl
Welcome to SWI-Prolog (Multi-threaded, Version 5.6.20)
Copyright (c) 1990-2006 University of Amsterdam.
?- [animales].
Yes
?- es_cebra.

5 / 43

PD Tema 13: Introducción a la programación lógica con Prolog

El sistema deductivo de Prolog

Deducción Prolog en lógica proposicional

Deducción Prolog en lógica proposicional

Árbol de deducción:

6 / 43

PD Tema 13: Introducción a la programación lógica con Prolog

El sistema deductivo de Prolog

Deducción Prolog en lógica proposicional

Deducción Prolog en lógica proposicional

Demostración por resolución SLD:

7 / 43

PD Tema 13: Introducción a la programación lógica con Prolog

El sistema deductivo de Prolog

Deducción Prolog en lógica relacional

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:

% Hecho 1
divide(2,6).
% Hecho 2
divide(2,4).
% Hecho 3
divide(2,12).
% Hecho 4
divide(3,6).
% Hecho 5
divide(3,12).
divide(6,X) :- divide(2,X), divide(3,X). % Regla 1

8 / 43

PD Tema 13: Introducción a la programación lógica con Prolog

El sistema deductivo de Prolog

Deducción Prolog en lógica relacional

Deducción Prolog en lógica relacional

Símbolos:

Constantes: 2, 3, 4, 6, 12
Relación binaria: divide
Variable: X

Interpretaciones de la Regla 1:

divide(6,X) :- divide(2,X), divide(3,X).
Interpretación declarativa:
(∀X )[divide(2, X ) ∧ divide(3, X ) → divide(6, X )]

Interpretación procedimental.

Consulta: ¿Cuáles son los múltiplos de 6?

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

9 / 43

PD Tema 13: Introducción a la programación lógica con Prolog

El sistema deductivo de Prolog

Deducción Prolog en lógica relacional

Deducción Prolog en lógica relacional

Árbol de deducción:

Comentarios:

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

10 / 43

PD Tema 13: Introducción a la programación lógica con Prolog

El sistema deductivo de Prolog

Deducción Prolog en lógica funcional

Deducción Prolog en lógica funcional
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).

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

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

11 / 43

PD Tema 13: Introducción a la programación lógica con Prolog

El sistema deductivo de Prolog

Deducción Prolog en lógica funcional

Deducción Prolog en lógica funcional

Árbol de deducción:

12 / 43

PD Tema 13: Introducción a la programación lógica con Prolog

El sistema deductivo de Prolog

Deducción Prolog en lógica funcional

Deducción Prolog en lógica funcional

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) ;
No

13 / 43

PD Tema 13: Introducción a la programación lógica con Prolog

El sistema deductivo de Prolog

Deducción Prolog en lógica funcional

Deducción Prolog en lógica funcional

Árbol de deducción:

14 / 43

PD Tema 13: Introducción a la programación lógica con Prolog

El sistema deductivo de Prolog

Deducción Prolog en lógica funcional

Deducción Prolog en lógica funcional

Consulta:

Pregunta: ¿Cuáles son las soluciones de la ecuación

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

Sesión:

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

Y = s(s(0)) ;
Y = s(0) ;
Y = 0 ;

15 / 43

PD Tema 13: Introducción a la programación lógica con Prolog

El sistema deductivo de Prolog

Deducción Prolog en lógica funcional

Deducción Prolog en lógica funcional

Árbol de deducción:

16 / 43

PD Tema 13: Introducción a la programación lógica con Prolog

El sistema deductivo de Prolog

Deducción Prolog en lógica funcional

Deducción Prolog en lógica funcional

Consulta:

Pregunta: resolver el 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) ;
No

17 / 43

PD Tema 13: Introducción a la programación lógica con Prolog

El sistema deductivo de Prolog

Deducción Prolog en lógica funcional

Deducción Prolog en lógica funcional

Árbol de deducción:

18 / 43

PD Tema 13: Introducción a la programación lógica con Prolog

Las listas en Prolog

Tema 13: Introducción a la programación lógica con Prolog

1. El sistema deductivo de Prolog

2. Las listas en Prolog

Definición de relaciones sobre listas

3. Operadores en Prolog

4. Control mediante corte

5. Negación como fallo

19 / 43

PD Tema 13: Introducción a la programación lógica con Prolog

Las listas en Prolog

Representación de listas

?- [X|Y] = [a,b].
X = a
Y = [b]
?- [X|Y] = [a,b,c,d].
X = a
Y = [b, c, d]
?- [X,Y|Z] = [a,b,c,d].
X = a
Y = b
Z = [c, d]

20 / 43

PD Tema 13: Introducción a la programación lógica con Prolog

Las listas en Prolog

Definición de relaciones sobre listas

Definición de concatenación (append)

Especificación: conc(A,B,C) se verifica si C es la lista obtenida

escribiendo los elementos de la lista B a continuación de los
elementos de la lista A. Por ejemplo,
?- conc([a,b],[b,d],C).
C =[a,b,b,d]

Definición 1:

conc(A,B,C) :- A=[], C=B.
conc(A,B,C) :- A=[X|D], conc(D,B,E), C=[X|E].

Definición 2:

conc([],B,B).
conc([X|D],B,[X|E]) :- conc(D,B,E).

21 / 43

PD Tema 13: Introducción a la programación lógica con Prolog

Las listas en Prolog

Definición de relaciones sobre listas

Definición de concatenación (append)

Especificación: conc(A,B,C) se verifica si C es la lista obtenida

escribiendo los elementos de la lista B a continuación de los
elementos de la lista A. Por ejemplo,
?- conc([a,b],[b,d],C).
C =[a,b,b,d]

Definición 1:

conc(A,B,C) :- A=[], C=B.
conc(A,B,C) :- A=[X|D], conc(D,B,E), C=[X|E].

Definición 2:

conc([],B,B).
conc([X|D],B,[X|E]) :- conc(D,B,E).

21 / 43

PD Tema 13: Introducción a la programación lógica con Prolog

Las listas en Prolog

Definición de relaciones sobre listas

Definición de concatenación (append)

Especificación: conc(A,B,C) se verifica si C es la lista obtenida

escribiendo los elementos de la lista B a continuación de los
elementos de la lista A. Por ejemplo,
?- conc([a,b],[b,d],C).
C =[a,b,b,d]

Definición 1:

conc(A,B,C) :- A=[], C=B.
conc(A,B,C) :- A=[X|D], conc(D,B,E), C=[X|E].

Definición 2:

conc([],B,B).
conc([X|D],B,[X|E]) :- conc(D,B,E).

21 / 43

PD Tema 13: Introducción a la programación lógica con Prolog

Las listas en Prolog

Definición de relaciones sobre listas

Consultas con la relación de concatenación
Analogía entre la definición de conc y la de suma,
¿Cuál es el resultado de concatenar las listas [a,b] y [c,d,e]?

¿Qué lista hay que añadirle a la lista [a,b] para obtener

?- conc([a,b],[c,d,e],L).
L = [a, b, c, d, e]

[a,b,c,d]?
?- conc([a,b],L,[a,b,c,d]).
L = [c, d]

¿Qué dos listas hay que concatenar para obtener [a,b]?

?- conc(L,M,[a,b]).
L = []
L = [a]
L = [a, b]
No

M = [a, b] ;
M = [b] ;
M = [] ;

22 / 43

PD Tema 13: Introducción a la programación lógica con Prolog

Las listas en Prolog

Definición de relaciones sobre listas

Consultas con la relación de concatenación
Analogía entre la definición de conc y la de suma,
¿Cuál es el resultado de concatenar las listas [a,b] y [c,d,e]?

¿Qué lista hay que añadirle a la lista [a,b] para obtener

?- conc([a,b],[c,d,e],L).
L = [a, b, c, d, e]

[a,b,c,d]?
?- conc([a,b],L,[a,b,c,d]).
L = [c, d]

¿Qué dos listas hay que concat