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

1. 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ⁱ ,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₁ ≤ ) 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.