INTRODUCCIÓN A LA PROGRAMACIÓN LÓGICA

La Programación Lógica estudia el uso de la lógica para el planteamiento de problemas y el control sobre las reglas de inferencia para alcanzar la solución automática.

La Programación Lógica, junto con la funcional, forma parte de lo que se conoce como Programación Declarativa, es decir la programación consiste en indicar como resolver un problema mediante sentencias, en la Programación Lógica, se trabaja en una forma descriptiva, estableciendo relaciones entre entidades, indicando no como, sino que hacer, entonces se dice que la idea esencial de la Programación Lógica es

Programa= lógica + control

Lógica (programador): hechos y reglas para representar conocimiento

Control (interprete): deducción lógica para dar respuestas (soluciones)

La programación lógica intenta resolver lo siguiente:

Dado un problema S, saber si la afirmación A es solución o no del problema o en qué casos lo es. Además queremos que los métodos sean implantados en maquinas de forma que la resolución del problema se haga de forma automática.

La programación lógica: construye base de conocimientos mediante reglas y hechos

*      Regla: implicación o inferencia lógica que deduce nuevo conocimiento, la regla permite definir nuevas relaciones a partir de otras ya existentes

Ej.:

Mortal (x): - humano(x)

x es mortal si x es humano

*      Hecho: declaración, cláusula o proposición cierta o falsa, el hecho establece una relación entre objetos y es la forma más sencilla de sentencia

Ej.:

Humano (Sócrates); Sócrates es humano

Ama (Juan, María) ; ama Juan a María

*      Consulta: se especifica el problema, la proposición a demostrar o el objetivo Partiendo de que los humanos son mortales y de que Sócrates es humano, deducimos que

Sócrates es mortal

Mortal (x): - humano(x);- los humanos son mortales; regla

Humano (Sócrates); Sócrates es humanos; hecho

Sócrates es mortal ; consulta

La programación lógica comprende dos Paradigmas de Programación la Programación Declarativa y la Programación funcional. La programación declarativa gira en torno al concepto de predicado, o relación entre elementos. La programación funcional se basa en el concepto de función (que no es más que una evolución de los predicados), de corte más matemático.

MECANISMOS BÁSICOS

Son predicados predefinidos en PROLOG para las operaciones matemáticas básicas. Su sintaxis depende de la posición que ocupen, pudiendo ser infijos o prefijos. Por ejemplo el operador suma ("+"), podemos encontrarlo en forma prefija '+(2,5)' o bien infija, '2 + 5'.

También dispone de predicados de igualdad y desigualdad.

X = Y igual

X \= Y distinto

X < Y menor

X > Y mayor

X =< Y menor o igual

X >= Y mayor o igual

Al igual que en otros lenguajes de programación es necesario tener en cuenta la precedencia y la asociatividad de los operadores antes de trabajar con ellos.  En cuanto a precedencia, es la típica. Por ejemplo, 3+2*6 se evalúa como 3+(2*6). En lo referente a la asociatividad, PROLOG es asociativo por la izquierda. Así, 8/4/4 se interpreta como (8/4)/4. De igual forma, 5+8/2/2 significa 5+((8/2)/2).

El operador 'is'. Es un operador infijo, que en su parte derecha lleva un término que se interpreta como una expresión aritmética, contrastándose con el término de su izquierda.

Por ejemplo, la expresión '6 is 4+3.' es falsa. Por otra parte, si la expresión es 'X is 4+3.', el resultado será la instanciación de X:

X = 7

Una regla PROLOG puede ser esta:

densidad(X,Y) :- población(X,P), área(X,A), Y is P/A.

Algunos comandos básicos

* consult.

El predicado _consult_ está pensado para leer y compilar un programa PROLOG o bien para las situaciones en las que se precise añadir las cláusulas existentes en un determinado fichero a las que ya están almacenadas y compiladas en la base de datos. Su sintaxis puede ser una de las siguientes:

consult(fichero).

consult('fichero.ext').

consult('c:\ia\prolog\fichero').

* recon.

El predicado recon es muy parecido a consult, con la salvedad de que las cláusulas existentes en el fichero consultado, reemplazan a las existentes en la base de hechos. Puede ser útil para sustituir una única cláusula sin consultar todas las demás, situando esa cláusula en un fichero. Su sintaxis es la misma que la de consult.

*forget.

Tiene como fin eliminar de la base de datos actual aquellos hechos consultados de un fichero determinado. Su sintaxis es:

forget(fichero).

* exitsys.

Este predicado nos devuelve al sistema operativo.

ESTRUCTURA DE UN PROGRAMA

Un programa Prolog está formado por una secuencia de enunciados: hechos, reglas y comentarios.

Una relación puede estar especificada por hechos, simplemente estableciendo objetos que satisfacen la relación o por reglas establecidas acerca de la relación. Cada regla está formada por un primer miembro (o la cabeza de la regla), un segundo miembro (o cola de la regla) ligados por " :- " y termina con el carácter " .

código del programa

** Hechos **

mujer(maria).

hombre(pedro).

hombre(manuel).

hombre(arturo).

** Relaciones **

padre(pedro,manuel).

padre(pedro,arturo).

padre(pedro,maria).

** Reglas **

nino(X,Y):- padre(Y,X)

hijo(X,Y):-nino(X,Y),hombre(X).

hija(X,Y):-nino(X,Y),mujer(X).

hermano_o_hermana(X,Y):-padre(Z,X),padre(Z,Y).

hermano(X,Y):-hermano_o_hermana(X,Y),hombre(X).

hermana(X,Y):-hermano_o_hermana(X,Y),mujer(X).

OBJETOS COMPUESTOS

Un programa en Visual Prolog está compuesto de varias secciones que se describen a continuación:

   * Directivas de compilación: que se dan al comienzo del programa.

   * Sección de constantes: puede contener cero, una o varias constantes.

   * Sección de dominios: puede contener cero, uno o varios dominios.

   * Sección de la base de datos: puede contener cero, uno o varios predicados de la base de datos.

   * Sección de predicados: puede contener cero, una o varias declaraciones de predicados.

   * Sección de cláusulas: puede contener cero, una o varias cláusulas.

   * Sección de meta: para que el programa se ejecute de forma independiente debe existir una meta construida dentro del propio programa.

RECURSIVIDAD

La recursividad es un mecanismo que da bastante potencia a cualquier lenguaje de programación. Veamos un ejemplo de programación recursiva que nos permitirá determinar si un tomo es miembro de una lista dada:

(1) miembro(X,[X|_]).

(2) miembro(X,[_|Y]) :- miembro(X,Y).

La regla (1) es el caso base de la recursión. Se evaluar como cierta siempre que coincida la variable X con la cabeza de la lista que se pasa como argumento. En la regla (2) est la definición recursiva. X es miembro de una lista si lo es de la cola de esa lista (la cabeza se comprueba en la regla (1)).

La regla (1) es una simplificación de la regla:

miembro(X,[Y|_]) :- X = Y.

La traza para el caso de 'miembro(b,[a,b,c]).' es la siguiente:

(1) miembro(b,[a,b,c]) :- b = a. ---> no.

(2) miembro(b,[a,b,c]) :- miembro(b,[b,c]).

(1) miembro(b,[b,c]) :- b = b. ---> yes.

Si necesitamos conocer la longitud de una lista, emplearemos una función recursiva como la siguiente:

longitud([],0).

longitud([_|Y],L1) :- longitud(Y,L2), L1 is L2 + 1.

JUEGOS MINI-MAX

La estrategia minimax es una estrategia de búsqueda exhaustiva mediante un árbol de búsqueda. Este algoritmo considera el caso de 2 participantes a los que se les denomina Max y Min.

El que inicia el juego es Max y existe una alternancia en la participación del juego. Por lo tanto lo que tiene que hacer Max, es determinar la secuencia de jugadas que conduzca a un estado Terminal ganador o favorecedor. La figura 1 muestra parte del árbol generado para la búsqueda por la técnica de Minimax para el juego del tres en raya.

Sin embargo, esta búsqueda muchas veces tiene que evaluar ramas innecesarias que no le traerán beneficio alguno para obtener el mejor resultado. Por lo tanto, es aquí donde se plantea la solución mediante la poda de esas ramas que no beneficiaran en nada a la mejor jugada: La técnica de Poda Alpha-Beta. El algoritmo 1 muestra la implementación de la técnica de Minimax en forma recursiva.

Algoritmo 1: Algoritmo recursivo de la técnica de Minimax

Entrada:
  - Nodo N.
Salida:
  - Valor de utilidad de N
-------------------------------------------------------------------------------------------------------------
Si N es nodo Hoja
     ValorUtilidad<-función de utilidad
De lo contrario
Para cada nodoHijo Hi de
      valorUtilidadi<-MiniMaxR(Hi)
Fin para
Si N es max
       valorUtilidad<- max(H1,H2,...Hn)
De lo contrario
       valorUtilidad<- min(H1,H2,...Hn)

Devolver (valorUtilidad)

PODA ALFA - BETA

Este algoritmo es el más utilizado en las aplicaciones referidas a juegos, dada su excepcional utilidad en el aumento de la velocidad de la búsqueda sin producir pérdida de la información. Es una extensión en particular del algoritmo de Búsqueda Minimax en juegos de dos contrincantes.

Cada vez que se evalúa un nodo u hoja, el algoritmo determina s los nuevos hijos generados pueden generar una mejor utilidad de la que ya posee el nodo estudiado y si afecta al nodo padre. De no ser así, eso significa que seguir analizando esa rama es desperdiciara recursos como tiempo y espacio, por lo cual no se sigue generando y simplemente se le poda, de allí el nombre.

El algoritmo 2, muestra como es el desarrollo para una búsqueda por medio de la Poda Alpha –Beta. Se detalla las entradas. Para ingresar al algoritmo, se necesita ingresar el nodo a ser evaluado, del que se obtendrá su utilidad, así como la utilidad del padre para evaluar si es que la nueva utilidad afecta o no al nodo padre. De no ser así, se procederá a podar la rama [6].

Una vez podada la rama, la nueva utilidad será la última en ser registrada o actualizada. Esto se da mediante la variable fNodo, que contiene la función de utilidad del nodo ingresado [7].

Algoritmo Poda Alpha–Beta

Entrada:
- Nodo, fNodoP
Salida:
- fNodo
----------------------------------------------------------------------------------------
Si nodo es MAX
     fNodo <- -inf
De lo contrario
     fNodo <- inf
fin si
Si nodo es hoja
 fNodo <- utilidadNodo(nodo)
de lo contrario
   para cada ficha fi que se pueda mover
      para cada accion aj de fi
          nodoH <- crear nodo con ai
          nodoH <- PodaAb(nodoH,fNodo)
          si nodo es MAX
                si fHijo> fNodo
                            fNodo<- fHijo
                            si fNodo>=fNodoP
                                    eliminar fNodo
                                    retorna null;
                             fin si
                fin si
           fin si
           si nodo es MIN
                    si fHijo < fNodo
                           fNodo<- fHijo
                           si fNodo=<fNodoP
                                 eliminar fNodo
                                 retornar null;
                            fin si
                    fin si
           fin si
      fin para
  fin para
retorna nodo;
fin si