Sintaxis y semántica de la programación lógica

Muchas implementaciones de programación lógica extienden la gramática anterior para permitir escribir hechos sin el :-, como por ejemplo:

r ( x ).

Muchos también permiten escribir relaciones 0-arias sin paréntesis, como por ejemplo:

p :- q .

Se trata simplemente de abreviaturas ( azúcar sintáctico ); no tienen ningún impacto en la semántica del programa.

El siguiente programa calcula la relación path, que es el cierre transitivo de la relación edge.

borde ( x , y ). borde ( y , z ). ruta ( A , B ) :- borde ( A , B ). ruta ( A , C ) :- ruta ( A , B ), borde ( B , C ).

Una regla se llama fundamental si todos sus átomos (cabeza y cuerpo) son fundamentales. Una regla fundamental R ₂ es una instancia fundamental de otra regla R ₁ si R ₂ es el resultado de una sustitución de constantes por todas las variables en R ₁ .

La base de Herbrand de un programa Datalog es el conjunto de todos los átomos básicos que se pueden crear con las constantes que aparecen en el programa. Una interpretación (también conocida como instancia de base de datos ) es un subconjunto de la base de Herbrand. Un átomo básico es verdadero en una interpretación I si es un elemento de I. Una regla es verdadera en una interpretación I si, para cada instancia básica de esa regla, si todos los átomos del cuerpo son verdaderos en I , entonces la cabeza de la regla también es verdadera en I.

Un modelo de Herbrand de un programa Datalog P es una interpretación I de P que contiene todos los hechos fundamentales de P y hace que todas las reglas de P sean verdaderas en I. La semántica de la teoría de modelos establece que el significado de un programa Datalog es su modelo de Herbrand mínimo (o, equivalentemente, la intersección de todos sus modelos de Herbrand) . ^{[ 4 ]}

Por ejemplo, este programa:

borde ( x , y ). borde ( y , z ). ruta ( A , B ) :- borde ( A , B ). ruta ( A , C ) :- ruta ( A , B ), borde ( B , C ).

tiene este universo Herbrand: x, y,z

y esta base de Herbrand: edge(x, x), edge(x, y), ..., edge(z, z), path(x, x), ...,path(z, z)

y este modelo minimalista de Herbrand: edge(x, y), edge(y, z), path(x, y), path(y, z),path(x, z)

Sea I el conjunto de interpretaciones de un programa Datalog P , es decir, I = P ( H ) , donde H es la base de Herbrand de P y P es el operador de conjunto potencia . El operador de consecuencia inmediata para P es la siguiente aplicación T de I a I : Para cada instancia básica de cada regla en P , si cada cláusula en el cuerpo está en la interpretación de entrada, entonces se agrega la cabeza de la instancia básica a la interpretación de salida. Esta aplicación T es monótona con respecto al orden parcial dado por la inclusión de subconjuntos en T. Por el teorema de Knaster-Tarski , esta aplicación tiene un punto fijo mínimo; por el teorema del punto fijo de Kleene, el punto fijo es el supremo de la cadena${\displaystyle T(\emptyset ),T(T(\emptyset )),\ldots ,T^{n}(\emptyset ),\ldots }$. El punto fijo mínimo de M coincide con el modelo mínimo de Herbrand del programa. ^{[ 5 ]}

La semántica de punto fijo sugiere un algoritmo para calcular el modelo mínimo de Herbrand: se parte del conjunto de hechos básicos del programa y, a continuación, se añaden repetidamente las consecuencias de las reglas hasta alcanzar un punto fijo. Este algoritmo se denomina evaluación ingenua .

Dado un programa P , un árbol de prueba de un átomo fundamental A es un árbol con una raíz etiquetada por A , hojas etiquetadas por átomos fundamentales de las cabezas de los hechos en P , y ramas con hijos.${\displaystyle A_{1},\ldots ,A_{n}}$etiquetados por átomos fundamentales G de tal manera que existe una instancia fundamental

G :- A1, ..., An.

de una regla en P. La semántica de la teoría de la demostración define el significado de un programa Datalog como el conjunto de átomos básicos que se pueden derivar de dichos árboles. Este conjunto coincide con el modelo mínimo de Herbrand. ^{[ 6 ]}

Podría interesar saber si un átomo fundamental en particular aparece o no en el modelo mínimo de Herbrand de un programa Datalog, quizás sin prestar mucha atención al resto del modelo. Una lectura descendente de los árboles de prueba descritos anteriormente sugiere un algoritmo para calcular los resultados de tales consultas ; dicha lectura informa el algoritmo de resolución SLD , que constituye la base para la evaluación de Prolog .

La semántica de Datalog también se ha estudiado en el contexto de puntos fijos sobre semianillos más generales . ^{[ 7 ]}

Un programa lógico con negación es estratificado cuando es posible asignar cada relación a algún estrato , de modo que si una relación R aparece negada en el cuerpo de una relación S , entonces R está en un estrato inferior al de S. [ ^{9 ] La} semántica de punto fijo y de teoría de modelos de Datalog se puede extender para manejar la negación estratificada, y se puede demostrar que dichas extensiones son equivalentes.

Muchas implementaciones de Datalog utilizan un modelo de evaluación ascendente inspirado en la semántica de punto fijo. Dado que esta semántica puede manejar la negación estratificada, varias implementaciones de Datalog implementan la negación estratificada.

Si bien la negación estratificada es una extensión común de Datalog, existen programas razonables que no pueden ser estratificados. El siguiente programa describe un juego de dos jugadores donde un jugador gana si su oponente no tiene movimientos: ^{[ 10 ]}

mover ( a , b ). ganar ( X ) :- mover ( X , Y ), no ganar ( Y ).

Este programa no está estratificado, pero parece razonable pensar que adebería ganar el juego.

La semántica de modelos estables define una condición para considerar estables ciertos modelos de Herbrand de un programa . Intuitivamente, los modelos estables son los "conjuntos posibles de creencias que un agente racional podría sostener, dado [el programa]" como premisas. ^{[ 11 ]}

Un programa con negación puede tener muchos modelos estables o ningún modelo estable. Por ejemplo, el programa

p :- no q . q :- no p .

tiene dos modelos estables${\displaystyle \{p\}}$,${\displaystyle \{q\}}$El programa de una sola regla

p :- no p .

no tiene modelos estables.

Todo modelo estable es un modelo Herbrand mínimo. Un programa Datalog sin negación tiene un único modelo estable, que coincide exactamente con su modelo Herbrand mínimo. La semántica de modelos estables define que un programa lógico con negación es su modelo estable, si existe exactamente uno. Sin embargo, puede ser útil investigar todos (o al menos varios) de los modelos estables de un programa; este es el objetivo de la programación de conjuntos de respuestas .