ASSIGNMENT 1. Due November 23.
=============================
  1. Translate the folloiwng sentences into logic formulas:

     (a) Some scientists are geniuses.
     (b) Einstein is a scientist.
     (b) Only birds fly.
     (c) Penguins are birds.

     Assuming that (a)-(c) are asserted, can you conclude that
  
     (d) Einstein is a genius?
     (e) Some penguins fly?

--------------------------------------------------------------------------------  
  2.
  
 (a) Define the predicate zip(list1,list2,list3), which succeeds, if list3 is
     the result of zipping the lists list1 and list2. It means that the first
     two elements of list3 are the first elements of list1 and list2,
     respectively, the next two elements of list3 are the second elements of
     list1 and list2, and so on. If list1 and list2 have different lengths, the
     program should fail.

     Sample runs:

     ?- zip([a,b,c], [1,2,3], X).
     X = [a, 1, b, 2, c, 3].

     ?- zip([a,b,c], X, [a,1,b,2,c,3]).
     X = [1, 2, 3].

     ?- zip(X, [1,2,3], [a,1,b,2,c,3]).
     X = [a, b, c] ;
     false.

     ?- zip(X, Y, [a,1,b,2,c,3]).
     X = [a, b, c],
     Y = [1, 2, 3] ;
     false.

     ?- zip([a,b,c], [1,2,3,4], X).
     false.

 (b) Now modify the program so that it does not fail when list1 and list2 have
     different lengths. Instead, it suceeds if a prefix of list3 is obtained
     by zipping list1 and and list2 as long as possible and then putting the
     remaining part of the longer list at the end of list3. Call the predicate
     zip_modified.

     Sample runs:

     ?- zip_modified([a,b,c], [1,2,3], X).
     X = [a, 1, b, 2, c, 3] ;
     false.

     ?- zip_modified([a,b,c,d,e], [1,2,3], X).
     X = [a, 1, b, 2, c, 3, d, e] ;
     false.

     ?- zip_modified([a,b,c], [1,2,3,4], X).
     X = [a, 1, b, 2, c, 3, 4].

     ?- zip_modified(X, [1,2,3], [a,1,b,2,c,3,d,e]).
     X = [a, b, c, d, e] ;
     false.

 (c) What does your program return on the following queries?

     ?- zip([a,b,c], L2, L3).
     ?- zip(L1, L2, L3).
     ?- zip_modified([a,b,c], L2, L3).
     ?- zip_modified(L1, L2, L3).

-------------------------------------------------------------------------------

  3. Define a predicate transform(list, term1, term2), which succeeds if term1
     and term2 are results of transformations of a prefix and the corresponding
     suffix of the list 'list'. The terms consist of unary function symbols
     'atom', 'number', and 'compound', applied at the end to the constant #.
     A function symbol, located at n-th depth in the term 'term1' (resp.,
     'term2'), is either
       - 'atom', if the n-th element of the prefix (resp., of the suffix)
         of 'list' is a Prolog atom, or
       - 'number', if the n-th element of the prefix (resp., of the suffix)
         of 'list' is a Prolog number, or
       - 'compound', if the n-th element of the prefix (resp., of the suffix)
         of 'list' is a Prolog compound term.

     For instance, for the input list [a,f(a),1] the predicate should take an
     arbitrary split of the list, say, into [a,f(a)] and [1], transform
     [a,f(a)] into the term atom(compound(#)), [1] into number(#), and return
     these two terms.

     To check whether a Prolog term is an atom, number, or a compound term,
     you can use unary built-in predicates 'atom', 'number', 'compound'.

     Sample runs:

     ?- transform([a,1,f(a),"str",1/2,0.5],X,Y).
     X = #,
     Y = atom(number(compound(compound(compound(number(#)))))) ;
     X = atom(#),
     Y = number(compound(compound(compound(number(#))))) ;
     X = atom(number(#)),
     Y = compound(compound(compound(number(#)))) ;
     X = atom(number(compound(#))),
     Y = compound(compound(number(#))) ;
     X = atom(number(compound(compound(#)))),
     Y = compound(number(#)) ;
     X = atom(number(compound(compound(compound(#))))),
     Y = number(#) ;
     X = atom(number(compound(compound(compound(number(#)))))),
     Y = # ;
     false.

--------------------------------------------------------------------------------

  4. Explain what the following program does.
  
  rep.
  rep :- rep.

  run :-
      rep,
         write('Try to guess the secret number'),
         nl,
      read(42),
      write("Congrats!"),
      nl,
      write('Sorry, wanted to say: Congrats!').


--------------------------------------------------------------------------------

  5. Alternating factorial on natural numbers is defined as follows:

     alternating_factorial(1) = 1.
     alternating_factorial(n) = n! - altermating_factorial(n-1).

     For instance, alternating_factorial(3) = 3! - 2! + 1! = 5,
     alternating_factorial(4) = 4! - 3! + 2! - 1! = 19. 

     Write a Prolog program which implements it. Use accumulators.

     Sample runs:

     ?- alternating_factorial(3,X).
     X = 5 ;
     false.

     ?- alternating_factorial(4,X).
     X = 19 ;
     false.

     ?- alternating_factorial(50,X).
     X = 29817972015629302995182567242334801579950768815528034161635577019 ;
     false.

     ?- alternating_factorial(100,X).
     X = 92402284968649460451060535220066878189242360067783427018009608611042990392567410879552702599150890025886974375474305774025602890553942821446539362161635577019 ;
     false.

------------------------------------------------------------------------------

  6.
     (a) Define the predicate palindrome(list) that recognizes palindromes.

         A list is a palindrome if it reads the same in the forward and in
         the backward direction. For example:

        ?- palindrome([m,a,d,a,m]).
        true.

        ?- palindrome([s,i,r]).
        false.

        ?- palindrome([a,b,b,a]).
        true.

    (b) Draw the complete derivation tree for the last goal.
      
--------------------------------------------------------------------------------

  7. Define the relation maximum(list,term) that succeeds if 'term' 
     is the maximal element of the list of terms 'list'. Terms should
     be compared with respect to the standard order. In Prolog it is
     done with the help of the built-in predicates @>, @=<, @>, @>=.

     Sample runs:

     ?- maximum([1,2,3,2], M).
     M = 3 ;
     false.

     ?- maximum([a,b,1,2,3,2], M).
     M = b ;
     false.

     ?- maximum([a,b,1,2,3,2,f(a,g(b)), f(a,g(c))], M).
     M = f(a, g(c)) ;
     false.

     ?- maximum([a,b,1,2,3,2,f(a,g(b)), f(a,g(c)), [a,b]], M).
     M = f(a, g(c)) ;
     false.

     ?- maximum([], M).
     false.

--------------------------------------------------------------------------------

  8. Exercise from the book:

     Say whether the following goals would succeed, and which variables, if
     any, would be instantiated to what values:

     pilots(A,london) = pilots(london,paris).
     point(X,Y,Z) = point(X1,Y1,Z1).
     letter(C) = word(letter).
     noun(alpha) = alpha.
     'vicar' = vicar.
     f(X,X) = f(a,b).
     f(X,a(b,c)) = f(Z,a(Z,c)).
  
--------------------------------------------------------------------------------

  9. 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 do on the following queries?
   ?- list_sum(L, X).
   ?- list_sum(L, 2).
   ?- list_sum([a,b,c], X).

--------------------------------------------------------------------------------

 10. Fibonacci numbers, Lucas numbers and Fibonacci words are sequences defined
     respectively as follows:

     fib(0) = 0
     fib(1) = 1
     fib(n) = fib(n-1) + fib(n-2), when n > 1.

     lucas(0) = 2
     lucas(1) = 1
     lucas(n) = lucas(n-1) + lucas(n-2), when n > 1.

     fib_word(0) = b
     fib_word(1) = a
     fib_word(n) = fib_word(n-1) fib_word(n-2),
                   concatenation of two words, when n > 1.

     Define a predicate sequence_element(name,n,el), which succeeds if 'el'
     is the 'n'-th element of 'name'-s sequence.

     Sample runs:

     ?- sequence_element(fib,5,X).
     X = 5 ;
     false.

     ?- sequence_element(fib,6,X).
     X = 8 ;
     false.

     ?- sequence_element(fib,10,X).
     X = 55 ;
     false.

     ?- sequence_element(fib,100,X).
     X = 354224848179261915075 ;
     false.

     ?- sequence_element(lucas,3,X).
     X = 4 ;
     false.

     ?- sequence_element(lucas,4,X).
     X = 7 ;

     ?- sequence_element(lucas,100,X).
     X = 792070839848372253127 ;
     false.
                                                
     ?- sequence_element(fib_word,3,X).
     X = aba ;
     false.

     ?- sequence_element(fib_word,4,X).
     X = baaba ;
     false.

     ?- sequence_element(fib_word,5,X).
     X = ababaaba ;
     false.

     ?- sequence_element(fib_word,6,X).
     X = baabaababaaba ;
     false.

     ?- sequence_element(fib_word,7,X).
     X = ababaababaabaababaaba ;
     false.

     ?- sequence_element(fib_word,10,X).
     X = baabaababaabaababaababaabaababaabaababaababaabaababaababaabaababaabaababaababaabaababaaba ;
     false.