Week 46

Lecture Tuesday (10.11.2009)

The third lecture will further elaborate 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

Lecture Notes in Blackboard (Course Documents)

Exercise Wednesday (11.11.2009)

1) The first 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:

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

2)The second lecture 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:

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

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 second lecture also 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), r(X).
p(X) :- r(Y), s(Y), p(X).
p(X) :- r(Y).
q(a).
r(a).
r(b).
s(b).

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

4) The third 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)
• sum(X,Y,Z) % true if Z is the sum of all numbers from X to Y including X and Y, e.g., sum(1,6,21)

5) To make life easier for people using your predicates from 1), 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 1).

Lecture Thursday (12.11.2009)

Topics

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

Reading

Lecture Notes in Blackboard (Course Documents)