DMS QB

Discrete Mathematical Structures - Question Bank Shyam P. Joy Module 1 Set Theory 1. In a class of 52 students, 30 ar...

2 downloads 232 Views 84KB Size
Discrete Mathematical Structures -

Question Bank

Shyam P. Joy

Module 1 Set Theory 1. In a class of 52 students, 30 are studying C++, 28 are studying Pascal and 13 are studying both languages. How many in this class are studying atleast one of these languages ? How many are studying neither of these languages ? 2. An integer is selected at random from 3 through 17 inclusive. If A is the event that a number divisible by 3 is chosen and B is the event that the chosen number exceeds 10, determine the P r(A), P r(B), P r(A∩B) and P r(A ∪ B). 3. A problem is given to four students A, B, C, D whose chances of solving it are 12 , 31 , 41 , 51 . Find the probability that the problem is solved. 4. In a sample of 100 logic chips, 23 have defect D1 , 26 have defect D2 , 30 have defects D3 , 7 have defects D1 and D2 , 8 have defects D1 and D3 , 10 have defects D2 and D3 , and 3 have all the three defects. Find the number of chips having (i) at least one defect, (ii) no defect. 5. Prove that if two sets A and B are such that A ⊆ B and A is A is uncountable, then B is also uncountable. 6. If S, T ⊆ U . Then show that S and T are disjoint if and only if S∪T =S△T 7. For any universe U and any sets A, B ⊆ U , the following statements are equivalent: (a) A ⊆ B (b) A ∪ B = B (c) A ∩ B = A (d) B ⊆ A 1

8. (a) Express the set {x ∈ R | x2 = −1} in tabular form. Justify your answer. (b) If a set B has 64 subsets of odd cardinality, what is | B |? Justify your answer. 9. Using the laws of set theory, show that (A ∪ B) ∩ C ∪ B = B ∩ C. Mention the laws used in each step. 10. In a survey of 120 passengers, an airline found that 48 preferred ice cream with their meals, 78 preferred fruits and 66 preferred coffee. In addition, 36 preferred any pair of these and 24 preferred them all. If 2 passengers are selected at random from the sample of 120, what is the probability that they both preferred exactly 2 of the 3 beverages offered.

Module 1 Fundamentals of Logic 1. How many rows are needed in the truth table for the compound proposition (p ∨ ¬q) ↔ {(¬r ∧ s) → t} 2. Prove using a truth table that for any proposition p and q, the compound proposition (p ∨ q) ∧ (¬p ∨ ¬q) are logically equivalent. 3. Prove the following logical equivalences without using truth tables. p ∨ [p ∧ (p ∨ q)] ↔ p 4. Give the contrapositive of p → (q → r). 5. Prove that S ∨R is tautologically implied by (P ∨Q)∧(P → R)∧(Q → S) 6. List the laws of logic. 7. Negate and simplify the compound statement (p ∨ q) → r 8. For primitive statements p, q, is there any simpler way to express the compound statement (p ∨ q) ∧ ¬(¬ ∧ q) 9. Prove logically modus tollens 10. Prove logically modus ponens. 11. Verify that [p → (q → r)] → [(p → q) → (p → r)] is a tautology using truth table. 2

12. Write the following in the symbolic form and establish if the argument is valid: If A has a driving license then he is atleast 18 years old. A is atleast 18 years old. Therefore A has a driving license. 13. Verify the validity of the following arguments: (a) p → (q → r), ¬q → ¬p, p, ∴ r 14. Show that the hypothesis If you send me an e-mail message, then I will finish writing the” program”, ”If you do not send me an e-mail message, then I will go to sleep early” and ”If I go to sleep early then I will wake up feeling refreshed” lead to the conclusion ”If I do not finish writing:the program, then I will wake up feeling refreshed”.

Module 2 Fundamnetals of Logic cont. 1. Negate and simplify each of the following: (a) ∃x.(p(x) ∨ q(x)) (b) ∀x(p(x) ∧ ¬q(x) 2. Negate ∀x, ∀y((x > y) → ((x − y) > 0) 3. For any integer n, prove that if n2 is odd, then n is odd. 4. Prove that if m is an even integer, then m + 7 is an odd integer. 5. Prove that for every even integer n with 2 ≤ n ≤ 26 can be written as the sum of atmost three perfect squares. 6. For all integers k, l, if k and l are odd then show that their product kl is also odd. 7. For all positive real numbers x and y, if the product xy exceeds 25, then x ≥ 5 or y ≥ 5 8. If p(x) : x2 − 7x + 10 = 0, q(x) : x2 − 2x − 3 = 0, r(x); x < 0, find the truth values of the following, where the universe is all integers. Whenever the answer is false, give a counter example: (a) ∀x[p(x) → ¬r(x)] (b) ∀x[q(x) → r(x)] (c) ∃x[q(x) → r(x)] 3

(d) ∃x[p(x) → r(x)] 9. Verify the validity of the following argument: ∀x[p(x) ∨ q(x)] ∃x¬p(x) ∀x[¬q(x) ∨ r(x)] ∀x[s(x) → ¬r(x)] ∴ ∃x¬s(x) 10. Prove by method of contraposition: For all real numbers x and y, if x + y ≥ 100 then x ≥ 50 or y ≥ 50

Module 2 Properties of Integers 1. Prove by mathematical induction that (n!) ≥ 2n−1 for all integers n ≥ 1. 2. Prove by mathematical induction that 2n > n2 for all positive integers n > 4. 3. Prove by mathematical induction that 5 divides n5 − n, n > 0 4. Prove by mathematical induction that An = 5n +2.3n−1 +1 is a multiple of 8. 5. Prove by mathematical induction that power set of an n element set has 2n elements. 6. A sequence {an } is defined recursively by a1 = 4, an = an−1 + n, n ≥ 2 7. Fibonacci numbers are P defined recursively by F0 , F1 , F2 ... are Fibonacci numbers prove that ni=0 Fi 2 = Fn xFn+1 8. If Fi′ s are the Fibonacci numbers and L′i s are Lucas numbers, prove that Ln = Fn−1 + Fn+1 9. Define well-ordering principle. 10. Define the principle of mathematical induction. 11. Establish the following using mathematial induction: Σni=1 i(2i ) = 2 + (n − 1)2n+1 12. Find a unique solution for the recurrence relation 4an − 5an−1 = 0, n ≥ 1, n0 = 1 4

Module 3 Relations and Functions 1. Let A, B, C, D be non-empty sets. Prove that (A × B) ⊆ (C × D) if and only if A ⊆ C and B ⊆ D. 2. Let | A |= m and | B |= n. Find the number of possible relations from A to B. 3. Let A = {1, 2, 3, 4}. Determine whether or not the following relations on A are functions. (a) f = {(2, 3), (1, 4), (2, 1), (3, 2), (4, 4)} (b) g = {(3, 1), (4, 2), (1, 1)} (c) h = {(2, 1), (3, 4), (1, 4), (2, 1), (4, 4)} 4. Let a function f : R → R be defined by f (x) = x2 + 1. Determine the images of the following subsets of R. (a) A1 = {2, 3} (b) A2 = {−2, 0, 3} 5. Let f : R → R be defined by f (x) = 3x − 5 for x > 0 and −3x + 1 for x ≤ 0. (a) Determine f (0), f (−1), f ( 35 ), f ( −5 3 (b) Find f −1 (0), f −1 (1), f −1 (3), f −1 (−3), f −1 (−6) 6. Let X → Y and A and B be arbitrary non empty subsets of X. Prove that (a) A ⊆ B ⇒ f (A) ⊆ f (B) (b) f (A ∪ B) = f (A) ∪ f (B) (c) f (A ∩ B) ⊆ f (A) ∩ f (B) 7. Let A and B be finite sets and f be a function from A to B, Then show that (a) f is one-one →| A |≤| B | (b) f is onto →| B |≤| A | (c) f is one-one correspondence →| B |=| A | (d) | A |>| B |→ atleast two different elements of A have the same image under f . 5

8. There are six programmers who can assist eight executives. In how many ways can the executives be assisted so that each programmer assists atleast one executive. 9. Find the number of ways of distributing four distinct objects among three identical containers, with some containers possibly empty. 10. A bag contains 12 pair of socks. If the person draws the socks one-byone at random , determine atmost how many draws are required to get atleast a pair of matched socks. 11. Prove that in a set of 29 persons atleast five persons must have been born on the same day of the week. 12. Shirts numbered consecutively from 1 to 20 are worn by 20 students of a class. When any three of these students are chosen to be a debating team from the class, the sum of these shirt numbers is used as a code number of the team. Show that any 8 of 20 are selected, then from these 8, we may from atleast two different teams having the same code number. 13. Prove that every set of 37 positive integers contain atleast two integers that leave the same remainder upon division by 36. 14. Shirts numbered consecutively from 1 to 20 are worn by 20 students of a class. When any 3 of these students are chosen to be a debating team from the class, the sum of their shirt numbers is used as the code number of the team. Show that if any 8 of the 20 are selected, then from these 8 we may form at least two different teams having the same code number. 15. (a) If there are 2187 functions f : A → B and | B |= 3 what is | A |? Justify your answer. (3) (b) If A = {1, 2, 3, 4, 5} and there are 6720 injective functions f : A → B, what is | B | ? Justify your answer. (4) (c) If A = {1, 2, 3, 4} and B = {u, v, w, x, y, z, }, find the number of surjective functions from A to B. Justify your answer. (3) 16. A chemist who has 5 assistants (distinct) is engaged in a research project that calls for 9 different compounds to be synthesised. In how 6

many ways can the chemist assign these synthesis to the 5 assistants so that each is working on atleast one synthesis. (10) 17. Let f : A → B and g : B → C. Then prove the following: (a) If f, g are injective, then g ◦ f is injective.

(5)

(b) If f, g are surjective, then g ◦ f is surjective.

(5)

Module 4 Relations cont. 1. Let A = {1, 2, 3, 4, 6} and R be relation defined by a multiple of b. Represent the relation R as a matrix and draw its digraph. 2. On the set A = {a, b, c, d, e, f }, the relation R is defined as follows:R = {(a, b), (a, c), (b, b), (b, d), (b, e), (c, d), (d, e), (e, f )} 3. If A = {1, 2, 3, 4} and R and S are relations on A defined by R = {(1, 2), (1, 3), (2, 4), (4, 4)} and S = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4)}. Find R ◦ S, S ◦ R, R2 , S 2 , write down their matrices. 4. Define reflexive relation with an example. 5. Define irreflexive relation with an example. 6. Define symmetric relation with an example. 7. Define asymmetric relation with an example. 8. Define antisymmetric relation with an example. 9. Define transitive relation with an example. 10. Let S be a universal set. On P (S), define a relation on (A, B) if and only if A ⊆ B. Prove that R is reflexive, antisymmetric and transitive. 11. If a finite set A having n elements, prove the following: (a) There are 2n (b) There are 2

2 −n

n2 −n

(c) There are 2 (d) There are 2 metric.

n2 +n 2 n2 −n 2

reflexive relations on A. irreflexive relations on A. symmetric relations on A. relations on A that are both reflexive and sym-

7

(e) There are 2n × 3

n2 −n 2

antisymmetric relations on A.

12. If A is a nonempty set, then prove that: (a) Any equivalence relation R on A induces a partition of A. (b) Any partition of A gives rise to an equivalence relation R on A. 13. Define partial order, give an example relation, and draw the Hasse diagram. 14. For each of the following relation determine if the relation R is reflexive, symmetric, anti-symmetric or transitive. Justify your answer. (a) On the set of all lines in a plane, l1 Rl2 if line l1 is perpendicular to line l2 . Not Reflexive. A line is parellel to itself and not perpendicular. Symmetric because if l1 ⊥l2 then l2 ⊥l1 . Since the relation is symmetric it is not anti-symmetric. Not transitive, as if l1 ⊥l2 and l2 ⊥l3 , then l1 is parellel to l3 . (b) On Z, xRy if and only if x − y is even.(0 may be considered as even.) 15. Let A = {1, 2, 3, 4}, B = {w, x, y, z}, C = {p, q, r, s}. Consider R1 = {(1, x), (2, w).(3, z)}, a relation from A to B. R2 = {(w, p), (z, q), (y, s), (x, p)} a relation from B to C. (a) What is the composite relation R1 ◦ R2 from A to C. (b) Verify M (R1 ) ◦ M (R2 ) = M (R1 ◦ R2 ) 16. Let A = {1, 2, 3, 4, 5} × {1, 2, 3, 4, 5} and define R as (x1 , y1 )R(x2 , y2 ) if and only if x1 + y1 = x2 + y2 (a) Verify that R is an equivalence relation on A. (b) Determine the partition induced by R.

Module 5 Groups 1. Define a group with an example. 2. Show that the set of all fourth roots of unity along with operation multiplication forms an abelian group. 8

3. Prove that in group there exists only one identity element. 4. Let G be a set of non-zero real numbers and let a ∗ b = 21 ab. Show that (G, ∗) is an abelian group. 5. Let p be a prime. Find all x in Zp∗ such that x = x−1 6. Prove Wilson’s Theorem. 7. Let G be a group, and let J = {x ∈ G | xy = yx∀y ∈ G}. Prove that J is a subgroup of G. 8. Let G be the finite group with identity e and let a be an arbitrary element in G. Prove that an = e for some non-negative integer n. 9. Prove that every cyclic group is abelian, but the converse is not true. 10. If every element of a group G other than the identity has order 2, prove that the group G is abelian. 11. State and prove Lagrange’s Theorem. 12. Let G be a group with subgroups H and K. If | G |= 660, | K |= 66 and K ⊂ H ⊂ G, what are the possible values for | H |? (10) 13. A binary symmetric channel has a probability of p = 0.05 of incorrect transmission. If the codeword c = 011011101 is transmitted what is the probability that (a) single bit error occurs. (b) three errors occurs but no two of them consecutive.

Module 5 Group Codes 1. An encoding function E : Z 8 2 → Z 9 2 is defined as follows: For each w = w1 w2 ..w8 ∈ Z 8 2 , E(w) = w1 w2 ...w9 where w9 = Σ8i=1 wi , the summation being modulo 2. If p = 0.001 is the probability that a signal is received incorrectly, find the probability that the code word 110101101 is received with atmost one error. 2. The word c = 110101 is transmitted through a binary symmetric channel T . If e = 101010 is the error in pattern, find the word received.

9

3. If p = 0.02 is the probability that a signal is received incorrectly in a binary symmetric channel, find the probability that the word c = 11010011 is received with (a) no error. (b) one error (c) two errors (d) atmost two errors. 4. Let E : W → C be an encoding function where W ⊆ Z n 2 and C = E(W ) ⊆ Z n 2 , m < n. For any k ∈ Z + . For any k ∈ Z + , we can detect errors of weight less than or equal to k if and only if the minimum distance in E is atleast k + 1. 5. An encoding function E : Z 2 2 → Z 5 2 is given by the generator matrix. The rows of the generator matrix are G = [10110], [01011] (a) Determine the code words. (b) Find the associated parity check matrix. 6. Prove that the set Z with binary operations ⊕, and ⊙ defined by x⊕y = x + y − 1, x ⊙ y = x + y − xy is a commutative ring with unity. 7. Check whether the above ring is an integral domain. 8. Check whether the above ring is a field. 9. Show that Z5 is an integral domain. 10. Let G be a group with subgroups H and K. If | G |= 660, | K |= 66 and K ⊂ H ⊂ G, what are the possible values for | H |? 11. A binary symmetric channel has a probability of p = 0.05 of incorrect transmission. If the codeword c = 011011101 is transmitted what is the probability that (a) single bit error occurs. (b) three errors occurs but no two of them consecutive. 12. Determine whether Z(⊕, ⊙) is a ring with binary operations with x ⊕ y = x + y − 7 and x ⊙ y = x + y − 3xy for all x, y ∈ Z 13. Let R be a ring with unity and a, b be units in R. Prove that ab is a unit of R and ab−1 = b−1 a−1 . 10