Week 37

Exercise Tuesday (11.9.2012)

1) 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)
• 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 the previous exercise on using 0 and s for natural numbers, 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) Predicates can be used to perform different functions according to which arguments are instantiated. Draw the SLD trees for the queries ?- add(s(s(0)), s(s(s(0))), Z). and ?- add(s(s(0)), Y, s(s(s(s(s(0)))))). and compare them. Use the following program:

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

5) The same technique can be used with lists. Consider the following program for appending two lists and for rotating lists:

append([],M,M).
append([X|L],M,[X|N]) :- append(L,M,N).
rotate(L,M) :- append(X,Y,L), append(Y,X,M).

Draw the SLD tree for the query ?- rotate([1,2,3],A).

Lecture Wednesday (12.9.2012)

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)

Lecture Friday (14.9.2012)

The fifth lecture will start with a short repetition of constraint logic programming. Then we will continue with an introduction to Haskell. Here, we will focus on the basics of function declarations and pattern matching.

Topics

functional programming, function declarations, pattern matching

Reading

Lecture Notes in Blackboard (Course Documents)