Searching graphs
12.5. Searching graphs#
Consider the following program:
brother(peter,paul).
brother(adrian,paul).
brother(X,Y):-brother(Y,X).
brother(X,Y):-brother(X,Z),brother(Z,Y).
Compare and explain the behaviour of prove_bf/1 and Prolog on the query ?-brother(peter,adrian). Can you re-order the clauses, such that Prolog succeeds?
Prolog will be trapped in an infinite loop, regardless of the order of the clauses. This is so because a refutation of ?-brother(peter,adrian) requires both recursive clauses, but whichever is found first will also be tried before the second one in all the other refutation steps. In contrast, prove_bf/1 will be able to construct a refutation.
Give the models of the program
married(X);bachelor(X):-man(X),adult(X).
has_wife(X):-married(X),man(X).
man(paul).
adult(paul).
This program has four models (bachelors may have a wife, and married man may be bachelors):
{ man(paul), adult(paul), bachelor(paul) }
{ man(paul), adult(paul), bachelor(paul), has_wife(paul) }
{ man(paul), adult(paul), married(paul), has_wife(paul) }
{ man(paul), adult(paul), married(paul), bachelor(paul), has_wife(paul) }
The second and fourth models are non-minimal.
Yes. The set of all Herbrand interpretations can be seen as a search space, in which the models are to be found. This search space is ordered by the subset relation. model/1 starts from the empty interpretation, and repeatedly adds ground atoms until a model is constructed. Since one atom is added at a time, the procedure will never jump over a model. Since, on backtracking, all possible ways to satisfy a violated clause are considered, model/1 performs a breadth-first search (which is complete).