Predicate Logic, Nonmonotonic Rules and Priorities

Quotes taken from 'A Semantic Web Primer' (2004), by Grigoris Antoniou and Frank van Harmelen

(page 94, An axiomatic semantics for RDF and RDF Schema)

... we formalize the meaning of the modeling primitives of RDF and RDF Schema. Thus we capture the semantics of RDF and RDFS.

The formal language we use is predicate logic , universally accepted as the foundation of all (symbolic) knowledge representation. Formulas used in the formalization are referred to as axioms.

By describing the semantics of RDF and RDFS in a formal language like logic we make the semantics unambiguous and machine accessible. Also, we provide a basis for reasoning support by automated reasoners manipulating logical formulas.

(page 161, Nonmonotonic rules: Motivation and syntax)

... we turn our attention to nonmonotonic rule systems. So far (i.e. with monotonic rules), once the premises of a rule were proved, the rule could be applied and its head could be derived as a conclusion. In nonmonotonic rule systems, a rule may not be applied even if all premises are known because we have to consider contrary reasoning chains. In general, the rules we consider from now are called defeasible, because they can be defeated by other rules. To allow conflicts between rules, negated atomic formulas may occur in the head and the body of rules...

... To distinguish between defeasible rules and standard, monotonic rules, we use a different arrow:

p(X) => q(X)
r(X) => ¬q(X)

In this example, given also the facts

p(a)
r(a)

we conclude neither q(a) nor ¬q(a). It is a typical example of two rules blocking each other. This conflict may be resolved using priorities among rules. Suppose we knew somehow that the first rule is stronger than the second; then we could indeed derive q(a).

Priorities arise naturally in practice, and may be based on various principles:
- The source of one rule may be more reliable than the source of the second, or may even have higher priority. For example, in law, federal law preempts state law...
- One rule may be preferred over another because it is more recent.
- One rule may be preferred over another because it is more specific. A typical example is a general rule with some exceptions; in such cases, the exceptions are stronger than the general rule.

Specificity may often be computed based on the given rules, but the other two principles cannot be determined from the logical formalization. Therefore, we abstract from the specific prioritization principle used, and assume the existence of an external priority relation on the set of rules. To express the relation syntactically, we extend the rule syntax to include a unique label, for example,

r1: p(X) => q(X)
r2: r(X) => ¬q(X)

Then we can write

r1 > r2

to specify that r1 is stronger than r2.

We do not impose many conditions on >. It is not even required that the rules form a complete ordering. We only require the priority relation to be acyclic. That is, it is impossible to have cycles of the form

r1 > r2 > ... rn > r1

Note that priorities are meant to resolve conflicts among competing rules. In simple cases two rules are competing only if the head of one rule is the negation of the head of the other. But in applications it is often the case that once a predicate p is derived, some other predicates are excluded from holding...