Prolog Programming for AI - Chapter 5 Notes and Exercises (5.3 ~ 5.4)

Posted on | Post modified | In , ,

Negation as failure

‘Mary likes all animals but snakes’. How can we say this in Prolog? It is easy to express one part of this statement: Mary likes any X is X is an animal. This is in Prolog: likes(mary, X) :- animal(X).

But we have to exclude snakes. This can be done by using a different formulation:

If X is a snakes then Mary likes X is not true.

Otherwise if X is an animal then Mary likes X.

That something is not true can be said in Prolog by using a special goal, fail, which always fails, thus forcing the parent goal to fail. The above formulation is translated into Prolog, using fail, as follows:

1
2
3
4
likes(mary, X) :-
    snakes(X), !, fail.
likes(mary, X) :-
    animal(X).

or 

1
2
3
likes(mary, X) :-
    snakes(X), !, fail;
    animal(X).

We can use the same idea to define the relation different(X, Y), which is true if X and Y are different. But what is ‘different’? ‘different’ can be understood in several ways:

  • X and Y are not literally the same;
  • X and Y do not match;
  • the values of arithmetic expressions X and Y are not equal.

Now, let us choose here that X and Y are different if they do not match. The key to saying this in Prolog is:

If X and Y match then different(X, Y) fails,

Otherwise different(X, Y) succeeds.

We again use the cut and fail combination:

1
2
different(X, X) :- !, fail.
different(X, Y).

or

1
2
3
different(X, Y) :-
   X = Y, !, fail;
   true.              % true is a goal that always succeeds.

We will now define the not relation as follows:

If Goal succeeds then not(Goal) fails,

Otherwise not(Goal) succeeds.

This definition can be written in Prolog as:

1
2
3
not(P) :-
    P, !, fail;
    true.

Assume that not is a built-in Prolog procedure

We will also assume that not is defined as a prefix operator, so that we can also write the goal

not(snake(X)) as not snake(X)

What if some particular Prolog implementation does not support this notation?

We can always define not ourselves.

Examples with not:

1
2
3
likes(mary, X) :-
    animal(X),
    not snake(X).
1
2
different(X, Y) :-
    not (X = Y).
1
2
3
4
5
6
7
8
9
10
% tennis classification program
class(X, fighter) :-
    beat(X, _),
    beat(_, X).
class(X, winner) :-
    beat(X, _),
    not beat(_, X).
class(X, sportsman) :-
    beat(_, X),
    not beat(X, _).

Exercises

  1. Given two lists, Candidates and RuledOut, write a sequence of goals (using member and not) that will through backtracking find all the items in Candidates that are not in RuledOut.
1
member(Item, Candidates),not member(Item, RuledOut).

or

1
2
3
4
5
6
7
8
9
10
11
12
rule_out(L, [], L).
rule_out([], _, []).
rule_out([X | CandidatesL], RuledOut, [X|Res]) :-
    not(member(X, RuledOut)),!,
    rule_out(CandidatesL, RuledOut, Res).
rule_out([X | CandidatesL], RuledOut, Res) :-
    rule_out(CandidatesL, RuledOut, Res).

% helper function
member(X, [X|_]) :- !.
member(X, [_|L]) :-
    member(X, L).
  1. Define the set substraction relation difference(Set1, Set2, SetDifference) where all the three sets are represented as lists. For example: difference([a,b,c,d], [b,d,e,f], [a, c])
1
2
3
4
5
6
7
difference([], _, []):- !.
difference(L, [], L).:- !.
difference([X | L], Set, [X | Res]) :-
    not(member(X, Set)), !,
    difference(L, Set, Res).
difference([_ | L], Set, Res) :-
    difference(L, Set, Res).

or

1
2
3
4
5
6
difference([], _, []).
difference([X | L1], L2, L) :-
    member(X, L2), !,
    differtence(L1, L2, L).
difference([X | L1], L2, [X | L]) : -
    differnece(L1, L2, L).

  1. Define the predicate unifiable(List1, Term, List2) where List2 is the list of all the members of List1 that match Term, but are not instantiated by this matching. For example:

    1
    2
    ?- unifiable([X, b, t(Y)], t(a), List).
    List = [X, t(Y)].

    Note that X and Y have to remain uninstantiated although the matching with t(a) does cause their instantiation.

    Hint: Use not (Term1 = Term2). If Term1 = Term2 succeeds then not(Term1 = Term2) fails and the resulting instatiation.

1
2
3
4
5
6
unifiable([], _, []).
unifiable([First | Rest], Term, List) :-
    not(First = Term), !,
    unifiable(Rest, Term, List).
unifiable([First | Rest], Term, [First | List]) :-
    unifiable(Rest, Term, List).

Problems with cut and negation

The advantages and disadvantages of using cut are listed as follows:

Advantages:

  • With cut we can often improve the efficiency of the program.

    The idea is to explicitly tell Prolog: do not try other alternatives because they are bound to fail.

  • Using cut we can specify mutually exclusive rules; so we can express rules of the form:

    if condition P then conclusion Q,

    otherwise conclusion R.

    In this way, cut enhances the expressive power of the language.

Disadvantages:

The reservations against the use of cut stem from the fact that we can lose the valuable correspondence between the declarative and procedural meaning of programs.

If there is no cut in the program we can change the order of clauses and goals, and this will only affect the efficiency of the program, not the declarative meaning.

On the other hand, in programs with cuts, a change in the order of clauses may affect the declarative meaning. This means that we can get different results.

e.g.

1
2
p :- a, b.
p :- c.

Tge declarative meaning of this program is: p is true iff a and b are both true of c is true. This can be written as a logic formula:

p <===> (a & b) $\or$ c

We can change the order of the two clauses and the declarative meaning remains the same.

Now, let us insert a cut:

1
2
p :- a, !, b.
p :- c.

The declarative meaning is now:

p <===> (a & b) $\or$ (~a & c)

If we swap the clauses,

1
2
p :- c.
p :- a, !, b.

then the meaning becomes:

p <===> c $\or$ (a & b)

The important point is that when we use the cut facility we have to pay more attention to the procedural aspects. Unfortunately, this additional difficulty increases the probability of a programming error.

Green cuts

Sometimes the removal of a cut from the program can change the declarative meaning of the program. But there were also cases in which the cut had no effect on the declarative meaning. The use of cuts of the latter type is less delicate, and therefore cuts of this kind are sometimes called ‘green cuts’.

From the point of view of readability of programs, green cuts are:

  • innocent
  • their use is quite acceptable

When reading a program, green cuts can simply be ignored.

Red cuts

This kind of cuts do affect the declarative meaning. Red cuts are the ones that make programs:

  • hard to understand
  • they should be used with special care

Negation (fail or not)

Cuts is often used in combination with a special goal, fail. In particular, we defined the negation of a goal (not) as the failure of the goal.

The negation is just a special (more restricted) way of using cut.

For reasons of clarity we will prefer to use not instead of the cut-fail combination (whenever possible), because the negation is a higher level concept and is intuitively clearer than the cut-fail combination.

What the problem of not

The problem is that not does not correspond exactly to negation in mathematics.

For example,

1
?- not human(mary).

Prolog will probably answer ‘yes’. But this should not be understood as Prolog saying ‘Mary is not human’. What Prolog really means to say is: ‘There is not enough information in the program to prove that Mary is human’. This arises because when processing a not goal, Prolog does not try to prove this goal directly. Instead, it tries to prove the opposite, and if the opposite cannot be proved then Prolog assumes that the not goal succeeds.

another example,

1
2
3
4
5
6
7
8
9
r(a).
q(b).
p(X) :- not r(X).

?- q(X), p(X).
X = b.

?- p(X), q(X).
no.

The key difference between both question is that the variable X is.

  • in the first case, already instantiated when p(X) is executed
  • in the second case, at that point X is not yet instantiated

Summary

  • The cut facility prevents backtracking.

    It is used both to improve the efficiency of programs and to enhance the expressive power of the language.

  • Efficiency is improved by explicitly telling Prolog (with cut) not to explore alternatives that we know are bound to fail.

  • Cut make it possible to formulate mutually exclusive conclusions through rules of the form:

    if Condition then Conclusion1 otherwise Conclusion2

  • Cut makes it possible to introduce negation as failure: not Goal is defined through the failure of Goal.

  • Two special goals are sometimes useful: true always succeeds, fail always fails.

  • There are also some reservations against cut: inserting a cut may destroy the correspondence between the declarative and procedural meaning of a program. Therefore, it is part of good programming style to use cut with care and not to use it without reason.

  • not defined through failure does not exactly correspond to negation in mathematical logic. Therefore, the use of not also requires special care.