If you take a look at some Prolog programming texts, you'll find Prolog solutions to most, if not all, of these problems. A little web surfing will locate solutions as well. Try to do as much as you can without those aids though, as they won't be available to you during exams. ------------------------------------------------------------------- Problem 1 (10 points): Write a relation shorter(L1,L2) that is true if list L1 contains the same number or fewer elements than list L2. The relation is false if list L1 contains more elements than list L2. Sample behavior follows: cilog: ask shorter([a,b],[a,b,c]). Answer: shorter([a, b], [a, b, c]). Runtime since last report: 0 secs. [ok,more,how,help]: ok. cilog: ask shorter([a],[a,b,c]). Answer: shorter([a], [a, b, c]). Runtime since last report: 0 secs. [ok,more,how,help]: ok. cilog: ask shorter([a,b],[a,b]). Answer: shorter([a, b], [a, b]). Runtime since last report: 0 secs. [ok,more,how,help]: ok. cilog: ask shorter([a,b,c],[a]). No. shorter([a, b, c], [a]) doesn't follow from the knowledge base. Runtime since last report: 0 secs. cilog: ask shorter(X,[a,b,c]). Answer: shorter([], [a, b, c]). Runtime since last report: 0 secs. [ok,more,how,help]: more. Answer: shorter([A], [a, b, c]). Runtime since last report: 0 secs. [ok,more,how,help]: more. Answer: shorter([A, B], [a, b, c]). Runtime since last report: 0 secs. [ok,more,how,help]: more. Answer: shorter([A, B, C], [a, b, c]). Runtime since last report: 0 secs. [ok,more,how,help]: more. No more answers. Runtime since last report: 0 secs. cilog: ------------------------------------------------------------------- Problem 2 (10 points): Write a relation delete_one(E,L,R) that is true if R is the resulting list of removing any single instance of E from L. The relation is false if E is not a member of L. Sample behavior follows: cilog: ask delete_one(x,[a,x,b,x,c],[a,b,x,c]). Answer: delete_one(x, [a, x, b, x, c], [a, b, x, c]). Runtime since last report: 0 secs. [ok,more,how,help]: ok. cilog: ask delete_one(x,[a,x,b,x,c],[a,x,b,c]). Answer: delete_one(x, [a, x, b, x, c], [a, x, b, c]). Runtime since last report: 0 secs. [ok,more,how,help]: ok. cilog: ask delete_one(x,[a,b,c],Z). No. delete_one(x, [a, b, c], A) doesn't follow from the knowledge base. Runtime since last report: 0 secs. cilog: ask delete_one(x,[a,x,b,x,c],Z). Answer: delete_one(x, [a, x, b, x, c], [a, b, x, c]). Runtime since last report: 0 secs. [ok,more,how,help]: more. Answer: delete_one(x, [a, x, b, x, c], [a, x, b, c]). Runtime since last report: 0 secs. [ok,more,how,help]: more. No more answers. Runtime since last report: 0 secs. cilog: ------------------------------------------------------------------- Problem 3 (10 points): Write a relation subsequence(L1,L2) that is true if the elements of list L2 occur within list L1 as a subsequence. For example, subsequence([c,d,e],[a,b,c,d,e,f]). is true, but subsequence([c,e],[a,b,c,d,e,f]). is not. Sample behavior follows: cilog: ask subsequence([b,c,d],[a,b,c,d,e]). Answer: subsequence([b, c, d], [a, b, c, d, e]). Runtime since last report: 0 secs. [ok,more,how,help]: ok. cilog: ask subsequence([b,d],[a,b,c,d,e]). No. subsequence([b, d], [a, b, c, d, e]) doesn't follow from the knowledge base. Runtime since last report: 0 secs. cilog: ask subsequence(X,[a,b,c]). Answer: subsequence([], [a, b, c]). Runtime since last report: 0.01 secs. [ok,more,how,help]: more. Answer: subsequence([a], [a, b, c]). Runtime since last report: 0 secs. [ok,more,how,help]: more. Answer: subsequence([a, b], [a, b, c]). Runtime since last report: 0 secs. [ok,more,how,help]: more. Answer: subsequence([a, b, c], [a, b, c]). Runtime since last report: 0 secs. [ok,more,how,help]: more. Answer: subsequence([], [a, b, c]). Runtime since last report: 0 secs. [ok,more,how,help]: more. Answer: subsequence([b], [a, b, c]). Runtime since last report: 0 secs. [ok,more,how,help]: more. Answer: subsequence([b, c], [a, b, c]). Runtime since last report: 0 secs. [ok,more,how,help]: more. Answer: subsequence([], [a, b, c]). Runtime since last report: 0 secs. [ok,more,how,help]: more. Answer: subsequence([c], [a, b, c]). Runtime since last report: 0 secs. [ok,more,how,help]: more. Answer: subsequence([], [a, b, c]). Runtime since last report: 0 secs. [ok,more,how,help]: more. No more answers. Runtime since last report: 0 secs. cilog: ------------------------------------------------------------------- Problem 4 (10 points): Write a relation substitute(X,Y,L1,L2) that is true is the list L2 is the result of substituting Y for all occurrences of X in the list L1. Sample behavior follows: cilog: ask substitute(a,x,[a],[x]). Answer: substitute(a, x, [a], [x]). Runtime since last report: 0 secs. [ok,more,how,help]: ok. cilog: ask substitute(a,x,[a,b],[x,b]). Answer: substitute(a, x, [a, b], [x, b]). Runtime since last report: 0 secs. [ok,more,how,help]: ok. cilog: ask substitute(a,x,[a,b,a,c,a],[x,b,x,c,x]). Answer: substitute(a, x, [a, b, a, c, a], [x, b, x, c, x]). Runtime since last report: 0 secs. [ok,more,how,help]: ok. cilog: ask substitute(a,x,[a,b,a,c,a],Z). Answer: substitute(a, x, [a, b, a, c, a], [x, b, x, c, x]). Runtime since last report: 0 secs. [ok,more,how,help]: more. No more answers. Runtime since last report: 0 secs. cilog: ask substitute(a,x,Z,[x,b,x,c,x]). Answer: substitute(a, x, [a, b, a, c, a], [x, b, x, c, x]). Runtime since last report: 0 secs. [ok,more,how,help]: ok. cilog: ask substitute(X,Y,[a,b,a,c,a],[x,b,x,c,x]). Answer: substitute(a, x, [a, b, a, c, a], [x, b, x, c, x]). Runtime since last report: 0 secs. [ok,more,how,help]: ok. cilog: ------------------------------------------------------------------- Problem 5 (10 points): Write a relation last(L,E) that is true if E is the last element of list L. Sample behavior follows: cilog: ask last([a,b,c],c). Answer: last([a, b, c], c). Runtime since last report: 0 secs. [ok,more,how,help]: ok. cilog: ask last([a,b,c],b). No. last([a, b, c], b) doesn't follow from the knowledge base. Runtime since last report: 0 secs. cilog: ask last([a,b,c],X). Answer: last([a, b, c], c). Runtime since last report: 0 secs. [ok,more,how,help]: more. No more answers. Runtime since last report: 0 secs. cilog: ask last([],X). No. last([], A) doesn't follow from the knowledge base. Runtime since last report: 0 secs. cilog: ask last(X,c). Answer: last([c], c). Runtime since last report: 0 secs. [ok,more,how,help]: more. Answer: last([A, c], c). Runtime since last report: 0 secs. [ok,more,how,help]: more. Answer: last([A, B, c], c). Runtime since last report: 0 secs. [ok,more,how,help]: more. Answer: last([A, B, C, c], c). Runtime since last report: 0 secs. [ok,more,how,help]: more. Answer: last([A, B, C, D, c], c). Runtime since last report: 0 secs. [ok,more,how,help]: ok. cilog:
Last revised: September 27, 2004