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

- a. Give an example of a relation which is reflexive and transitive but not symmetric.

b. Consider the relation on { 1,2,3,4,5,6}, R = { (i.j) : |i-j|=2}. Is ‘R’ transitive ?

c. Show that f(x,y) =x*y is primitive recursive.

d. Consider the poset A= ({1,2,3,4,6,9,12,18,36},/) find the greatest lower bound and the least upper bound of the sets {6,18} and {4,6,9}.

e. Define sub lattice and give an example.

f. Prove that if a² = a then a=e , a being an element of a group.

g. Define regular grammar.

2) a. Let R be the equivalence relation on the set A ={ 1,2,3,4,5 } and R = { {1,1),(2,1),(1,2),(2,2),(3,3),(4,4),(5,4),(4,5),((5,5,)}. Find the partition of A induced by R.

b. If R be a relation on the set of real numbers such that aRb if and only if a-b is an integer. Is R an equivalence relation?

3)a.Show that every distributive lattice is a modular.

b. Show that every finite lattice is complete.

4. a.Obtain a grammar for the language

L=(0^{i },1^{j }/ i≠ j > 0 and I,j >0}.

b. Show that in boolean algebra

5. a. Let M= (I,S,O, be afinite – state machine.then show that there exists an equivalence machine M’ with a set of state S’ such that S’ ⊆ S and M’ is reduced.

b. Let A = {1,3,9,27,81 }. Draw Hasse diagram of the poset (A,/).

6. a . Let (L_{1} ≤ ) be a lattice and a,b,c, L .prove that if a ≤ c, b≤ c,

(i) a v b =

(ii) a ^ b = a*b ≤ c.

b. Show that 0 is the only complement of 1 in any lattice.

7. a. Show that the relation “ congruence modulo m “ is an equivalence relation.

b. Show that there are only five distinct Hasse diagrams for a poset containing three elements.

8. Let a language L be accepted by a non deterministic finite-state acceptor.then show that there exists an equivalent deterministic finite state acceptor that accepts L.

http://www.stepinau.com/2013/10/31/andhra-university-beb-tech-discrete-mathematics-structures-ii-2011/CSE 2.2 SyllabusCSE,CSE 2.2 Previous Papers,CSE Previous Papers,Discrete Mathematics Structures-II Previous Papers,IT,IT 2.2 Previous Papers,IT Previous Papers
## Leave a Reply

You must be logged in to post a comment.