Week 36

Exercise Tuesday (15.11.2011)

1) The second lecture introduced a representation of natural numbers by functors 0 and s, e.g., s(s(s(0))) for the natural number 3. Use these functors to define the following predicates without using any built-in arithmetics:

• triple(X,Y) % true if X = 3*Y, e.g. triple(s(s(s(0))),s(0))
• divides(X,Y) % true if there is a Z such that X * Z = Y, e.g., divides(s(s(s(0))),s(s(s(s(s(s(s(s(s(0))))))))))

2)The second lecture also introduced unfication. Use the algorithm from the lecture to compute the most general unifier of the the following term pairs if it exists and give a reason for the failure (occur-failure or clash-failure) if the two terms do not unify:

• g(a,C,f(C),A) and g(B,h(B),D,f(D))
• g(v(u(Y)),Y) and g(v(W),u(W))
• f(Y,g(Y,Y),g(A,A)) and f(g(Z,Z),A,X)
• g(f(Y),Z,Y) and g(Z,f(h(X)),f(X))

First execute the algorithm by hand. Then see what happens if you use gprolog with ?- t1 = t2.
What happens when you use ?- unify_with_occurs_check(t1,t2). instead?

Lecture Friday (7.9.2012)

The third lecture will introduce SLD trees. Then we will look at the connection between predicate logic and logic programming. We will then introduce more advanced features of Prolog focusing on built-in data types and operations.

Topics

predicate logic, conversion to CNF, SLD resolution, arithmetics, lists, operators

Reading

rest of Section 2.3 and Sections 2.4-2.6 in Lecture Notes in Blackboard (Course Documents)

Exercise Friday (7.9.2012)

The third lecture introduced SLD trees. Consider the following Prolog program:

add(0,Y,Y).
add(s(X),Y,s(Z)) :- add(X,Y,Z).
mul(0,Y,0).
mul(s(X),Y,Z) :- mul(X,Y,U), add(U,Y,Z).

Draw the SLD tree for the query ?- mul(s(s(0)),s(0),Z).
What solution do you obtain?

Now, consider the following Prolog program:

p(X) :- q(X), s(X).
p(X) :- s(Y), r(Y), p(X).
p(X) :- s(Y).
q(a).
s(a).
s(b).
r(b).

Draw the SLD tree for the query ?- p(X).
Which solutions do you obtain? Does Prolog find all of them?