Title 3140708 - DM 2022W.pdf ✅

1 Seat No.: ________ Enrolment No.___________ GUJARAT TECHNOLOGICAL UNIVERSITY BE - SEMESTER–IV(NEW) EXAMINATION – WINTER 2022 Subject Code:3140708 Date:16-12-2022 Subject Name:Discrete Mathematics Time:10:30 AM TO 01:00 PM Total Marks:70 Instructions: 1. Attempt all questions. 2. Make suitable assumptions wherever necessary. 3. Figures to the right indicate full marks. 4. Simple and non-programmable scientific calculators are allowed. Marks Q.1 (a) A committee 5 persons, is to be formed from 6 men and 4 women. In how many ways this can be done when (i) at least 2 women are included, (ii) at most 2 women are included. 03 (b) If A  4,5,7,8,10 , B  4,5,9 and C  1,4,6,9 , then verify that A B C A B A C            . 04 (c) Define Functionally complete set of connectives, Principal Disjunctive Normal Form (PDNF). Obtain PDNF for the expression         p q p q q r      07 Q.2 (a) Define Partial Order Relation. Illustrate with an example. 03 (b) Define one – one function. Show that the function f R R :  , f x x     3 7 is one – one and onto both. Also find its inverse. 04 (c) Solve the recurrence relation 2 1 5 6 2 n n n a a a      with initial condition 0 a 1 and 1 a 1 using method of undetermined coefficients. 07 OR (c) Use generating function to solve a recurrence relation 1 3 2 n n a a    with 0 a 1. 07 Q.3 (a) Define Partition of a Set. Let A  1,2,3,4,5 and R  1,2 , 1,1 , 2,1 , 2,2 , 3,3 , 4,4 , 5,5              be an equivalence relation on A . Determine the partition for 1 R  , if it an equivalence relation. 03 (b) Draw Hasse Diagram for the lattice S D 30 ,  where 30 S is the set of divisors of 30 and D is the relation divides. 04 (c) Show that the set S of all matrices of the form a b b a        where a b R ,  is a field with respect to matrix addition and matrix multiplication. 07 OR Q.3 (a) Define Semi Group, Monoid. Give an example of an algebraic structure which is semi group but not monoid. 03

3 Figure 1 Figure 2 ***************