logic programming Logic programming is a programming paradigm which is largely based on formal logic Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of log ...

, the well-founded semantics is one definition of how we can make conclusions from a set of logical rules. In logic programming, we give a computer a set of facts, and a set of "inference rules" about how these facts relate. There are several different ways that we might want the computer to apply these rules; the well-founded semantics is one of these ways.

History

The well-founded semantics was defined by Van Gelder, et al. in a 1991 paper.

Relations to other models

The well-founded semantics can be viewed as a three-valued version of the stable model semantics.Przymusinski, Teodor.
Well-founded Semantics Coincides with Three-Valued Stable Semantics
'. Fundamenta Informaticae XIII pp. 445-463, 1990. Instead of only assigning

proposition In logic and linguistics, a proposition is the meaning of a declarative sentence. In philosophy, "meaning" is understood to be a non-linguistic entity which is shared by all sentences with the same meaning. Equivalently, a proposition is the no ...

s ''true'' or ''false'', it also allows for a value representing ignorance. For example, if we know that


Specimen A is a moth if specimen A does not fly during daylight.

but we do not know whether or not specimen ''A'' flies during the day, the well-founded semantics would assign the proposition ``specimen A is a moth`` the value ''bottom'' which is neither ''true'' nor ''false''.

Applications

The well-founded semantics is also a way of making safe

inference Inferences are steps in reasoning, moving from premises to logical consequences; etymologically, the word '' infer'' means to "carry forward". Inference is theoretically traditionally divided into deduction and induction, a distinction that ...

s in the presence of contradictory data such as noisy data, or data acquired from different experts who may posit differing opinions. Many two-valued semantics simply won't consider such a problem state workable. The well-founded semantics, however, has a built-in mechanism to circumvent the presence of the contradictions and proceeds to derive as many two-valued facts as possible, even though some consequences may remain unknown.

Complexity and algorithms

The fastest known algorithm to compute the WF-Semantics in general, is of quadratic complexity.

References

Logic programming {{formalmethods-stub