Discrete Mathematical Structures - Dec 2013

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 power set of a set. Determine power sets of the following sets.
A=[a,[b]] B=[ϕ, 1, [ϕ]].(4 marks) 1 (b) Using laws of set theory show that (A∩B)∪[B∩((C∩D)∪(C∩D))]=B∩(A∪C).(5 marks) 1 (c) In a survay of 260 collage students, the following data were obtained; 64 had taken Mathematics course. 94 had take CS course. 58 had take EC course, 28 had taken both Mathematics and EC course, 26 had taken both Mathematics and CS course, 22 had taken both CS and EC course, and 14 had taken all three types of courses. Determine:
i) How many of these students had taken none of the three courses?
ii) How many had taken only CS course?(6 marks) 1 (d) 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 even that the number exceeds 10. Determine Prt(A). Ptr(B). Ptr(A∩B) and Ptr(A∪B).(5 marks) 2 (a) Let p,q be primitive statements for which implication p→q is false. Determine the truth values of the following: i) p∧q ii) ¬p∨q iii) q→p iv) ¬q → ¬p(5 marks) 2 (b) By constructing truth table. Show that the compound propositions p∧(¬ q∨r) and p∨(q∧ ¬ r) are not logically equivalent.(5 marks) 2 (c) Prove that (¬ p∧q)∧(p∧(p∧q)) ⇔ p∧q. Hence deduce that (¬ p∧q)∨(p∨(p∨q) ⇔ p∨q.(5 marks) 2 (d) Show that R∨S follwos logically from the premises C∨D⋅(C∨D)→ ¬ H. ¬ H → (A∧ ¬ B) and (A ∧ ¬ B) and (A∧ ¬ B) → R ∨ S.(5 marks) 3 (a) Write down the converse, inverse and contrapositive of the following statement, for which the set of real numbers is the universe. Also indicate their truth values. ∀_x[ (x>3) → (x²>9)].(6 marks) 3 (b) Write the following proposition in symbolic form and find its negation. For all x, if if x is odd then x²-1 is even.(4 marks) 3 (c) Let p(x), q(x) and r(x) be open statement, determine whether the following argument is valid or not. [ ?egin {align} forall x[p(x) o q(x)] \ forall x[q(x) o r(x)] \ hline { herefore forall x [p(x) o r(x)]} end{align} ](6 marks) 3 (d) Give a direct proof of he statement: " The square of an odd integer is an odd integer".(4 marks) 4 (a) Usinf mathematical induction, prove that 4n<(n²-7) for all positive integers n≥6.(6 marks) 4 (b) For the Fibonacci sequence F₀, F₁, F₂??. Prove that [ F_n=dfrac {1}{sqrt{5}}left [ left ( dfrac {1+sqrt{5}}{2} ight )^2 -left ( dfrac {1-sqrt{5}}{2} ight )^n ight ] ](8 marks) 4 (c) Find an explicit formula for a_n-a_n-1+n, a₁=4 for n ≥2.(6 marks) 5 (a) Define Cartesian product of two sets. For any non-empty sets A,B and C prove that A×(B∪C)=(A×B)∪(A×C).(5 marks) 5 (b) Define the following with one example for each
i) Function ii) one-to-one function iii) on to function.(6 marks) 5 (c) State the pigeonhole principle. AN office employs 13 clerks. Show that at least 2 of them will have birthdays during the same month of the year.(4 marks) 5 (d) Lef f:R→R, g:R→R be defined by f(x)=x², and g(x)=x+5. Determine f⋅g and g⋅f. Show that the composition of two functions is not commutative.(5 marks) 6 (a) Let A={1,2,3,4}, and let R the relation defined by R={(x,y)|x,y∈A, x≤y}. Determine whether R is reflexive, symmetric antisymmetric or transitive.(5 marks) 6 (b) What is partition of a set. If R={(1,1),(1,2),(2,1),(2,2),(3,4),(4,3),(3,3),(4,4)} defined on the set A={1,2,3,4}. Determine the partition included.(5 marks) 6 (c) Define partial order. If R is a relation on A={1,2,3,4} defined by X R Y if x|y. Prove that (A,R) is a POSET. Draw its Hasse diagram.(6 marks) 6 (d) Let A={2,3,4,6,8,12,24} and let ≤ denotes the partial order of divisibility that is x≤y means x|y. Let B={4,6,12}, Determine:
i) All upper bounds of B
ii) All lower bounds of B
iii) Least upper bound of B
iv) Greatest lower bound of B.(4 marks) 7 (a) Define abelian group. Prove that a group G is abelian iff (ab)²=a²b² for all a, b, ∈ G.(7 marks) 7 (b) If H and K are subgroups of group G.Prove that H∩K is also a sub group of G.(5 marks) 7 (c) Define homomarphism anod isomorphism in group. Let f be homonorphism from a group G₁ to group G₂. Prove that
i) if e₁ is the identity in G₁ and e₂ is the identity in G₂ then f(a₁)=e₂
ii) f(a^-1)=[f(a)]^-1 for all a ∈ G₁.(8 marks) 8 (a) An encoding function E:Z₂² → Z₂⁵ is given by the generator matrix:
[ G=?egin{bmatrix} 1&0 &1 &1 &0 \0 &1 &0 &1 &1 end{bmatrix} ]
i) Determine all the code words
ii) Find the associated parity-check matrix H
iii) Use H to decode received words: 1 1 1 0 1, 1 1 0 1 1.(7 marks) 8 (b) A binary symmetric channel has probability P=0.05 of incorrect transmission. If the word C=011011101 is transmitted. What is the probability that i) single error occurs ii) a double error occurs iii) a three error occurs vi) three errors occurs no two of them consecutive?(8 marks) 8 (c) Define a ring In a ring (R,+,0) for all a, b ∈ R, prove that
i) a⋅0=0⋅a=0
ii) a(-b)=(-a)b=-(ab).(5 marks)