# Andhra University BE/B.Tech Discrete Mathematics Structures-II Previous Paper 2008

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)=x^{y } 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 S_{i} = S_{j} then for any input sequence (S_{i} x) = (S_{j},x).

b. Construct turing machine that will compute f<x,y> where f is (i) Multiplication

(ii)|x-y|.

## Leave a Reply

You must be logged in to post a comment.