Title 3140708 - DM 2021S.pdf ✅

1 Seat No.: ________ Enrolment No.___________ GUJARAT TECHNOLOGICAL UNIVERSITY BE - SEMESTER–IV (NEW) EXAMINATION – SUMMER 2021 Subject Code:3140708 Date:07/09/2021 Subject Name:Discrete Mathematics Time:02:30 PM TO 05: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) Among 100 people at least how many of them were born in the same month? 03 (b) Prove that: (A ∪ B) ′ ≡ A ′ ∩ B ′ . 04 (c) Define the following: 1) Composition of functions 2) Monoid 3) Existential Quantifier 4) Partially Ordered Set 5) Boolean Algebra 6) Tree 7) Complete Graph 07 Q.2 (a) Explain types of a Relation with a suitable example. 03 (b) Rewrite the following statements using quantifier variables and predicate symbols: 1) All birds can fly. 2) Some women are genius. 3) There is a student who likes Discrete Mathematics but not Probability and Statistics. 4) Each integer is either even or odd. 04 (c) Determine the validity of the argument given: If I study, then I will not fail in Discrete Mathematics. If I do not play cricket, then I will study. But I failed in Discrete Mathematics. ---------------------------------------------------------- Therefore I must have played cricket. 07 OR (c) Find if the following is a tautology, contradiction or contingency. (p → (q → r)) → ((p → q) → (p → r)) 07 Q.3 (a) Define: Bounded, Distributive and Complemented Lattices. 03 (b) Find the transitive closure of R = {(1,2), (3,4), (4,5), (4,1), (1,1)}. Where, A = {1,2,3,4,5}. 04 (c) Let A be a set of factors of positive integer m and relation is divisibility on A. For m = 45, show that POSET (A, ≤) is a Lattice. 07 OR Q.3 (a) Draw the Hasse diagram of the set {1,3,9,18} under partial order relation ‘divides’ and indicate those which are chains. 03 (b) Let X = {1,2,3, ... ,7} and R = {(x, y): x − y is divisble by 3}. Show that R is an equivalence relation. Draw the graph of R. 04