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)=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