next up previous
Next: A Legal Reasoning Up: Well-Founded Semantics for Extended Previous: Well-Founded Semantics for

Adding Preferences

In order to handle preferences we need to be able to express preference information explicitly. Since we want to do this in the logical language we have to extend the language. We do this in two respects:

  1. we use a set of rule names N together with a naming function name to be able to refer to particular rules,
  2. we use a special (infix) symbol that can take rule names as arguments to represent preferences among rules.
Intuitively, where and are rule names means the rule with name is preferred over the rule with name .gif

A prioritized logic program is a pair where R is a set of rules and name a naming function. To make sure that the symbol has its intended meaning, i.e., represents a transitive and anti-symmetric relation, we assume that R contains all ground instances of the schemata


where are parameters for names. Note that in our examples we won't mention these rules explicitly.

The function name is a partial injective naming function that assigns a name to some of the rules in R. Note that not all rules do necessarily have a name. The reason is that names will only play a role in conflict resolution among defeasible rules, i.e., rules with weakly negated preconditions. For this reason names for strict rules, i.e., rules in which the symbol does not appear, won't be needed. A technical advantage of leaving some rules unnamed is that the use of rule schemata with parameters for rule names does not necessarily make programs infinite. If we would require names for all rules we would have to use a parameterized name for each schema and thus end up with an infinite set N of names.

In our examples we assume that N is given implicitly. We also define the function name implicitly. We write:

to express that .

For convenience we will simply speak of programs instead of prioritized logic programs whenever this does not lead to misunderstandings.

Before introducing new definitions we would like to point out how we want the new explicit preference information to be used. Our approach follows two principles:

  1. we want to extend well-founded semantics, i.e. we want that every -conclusion remains a conclusion in the prioritized approach,
  2. we want to use preferences to solve conflicts whenever this is possible without violating principle 1.
Let us first explain what we mean by conflict here. Rules may be conflicting in several ways. In the simplest case two rules may have complementary literals in their heads. We call this a type-I conflict. Conflicts of this type may render the set of well-founded conclusions inconsistent, but do not necessarily do so. If, for instance, a precondition of one of the rules is not derivable or a rule is defeated the conflict is implicitly resolved. In that case the preference information will simply be neglected. Consider the following program :

There is a type-I conflict between and . Although the explicit preference information gives precedence to we want to apply here to comply with the first of our two principles. Technically, this means that we can apply a preferred rule r only if we are sure that r's application actually leads to a situation where literals defeating r can no longer be derived.

The following two rules exhibit a different type of conflict:

The heads of these rules are not complementary. However, the application of one rule defeats the other and vice versa. We call this a direct type-II conflict. Of course, in the general case the defeat of the conflicting rule may be indirect, i.e. based on the existence of additional rules. We say and are type-II conflicting wrt. a set of rules R iff
  1. neither defeats nor ,
  2. defeats , and
  3. defeats
Here R + r abbreviates . A direct type-II conflict is thus a type-II conflict wrt. the empty set of rules. The rule sets R that have to be taken into account in our well-founded semantics based approach are subsets of the rules which are undefeated by the set of literals known to be true. Note that the two types of conflict are not disjoint, i.e. two rules may be in conflict of both type-I and type-II. Consider the following program , a slight modification of :

Now we have a type-II conflict between and (more precisely, a direct type-II and a type-I conflict) that is not solvable by the implicit mechanisms of well-founded semantics alone. It is this kind of conflict that we try to solve by the explicit preference information. In our example will be used to derive . Note that now the application of defeats and there is no danger that a literal defeating might become derivable later. Generally, a type-II conflict between and (wrt. some undefeated rules of the program) will be solved in favour of the preferred rule, say , only if applying excludes any further possibility of deriving an -defeating literal.

Note that every type-I conflict can be turned into a direct type-II conflict by a (non-equivalent!) rerepresentation of the rules: if each conflicting rule r is replaced by its seminormal formgif then all conflicts become type-II conflicts and are thus amenable to conflict resolution through preference information.

After this motivating discussion let us present the new definitions. Our treatment of priorities is based on a weakening of the notion of X-safeness. In Sect. 2 we considered a rule r as X-safe whenever there is no proof for a literal defeating r from the monotonic counterparts of X-undefeated rules. Now in the context of a prioritized logic program we will consider a rule r as X-safe if there is no such proof from monotonic counterparts of a certain subset of the X-undefeated rules. The subset to be used depends on the rule r and consists of those rules that are not ``dominated'' by r. Intuitively, is dominated by r iff is (1) known to be less preferred than r and (2) defeated when r is applied together with rules that already have been established to be X-safe. (2) is necessary to make sure that explicit preference information is used the right way, according to our discussion of .

It is obvious that whenever there is no proof for a defeating literal from all X-undefeated rules there can be no such proof from a subset of these rules. Rules that were X-safe according to our earlier definition thus remain to be X-safe. Here are the precise definitions:

Note that is monotonic in both X and Y. We can now define the X-safe rules inductively:

Note that X-safeness is obviously monotonic in X. Based on this notion we introduce a new monotonic operator :

As before we define the (prioritized) well-founded conclusions of P, denoted , as the least fixpoint of . If a program does not contain preference information at all, i.e., if the symbol does not appear in R, the new semantics coincides with since in that case no rule can dominate another rule. In the general case, since the new definition of X-safeness is weaker than the one used earlier in Sect. 2 we may have more X-safe rules and for this reason obtain more conclusions than via . The following result is thus obvious:

From this and the monotonicity of both operators it follows immediately that .gif

Well-founded semantics has sometimes been criticized for being too weak and missing intended conclusions. The proposition shows that we can strengthen the obtained results by adding adequate preference information.

As a first simple example let us consider the following program :

We first apply to the empty set. Besides the instances of the transitivity and anti-symmetry schema that we implicitly assume only is in . We thus obtain

We next apply to . Since we have . since does not defeat and we obtain

Further iteration of yields no new literals, i.e. is the least fixpoint. Note that c is not a conclusion under the original well-founded semantics.

We next show that the programs and discussed earlier are handled as intended. Here is :

Since does not defeat this rule is safe from the beginning, i.e., . yields

which is also the least fixpoint. The explicit preference does not interfere with the implicit one, as intended.

The situation changes in where the first rule in is replaced by

The new rule is not in since it is defeated by the consequence of and is not dominated by . yields

Now since dominates wrt. and the empty set of rules. We thus conclude as intended. The least fixpoint is

In [4] we used an example to illustrate the possible non-existence of extensions in our earlier approach. This example involved two normal defaults each of which had the conclusion that the other one is to be preferred. The prioritized logic programming representation of this example is the following:

It is straightforward to verify that the set of well-founded conclusions for this example is empty.

next up previous
Next: A Legal Reasoning Up: Well-Founded Semantics for Extended Previous: Well-Founded Semantics for

Gerd Brewka
Thu Feb 8 10:26:15 MET 1996