# Andhra University BE/B.Tech Discrete Mathematics Structures-II 2007

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

## Leave a Reply

You must be logged in to post a comment.