ASSIGNMENT 1. Due November 22.
=============================

Total points: 40
-----------------

1. (5 points) 

Translate the following 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]).