Programación Declarativa.
Programación Lógica.
Prog. Imperativa vs. Declarativa
La programación lógica, junto con la
funcional, forma parte de lo que se conoce como programación declarativa.
En los lenguajes imperativos, la programación consiste en indicar cómo resolver un problema mediante sentencias; en la programación lógica, se trabaja de una forma descriptiva, estableciendo relaciones entre entidades, indicando no cómo, sino qué hacer.
Programa lógico
En este paradigma, un algoritmo se
construye especificando una base de
conocimiento sobre la que se
realizan consultas y aplicando un
mecanismo de inferencia o
deducción sobre dicha base.
Base de conocimiento
Las cláusulas o enunciados que conforman la base de conocimientos declaran la forma de demostrar o deducir constructivamente un objetivo a partir del programa.
Estas cláusulas se denominan ‘Cláusulas de Horn’
Cláusula de Horn
Es un predicado con una sola conclusión y un conjunto de premisas de cuyo valor de verdad se deriva o deduce el valor de verdad de la conclusión.
c:- pr1,pr2,pr3,pr4.
Una conclusión es verdadera si lo son todas sus premisas.
Base de conocimiento
La base de conocimiento está formada
por hechos, que representan la
información válida del sistema
expresada como relaciones entre
datos; y por reglas lógicas, que
permiten deducir consecuencias a
partir de la combinación entre los
hechos y otras reglas.
Motor de inferencias:
El mecanismo de inferencia o ‘motor
de búsqueda’, actúa como control de
la secuencia de ejecución.
Durante la ejecución del programa, el
sistema va evaluando y combinando
las reglas lógicas de la base de
conocimiento para lograr el objetivo
deseado.
Mecanismos del motor de
inferencia.
El mecanismo de evaluación e
inferencia permite construir todas las
combinaciones posibles para poder
alcanzar un objetivo. Para este fin
aplica la técnica de backtracking.
La recursividad es la otra
herramienta utilizada para encontrar
soluciones.
Características del paradigma
lógico:
Tiene como característica principal el
uso de reglas lógicas para inferir o
derivar conclusiones a partir de datos.
Conociendo dichos datos y las
condiciones del problema, la ejecución
de un programa consiste en demostrar
un objetivo a partir de las reglas
declaradas.
Carácter declarativo:
Un programa lógico NO tiene un
algoritmo que indique los pasos a
seguir para llegar al resultado, sino
que está formado por expresiones
lógicas que declaran o describen la
solución y es el sistema interno quien
proporciona la secuencia de control en
que se utilizan esas expresiones.
Aplicaciones:
Inteligencia Artificial
Sistemas expertos
Procesamiento de Lenguaje Natural
Compiladores
Bases de datos deductivas
Acceso a bases de datos desde
páginas web
PROLOG
PROgrammation en LOGique
Este lenguaje es el principal representante del paradigma.
La base conceptual de la lógica proposicional es desarrollada por Alfred Horn en los años 50.
Philippe Roussel y Alain Colmerauer (Universidad de Aix- Marsella) lo crearon en 1972, y su base teórica se debe en gran parte a Kowalski
Estructuras básicas del lenguaje
Prolog cuenta con dos tipos de estructuras: términos y sentencias.
Los términos pueden ser constantes, variables o functores:
- Las constantes, representadas por una cadena de caracteres, pueden ser números o cualquier cadena que comience en minúscula.
- Las variables son cadenas que comienzan con una letra mayúscula.
- Los functores son identificadores que empiezan con minúscula, seguidos de una lista de parámetros (términos) entre paréntesis, separados por comas.
Estructuras básicas del lenguaje
Las sentencias son cláusulas: hechos, reglas y consultas.
- Un hecho establece una relación entre objetos, y es la forma más sencilla de sentencia.
Ejemplo:
humano (socrates).
ama (juan,maría).
Se establece que Sócrates es humano y que Juan ama a María.
Estructuras básicas del lenguaje
Una regla permite definir nuevas relaciones a partir de otras ya existentes.
Las reglas son de la forma p q
p es el antecedente q es el consecuente
En Prolog se expresa: q:-p
El símbolo :- se lee: ‘si’
En el ejemplo: q si p Si p entonces q
Reglas con cuantificadores
Si queremos establecer que todo humano
es mortal, en lógica estándar escribiríamos:
Para todo x ,humano(x) mortal(x)
En Prolog escribimos:
mortal(X):-humano(X).
Esto se lee: X es mortal si X es humano
Si X es humano entonces X es mortal
Partes de una regla:
mortal(X):- humano (X).
El símbolo :- significa si / entonces
En esta regla, mortal(X) es la cabeza,
y humano(X) es el cuerpo.
Hechos.
%Relación progenitor X de Y
progenitor (pilar, belen).
progenitor (tomas, belen).
progenitor (tomas, lucia).
progenitor (belen, ana).
progenitor (belen, pedro).
progenitor (pedro, jose).
progenitor (pedro, maria).
Constantes y predicados empiezan en minúscula
Los hechos terminan
en .
Las variables
comienzan con mayúscula
Consultas: El sistema es capaz de responder
? progenitor (pilar,belen).
yes
? progenitor(pilar,lucia).
no no se deduce de la base de conocimiento.
? progenitor( belen,X).
X=ana;
X=pedro;
no
Predicados reversibles
Una de las características de Prolog es la
capacidad que tienen los predicados de ser
utilizados de forma reversible.
Se pueden introducir unos valores en las
entradas, esperando que las variables de salida,
unifiquen con el resultado. Pero también podemos
utilizarlos al revés, es decir, introducir la salida
esperando que Prolog encuentre la/s entrada/s
necesarias para hacer cierto el predicado.
Reversibilidad de los predicados.
?progenitor(belen,X).
X=ana;
X=pedro;
no.
?progenitor(X,jose).
X=pedro;
no.
Reglas.
A- simples
B- con variables
C- recursivas
D- con funciones
Reglas simples.
%hechos
notrabaja(belen).
bueno(pedro).
%reglas
cuida(belen,pedro):- notrabaja(belen), bueno(pedro).
Este programa dice que: belen cuida a pedro si ella no trabaja y pedro es bueno. La coma es una conjunción entre cláusulas.
Reglas con variables
%hechos
mujer(maria).
mujer(pilar).
mujer(belen).
mujer(lucia).
mujer(ana).
hombre(tomas).
hombre(pedro).
hombre(jose).
%reglas
madre(X,Y):- mujer(X), progenitor(X,Y).
Consulta:
? madre(belen,pedro).
yes
?madre(X,Y).
X=pilar;
Y=belen;
X=belen; % el ; permite listar todos
Y=ana; % los resultados posibles
X=belen;
Y=pedro;
no.
Reglas recursivas
antepasado(X,Y):-progenitor(X,Y).
antepasado(X,Y):-progenitor(X,Z), antepasado(Z,Y).
Importa el orden de las cláusulas, 1º van los casos bases.
Consulta:
?antepasado(X,ana).
X=belen;
X=tomas;
X=pilar;
no.
Reglas con funciones grande(pepe).
grande(cabeza(juan)).
grande(X):-mayor(X,Y).
mayor(cabeza(X), cabeza(Y)):- progenitor(X,Y).
Consulta:
?grande(X).
X=pepe;
X=cabeza(juan);
X=cabeza(pilar);
…..;
no.
Mecanismo de inferencia
El cómputo en un programa lógico es realizado por medio de la combinación de dos mecanismos:
- Reemplazo y unificación
Mediante la repetición de este proceso de reemplazo se obtiene una secuencia de resolventes la cual es llamada una derivación.
Para resolver objetivos el sistema debe realizar la unificación o ligadura entre los objetivos y las cabezas de las reglas o de los hechos.
Unificación
Es el mecanismo mediante el cual las
variables toman valor.
El valor que puede tomar una variable
consiste en cualquier término.
No existe el concepto de asignación ni de
celda de memoria.
Las variables se unifican, instancian o ligan
a un valor particular y NO cambian.
Listas. Las listas se denotan con corchetes, separando
los elementos por comas.
Contienen términos (variables, constantes o estructuras) en general. Es posible anidar listas.
[ ] es la lista vacía
Ejemplos de listas: [1,2,3,4]
[a,b,c,d]
[1,’a’, X,[1,2,3]]
[[1,2],[3,4],[5,6]
Listas: operador |
Se utiliza el operador “|”, para separar el primer elemento de una lista del resto.
Ejemplos:
?- [Cabeza|Resto] = [1,2,3].
Cabeza=1
Resto=[2,3]
?- [Cabeza|Resto] = [1].
Cabeza=1
Resto=[]
El resto o cuerpo de una lista, siempre es una lista.
Recorrido de una lista
hombre(tomas).
hombre(pedro).
hombre(jose).
%reglas recursivas para recorrer una lista
hombres([ ]).
hombres([X|Xs]):- hombre(X), hombres(Xs).
?hombres([jose,tomas,pedro)].
yes
Pertenencia a una lista
member(X,[X|Xs]).
member(X,[Y|Ys]) :- member(X,Ys).
Si usamos el predicado member: se puede
chequear pertenencia, obtener todos los
miembros de una lista (por backtracking) y
obtener todas las listas que contienen a X
como elemento.
Búsqueda = pertenencia
? member(jose, X).
X=[jose,pedro];
X=[tomas,jose];
……
…
no.
?member(X,[jose,pedro,tomas]).
X=jose;
X=pedro;
X=tomas;
no.
Otra forma de pertenencia:
nopertenece(X,[ ]).
nopertenece(X, [Y|Ys]) :- X\=Y,
nopertenece(X,Ys).
?nopertenece(pilar,[jose,tomas]).
yes
Otros ejemplos:
Añadir un elemento a una lista
add(X,[],[X]).
add(X,L,[X|L]).
Borrar un elemento de una lista
del(X,[X|Xs],Xs).
del(X,[Y|Xs],[Y|Ys]) :- X\=Y,del(X,Xs,Ys).
Longitud de una lista
long([],0).
long([X|Xs], C):- long(Xs,C1), C is C1 + 1.
Se define la longitud de una lista como la
longitud del cuerpo más la cabeza.
Suma de los elementos de una lista
sum([],0).
sum([X|Xs], S):-sum(Xs,S1), S is S1 + X.
La suma de los elementos de una lista se
obtiene como la suma de los elementos del
cuerpo más la cabeza de la lista.
Cantidad de pares de una lista:
cantP([],0).
cantP([X|Xs], S):- par(X),cantP(Xs,S1),
S is S1 + 1.
cantP([X|Xs], S):- impar(X),cantP(Xs,S1),
S is S1 .
La cantidad de elementos pares de una lista se obtiene como la cantidad de elementos pares del cuerpo, si la cabeza de la lista es impar, o le suma 1 si la cabeza de la lista es par.
Varios:
suma(X,Y,Z):- Z is X+Y.
par(X):- 0 is X mod 2.
Esta regla devuelve true si 0 es el resultado de hacer X mod 2.
impar(X):- 1 is X mod 2.
igual(X,Y):- X=Y.
mayor(X,Y,X):- X>Y.
mayor(X,Y,Y):- X<Y.
mayor(X,Y,0):- X=Y.
posit(X):- X>0.