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 HL,
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:
HL
= {0,suc(0),suc(suc(0),...,suci(0),...}
2.
La base de
Herbrand de L, denotada BL, es el conjunto de todos los ´átomos
que pueden formarse a partir de los predicados que ocurren en L y los términos
en HL.
Ejemplo La
base de Herbrand de L es:
BL = {nat(0),nat(suc(0)),...,nat(suci(0)),...}.
3.
Una estructura A para L es una estructura de Herbrand si su dominio es HL y, para cada símbolo
de función f de L y elementos t1 ...,tn de A, fA(t1,...,tn)
= f(t1,...,tn).
Para cada constante c en L, cA = c.
Ejemplo Una
estructura de Herbrand para L es:
A = hHL,0A,sucA,BLi,
donde 0A = 0 y sucA(t) = suc(t) para todo t ∈ HL.
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 HP. Asimismo, podemos hablar
de la base de Herbrand de P, denotada BP.
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:
HP
= {a,b,,f(a),f(b),f(f(a)),f(f(b)),f(f(f(a))),...}
BP = {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, BP, 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,
MP. El modelo MP se define como sigue:
MP = {A ∈ BP : P |= A}
Ejemplo El modelo mínimo del programa P es:
MP =
{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.
