Well-founded semantics
Encyclopedia
In logic programming
, 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.
. Instead of only assigning proposition
s true or false, it also allows for a value representing ignorance.
For example, if we know that
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.
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 in the best way that it can.
Logic programming
Logic programming is, in its broadest sense, the use of mathematical logic for computer programming. In this view of logic programming, which can be traced at least as far back as John McCarthy's [1958] advice-taker proposal, logic is used as a purely declarative representation language, and a...
, 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.
Relations to other models
The well-founded semantics can be viewed as a three-valued version of the stable model semanticsStable model semantics
The concept of a stable model, or answer set, is used to define a declarative semantics for logic programs with negation as failure. This is one of several standard approaches to the meaning of negation in logic programming, along with program completion and the well-founded semantics...
. Instead of only assigning proposition
Proposition
In logic and philosophy, the term proposition refers to either the "content" or "meaning" of a meaningful declarative sentence or the pattern of symbols, marks, or sounds that make up a meaningful declarative sentence...
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 inferenceInference
Inference is the act or process of deriving logical conclusions from premises known or assumed to be true. The conclusion drawn is also called an idiomatic. The laws of valid inference are studied in the field of logic.Human inference Inference is the act or process of deriving logical conclusions...
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 in the best way that it can.