Andhra University BE/B.Tech Discrete Mathematics Structures-II Previous Paper 2006
1.(a) define minterms and maxterms.
(b) construct truth table for (pvq)v ~p.
(c) define logical equivalence and tautology.
(d) define rules Universal generalisation and existential generalisation.
(e) define partial recursive funtion.
(f) define regular funtion.
(g) define a finite state machine.
2.(a) show that qv(p ^ ~q)v(~p ^ ~q) is atautology.
(b) obtain disjunctive normal form of ~(pvq) ó(p ^q).
3. (a) show that pv(~p ^ q)ópvq.
(b) obtain pricipal conjunctive normal form of (~ pv ~q)-. (pó ~q).
4. (a) show that (x)(p(x)->p(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.therefor
5. (a) show that (( yp(y))-> using derivatives.
(b) show that (x)(H(x)->A(x))->( [(y)H(y)
N(x,y)->(Y)(A(y)N(x,y))] is logically valid statement.
6. (a) show that f(x,y)=xy is primitive recursive function.
(b) show that the function f(x,y)=x-y is partial recursive.
7. (a) let [ ] be the greatest integer show that [.
(b) show that the set of divisors of a positive integers is recursive.
8. (a) if si ≡sj then for any input sequence (six)≡(sj,x).
(b). construct turing machine that will compute f<x,y> where f is (i) multiplication (ii)|x-y|.