Discrete Mathematical Structures - Jun 2015

Computer Science Engg. (Semester 3)

TOTAL MARKS: 100
TOTAL TIME: 3 HOURS (1) Question 1 is compulsory.
(2) Attempt any four from the remaining questions.
(3) Assume data wherever required.
(4) Figures to the right indicate full marks. 1 (a) Define the following terms and give an example for each:
i) Set ii) Proper subset iii) Power set iv) nullset(4 marks) 1 (b) Using Venn diagram, prove that, for any three sets A, B, C, $$ i) \ \overline {(A\cup B) \cap C } = (\overline{A} \cup \overline{B}) \cup \overline{C} \\ ii) \ A- (B \cup C) = (A -B) \cap (A-C) $$(6 marks) 1 (c) In a survey of 120 passengers, an airline found that 48 enjoyed ICE cream with their meals, 78 enjoyed fruits and 66 preferred lime juice. In addition, 36 enjoyed any given pair of these and 24 passengers preferred them all. If two passengers are selected at random from the survey sample of 120, what is the probability that:
i) (Event A) they both want only lime juice with their meals?
ii) (Event B) they both enjoy exactly two the offerings?(6 marks) 1 (d) Prove that the open interval (0, 1) is not a countable set.(4 marks) 2 (a) Define a proposition, a tautology and contradiction. Prove that, for any proposition p,q,r the compound proposition:
[(p→q)^(q→r)] → (p→r) is a Tautology.(7 marks) 2 (b) Prove the logical equivalence by using the laws of logic. $$ (p\to q)\wedge [\neg q \wedge [ r \vee \neg q]] \Leftrightarrow \neg (q \vee p) . $$(7 marks) 2 (c) 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, the 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'.(6 marks) 3 (a) Define, i) open sentence ii) quantifiers iii) free variable iv) bound variable.(4 marks) 3 (b) Negate the following statements: there exists an integer x such that 2x+1=5 and x²=9.(6 marks) 3 (c) Over the universe of all quadrilaterals in plane geometry, verify the validity of the argument. 'Since every square is a rectangle, and every rectangle is a parallelogram, it follows that every square is parallelogram'.(6 marks) 3 (d) Give an indirect proof of the statement 'the product of two even integers is an even integers'.(4 marks)

Define:

4 (a) (i) Well ordering principle(3 marks) 4 (a) (ii) State and prove that principle of mathematical induction.(3 marks) 4 (b) For all the positive integers n, prove that, if n≥24, then n can be written as a sum of 5's and / or 7's.(7 marks) 4 (c) If F₀, F₁, F₂, ..... are Fibonacci numbers, prove that: $$ i) \ \sum^n_{i=0}F_1^2 = F_n \times F_{n+1} \\ ii) \ \sum^n_{i=1} \dfrac {F_1-1}{2^i} = 1 - \dfrac {F_{n+2}}{2^n} $$(7 marks) 5 (a) Let A={1,2,3} and B={2,4,5}. Determine the following:
i) [A×B]
ii) Number of relations from A to B
ii) Number of binary relations on A
iii) Number of relations from A to B that contain (1,2) and (1,5)
v) Number of relation from A to B contain exactly five ordered pairs.
vi) Number of binary relations on A that contain at least seven ordered pairs.(6 marks) 5 (b) Prove that a function f: A→ B is invertible if and only if it is one-to-one and onto.(7 marks) 5 (c) Shirts numbered consecutively from 1 to 20 are won by 20 students of a class. When any 3 of these students are chosen to be debating team from 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 from at least two different teams having the same code number.(7 marks) 6 (a) Let A={1,2,3,4,6} and R be a relation on A defined by a R_b if and only if 'a is a multiple of b'. Write down in the relation matrix M(R) and draw its diagram.(6 marks) 6 (b) For a fixed integer n>1, prove that the relation 'Congruent modulo n' is an equivalence relation on the set of all integers, z.(7 marks) 6 (c) Draw the Hasse diagram representing the positive divisors of 72.(7 marks) 7 (a) If * is an operation on z defined by x*y=x+y+1, prove, that (z, *) is an abelian group.(6 marks) 7 (b) For a group G, prove that the function f: G→G defined by f(a)=a^-1 is in isomorphism if and only if G is abelian.(7 marks) 7 (c) State and prove Language's theorem.(7 marks) 8 (a) For all x, y, z e x^m₂. Prove that:
i) d(x,y) = 0 (y, x)
ii) d(x, y)= 0
iii) d(x,y)=0 if and only if x=y
iv) d(x,z) ≤ d(x, y)+ d(y, z)(6 marks) 8 (b) The generator for an encoding function: $$ E: Z^3_2 \rightarrow Z^6_2 \ is given by $$ $$ G= \begin{bmatrix} 1 &0 &0 &1 &1 &0 \\0 &1 &0 &0 &1 & 1 \\0 &0 &1 &1 &0 &1 \end{bmatrix} $$ i) Find the code words assigned to 110 and 010
ii) Obtain the associated parity - check matrix
iii) Hence decode the received words: 110110, 111101(7 marks) 8 (c) Prove that every finite integral domain is a field.(7 marks)