Title 3140708 - DM 2022S.pdf ✅

1 Seat No.: ________ Enrolment No.___________ GUJARAT TECHNOLOGICAL UNIVERSITY BE - SEMESTER–IV (NEW) EXAMINATION – SUMMER 2022 Subject Code:3140708 Date:02-07-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) Determine whether each of these statements is true or false. 1)0 ∈ ∅ 2)∅ ⊂ {0} 3){0} ∈ {0} 4) ∅ ∈ {∅} 5){∅} ∈ {{∅}} 6) {{∅}} ⊂ {∅,{∅}} 03 (b) Determine whether f is a function from the set of all bit strings to the set of integers if 1) f(s) is the position of a 0 bit in S. 2) f(s) is the number of a 1 bits in S. Find the range of each of the following functions that assigns: 3) to a bit string the number of one bits in the string 4) to each bit string twice the number of zeros in that string. 04 (c) 1) Find the bitwise OR, and bitwise XOR of the bit string 1111 0000, 1010 1010 2) Show that the function f: R → R + ∪ {0} defined by f(x) = |x| is not invertible. Modify the domain or codomain of f so that it becomes invertible. 3) Let S be subset of a universal set ∪. The characteristic function fS : ∪→ {0,1} , fS (x) = 1, if x ∈ S and 0 is x ∉ S. Let A and B be sets. Then show that fA∩B(x) = fA (x). fB(x) 07 Q.2 (a) Let P(x) be the statement “x = x2 “. If the domain consists of the integers, what are the truth values of the following? 1) ∃x P(x) 2) ∀x ¬P(x) 3) ∃x ¬P(x) 03 (b) Identify the error or errors in this argument that supposedly shows that if ∃x P(x) ∧ ∃x Q(x) is true then ∃x (P(x) ∧ Q(x)) is true. 1. ∃x P(x) ∧ ∃x Q(x) Premise 2. ∃x P(x) Simplification from (1) 3. P(c) Existential instantiation from (2) 4. ∃x Q(x) Simplification from (1) 5. Q(c) Existential instantiation from (2) 6. P(c) ∧ Q(c) Conjunction from (3) and (5) 7. ∃x (P(x) ∧ Q(x)) Existential generalization 04 (c) 1) Use a truth table to verify the De Morgan’s law ¬(p ∨ q) ≡ ¬p ∧ ¬q 2) Show that (p → q) ∧ (q → r) → (p → r) is a tautology. 07 OR
2 (c) 1) Suppose that the domain of Q(x, y, z) consists of triples x, y, z, where x = 0, 1, or 2, y = 0 or 1, and z = 0 or 1. Write out following propositions using disjunctions and conjunctions. i) ∃z¬Q(0,0, z) ii). ∀yQ(0, y, 0) 2) i) Show that ∃x P(x) ∧ ∃x Q(x) and ∃x(P(x) ∧ Q(x)) are not logically equivalent. ii) Show that ∃x(P(x) ∨ Q(x)) and ∃x P(x) ∨ ∃x Q(x) are logically equivalent. 07 Q.3 (a) For the relation {(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4)} on the set {1,2,3,4}, decide whether it is reflexive, whether it is symmetric, whether it is antisymmetric, and whether it is transitive..(Justify your answer if the property is not satisfied) 03 (b) For the following relations on the set of real numbers, R1 = {(a, b) ∈ R 2 |a ≥ b}, R2 = {(a, b) ∈ R 2 |a ≤ b} R3 = {(a, b) ∈ R 2 |a ≠ b} find 1) R1⨁R3 2) R2o R3 04 (c) 1) Draw the Hasse diagram for the poset ({2, 4, 6, 9, 12, 18, 27, 36, 48, 60, 72}, |). Hence find glb({60,72}) and all maximal elements. 2) Determine whether the relation with the directed graph shown is an equivalence relation. 07 OR Q.3 (a) Suppose that the relations R1 and R2 on a set A are represented by the matrices MR1 = [ 1 0 1 1 0 0 0 1 0 ] and MR2 = [ 1 0 1 0 1 1 1 0 0 ] What are the matrices representing R1 ∪ R2 and R1 ∩ R2 ? 03 (b) Use Warshall’s algorithm to find the transitive closures of the relation R = {(1,4), (2, 1), (2,3), (3,1), (3,4), (4,3)} on {1, 2, 3, 4} 04 (c) 1) Draw the Hasse diagram for the poset({2, 4, 5, 10, 12, 20, 25}, |). Hence, find the are maximal and minimal elements. 2) Which of these collections of subsets are partitions of {1, 2, 3, 4, 5, 6}? Justify your answer if it is not a partition. i) {1, 2}, {2, 3, 4}, {4, 5, 6} ii) {1, 4, 5}, {2, 6} 07 Q.4 (a) Explain Path and Circuit of a graph. 03

4 Q.5 (a) 1) Define: SemiGroups. 2) Let S = {a, b, c, d}. The following multiplication table, define operations ∙ on S. Is 〈S, ∙〉semigroup? Justify 03 (b) Let H = {1, – 1} and G = {1, – 1, i, – i} . (H,×) is a sub-group (G,×). Then find all left cosets and right cosets of H in G. 04 (c) 1) Define:Ring. 2) Write elements of the ring 〈z10, +10, ×10〉. And find −3, −8 , 3 −1 , 4 −1 07 OR Q.5 (a) Consider the set Q of a rational numbers. Let ∗ be the operation on Q defined by a∗ b = a + b − ab. Find 1) 3 ∗ 4 2) the identity element for ∗. 03 (b) Write the equivalence classes for congruence modulo 4 i.e.. z4 Let the subset H={[0],[2]} is a subgroup of G = 〈z4 , +4 〉. Then determine all left cosets of H in G. 04 (c) We are given the ring 〈{a, b, c, d}, +,∙〉 the operations + and ∙ on R are as shown in the following table. + a b c d a a b c d b b c d a c c d a b d d a b c ∙ a b c d a a a a a b a c a c c a a a a d a c a a 1) Does it have an identity? 2) What is the zero of this ring? 3) Find the additive inverse of each of its elements 07 ********