Semántica bien fundamentada

En informática , la semántica bien fundamentada es una semántica trivalente para la programación lógica , que otorga un significado preciso a los programas lógicos generales.

La semántica bien fundamentada fue definida por Van Gelder et al. en 1988. ^{[ 1 ] [ 2 ]} El sistema Prolog XSB implementa la semántica bien fundamentada desde 1997. ^{[ 3 ] [ 4 ]}

La semántica bien fundamentada asigna un modelo único a cada programa lógico general. Sin embargo, en lugar de simplemente asignar proposiciones verdaderas o falsas , añade un tercer valor desconocido para representar la ignorancia. ^{[ 1 ]}

Un ejemplo sencillo es el programa lógico que codifica dos proposiciones ay b, y en el que a debe ser verdadera siempre que bno lo sea y viceversa:

a :- no ( b ). b :- no ( a ).

Ni ani bson verdaderas ni falsas, pero ambas tienen un valor de verdad desconocido. En la semántica de modelos estables de dos valores , hay dos modelos estables, uno en el que aes verdadero y bes falso, y otro en el que bes verdadero y aes falso.

Los programas de lógica estratificada poseen un modelo bien fundado de dos valores, en el que cada proposición es verdadera o falsa. Esto coincide con el modelo estable único del programa. La semántica bien fundada puede considerarse una versión trivalente de la semántica del modelo estable . ^{[ 5 ]}

En 1989, Van Gelder propuso un algoritmo para calcular la semántica bien fundamentada de un programa de lógica proposicional cuya complejidad temporal es cuadrática en el tamaño del programa. ^{[ 6 ]} A partir de 2001, no se conocía ningún algoritmo subcuadrático general para el problema. ^{[ 7 ]}