Semántica de los programas lógicos

La semántica da significado a los programas y nos permite describir formalmente lo que calculan. Hay tres maneras bien conocidas de dar significado o semántica a los programas lógicos: la semántica declarativa, la semántica operacional y la semántica denotacional (comúnmente llamada semántica de punto fijo). En esta sección presentamos algunas nociones y teoremas básicos relacionados a la semántica de los programas lógicos definidos.

Definición 2 : Sea L un lenguaje de primer orden.

1.        El universo de Herbrand de L, denotado H_L, es el conjunto de todos los términos de base que pueden formarse a partir de las constantes y los símbolos de función que ocurren en L.

Ejemplo Sea L = {0,suc,nat} donde 0 es una constante, suc es un símbolo de función de aridad 1 y nat es un predicado de aridad 1. En los próximos tres ejemplos nos referiremos a este lenguaje. El universo de Herbrand de L es:

H_L = {0,suc(0),suc(suc(0),...,sucⁱ(0),...}

2.        La base de Herbrand de L, denotada B_L, es el conjunto de todos los ´átomos que pueden formarse a partir de los predicados que ocurren en L y los términos en H_L.

              Ejemplo       La base de Herbrand de L es:

B_L = {nat(0),nat(suc(0)),...,nat(sucⁱ(0)),...}.

3.        Una estructura A para L es una estructura de Herbrand si su dominio es H_L y, para cada símbolo de función f de L y elementos t₁ ...,t_n de A, f^A(t₁,...,t_n) = f(t₁,...,t_n). Para cada constante c en L, c^A = c.

              Ejemplo       Una estructura de Herbrand para L es:

A = hH_L,0^A,suc^A,B_Li, donde 0^A = 0 y suc^A(t) = suc(t) para todo t ∈ H_L.

4.        Si Γ un conjunto de sentencias, un modelo de Herbrand de Γ es una estructura de Herbrand que es un modelo para Γ. Debido a que en los modelos de Herbrand la interpretación de las constantes y los símbolos de función son fijas, es posible identificar un modelo de Herbrand con un subconjunto de la base de Herbrand.

Consideremos un programa lógico P. P induce un lenguaje de primer orden donde las constantes, los símbolos de función y los predicados son, respectivamente, las constantes, los símbolos de función y los predicados que ocurren en P. Entonces, podemos hablar del universo de Herbrand de P, denotado H_P. Asimismo, podemos hablar de la base de Herbrand de P, denotada B_P.

Ejemplo        Sea P el siguiente programa:

p(a)← p(b)← q(a)← r(f(x))←p(x),q(x)

El universo y la base de Herbrand de P son, respectivamente:

H_P = {a,b,,f(a),f(b),f(f(a)),f(f(b)),f(f(f(a))),...}

B_P = {p(a),p(b),q(a),q(b),p(f(a)),p(f(b)),q(f(a)),p(f(b)),p(f(f(a))), p(f(f(b))),q(f(f(a)),q(f(f(b))...}

Semántica declarativa. Desde el punto de vista lógico, un programa P puede verse como una teoría lógica formada por las cláusulas del programa. Los modelos de Herbrand de esta teor´ıa son considerados los modelos del programa P. Por ejemplo, la base de Herbrand del programa P, B_P, es un modelo de P.

Entre las estructuras de Herbrand que son modelos de P, se destaca el que contiene exactamente los ´átomos que son consecuencia lógica de P. Este modelo corresponde al significado “entendido” o “estándar” del programa y es llamado el modelo mínimo de P, M_P. El modelo M_P se define como sigue:

M_P = {A ∈ B_P : P |= A}

Ejemplo         El modelo mínimo del programa P es:

M_P = {p(a),p(b),q(a),r(f(a))}

Semántica operacional. Esta definida por el proceso de inferencia utilizado para probar que un objetivo puede ser derivado del programa. En la próxima sección estudiaremos en detalle este punto.

Semántica denotacional. Esta semántica asigna significado a un programa asociándole una función sobre el dominio calculado por el programa. El significado viene dado entonces por el punto fijo de la función, si existe.