3.- Programación Lógica

3.1.- Repaso de la lógica de primer orden

La programación lógica es un tipo de paradigmas de programación dentro del paradigma de programación declarativa. El resto de los subparadigmas de programación dentro de la programación declarativa son: programación funcional, programación con restricciones, programas DSL (de dominio específico) e híbridos. 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. La programación lógica gira en torno al concepto de predicado, o relación entre elementos.

3.2.- Unificación y resolución 

El Método de Resolución es un intento de mecanizar el proceso de deducción natural de forma eficiente.
Las demostraciones se consiguen utilizando el método refutativo (reducción al absurdo), es decir lo que se intenta es encontrar contradicciones. Para probar una sentencia basta con demostrar que su negación nos lleva a una contradicción con las sentencias conocidas (es insatisfactible).


ALGORITMO DE RESOLUCIÓN

Existen distintas Estrategias de Resolución: sistemática, con conjunto soporte, unitaria, primaria y lineal.

El procedimiento de resolución consiste en un proceso iterativo en el cual comparamos (resolvemos), dos cláusulas llamadas cláusulas padres y producimos una nueva cláusula que se ha inferido (deducido), de ellas. 


EJEMPLO
La resolución opera tomando dos cláusulas tales que cada una contenga un mismo literal, en una cláusula en forma positiva y en la otra en forma negativa. El resolvente se obtiene combinando todos los literales de las cláusulas padres y eliminando aquellos que se cancelan.
ALGORITMO DE UNIFICACIÓN
Podemos definir la Unificación como un procedimiento de emparejamiento que compara dos literales y descubre si existe un conjunto de sustituciones que los haga idénticos. 


Ejemplo
Se unificara P(x, x) con P(y, z):
Primera sustitución: (y/x)
Resultado: P(y, y) P(y, z)
Segunda sustitución: (z/y)
Resultado: P(z, z) P (z, z)
La sustitución resultante es la composición de las sustituciones: s = { z/y , y/x}

                       3.3.- Cláusulas de Horn, resolución SLD.

En lógica proposicional, una fórmula lógica es una cláusula de Horn si es una cláusula (disyunción de literales) con, como máximo, un literal positivo. Se llaman así por el lógico Alfred Horn, el primero en señalar la importancia de estas cláusulas en 1951.
Una cláusula de Horn con exactamente un literal positivo es una cláusula "definite"; en álgebra universal las cláusulas "definites" resultan como cuasi-identidades. Una cláusula de Horn sin ningún literal positivo es a veces llamada cláusula objetivo (goal) o consulta (query), especialmente en programación lógica.

Ejemplo
Se llaman cláusulas de Horn aquellas que tienen como máximo un literal positivo. Hay dos tipos:
Las cláusulas determinadas (definite clauses), o «cláusulas de Horn con cabeza» son las que sólo tienen un literal positivo:
(¬p1 ¬p2 ... ¬pk q) (p1 p2 ... pk q)
Caso particular son las no tienen más que ese literal positivo, que representan «hechos», es decir, conocimiento factual.
Los objetivos determinados (definite goals), o «cláusulas de Horn sin cabeza» son las que no tienen ningún literal positivo:
(¬p1 ¬p2 ... ¬pk) ¬(p1 p2 ... pk)

RESOLUCIÓN SLD
La resolución general es un mecanismo muy potente de demostración pero tiene un alto grado de indeterminismo: en la selección de las clausulas con las que hacer resolución y en la selección de los literales a utilizar en la resolución.
Los hechos y las reglas se denominan clausulas definidas: Los hechos representan “hechos acerca de los objetos” (de nuestro universo de discurso), relaciones elementales entre estos objetos las reglas expresan relaciones condicionales entre los objetos, dependencias.

REGLAS
Un hecho es una regla con cuerpo vacío un objetivo es una regla con cabeza vacía y el éxito es una regla con cabeza y cuerpo vacíos. En las cláusulas de Horn se trabaja con secuencias de literales en vez de conjuntos Esto implica dos cosas: los literales pueden aparecer repetidos en el cuerpo hay un orden en los literales del cuerpo.

3.4.- Programación lógica con cláusulas de Horn. 

La aplicación de refutación por resolución en cláusulas de Horn es un mecanismo ampliamente utilizado. El lenguaje de programación Prolog, se basa en este tipo de cláusulas y los programas implementados en él se denominan programas lógicos definidos
Tenemos tres tipos de cláusulas de Horn

Tipo I: un átomo simple (hecho) ej. P11(x)
Tipo II: una implicación (llamada regla) cuyo antecedente consiste de una conjunción de literales positivos y el consecuente es sólo un literal positivo: L1^L2…^Ln-1 Ln donde las L son literales positivos. Muchas veces se nota: L1,L2,…,Ln-1 Ln .
Tipo III: Un conjunto de literales negados, que puede notarse como una implicación sin consecuente L1, L2…Ln 

La notación utilizando implicación es la preferida para escribir cláusulas de Horn y resulta equivalente a la notación utilizando la disyunción de literales. Una cláusula de Horn notada como disyunción finita de literales, siendo las L literales, se escribe así:

-L1v-L2v….-Ln-1 vLn ,
Lo cual pude notarse como conjunto:
{-L1,-L2,…..-Ln-1, Ln}
Y es equivalente a:
L1,L2,…,Ln-1 Ln (las comas son conjunciones)

En general cualquier cláusula puede escribirse como implicación, dando lugar a lo que se conoce como forma normal conjuntiva. La equivalencia es directa, si tenemos una cláusula de la forma A1 v….vAn v-B1 v….v-Bn equivale a
B1^...^Bn A1,v…v An