Week 47

Exercise Tuesday (17.11.2009)

1) 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,[2,1,3]) given the following logic program:

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

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

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

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

3) Implement the programs from Tasks 4 and 5 of the previous weekly notes and use the cut operator where it makes sense.

4) Consider the following Prolog program (introduced exactly like this in lecture notes for DM509 at least 2 years old):

income(peter,400000).
foreigner(peter).
average_taxpayerWrong(X) :- foreigner(X), fail.
average_taxpayerWrong(X) :- income(X,I), I < 500000.

Here, fail/0 is used to force a finite failure. The query ?- average_taxpayerWrong(peter). should clearly fail since Peter is a foreigner. Why does it not fail? How can you repair the program such that it works as one would expect?

Shorten the program to three clauses by having just one clause for average_taxpayer/1 and keeping the clauses for income/2 and foreigner/1.

5) Write definitions for a predicate divide/3 that performs division of natural numbers. For example, the query ?- divide(13,3,D) should yield the answer D = 4. Use a generate-and-test approach, i.e., use a predicate is_nat/1 defined as follows:

is_nat(0).
is_nat(X) :- is_nat(Y), X is Y+1.

Calling is_nat/1 with a variable as the argument will successively enumerate all natural numbers by backtracking. Now, define a predicate that tests whether a given natural number is a solution to the division problem. Finally, define divide using the generating predicate and the test.

6) A program that uses "," for conjunction and ";" for disjunction can always be written only using "," for conjunction. Discuss how to transform a clause with a right-hand side that is an arbitrary Boolean expression using "," and ";" step by step to a number of clauses that yield the same behaviour.

Apply your transformation to the following clause:

f(X,Y) :- X =:= 0, Y = 0; X > 0, (X > 1, X1 is X-1, X2 is X-2, f(X1,Y1), f(X2,Y2), Y is Y1+Y2; X =:= 1, Y is 1).

Simplify the resulting clauses. What does f actually compute?

Exercise Wednesday (18.11.2009)

1) Read Section 2.8 (Input/Output) in the lecture notes. Follow the example both with user interactions and with files.

Write a program that asks the user for a query until the user inputs stop. and executes each query. The user should then be informed whether the query succeeded or not.

2) Read Section 2.9 (Constraint Programming) in the lecture notes. Follow the SEND+MORE=MONEY example.

Lecture Thursday (19.11.2009)

The fifth lecture will start with an introduction to Haskell. We will then introduce the basics of function declarations and pattern matching.

Topics

functional programming, function declarations, pattern matching

Reading

Lecture Notes in Blackboard (Course Documents)