Tiêu đề 3140708 - DM 2020W.pdf ✅

1 Seat No.: ________ Enrolment No.___________ GUJARAT TECHNOLOGICAL UNIVERSITY BE- SEMESTER–IV (NEW) EXAMINATION – WINTER 2020 Subject Code:3140708 Date:17/02/2021 Subject Name:Discrete Mathematics Time:02:30 PM TO 04:30 PM Total Marks:56 Instructions: 1. Attempt any FOUR questions out of EIGHT questions. 2. Make suitable assumptions wherever necessary. 3. Figures to the right indicate full marks. Marks Q.1 (a) Find the power sets of (i)a , (ii)a,b,c. 03 (b) If ( ) 2 , ( ) , ( ) 1 2 f x  x g x  x h x  x  then find (fog)oh and fo(goh). 04 (c) (i) Let N be the set of natural numbers. Let R be a relation in N defined by xRy if and only if x  3y  12 . Examine the relation for (i) reflexive (ii) symmetric (iii) transitive. 03 (ii) Draw the Hasse diagram representing the partial ordering {(a,b)/ a divides b} on {1,2,3,4,6,8,12}. 04 Q.2 (a) Let R be a relation defined in A={1,2,3,5,7,9} as R={(1,1), (1,3), (1,5), (1,7), (2,2), (3,1), (3,3), (3,5), (3,7), (5,1), (5,3), (5,5), (5,7), (7,1), (7,3), (7,5), (7,7), (9,9)}. Find the partitions of A based on the equivalence relation R. 03 (b) In a box there are 5 black pens, 3 white pens and 4 red pens. In how many ways can 2 black pens, 2 white pens and 2 red pens can be chosen? 04 (c) Solve the recurrence relation n an  4an1  4an2  n  3 using undetermined coefficient method. 07 Q.3 (a) Define self-loop, adjacent vertices and a pendant vertax. 03 (b) Define tree. Prove that if a graph G has one and only one path between every pair of vertices then G is a tree. 04 (c) (i) Find the number of edges in G if it has 5 vertices each of degree 2. 03 (ii) Define complement of a subgraph by drawing the graphs. 04 Q.4 (a) Show that the algebraic structure (G,*) is a group, where G  {(a,b)/ a,b  R,a  0} and * is a binary operation defined by (a,b) * (c, d)  (ac,bc  d) for all (a,b),(c,d) G. 03 (b) Define path and circuit of a graph by drawing the graphs. 04 (c) (i) Show that the operation * defined by y x * y  x on the set N of natural numbers is neither commutative nor associative. 03 (ii) Define ring. Show that the algebraic system ( , , ) 9 9 9 Z   , where {0,1,2,3,...,8} Z9  under the operations of addition and multiplication of congruence modulo 9, form a ring. 04