3 [40 pts] Prolog assignments
For the following exercises we will be using swipl, which is a freely available prolog imple- mentation. It is already installed on the lab computers. For documentation, visit http: //www.swi-prolog.org.
You are only allowed to use the built-in functions of Prolog, as well as any predicates already supplied by the assignment.
3.1 [4 pts] Biblical family
Load the file biblical.pl, study the rules in the KB and answer the following questions.
3.2 [21 pts] Arithmetic with natural numbers
Download the file arith.pl. In this file some operations on so-called Peano integers are defined. For the sake of readability, Arabic numerals are used in the questions below. Be sure to use Peano numbers in your exercises!
Study the rules in the KB and answer the following questions.
Questions:
a) Which Prolog query determines who is the grandfather of Lot? What is the answer? b) Which Prolog query determines all grandsons of Terach? What is the answer?
Questions:
a) What is a suitable query to ask the system whether 3+2=5? What does the system
answer?
b) What is a suitable query to ask the system whether 3+2=6? What does the system answer?
c) Add predicates even(N) and odd(N), that determine whether N is even or odd.
d) Add a predicate div2(N,D) that determines whether the integer division N/2 is equal to D. Your solution should not use the predicate times. Test your predicate for 4/2 = 2, 3/2 = 1 and 0/2 = 0.
e) Add a predicate divi2(N,D), that computes the same result as div2(N,D), but now using the predicate times. Of course, you need to test this predicate as well using the same numbers as before.
f) Find an n such that 2n = 8 using a suitable query. Add a predicate log(X,B,N) that determines whether BN = X.
g) Extend the KB with a predicate fib(X,Y), where fib denotes the Fibonacci function. The predicate returns true if and only if fib(X) = Y. [Note: fib(0) = 0,fib(1) = 1,fib(n) = fib(n−1)+fib(n−2)]
5
h) In the course Imperative programming you learned that BN can be computed in O(logN) steps using the rules: a2b = (a2)b and a2b+1 = a · a2b. Extend the KB with the predicate power(X,N,Y), based on these rules. The predicate returns true if XN = Y. Is this predicate an improvement over a direct O(N) computation? Why (not)?
3.3 [8 pts] Lists
In Prolog it is possible to use lists. For example, the following snippet of code determines the length of a list:
Note that lists are not types, i.e. the elements of a list can be anything. For example, the query len([1,2,[artificial,intelligence]],X). will be answered with X=3.
len([],0).
len([H|T],N) :- len(T,N1), N is N1+1.
Questions:
Download the file arith.pl, and extend it with the following functionality:
a) member(X,L) returns true if X is a member of the list L.
b) concat(L,X,Y) returns true if L is the concatenation of the lists X and Y.
c) reverse(L,R) returns true if R is the reversal of the list L.
d) palindrome(L) returns true if L is a palindrome.
3.4 [7pts] Maze
Consider the following maze:
Questions:
a) Write a Prolog KB that represents the maze.
b) Extend the KB with a predicate path(X,Y) that returns true if there exists a path from X to Y. Test the query path(a,p), it should succeed.
c) Try also path(a,m). What is the result?
6