## Discrete Structures - Jun 19

### Computer Engineering (Semester 3)

Total marks: 80

Total time: 3 Hours
INSTRUCTIONS

(1) Question 1 is compulsory.

(2) Attempt any **three** from the remaining questions.

(3) Draw neat diagrams wherever necessary.

**1.a.**Prove using Mathematical Induction 2+5+8+...+(3n-1)=n(3n+1)/2

**1.b.**Find the generating function for the following finite sequences i) 1,2,3,4,… ii) 2,2,2,2,2

**1.c.**Let A = {1, 4, 7, 13} and R = {(1,4), (4,7), (7,4), (1,13)} Find Transitive Closure using Warshall’s Algorithm

**1.d.**Let f : R O R, where f(x) = 2x – 1 and f-1 (x) = (x+1)/2 (05M) Find (f O f

^{-1})(x)

**2.a.**Define Lattice. Check if the following diagram is a lattice or not.

**2.b.**Prove that set G = {1,2,3,4,5,6} is a finite abelian group of order 6 with respect to multiplication module 7

**2.c.**A travel company surveyed it's travellers, to learn how much of their travel is taken with an Air plane, a Train or a Car. The following data is known; make a complete Venn Diagram with all the data. The number of people who flew was 1307. The number of people who both flew and used a train was 602. The people who used all three were 398 in number. Those who flew but didn’t drive came to a total of 599. Those who drove but did not use a train totaled 1097. There were 610 people who used both trains and cars. The number of people who used either a car or a train or both was 2050. Lastly, 421 people used none of these Find out how many people drove but used neither a train nor an airplane, and also, how many people were in the entire survey.

**3.a.**. (08 M) Q.3 a) Prove $\neg(p \vee(\neg p \wedge q))$ and $\neg p \wedge \neg q$ and $\neg p \wedge \neg q$ are logically equivalent by developing a series of logical equivalences.

**3.b.**Consider the (3,5) group encoding function defined by

e(000)=0000 , e(001)=00110

e(010)=01001 , e(011)= 01111

e(100)=10011 , e(101)=10101

e(110)=11010 , e(111)=11000

**3.c.**Mention all the elements of set D36 also specify R on D36 as aRb if a | b. Mention Domain and Range of R. Explain if the relation is Equivalence Relation or a Partially Ordered Relation. If it is a Partially Ordered Relation, draw its Hasse Diagram. D

_{36}

**4.a.**Explain Extended pigeonhole Principle. How many friends must you have to guarantee that at least five of them will have birthdays in the same month.

**4.b.**Define Euler Path and Hamiltonian Path.

i) Determine Euler Cycle and path in graph shown in (a)

ii) Determine Hamiltonian Cycle and path in graph shown in (b)

**4.c.**In a group of 6 boys and 4 girls, four children are to be selected. In how many different ways can they be selected such that at least one boy should be there?

**5.a.**Let G be a group. Prove that the identity element e is unique.

**5.b.**A pack contains 4 blue, 2 red and 3 black pens. If 2 pens are drawn at random from the pack, NOT replaced and then another pen is drawn. What is the probability of drawing 2 blue pens and 1 black pen?

**5.c.**Let A be a set of integers, let R be a relation on AXA defined by (a,b) R (c,d) if and only if a+d=b+c. Prove that R is an equivalence Relation.

**6.a.**Define reflexive closure and symmetric closure of a relation. Also find reflexive and symmetric closure of R.

A={1,2,3,4}

R={(1,1),(1,2),(1,4),(2,4),(3,1),(3,2),(4,2),(4,3),(4,4)}

b) Let H=$\left|\begin{array}{lll}{1} & {0} & {0} \\ {0} & {1} & {1} \\ {1} & {1} & {1} \\ {1} & {0} & {0} \\ {0} & {1} & {0} \\ {0} & {0} & {1}\end{array}\right|$

Be a parity check matrix. Determine the group $e_{H} B^{3} \rightarrow B^{6}$

**6.c.**Determine if following graphs G

_{1}and G

_{2}are isomorphic or not.