Answer Question No.1 and any other FOUR.Answer question No. at one place.

ALL questions carry equal marks.

a.    Define principal conjunctive normal form.

b. Prove that  [(P ^ 7Q) -> R] -> [P-> (Q  v R]) is a tautology.

c. Define atomic statement.

d. Give one example of bound variable.

e. Define total function.

f. Define recursive function.

g. Define transition statement of a finite state machine.

2)a.   Obtain the principal disjunctive normal form of

P -> (P ^ (Q -> P))

b. Construct the truth table for     (Q ^ (P -> Q)) -> P

3 )a.   Show that (P -> Q) ^ (R -> Q) ó  (P v R ) -> Q

Obtain the conjunctive normal form of   7(P v Q)ó (P ^ Q)

4)a.  Find the truth values of (x)(P -> Q(x)) v  R(a),
where P:2 > 1 , Q(x) : x <= 3 , R(x) : x > 5 and a : 5 ,
with universe being {-2,3,6}.

b. prove that  ( x) (P(x)  ^  Q(x)) ó (x)P(x) ^ (x) P(x) ^ ( Q(x).

5 )a. Using CP or otherwise show the implications.

(x)(P(x) ->  Q(x) ) ó  (x) P(x)  ->  (x)  Q(x)

b. Show that 7P(a,b) follows logically from

(x)(y) (P(x,y))  -> w(x,y) and 7w(a,b).

6)a.  Show that the quotient function g < x,Y >= quotient upon division of y by x is primitive                          recursive.

Show that the function

f(x) =   x/2         when x is even
(x-1)/2   when  x is odd
is a primitive recursive.

7)a. Show that the set of even and odd natural numbers are both recursive.
b.  Show that the function f(x) = x/2 is a partial recursive function.

8)a. Design  a deterministic finite – state acceptor for sentences in {a,b} such that every a has a b immediately  to its right.

Construct the turing machine that will compute f< x,y> where f is (i) proper subtraction
(ii) |x – y|.

tejus mahiCSE 2.2 SyllabusCSE,CSE 2.2 Previous Papers,CSE Previous Papers,Discrete Mathematics Structures-II Previous Papers,IT,IT 2.2 Previous Papers,IT Previous Papers
Answer Question No.1 and any other FOUR.Answer question No. at one place. ALL questions carry equal marks. a.    Define principal conjunctive normal form. b. Prove that  -> ) is a tautology. c. Define atomic statement. d. Give one example of bound variable. e. Define total function. f. Define recursive function. g. Define transition statement of a...