1) 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.

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

tejus mahiCSE 2.2 Previous PapersCSE,CSE 2.2 Previous Papers,CSE Previous Papers,Discrete Mathematics Structures-II Previous Papers,IT,IT 2.2 Previous Papers,IT Previous Papers
1) 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 finite state machine. 2) a.   Obtain the principal disjunctive normal form of P -> (P ^...