Programación Lógica

Filosofia del paradigma

La mayoría de los Lenguajes de Programación se basan en la Teoría Lógica de Primer Orden, aunque también incorporan algunos comportamientos de orden superior, en este sentido, destacan los lenguajes funcionales ya que se basan en el Calculo Lambda, es la única teoría lógica de orden superior.

"Aplicación de reglas de la lógica para inferir conclusiones a partir de datos."

¿Qué es?

Paradigma de programación basado en la lógica de primer orden. 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
Se puede ver como una deducción controlada.
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 que 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.

Características del Paradigma

  • Unificación de términos
  • Mecanismos de inferencia automática
  • Recursion como estructura de control básica
  • Visión lógica de la computación

Lógica Proposicional

También llamada lógica de enunciados: toma como elemento básico las frases declarativas simples o proposiciones. Su estructura está dada por:
Es un sistema formal cuyos elementos más simples representan proposiciones, y cuyas constantes lógicas, llamadas conectivas lógicas, representan operaciones sobre proposiciones, capaces de formar otras proposiciones de mayor complejidad.
La lógica proposicional trata con sistemas lógicos que carecen de cuantificadores, o variables interpretables como entidades. En lógica proposicional si bien no hay signos para variables de tipo entidad, sí existen signos para variables proposicionales (es decir, que pueden ser interpretadas como proposiciones con un valor de verdad definido), de ahí el nombre proposicional. La lógica proposicional incluye además de variables interpretables como proposiciones simples signos para conectivas lógicas, por lo que dentro de este tipo de lógica puede analizarse la inferencia lógica de proposiciones a partir de proposiciones, pero sin tener en cuenta la estructura interna de las proposiciones más simples.
Proposiciones: Elementos de una frase que constituyen por sí solos una unidad de comunicación de conocimientos y pueden ser considerados verdaderos o falsos.
Proposición Simple: “Pepito es humano”.
Proposición Compuesta: “Pepito es hombre y pepita es mujer”.

Lógica de primer orden

También llamada lógica de predicados: es un sistema deductivo basado en un Lenguaje Lógico Matemático formal. Su estructura esta dada por:
Incluye proposiciones lógicas, predicados y cuantificadores.
Más expresiva de la Lógica proposicional.
  • ¿Qué se afirma? (predicado o relación)
  • ¿De quién se afirma? (objeto)
Es un sistema formal diseñado para estudiar la inferencia en los lenguajes de primer orden.1 Los lenguajes de primer orden son, a su vez, lenguajes formales con cuantificadores que alcanzan sólo a variables de individuo, y con predicados y funciones cuyos argumentos son sólo constantes o variables de individuo. La lógica de primer orden tiene el poder expresivo suficiente para definir a prácticamente todas las matemáticas.

Cláusulas de Horn

Secuencia de literales que contiene a lo sumo uno de sus literales positivos (disyunción de literales). Esto es un ejemplo de una cláusula de Horn, y abajo se indica una fórmula como esta también puede reescribirse de forma equivalente como una implicación:
  • Cláusula ‘definite’: Cláusula de Horn con exactamente un literal positivo.
  • Hecho: Cláusula ‘definite’ sin literales negativos.
  • Cláusula objetivo: Sin ningún literal positivo. (consulta)
antecedente → consecuente "Si es verdad el antecedente, entonces es verdad el consecuente"
En Prolog Se escribe primero el consecuente luego el antecedente.
Ej: Estructura de clúasulas de HornEstructura de clúasulas de Horn en Prolog

Resolución SLD (Selective Linear Definite clause resolution)

El nombre "SLD resolution" fue dado por Maarten van Emden para la regla de inferencia sin nombre introducida por Robert Kowalski. Su nombre deriva de la resolución de SL, que es a la vez sonido y refutación completa de la forma clausal sin restricciones de la lógica. "SLD"significa "SL resolution with Definite clauses".
En ambos, SL y SLD, "L" representa el hecho de que una prueba de resolución se puede restringir a una secuencia lineal de cláusulas:
C1,C2,⋯,Cl
Donde la "cláusula superior" C1, es una cláusula de entrada, y cada otra cláusula Ci+1 es una solución de cuyos padres es la cláusula anterior Ci. La prueba es una refutación si la última cláusula Cl, es la cláusula vacía.
En SLD, todas las cláusulas son una secuencia cláusulas objetivo y el otro padre es una cláusula de entrada. En la resolución SL, el otro padre es una cláusula de entrada o una cláusula ancestral anterior en la secuencia.
Tanto en SL como en SLD, "S" representa el único literal resuelto en cualquier cláusula Ci, es aquel que es seleccionado únicamente por una regla de selección o función de selección. En la resolución SL, el literal seleccionado está restringido a uno que ha sido introducido recientemente en la cláusula. En el caso más simple, tal función de selección de último en entrar primero en salir puede especificarse por el orden en el que se escriben los literales, como en Prolog. Sin embargo, la función de selección en la resolución SLD es más general que en la resolución SL y en Prolog. No hay ninguna restricción sobre el literal que se puede seleccionar.

Backtracking

En lenguajes de programación como Fortran, Pascal, C o Java, las instrucciones se ejecutan normalmente en orden secuencial, es decir, una a continuación de otra, en el mismo orden en que están escritas, que sólo varía cuando se alcanza una instrucción de control (un bucle, una instrucción condicional o una transferencia).
Los programas en Prolog se componen de cláusulas de Horn que constituyen reglas del tipo "modus ponendo ponens", es decir, "Si es verdad el antecedente, entonces es verdad el consecuente". No obstante, la forma de escribir las cláusulas de Horn es al contrario de lo habitual. Primero se escribe el consecuente y luego el antecedente. El antecedente puede ser una conjunción de condiciones que se denomina secuencia de objetivos. Cada objetivo se separa con una coma y puede considerarse similar a una instrucción o llamada a procedimiento de los lenguajes imperativos. En Prolog no existen instrucciones de control. Su ejecución se basa en dos conceptos: la unificación y el backtracking.

Gracias a la unificación, cada objetivo determina un subconjunto de cláusulas susceptibles de ser ejecutadas. Cada una de ellas se denomina punto de elección. Prolog selecciona el primer punto de elección y sigue ejecutando el programa hasta determinar si el objetivo es verdaderoo falso.
En caso de ser falso entra en juego el backtracking, que consiste en deshacer todo lo ejecutado situando el programa en el mismo estado en el que estaba justo antes de llegar al punto de elección. Entonces se toma el siguiente punto de elección que estaba pendiente y se repite de nuevo el proceso. Todos los objetivos terminan su ejecución bien en éxito ( "verdadero"), bien en fracaso ( "falso").
A continuación veremos un ejemplo de backtracking en caso de que todos los objetivos son falsos.
Selecciona el primer punto de elección.
Si encuentra un objetivo falso realiza backtracking hasta el punto de elección anterior, y continua.
Repite el mismo procedimiento y en caso de no encontrar objetivo verdadero, y no tener más puntos de elección que recorrer devuelve falsocomo resultado de la consulta.
En caso de que todos alguno de los objetivos sea verdadero este es el recorrido.

Conceptos clave del paradigma

Hechos

Declaración, cláusula o proposición cierta o falsa, el hecho establece una relación entre objetos.
Son las sentencias más sencillas. Un hecho es una fórmula atómica o átomo: p(t1,...,tn) e indica que se verifica la relación (predicado) psobre los objetos (términos) t1,...,tn.

Reglas

Implicación o inferencia lógica que deduce nuevo conocimiento, la regla permite definir nuevas relaciones apartir de otras ya existentes

Consultas

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 Pepito es mortal

Recursión

La recursividad puede ser tratada de una manera más eficaz si se piensa en que hace el algoritmo recursivo que se piensa aplicar, en vez de cómo hacerlo. Para esto se usará la modularidad, la cual se basa en separar el problema en otros más pequeños y hallar la solución a estos para luego unirlos, como es ususal en la programación lógica.
Lo que se ha estado mostrando hasta ahora es, este sistema de resolver problemas de la programación lógica mediante la modularidad, entonces ¿cómo puede ser aplicada ésta en la recursión?
Si nuestro problema es obtener el área de un cuadrado, lo que se debe hacer no es separar esta área en una de un triángulo o un círculo, sino en las áreas de otros cuadrados, por lo cual se puede dar el valor del área del cuadrado con las medidas mínimas y de ahí empezar a llamar recursivamente la función con medidas mayores a ésta. por ejemplo:
El área de un cuadrado de área de 2 unidades cuadradas es igual a cuatro veces el área de un cuadrado de 1 unidad cuadrada.
Y así se puede obtener resultados de un problema con solo definir los casos base y de ahí realizar las operaciones recursivamente.
En un ámbito más matemático ésta idea puede ser utilizada para resolver operaciones sencillas como es el caso de las sumatorias o factoriales, en general cualquier operación que requiera información del resultado que generan valores inferiores al dado. Un ejemplo de ésto podría ser el hallar las potencias de dos dado el exponente en la función, lo cual puede ser hallado con el siguiente programa de prolog.

Ejemplo:

Un conjunto de hechos constituye un programa (la forma más simple de programa lógico) que puede ser visto como una base de datos que describe una situación. Por ejemplo, el Programa 1 refleja la base de datos de las relaciones familiares que se muestran en el siguiente gráfico.
Todos los hechos de este programa son hechos de base (sin variables), pero también se pueden introducir hechos con variables como axiomas,por ejemplo: suma(0,X,X). En ellos, las variables se consideran cuantificadas universalmente. Es decir, ∀x suma(0,x,x).
Al igual que el hecho es_mujer(sarah) establece la verdad de la sentencia "Sarah es mujer", el hecho suma(0,X,X) establece la verdad para cualquier valor que pueda tomar la variable, es decir, nos dice que "para todo término x, la suma de 0 con x es x" . Equivale a un conjunto de hechos de base como serían: suma(0,1,1), suma(0,2,2), etc.
Una vez que se tiene el programa describiendo una situación, se pueden hacer consultas para obtener información acerca de él. Por ejemplo, podemos hacer consultas al Programa 1 del tipo siguiente:

Ventajas y Desventajas del uso de este paradigma

Ventajas





  • Puede mejorarse la eficiencia modificando el componente de control sin tener que modificar la lógica del algoritmo.
  • Relaciones multipropósito.
  • Simplicidad.
  • Generación rápida de prototipos e ideas complejas.
  • Sencillez en la implementación de estructuras complejas.
  • Potencia.

    • Desventajas





  • Altamente ineficiente.
  • Pocas áreas de aplicación
  • No existen herramientas de depuración efectivas.
  • En problemas reales, es poco utilizado.
  • Si el programa no contiene suficiente información para contestar una consulta responde false.

    • Lenguajes:

    Ejemplos en SWI-Prolog: Ejemplos listos para ejecutar
    Los siguientes son algunos de los lenguajes de programación que emplean como paradigma la programación lógica.
    • Prolog
    • Mercury
    • CLP (FD)
    • CSP (Constraint Satisfaction Problem)
    • Lambda Prolog
    • Logtalk
    • Alma-0
    • CLAC(Logical Composition with the Assistance of Computers)
    • Gödel
    • Curry
    • Ace
    • PALs
    • Actor Prolog

    Prolog :

    Es un Lenguaje de Programación diseñado para representar y utilizar el conocimiento que se tiene sobre un determinado dominio. Los programas en Prolog responden preguntas sobre el tema del cual tienes conocimiento.
    La popularidad del lenguaje se debe a su capacidad de deducción y además es un lenguaje fácil de usar por su semántica y sintaxis. Solo busca relaciones entre los objetos creados, las variables y las listas, que son su estructura básica.
    Escribir un programa en Prolog consiste en declarar el conocimiento disponible acerca de objetos, además de sus relaciones y sus reglas, en lugar de correr un programa para obtener una solución, se hace una pregunta, el programa revisa la base de datos para encontrar la solución a la pregunta, si existe mas de una solución, Prolog hace un barrido para encontrar soluciones distintas. El propio sistema es el que deduce las respuestas a las preguntas que se le plantean, dichas respuestas las deduce del conocimiento obtenido por el conjunto de reglas dadas.
    • Alain Colmerauer y Philippe Roussel (Finales de los 70’s)
    • Proviene del francés PROgrammation en LOGique.
    • Producción interpretada
    • Se basa en Lógica de primer orden
    • Es declarativo
    • Backtracking

    Mercury :

    Mercury es un lenguaje de alto nivel (es decir, no se preocupa de problemas como la reserva y liberación de memoria) derivado de Prolog, pero con una implementación que le hace ser más útil para representar y tratar problemas del mundo real. Combina toda la expresividad del lenguaje declarativo con avanzadas técnicas de análisis estático y detección de errores. Es un lenguaje compilado, lo que le permite detectar numerosos errores antes de poder ejecutar la aplicación. El compilador “traduce” el programa de lenguaje Mercury a C, que es un lenguaje portable a cualquier plataforma. Además, al igual que el lenguaje de Gödel, Mercury es un lenguaje que utiliza módulos, lo que da una gran modularidad en el desarrollo de aplicaciones, solventando así uno de los mayores problemas a los que se enfrentaban los lenguajes de programación lógicos.





  • Es puramente declarativo Æ los predicados y funciones en Mercury siempre obtienen conclusiones lógicas
  • La comunicación con el programa es mediante una librería de funciones que necesitan como parámetro el estado anterior del “mundo” además del resto de parámetros que considere el usuario necesario y dan como salida el nuevo estado del “mundo” además de otros resultados específicos.
  • La declaración de tipos en Mercury se hace de manera lógica:
  • Se puede predeterminar el número de veces que se va a llamar a un predicado dentro del programa.“det” indica una vez, “semidet” como mucho una vez, “multi” al menos una vez y “nondet” un número arbitrario de veces El compilador comprobará que se cumple y, en caso contrario, rechazará el programa.
  • Mercury tiene un sistema modular. Los programas consisten en la composición de uno o más módulos. Cada módulo tiene una sección llamada interface donde se declaran todos los tipos, funciones y predicados que se pueden exportar a otros módulos y otra sección mplementation donde están las definiciones de las entidades exportadas así como definiciones de tipos y predicados no exportables, locales al módulo.
  • El compilador genera código muy eficiente

    • Fergus Henderson, Thomas Conway y Zoltan Somogyi (1995)
    • Sintaxis parecida a PROLOG
    • Diseñado para resolver “aplicaciones del mundo real” de forma robusta.
    • Soporta polimorfismo
    • Un programa escrito en Mercury es más rápido que uno equivalente realizado en Prolog.

    CLP (FD)

    Otra extensión de Prolog, especializado en los problemas CSPs (Constraint Satisfaction Problem). De forma general, podemos decir que un programa en CLP(FD) consta de tres partes: “generación de variables” (donde también se especifica su domino), “definición de restricciones” (sobre las variables) y “labeling”, donde se instancian las variables por enumeración.
    Ejemplo: SEND MORE MONEY puzzle

    Godel

    Gödel es un lenguaje en el que las sentencias lógicas llevan un orden y en el que existe el polimorfismo. Está basado en módulos (que aceptan polimorfismo) y en tipos de datos (soporta enteros y racionales con una precisión infinita, y número en coma flotante) y tiene una amplia librería de módulos predefinidos.
    Es un buen lenguaje para tareas de meta-programación, tales como compilación, depuración, análisis, verificación o transformación de programas, ya que es mucho más declarativo que Prolog, por ejemplo. Como curiosidad, se puede destacar que este lenguaje no funciona en un entorno Windows.
    Ejemplo: Máximo Común Divisor

    miniKanren

    miniKanren es un lenguaje específico de dominio incorporado para la programación lógica.
    El lenguaje central miniKanren es muy simple, con solo tres operadores lógicos y un operador de interfaz. miniKanren se ha implementado en un número creciente de lenguajes de host, incluidos Scheme, Racket, Clojure, Haskell, Python, JavaScript, Scala, Ruby, OCaml y PHP, entre muchos otros idiomas.
    miniKanren está diseñado para ser modificado y ampliado fácilmente; las extensiones incluyen la Programación Lógica de Restricciones, programación de lógica probabilística, programación lógica nominal y presentación.
    A continuaccion un ejemplo de la implementacion de esta libreria en python con un enfoque de pade hijo

    Ahora tratemos de obtener un padre de bart

    Ahora los dos hijos de homero

    Otros Ejemplos:

    • Grafos dirigidos en Prolog, busqueda de caminos
    • Serie fibonacci en Prolog
    • Serie fibonacci en Mercury
    • Juego de ahorcado en Prolog
    • Algoritmo merge sort en prolog

    Aplicaciones:

    1. Desarrollo de aplicaciones de inteligencia artificial.
    2. Prueba de teoremas de forma automática, donde un programa genera nuevos teoremas sobre una teoría existente.
    3. Construcción de Sistemas expertos, donde un Sistema de información mita las recomendaciones de un experto sobre algún dominio de conocimiento.
    4. Procesamiento del lenguaje natural, donde un programa es capaz de comprender (con limitaciones) la información contenida en una expresión lingüística humana.
      5. Acontinuación se presenta un ejemplo simple de procesamiento de lenguaje natural.
    5. Consultas lógicas basadas en reglas
      • Búsquedas en bases de datos
      • Sistemas de control de voz