Week 46

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?

3) 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?

Lecture Tursday (17.11.2011)

The fourth lecture will introduce non-logical constructs in Prolog including constraint programming.

Topics

arithmetics, cut, negation-as-failure, meta-logical predicates

Reading

Lecture Notes in Blackboard (Course Documents)

Exercise Friday (18.11.2011)

1) The fourth lecture introduced built-in operations on integers. Use these to define the following predicates:

• power(X,Y,Z) % true if X^Y = Z, e.g., power(2,3,8)
• prod(X,Y,Z) % true if Z is the product of all numbers from X to Y including X and Y, e.g., prod(1,6,720)

2) To make life easier for people using your predicates from 1) of the previous exercise, define the following predicates:

• nat2int(X,Y) % true if X and Y represent the same natural number, e.g., nat2int(s(s(s(0))),3)
• int2nat(X,Y) % true if X and Y represent the same natural number, e.g., int2nat(2,s(s(0)))

Why is one predicate not enough? What is the problem when using nat2int to convert integers into natural numbers? What is the problem when using int2nat for the converse direction? Use these two predicates to test your predicates from the previous exercise.

3) The third lecture showed how to transform any formula in predicate logic into an equisatisfiable formula into CNF where all variables are universally quantified from the outside. Apply these transformation steps to a formula that corresponds to answering the query ?- member(X,[3,1,2]) given the following logic program:

member(X,[X|Xs]).
member(X,[Y|Ys]):- member(X,Ys).

4) The fourth lecture introduced the cut operator. Consider the following logic program:

a :- b, c.
a :- b.
b.
b.
c :- e.
c :- e, b, f.
c :- b.
e :- fail.
e.
f.
f.
f.

Draw the SLD tree and indicate all finite failures.
Now change the 6th clause from c :- e, b, f. to c :- e, b, !, f. and indicate all branches that are cut.