DOEACC Society 2006 DOEACC C Level CE8 - Logic & Functional Programming( ) - Question Paper

CE8-R3: LOGIC AND FUNCTIONAL PROGRAMMING
NOTE:
Time: three Hours Total Marks: 100
1.
a) Convert the subsequent FOL formula into its equivalent Prenex form
a:(" x){(~R(x)®P(a)) Ù ($z) ~ Q(z,a)} Ù ("x) {P(x)®($y) Q(y,x))}
b) Let S = {P(x), Q(x, f(x)) V ~ P(x), ~ Q (g(y), z)} bet set of clauses. obtain unsatisfiable set
S’ of ground instances of clauses in S.
c) Prove a theorem “from {P V Q, ~ P} infer Q” using Natural Deduction System.
d) Will the output of the subsequent queries same? If not, provide the cause and provide a situation
when both the queries provide identical output.
? member (X, [2,3,4]).
? not (not (member(X, [2,3,4]))).
e) Write l-abstraction, which generates l-function for computing successor or predecessor of
a number when applied on one or –1 respectively.
f) obtain normal form of the l-expression or actual y and show the valuation steps.
g) provide recursive datatype definition of a list in SML.
(7x4)
2.
a) Code the subsequent facts and rules as logic program and generate proof tree for the
query ‘notebook supports pen’
i) If X is on top of Y, Y supports X.
ii) If X is above Y and they are touching every other, X is on top of Y.
iii) A pen is above a notebook.
iv) A pen is touching a notebook.
b) Prove {P} |-(~ Q ® ~ (P ® Q)) using Axiomatic system.
c) Show that the FOL formula "y $x P(x, y) ® $x "y P(x, y) is satisfiable but not valid.
(7+6+5)
3.
a) Consider the subsequent Prolog program:
one(X, Y) :- X > 1, Y > 1.
two(0, 1). two(2, 3).
two(X, Y) :- three(P, Q), three(Q, P), X is P + 1, Y is Q + 1.
four(0). three(1, 3). three(2, 4). three(4, 2).
and the query ?-two(X, Y), not(four(X)), one(X, Y).
i) What will the output of the subsequent query? Draw the search tree.
ii) If rule for ‘one’ in (a) is changed by one(X, Y) :- X > 1, Y > 1, ! then what will be
the output for above query?
b) The subsequent program obtains the sum of 1st N natural numbers.
sum(1, 1).
sum(N, R) :- N1 is N – 1, sum(N1, R1), R is R1 + N.
i) Draw search tree for the query? - sum(4, R).
ii) Is this program terminating?
iii) If ans to ii) is no, then make it terminating program if possible.
iv) Write iterative version of this program.
([5+3]+[3+1+3+3])
CE8-R3 Page one of two January, 2006
1. ans ques. one and any 4 ques. from two to 7.
2. Parts of the identical ques. should be answered together and in the identical
sequence.
4.
a) Suppose that a node of a binary tree is coded in Prolog as ‘tree(left, data, right)’. Write a
predicate called “count(T, N)”, which succeeds by binding N with number of leaf nodes in a
binary tree T. Empty tree is represented by ‘null’.
b) Write a recursive and iterative Prolog programs named ‘sum(L, P, N)’, where L is list of
integers, P is the list of positive integers and N is the list of negative integers in L.
c) Identify what does the subsequent program do?
find([], []).
find([H|T],N) :- member(H, T), !, find(T, N).
find([H|T],[H|N|) :- find(T, N).
provide the search tree of the query ?- find([1,2,3,2,3], N).
(6+6+6)
5.
a) obtain normal form of the subsequent l-expressions and show the valuation steps.
i) (lx. x4)( ly. y+6)
ii) (lx. (ly. x*y)) 7
iii) (lxy. x*y) two 5
iv) (lxy. x y)( lz. z+5) 6
b) Write the expression (x * 3) * two – (x * 3)/5 + ((x * 3) + 4) using l-notation.
c) What do you understand by a normal form of l-expressions? It is not necessary that all
l-expressions have the normal forms. Justify this statement through example of l-
expression, which does not have normal form.
d) Write a l-function named ‘union’ to generate 1 list by eliminating common elements of
two lists, assuming that individual lists have no duplication. Use functions such as null,
head, tail, cons(constructor) etc. with the obvious meanings for manipulating lists.
(6+2+5+5)
6.
a) Consider the subsequent function declaration in SML.
fun compute(0, x) = x
| compute(x, y) = calculate (x-1, x*y);
i) Determine the kind of function ‘compute’.
ii) Under what condition ‘compute’ be terminating function?
iii) Write the valuation steps for calculate (3, 4)?
b) provided the subsequent Datatype declaration in SML, write a function to test whether a provided
day is working or not.
datatype DAY = Mon | Tue | Wed | Thr | Fri | Sat | Sun;
c) provided datatype for a binary tree. Write a SML function to swap a binary tree at all levels.
(6+6+6)
7.
a) SML does not support array representation. Suggest a scheme for array representation in
SML so that any index value of an array can be retrieved in at most (log2N) time, where ‘N’
is number of elements in an array.
b) elaborate lazy and eager valuation strategies? Which strategy is used in SML? List two
advantages of every.
c) discuss ‘let’ expression and ‘local’ declaration in SML. provide a suitable example.
d) How are exceptions declared and handled in SML?
e) How do we achieve polymorphism in SML?
(4+3+5+3+3)
CE8-R3 Page two of two January, 2006

Earning:   Approval pending.