Reasoning with logically inconsistent information has been studied by a number of writers ( Bel77a, KL89, GS95). In this paper we go beyond this work by doubly generalize the idea of reasoning with logically inconsistent information. The assignment of a truth value to a sentence constrains as well as determines the assignment of a truth value to its logical negation. Indeed, it does the former by doing the latter. But, conceptually, we can seperate out the former role of negation and generalize it. Thus, we can consider two sentences p and q not necessarily logically related, and specify for whatever reason, not just because of logical inconsistency among them, that if one is true the other cannot be true (they constrain each other's truth value), but if one is false, it does not determine the truth value of the other. In this case we say that the two sentences contest each other. In the context of deductive databases, denial integrity constraints play precisely this role. The constraint <-- p, q says that both p and q cannot be true. Of course, if we interpret this constraint using two-valued logic, then the truth of p not only constrains the truth value of q (i.e., q cannot be true), but also determines that q must be false. But in a multi-valued logic constraining the truth value of q does not determine it. In this paper we generalize reasoning with inconsistent information using a four-valued logic.
The second generalization of reasoning with inconsistent information consists in allowing that a sentence p might contest a sentence q without q contesting p. In this case too there is a conflict between p and q, but it is different from the case where p and q contest each other. In this way reasoning with logically inconsistent information is generalized into reasoning with contested information.
Another important respect in which the proposed work goes beyond the work on reasoning with logically inconsistent information is that we permit the reasoner to include preferences among conflicting statements. A reasoner may prefer to believe statement p over statement q in a conflict. Such a preference means that if the reasoner had to choose only between these two statements, she would choose p instead of q. But, since p may be in several conflict points, this preference does not mean that she in fact keeps p and throws out q. Our framework shows how to reason with a set of such preferences and conflicts.
It is well accepted that logic programming provides a declarative framework for representing knowledge and a mechanism for drawing inferences from this knowledge. Hence, we choose to conduct this investigation in the context of logic programming. Our work can also be viewed as a way of extending the logic programming paradigm by including in a logic program statements about which information contests which information (we call such statements contestations) and by including the a reasoner's preferences among contesting information.
A three-valued logic (Kl50, Prz90), with unknown or undefined as the third value, would assign both p and q this third value and, hence, regard p or q as unknown. A four-valued logic, as in Bel77a and Fit93, would assign the over-determined truth-value to both p and q. Hence, depending on the definition of satisfaction, it would entail both p and q or would not entail p or q. Every model of the theory assigns p the same truth-value it assigns to q. No model theory with this feature can entail p or q without entailing both p and q. In this work we propose a four-valued logic that does not have this drawback.
In the following, we propose C4 a four-valued semantics for LP + C + P where LP is a normal, logic program and C is a set of contestations and P is a set of preferences. We restrict our discussion to fully ground logic programs.
We propose a four-valued logic with the truth values, V = {T, CT, CF, F}. Here, T and F have their usual meanings, but intuitively CT and CF mean contested truth and contested falsehood. We define a one-to-one mapping between members of V and members of N = {1, 3/4, 1/4, 0} thus:
An interpretation I for LP is a mapping from Atoms(LP) to V or equivalently to N. We informally extend this mapping to the clauses of the language (assumed to be fixed by Atoms(LP) by letting I (not a) = 1 - I(a) and I (a & b) = min( I(a), I(b)) and I (a or b) = max( I(a), I(b)). Furthermore, we stipulate that I(a <-- b ) = 1 if I (a) is greater than or equal to I(b), otherwise I(a <-- b ) = I (a)
Given a set of literals {a_1,...,a_n} and an interpretation
I, we use
I {a_1,...,a_n} as shorthand for
{I (a_1),..., I (a_n)}
For the purposes of the model theory of logic programs, we envisage the program LP to be augmented by the atoms true and false. It is assumed that true evaluates to T and false evaluates to F in any interpretation. We also assume that any clause with an empty body has true as its body. For each atom in Atoms(LP) such that there is no clause in LP with that atom in the head, we add a clause with that atom as head and false as body. It should be clear in the following that this augmentation makes no difference to the actual semantics attributed to a logic program.
Definition 1
We say that an interpretation I satisfies a ground clause C if
C is not false in that interpretation.
In other words,
I satisfies C if either I (head(C)) > 0 or
I (body(C)) = 0.
Our notion of satisfaction is one way of generalizing the classical
notion which says that a clause is satisfied by an interpretation
if it is true, or equivalently, if it is not false in that
interpretation.
However, consider LP = {p <-- p} and an interpretation I such that I (p) = 1. In this case, the assignment of 1 to p is supported in terms of itself, which is supported in terms of itself, and so on. That is, the assignment of 1 to p does not seem well-supported. Hence, we introduce the following definition.
Definition 2
A model I of LP is a well supported model if
there exists a strict well-founded partial ordering << on the
atoms in Atoms(LP) such that for any atom a in Atoms(LP)
such that
0 < I (a)
there exists a clause C in LP such that
I (a) <= min(I (body(C))) where
head(C) = a and b << a for every b in posbody(C)
We assume that in any such well-founded ordering true
is less than any other atom.
In this definition, the well-founded ordering << ensures that the assignment of a truth-value to an atom is not justified in terms of itself and that the assignment has a finite justification in terms of the program. This definition is a four-valued generalization of the definition of a well-supported two-valued model in Fage91.
Definition 3
Let a and b be any atoms in Atoms(LP) a
contests b
(written as a ~% b
is satisfied by an interpretation I of LP if, and only if,
if I (a) is at least CT then I (b) is at most CF
Definition 4
An interpretation is a model of LP + I if it satisfies all the
clauses of LP and all the contestations in C
Example 1
Let LP = {a <--; b <-- } Let C = {a ~% b; b ~% a}. Then,
the models of LP + C are
The truth value of a noncontested clause in an interpretation depends in the standard way on the truth values of the atoms in the clause and the meaning assigned to negation, implication and conjunction. The truth value of a contested clause however is affected by the truth value of its contestor. If the truth value of the contestor is at least CT then we know the truth value of its head can be at most CF regardless of the truth value of the body of the clause. That is, if the contestor of the head of a clause evaluates to at least CT then the truth value of the body cannot play any role in determining the truth value of that clause. Thus, in evaluating the truth value of a contested clause in an interpretation, if the contestor evaluates to at least CT we must disregard the truth value of the body and assign that clause the value T if its head evaluates to at most CF and otherwise assign it the value F However if the contestor evaluates to at most CF then it does not in any way constrain the truth value of the head of a contested clause and in this case the normal rules of evaluation apply.
Let Truth( I) denote the set of atoms that are assigned either CT or
T by the interpretation I.
Let I be a well-supported model of LP + C
and let X be a
set of ground atoms. Then, Dep( X, I) denotes all the members of
Truth( I) which
become unsupported in any mapping I' such that the only difference
between I and I' is that I' assigns at most CF
to members of X.
Intuitively, Dep( X, I)
are those atoms whose status as members of
Truth( I)
depends on the status of X in I.
By Effect(X, I ) we mean X unioned with Dep( X, I). Thus, by Effect(X, I ) we mean all those atoms that will be demoted from the status of the Truth in I if X is demoted from the status of Truth.
When LP + C is augmented with a preference x Pref y (x is preferred to y) where x and y both belong to Atoms(LP) we take this preference as inducing an ordering among the models of LP + C. We say that I1 [= I2 by x Pref y if
The idea here is that x Pref y can make I1 less preferable than I2 only if, setting aside Effect(y, I1 ) and Effect(x, I2 ) the Truth content of I1 is a subset of the Truth content of I2.
Given a set of preferences P, we say that I1 [= I2 by P if there is a preference P in P such that I1 [= I2 by P. We say that I1 [ I2 by P if I1 [= I2 by P and not I2 [= I1 by P.
I1 is a model of LP + C + P if it is a model of LP + C and there is no model I2 of LP + C such that I1 [= I2 by P.
Example 2
Let LP and C be as in Example 1. There we saw that
LP + C has five models.
Let P = { a Pref b}. The models of
LP + C + P are I1, I2, and
I5.
Definition 5
Let I1 and I2 be two interpretations of LP + C + P.
Then,
I1 <= I2 in terms of LP + C + P
if, and only if,
I1(R) <= I2(R)
for every
clause R in LP
Given a set of interpretations S we say that an interpretation I1 is {\em maximal with respect to LP + C + P in S if there is no interpretation I2 in S such that I1 < I2 in terms of LP + C + P.
According to C4, the canonical models of LP + C + P are the clausally maximal models among the preferred models among the well-supported models of LP which satisfy all the contestations in C.
Thus, to determine the canonical models of LP + C + P we first determine all the well-supported models of LP. This is done without bringing in any of the contestations. Second, from these models we select those which satisfy all the contestations. Thirdly, we induce an ordering among these models in terms of the preferences. Then we select the preferred models in terms of this ordering. Finally, we choose as canonical those models which are maximal among the preferred models. In determining the maximal models recall that we assume that a contested clause evaluates to T if the head of the clause evaluates to CF and the contestor of the head evaluates to at least CT.
Example 3
As in Example 1 and 2 above, let LP = {a <--; b <-- } and let
C = {a ~% b; b ~% a}. Furthermore, let
P = {a Pref b}. Then, as seen in Example 1,
the preferred models are
I1 , I2 and I5 . But the only canonical model of
LP + C + P
is I1.
Definition 6
LP + C + P
strongly entails a literal p under C4
if, and
only if, p evaluates to T in all the canonical models of
LP + C + P.
LP + C + P
weakly entails a literal p under C4
if, and only if, p evaluates to at least
CT in all the canonical models of LP + C + P
It is clear that if LP + C + P strongly entails p then it weakly entails p
In the case where C = {} and P = {} the canonical models of LP + C + P = LP are simply the clausally maximal models among the well-supported models of LP. Thus, C4 provides a new semantics for normal logic programs. It is clear that the definitions of weak and strong entailment carry over to this case. In Pra96 we have shown that C4 subsumes both the two-valued stable model semantics (GL88) and the well-founded semantics for normal logic programs.
We can now answer the question we started out with: What should be the canonical models of LP + IC where IC is a set of integrity constraints. The canonical models of LP + IC are the clausally maximal, well-supported models of LP in which each member of IC evaluates to at least CT It is evident that in terms of the model theory suggested here, if LP = {a <--; b <-- } and IC = {<-- a, b} then LP + IC entails a or b.
We are in the early stages of devising a proof procedure for ground logic programs with contested information and preferences.
We envisage contested reasoning with preferences to be useful not only in logic programming, but also in formalizing nonmonotonic reasoning, belief revision, and legal reasoning. It can also be useful in integrating information from different sources and in query processing for federated or multi knowledge bases.