A semantics for logic programming
In computer science, the well-founded semantics is a three-valued semantics for logic programming, which gives a precise meaning to general logic programs.
History.
The well-founded semantics was defined by Van Gelder, et al. in 1988. The Prolog system XSB implements the well-founded semantics since 1997.
Three-valued logic.
The well-founded semantics assigns a unique model to every general logic program. However, instead of only assigning propositions "true" or "false", it adds a third value "unknown" for representing ignorance.
A simple example is the logic program that encodes two propositions codice_1 and codice_2, and in which codice_1 must be true whenever codice_2 is not and vice versa:
a :- not(b).
b :- not(a).
neither codice_1 nor codice_2 are true or false, but both have the truth value unknown. 
In the two-valued stable model semantics, there are two stable models, one in which codice_1 is true and codice_2 is false, and one in which codice_2 is true and codice_1 is false.
Stratified logic programs have a 2-valued well-founded model, in which every proposition is either true or false. This coincides with the unique stable model of the program. The well-founded semantics can be viewed as a three-valued version of the stable model semantics.
Complexity.
In 1989, Van Gelder suggested an algorithm to compute the well-founded semantics of a propositional logic program whose time complexity is quadratic in the size of the program. As of 2001[ [update]], no general subquadratic algorithm for the problem was known.
References.
 ;templatestyles src="Reflist/styles.css" / ;