DOEACC Society 2006 DOEACC C Level CE8 - Logic
Friday, 14 June 2013 01:35Web
CE8-R3: LOGIC AND FUNCTIONAL PROGRAMMING
NOTE:
Time: three Hours Total Marks: 100
1.
a) Convert ( " x) ( " y) ((" z) (a(x,y,z) v B (y))) ® ( " x) C (x,z) prenex normal form.
b) Write a SML program for calculation GCD.
c) Who exceptions are intercepted and handled in SML?
d) What is the subsequent program doing? Is this program recursive and iterative? Justify.
ABC (N,F) ¬ ABC (0,N,1,F).
ABC (I,N,T,F) ¬ I
e) explain Cut in Prolog.
f) describe satisfiability, Validity and consistency in prepositional logic.
g) describe signature and functions in Functional programming, in brief.
(7x4)
2.
a) describe tree data kind for a binary tree. Write a SML code to get depth of a binary tree.
b) Show that ((P Ù q) ® R) Ú (~q ® ~R) is valid using semantic tableux method.
c) Write iterative program in Prolog to add the elements (integers) of a provided list.
(6+6+6)
3.
a) Write a Prolog code for Quick sort.
b) Prove {(pi ® pj), (Ø(pj ® pk) ® Øpi)} + (pi ® pk).
c) What is Resolution fefutation? Display a Resolution Refutation of
{{Ø pi,pj},{Øpj,pk Øpi},{pi}{Øpk}}
(6+4+4+4)
4. Letå = {zero, succ, pred, plus} be a signature. Let I be the interpretation in Z, the set
of integers such that I(zero)=0, I(succ)=lx[x+1], I(pred)=lx[x-1] and I(plus)=l(x, y) [x
+y]?
a) describe the set of normal forms (subset of Tå ).
b) describe rewrite rules to calculate the normal form of every term.
c) describe the Unique å -homomorophism hz : Tå ® Z.
d) Let I` be a different interpretation in E, the set of all even inters with I` (zero) = 0
I` (succ) = lx[x+2], I` (pred) = lx[x-2] and I (plus) = l(x,y )[x+y]. Show that the two
interpretations are isomorphic.
(4+4+4+6)
CE8-R3 Page one of two July, 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.
5.
a) Let b denotes any base kind and let the subsequent grammer describe the language of simple
kinds for the simply-typed Lambda Calculus.
t :: b|t |(t ® t )
Let G be a set of kind assignments for variables. Then prove that substitution preserves
kinds in the simply typed lambda calculus, i.e. x:a, M:a, and L:b then L{M/x}:b.
b) obtain most general kind assignments for the combinatory SD
= lxyz[((xz)(yz))] in the
second order language of kinds described by
t :: b|t |(t ® t )
t ::t |" t[p ]
where b denotes any base kind and t denotes a kind variable.
c) How control in Prolog is characterized with the help of an example. Show how response
to a query is affected?
(6+6+6)
6.
a) Let derivatives (Y,X,Z) denote that the derivative of Y with respect to X is Z. provided the
subsequent facts:
derivative(N,X,0).
derivative(X,X,1).
derivative(sin(X),X,cos(X)).
derivative(cos(X),X,-sin(X)).
derivative(exp(X),X,exp(X)).
derivative(log(X),X,1/X).
write logic programming rules to calculate derivatives of
i) Sum of 2 expressions.
ii) Difference of 2 expressions.
iii) Product of 2 expressions.
iv) Quotient of 2 expressions.
In particular make sure your definitions can compute the derivatives of expressions such
as 3*exp(5*X)*sin(2*X)+cos(X)/log(X).
b) Translate the subsequent argument into 1st order logic and prove it using resolution.
Whoever visited the building was observed. Anyone who had observed Ajay, would
have remembered him. Nobody remembered Ajay. Therefore Ajay did not visit the
building.
(9+9)
7.
a) Let SD
= lxlylz[((x z)(y z))] and KD
= lxly[x]. Prove that application is not associative by
showing that:
((S K) K) ¹ b(S (K K))
b) In all of mathematics, function composition denoted by the infix operator o is associative.
That is, if f : A ® B, g: B ® C and h: C ® D are any 3 functions, then the
composition f o g : A ® C is described as the function (f o g)(a) = g( f (a)). It is then easy
to see that o is associative, i.e.
(f o g) o h = f o (g o h)
described a lambda-expression called compose and prove that it is associative.
CE8-R3 Page two of two July, 2006
(9+9)
CE8-R3 Page three of two July, 2006
| Earning: Approval pending. |
