8.2. The semantics of incomplete information#

In this section, we present a way to interpret not as a logical symbol rather than a meta-predicate. In this way, it can be assigned a declarative semantics of its own, without reference to procedural features like cut. The basic idea is to transform the given program into an intended (possibly indefinite) program, which explicitly captures the intended meaning of the original general program. We will see that the intended program is complete, in the sense that for every ground fact in the Herbrand base, either that fact or its negation is a logical consequence of the intended program. Consequently, the intended program will have exactly one model, which is taken to be the intended model of the original program. We will discuss two methods to construct a complete program. The first, simple method is called the Closed World Assumption; it is simple in the sense that it only works for definite clauses without negation. The second method is called Predicate Completion; it can handle general programs with negated literals in the body of clauses.

Informally, the Closed World Assumption (CWA) states that everything that is not known to be true, must be false. Under the CWA, we need not say that something is not true: we simply say nothing about it. This is motivated by the assumption that, in general, there are many more false statements that can be made than true statements. Let us state the CWA more precisely. It suffices to know the truth or falsity of every ground atom in the Herbrand base, since this results in a single model from which the truth or falsity of any clause can be determined. Saying that such a ground atom A is false, is the same as saying that :-A is true. Thus, if \(P\) is a program and \(B\) is its Herbrand base, then we define the CWA-closure \(CWA(P)\) of \(P\) as

\[ CWA(P) = P \cup \{ \texttt{:-A} \; | \; \texttt{A} \in B \; \text{and} \; P \nvDash \texttt{A} \} \]

We refer to \(CWA(P)-P\) as the CWA-complement of \(P\). \(CWA(P)\) is the intended program according to the Closed World Assumption.

For instance, if \(P\) is the program

likes(peter,S):-student_of(S,peter).
student_of(paul,peter).

then the ground atoms which are logical consequences of \(P\) are likes(peter,paul) and student_of(paul,peter). The remaining ground atoms in the Herbrand base are not known to be true, and we add their negation to obtain \(CWA(P)\):

likes(peter,S):-student_of(S,peter).
student_of(paul,peter).
:-student_of(paul,paul).
:-student_of(peter,paul).
:-student_of(peter,peter).
:-likes(paul,paul).
:-likes(paul,peter).
:-likes(peter,peter).

Note that \(CWA(P)\) has only one model:

{ student_of(paul,peter), likes(peter,paul) }

That is, \(CWA(P)\) is a complete program, assigning true or false to every ground atom in the Herbrand base. While our original program had several, alternative models, the extended program has exactly one model. This model is then declared to be the intended model of the original program.

Exercise 8.2 #

Give the models of \(P\).

If we add the clause \(C =\) likes(paul,X) to \(P\), we find that \(CWA(P \cup \{ C \} )\) is

likes(peter,S):-student_of(S,peter).
student_of(paul,peter).
likes(paul,X).
:-student_of(paul,paul).
:-student_of(peter,paul).
:-student_of(peter,peter).
:-likes(peter,peter).

This example shows that extending the set of clauses results in a smaller CWA-complement, just as we would expect from a non-monotonic form of reasoning.

The CWA is limited to definite clauses: if it is applied to indefinite clauses, the resulting CWA-closure will be inconsistent. For instance, let \(P\) be

bird(tweety).
flies(X);abnormal(X):-bird(X).

then the Herbrand base is

{ bird(tweety), abnormal(tweety), flies(tweety) }

of which only the first ground atom follows logically from \(P\). Thus, \(CWA(P)\) is

bird(tweety).
flies(X);abnormal(X):-bird(X).
:-flies(tweety).
:-abnormal(tweety).

which is inconsistent: it does not have a model, since the first two clauses require that at least one of abnormal(tweety), flies(tweety) is true. Since the Closed World Assumption is unable to handle indefinite clauses, it is equally unable to handle general clauses with negated literals in the body. The CWA originates from the field of databases, where all information is stored in the form of ground atoms, so that indefinite (disjunctive) information does not occur.

A more sophisticated way to construct complete programs is called Predicate Completion. The basic idea of Predicate Completion is to view each clause as part of the definition of a specific predicate. For instance, a clause like

likes(peter,S):-student_of(S,peter)

is seen as part of the definition of the likes predicate. Such a clause gives values for X and Y in which likes(X,Y) is true. In other words, it belongs to the if part of the definition: ‘\(X\) likes \(Y\) if …’. This definition can be completed by adding the only-if parts, resulting in a full definition: ‘\(X\) likes \(Y\) if and only if …’. Such a full definition is most easily expressed in Predicate Logic. For instance, the above clause could be completed to the following full definition:

\[ \forall \texttt{X} \forall \texttt{S} : \texttt{likes(X,S)} \leftrightarrow \texttt{X=peter} \land \texttt{student_of(S,peter)} \]

In words: ‘\(X\) likes \(S\) if and only if \(X\) is Peter, and \(S\) is a student of Peter’, that is, Peter is the only one who likes people, and the people Peter likes are his students, and nobody else. We can translate this formula back to clausal form (see Section 2.5), which yields a set of clauses

likes(peter,S):-student_of(S,peter).
X=peter:-likes(X,S).
student_of(S,peter):-likes(X,S).

The first clause was originally given; the other two are added by the Completion process.

In general, the procedure for completing a predicate definition consists of the following steps (a Prolog program which performs Predicate Completion is given in Section 11.2 (appendix)):

  1. make sure that every argument of the predicate in the head of each clause is a distinct variable, by adding literals of the form Var=Term to the body;

  2. if there are several clauses, combine them into a single formula with a disjunctive body (this is possible since after step 1 each clause has the same head);

  3. turn the implication in this formula into an equivalence.

Step 3 is the actual Completion step; the first two steps are preparatory.

As an example, consider the following set of clauses:

likes(peter,S):-student_of(S,peter).
likes(X,Y):-friend(Y,X).

The first step results in the clauses

likes(X,S):-X=peter,student_of(S,peter).
likes(X,Y):-friend(Y,X).

In the second step, these clauses are combined into a single formula in Predicate Logic:

\[ \forall \texttt{X} \forall \texttt{Y} : \texttt{likes(X,Y)} \leftarrow (( \texttt{X=peter} \land \texttt{student_of(Y,peter)}) \lor \texttt{friend(Y,X)}) \]

This is a formula which is logically equivalent with the original set of clauses1. The Completion step is done by turning the implication into an equivalence.

Care should be taken if one of the original clauses contains variables in the body which do not occur in the head, for example

ancestor(X,Y):-parent(X,Y).
ancestor(X,Y):-parent(X,Z),ancestor(Z,Y).

Here, the second clause is equivalent with the formula

\[ \forall \texttt{X} \forall \texttt{Y} \forall \texttt{Z}: \texttt{ancestor(X,Y)} \leftarrow ( \texttt{parent(X,Z)} \land \texttt{ancestor(Z,Y)}) \]

but also with the formula

\[ \forall \texttt{X} \forall \texttt{Y} : \texttt{ancestor(X,Y)} \leftarrow ( \exists \texttt{Z} : \texttt{parent(X,Z)} \land \texttt{ancestor(Z,Y)}) \]

For this reason, variables which occur in the body of a clause but not in the head are often called existential variables. When performing Predicate Completion we must use the second formula, with explicit existential quantification in the body, because we want all clauses to have exactly the same head. The two original clauses are thus converted to

\[ \forall \texttt{X} \forall \texttt{Y} : \texttt{ancestor(X,Y)} \leftarrow ( \texttt{parent(X,Y)} \lor ( \exists \texttt{Z} : \texttt{parent(X,Z)} \land \texttt{ancestor(Z,Y)})) \]

A program P consisting of several predicate definitions is completed by completing each predicate definition separately; for those predicates P(X1,...,Xn) which occur in the body of clauses but are themselves not defined, a clause :-P(X1,...,Xn) is added. The resulting set of clauses is denoted \(Comp(P)\). For instance, if \(P\) is

likes(peter,S):-student_of(S,peter).
student_of(paul,peter).

then \(Comp(P)\) is

likes(peter,S):-student_of(S,peter).
X=peter:-likes(X,S).
student_of(S,peter):-likes(X,S).
student_of(paul,peter).
X=paul:-student_of(X,Y).
Y=peter:-student_of(X,Y).

It is easily checked that the completed program has only one model:

{ student_of(paul,peter), likes(peter,paul) }

and is thus complete. As we saw earlier, this is also the single model of \(CWA(P)\), which means that, in this case, \(Comp(P)\) and \(CWA(P)\) are logically equivalent. This is true in general, provided \(P\) is a set of definite clauses.

Predicate Completion extends the Closed World Assumption by also being able to handle programs containing general clauses, like

bird(tweety).
flies(X):-bird(X),not abnormal(X).

Predicate Completion produces the following formulas:

\[\begin{align*} \forall \texttt{X} &: \texttt{bird(X)} \leftrightarrow \texttt{X=tweety} \\ \forall \texttt{X} &: \texttt{flies(X)} \leftrightarrow ( \texttt{bird(X)} \land \neg \texttt{abnormal(X)}) \\ \forall \texttt{X} &: \neg \texttt{abnormal(X)} \end{align*}\]

In words: Tweety is the only bird, something flies if and only if it is a bird which is not abnormal, and there are no abnormal birds. The last formula is added because there is no predicate definition for abnormal. The only model of this set of formulas is

{ bird(tweety), flies(tweety) }

However, there are also general clauses which Predicate Completion cannot handle. One such a clause is the following:

friendly(peter):-not friendly(peter).

This clause states that the assumption that Peter is not friendly leads to a contradiction; therefore Peter must be friendly, and friendly(peter) should be a logical consequence of the intended program associated with this clause. Predicate Completion will construct the formula

\[ \forall \texttt{X} : \texttt{friendly(X)} \leftrightarrow ( \texttt{X=peter} \land \neg \texttt{friendly(peter)} ) \]

It is easy to see that this formula is inconsistent.

Admittedly, the above clause is a bit awkward, since it is logically equivalent with

friendly(peter).

However, there are many programs which exhibit the same problem. Basically, the problem is caused by ‘recursion through negation’. For instance, the completion of the following two clauses is also inconsistent:

wise(X):-not teacher(X).
teacher(peter):-wise(peter).

These clauses say ‘anybody who is not a teacher is wise’ and ‘if Peter is wise, he is a teacher’. Assuming that Peter is not a teacher leads to a contradiction; therefore, he must be a teacher (and he may or may not be wise). However, Predicate Completion leads to inconsistencies. A stratified program is a program without recursion through negation. One can prove that for stratified programs, Predicate Completion never results in inconsistencies.

Exercise 8.3 #

Apply Predicate Completion to this program.

1

Ground literals of the form \(t_1 = t_2\) are true in an interpretation if and only if \(t_1\) and \(t_2\) are the same ground term. Thus, the predicate = (which represents, as usual, syntactical identity) is not explicitly represented in a model.