ASSIGNMENT 1. Due November 22. ============================= Total points: 40 ----------------- 1. (5 points) Translate the folloiwng sentences into logic formulas: (a) People who live in Linz love it. (b) Peter does not love Linz. (c) John likes somebody. (d) No one answers every question. (e) Everything is true or false. (f) Although no one made any noise, John was annoyed. Assuming that (a) and (b) are asserted, can you conclude that (g) Peter does not live in Linz. (h) Peter lives in London. ================================================================================ 2. (2 points) What does Prolog return to the following queries? (1) [a,X] = [a,b,c,d]. (2) [a,X] = [a,[b,c,d]]. (3) [a,b|X] = [a,b,c,d]. (4) [a,b|X] = [a,b,[c,d]]. (5) [X|Y] = [a|b]. (6) [X|Y] = [a,b]. (7) [X,Y] = [a|b]. (8) [X,Y] = [a,b]. (9) [_,_|_] = [a,b,c,d]. (10) [X,X|Y] = [a,b,c,d]. (11) [_] = []. (12) [_] = [a]. (13) [_] = [a,b]. (14) [_|_] = []. (15) [_|_] = [a]. (16) [_|_] = [a,b]. (17) X is 3+Y. (18) X is 3+5. (19) X = 3+5. (20) X is f(3+5). ================================================================================ 3. (4 points) Write a predicate list_sum(list, sum) that succeeds of 'sum' is the sum of elements of 'list', consisting of numbers. Sample runs: ?- list_sum([1,2,3], 6). true ?- list_sum([1,2,3], X). X=6. ?- list_sum([], X). X=0. What does your program return on the following queries? ?- list_sum(L, X). ?- list_sum(L, 2). ?- list_sum([a,b,c], X). ================================================================================ 4. (4 points) Write a binary predicate even_element(list, term) that succeeds if 'term' occurs in 'list' in an even position. Sample runs: ?- even_element([1], X). false. ?- even_element([1,2], X). X = 2 ; false. ?- even_element([1,2,3], X). X = 2 ; false. ?- even_element([1,2,3,4], X). X = 2 ; X = 4 ; false. ?- even_element([1,2,3,4], 2). true ?- even_element([1,2,3,4], 3). false. What does your program return of the following queries? ?- even_element(L, a). ?- even_element(L, X). ============================================================== 5. (5 points) Take your program that solves the problem 4 and draw the complete derivation tree (like those we did in the class) for the query even_element([1,2,3,4], X). ============================================================= 6. (4 points) Define the relation shift(List1, List2) so that List2 is List1 "shifted rotationally" by one element to the left. For example, ?- shift([1,2,3,4,5], L1), shift(L1,L2). L1=[2,3,4,5,1] L2=[3,4,5,1,2]; false ============================================================= 7. (4 points) Define the relation maximum(List,Integer) that succeeds if Integer is the maximal element of the list of integers List. Example, ?- maximum([1,2,3,4,2,-1,4], Max). Max=4; false ?- maximum([1,2,3,4,2,-1,4], 4). true ?- maximum([], Max). false =========================================================== 8. (3 points) Write a predicate twice_as_long(L1,L2) that succeeds if the list L2 is twice as long as the list L1. Do NOT compute the lengths of the lists. Sample run: ?- twice_as_long([], []). true. ?- twice_as_long([a], [1,2]). true. ?- twice_as_long([a], [1,2,3]). false. ?- twice_as_long([a,b], X). X = [_G328, _G331, _G334, _G337] ; false ============================================================ 9. (5 points) Assume that natural numbers are give in successor-zero notation, that means succ(0) stands for 1, succ(succ(0)) stands for 2, succ(succ(succ(0))) stands for 3 and so on. (a) Write a predicate is_natural(term) that succeeds iff 'term' is a natural number represented in successor-zero notation. (b) Write a predicate is_less_then(n1, n2) that succeeds iff where n1 and n2 are natural numbers in successor-zero notation and the number n1 is less than the number n2. Sample runs: ?- is_natural(0). true. ?- is_natural(succ(succ(0))). true. ?- is_natural(succ(a)). false. ?- is_less_than(succ(0), succ(succ(succ(0)))). true. ?- is_less_than(succ(0), succ(0)). false. ?- is_less_than(succ(succ(0)), succ(0)). false. What does your program return on the following queries? Explain the outputs. ?- is_natural(succ(X)). ?- is_natural(succ(_)). ?- is_less_than(0, Y). ?- is_less_than(succ(X), Y). ?- is_less_than(X, succ(succ(0))). ?- is_less_than(succ(X), succ(succ(succ(Y)))). ================================================================================ 10. (4 points) Write a ternary predicate select_greater_than(term, list1,list2) that succeeds if the list of terms 'list2' consists of those elements of 'list1' that are greater than 'term' with respect to the standard order. (Check the manual of the system you are using for the built-in predicate for the standard order.) Sample runs: ?- select_greater_than(5, [1,7,5,6,3,4,8], L). L = [7,6,8] ; false. ?- select_greater_than(5, [1,2,3], L). L = [] ; false. ?- select_greater_than(a, [b,c,a,d], L). L = [b,c,d] ; false. ?- select_greater_than(f(a), [b,f(c,1),a,d,5,g(2)], L). L = [f(c,1),g(2)] ; false. ?- select_greater_than(B,[A,a,B,b,_,X],L). L = [a, b, _G223, X] ; false. What happens if you ask ?- select_greater_than(5, L, [1,2,3]).