Answer the following:

1) a.Define minterms and maxterms.
b. Construct truth table for (p v  q) V ~ P.
c. Define logical equivalence and tautology.
d. Define rules Universal generalisation and Existential generalisation.
e. Define partial recursive function.
f. Define regular function.
g. Define a finite state machine.

2)a. Show that q V (p ^ ~q) V (~p ^ ~q) is a tautology.

b. Obatin disjunctive normal form of ~(p  v q) ó (p ^ q).

3)a.Show that p V (~p ^ q) ó p v q.

b.Obtain principal conjunctive  normal form of  (~p V ~q ) ->  (pó ~q)

4)a. Show that (x)(p(x)) -> q(x)) ^ (x)(q(x) -> r(x) ) => (x)(p(x) -> r(x))

b. Verify the validity of the following argument .   Every  living thing is a plant or animal.john’s gold fish is alive and is not a plant. All animals  have hearts. Therefore john’s gold fish has a heart.

5) a.Show that         (p(x) -> q(x) ^Using derivations .

b.Show that (H(x) -> A(x) ) -> (        [ ( H(y) ^ N (x,y) -> (y) (A(y) ^ N (x,y))] Is a logically valid statement.

6) a.Show that f(x,y)=xy  is a primitive recursive function.

b. Show that the function f(x,y)=x-y is  partial recursive.

7) a.Let [ be the greatest integer ≤  that [x] is a primitive recursive.

b.show that the set of divisors of a positive integer is recursive.

8′) a. If Si = Sj then for any input sequence (Si x) =  (Sj,x).

b. Construct turing machine that will compute f<x,y> where f is (i) Multiplication
(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
Answer the following: 1) a.Define minterms and maxterms. b. Construct truth table for (p v  q) V ~ P. c. Define logical equivalence and tautology. d. Define rules Universal generalisation and Existential generalisation. e. Define partial recursive function. f. Define regular function. g. Define a finite state machine. 2)a. Show that q V (p ^ ~q) V...