Concepts of Programming Languages

754 Chapter 16 Logic Programming Languages

16.7.2 The Closed-World Assumption

The nature of Prolog’s resolution sometimes creates misleading results. The

only truths, as far as Prolog is concerned, are those that can be proved using its

database. It has no knowledge of the world other than its database. When the

system receives a query and the database does not have information to prove the

query absolutely, the query is assumed to be false. Prolog can prove that a given

goal is true, but it cannot prove that a given goal is false. It simply assumes that,

because it cannot prove a goal true, the goal must be false. In essence, Prolog

is a true/fail system, rather than a true/false system.

Actually, the closed-world assumption should not be at all foreign to you—

our judicial system operates the same way. Suspects are innocent until proven

guilty. They need not be proven innocent. If a trial cannot prove a person

guilty, he or she is considered innocent.

The problem of the closed-world assumption is related to the negation

problem, which is discussed in the following subsection.

16.7.3 The Negation Problem

Another problem with Prolog is its difficulty with negation. Consider the fol-

lowing database of two facts and a relationship:

parent(bill, jake).

parent(bill, shelley).

sibling(X, Y) :- (parent(M, X), parent(M, Y).

Now, suppose we typed the query

sibling(X, Y).

Prolog will respond with

X = jake

Y = jake

Thus, Prolog “thinks” jake is a sibling of himself. This happens because

the system first instantiates M with bill and X with jake to make the first

subgoal, parent(M, X), true. It then starts at the beginning of the database

again to match the second subgoal, parent(M, Y), and arrives at the instan-

tiations of M with bill and Y with jake. Because the two subgoals are satis-

fied independently, with both matchings starting at the database’s beginning,

the shown response appears. To avoid this result, X must be specified to be a

sibling of Y only if they have the same parents and they are not the same.

Unfortunately, stating that they are not equal is not straightforward in Prolog,

as we will discuss. The most exacting method would require adding a fact for

every pair of atoms, stating that they were not the same. This can, of course,

cause the database to become very large, for there is often far more negative