Discrete Mathematical Structures - Dec 2011

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) If N is the set of positive integers and R is the set of real numbers, examine which of the following sets is empty:
i) {x|x∈N, 2x+7=3}
ii) {x|x∈R, x²+4=6}
iii) {x|x∈R, x²+3x+3=0}(4 marks) 1 (b) Using Venn diagrams, investigate the truth of falsity of:
i) A Δ(B∩C)=(AΔB)∩(AΔC)
ii) A-(B∪C)=(A-B)∩(A-C) for any three sets A, B, C.(6 marks) 1 (c) Simplify the following:
i) A∩(B-A)
ii) (A∩B)∪(A∩B)∪(A∩B∩C∩D).(5 marks) 1 (d) A fair coin is tossed five times. What is the probability that the number of heads always exceeds the number of tails as each outcome is observed.(5 marks) 2 (a) Write the following in symbolic form and establish if the argument is valid: if A gets the supervisor's position and works hard, then he will get a raise. If the gets a raise, then he will by a new car. He has not bought a new car. Therefore A did not get the supervisor's position or he did not work hard.(5 marks) 2 (b) Verify the following withot using thruth tables:
[ [(p o q)wedge( eg r vee s)wedge(pvee r) herefore eg q o s.] ](5 marks) 2 (c) Define tautology. Show that [(p∨q)∧(p→r)∧(q→r)]→r is a tautology, by constructing a truth table.(5 marks) 2 (d) Show that the following argument is invalid by giving a counter example:
[ [(pwedge eg q)wedge left { p o (q o r) ight }] o eg r ](5 marks) 3 (a) Verify the following is valid:
[ forall x[p(x)vee q(x)]; exists x eg p(x) \ forall x [ eg g(x)vee r(x)] \ forall x [s(x) o eg r(x) ] herefore exists x eg s(x)) ](5 marks) 3 (b) Prove that for all real numbers x and y, if x+y>100, then x>50 or y>50(5 marks) 3 (c) Determine if the argument is valid or not. All people concerned about the environment, recycle their plastic containers. B is not concerned about the environment. Therefore, B does not recycle his plastic containers.(5 marks) 3 (d) Negative and simplify:
[ i) forall x[left (p(x)wedge eg q(x)] \ \ ii) exists x [p(x)vee q(x) ight) o r(x)] ](5 marks) 4 (a) Define the following:
i) Well ordering principle
ii) Principle of mathematical induction.(4 marks) 4 (b) Establish the following by mathematical induction:
[ sum^{n}_{t=1}i(2^i)=2+(n-1)2^{n+1} ](5 marks) 4 (c) Find a unique solution for the recurrence relation:
4a_n-5a_n-1=0, n≥1, a₀=1(5 marks) 4 (d) Let F_n denote the n^th Fibonacci number: Prove that [ sum^{n}_{i=1}dfrac{F_{(i-1)}}{2^i}=1 - dfrac {F_{n+2}}{2^n} ](6 marks) 5 (a) Define Cartesian product of two sets. For non-empty set A, B, C prove that, A×(B∩C)=(A×B)∩(A×C).(4 marks) 5 (b) For each of the following functions, determine whether it is 1-1;
i) f:Z→Z, f(x)=2x+1
ii) f:Z→Z, f(x)=x³-x(6 marks) 5 (c) Let A=B=C=R, f:A→B, f(a)=2a+1; g; B→C, g(b)=b/2. compute gof and show that it is invertible.(5 marks) 5 (d) Let ΔABC be an equilateral triangle of side 1. show that if we select 10 points in the interior, there must be at least two points whose distance apart is less than 1/3.(5 marks) 6 (a) for each of the following relations, determine if the relation R is reflexive, symmetric, antisymmetric or transitive.
i) On the set of all line in the plane, l₁Rl₂ if line l₁ is perpendicular to live l₂
ii) On Z, xRy if x-y is even.(5 marks) 6 (b) For A={1,2,3,4,}, let R={(1,1), (1,2),(2,3),(3,3),(3,4)} be a relation on A. Draw the digraph of R² and find the matrix M(R²).(5 marks) 6 (c) Draw the Hasse diagram for all the positive integer division of 72.(5 marks) 6 (d) Let A={1,2,3,4,5,6} × {1,2,3,4,5,6}. Define R on A by (x₁, y₁) R(x₂, y₂) if x₁y₁. Verify that R is an equivalence relation on A.(5 marks) 7 (a) For a group(G₁'), prove that it is abelian if (a,b)²=a²,b² for all a, b∈G.(5 marks) 7 (b) [ Let A=?egin {pmatrix}0&1-1&0 end{pmatrix} ] Verify that (A, A², A³, A⁴) form an abelian group under matrix multiplication.(6 marks) 7 (c) Define a cyclic group. Verify that (Z:,⋅) is cyclic. Find a generator of this group. Examine if it has any subgroups.(9 marks) 8 (a) Determine whether (Z, ⊕,&otimes,) is a ring with the binary operations x⊕y=x+y-7, x⊗y=x+y-3xy for all x,y,∈Z.(6 marks) 8 (b) The (5m, m) five times repetition code has encoding function E:Z₂^m→Z₂^5m. Decoding with D:Z₂^5m → Z₂^m is done by majority rule. With p=0.05, what is the probability for the transmission and correct decoding of the signal 110.(6 marks) 8 (c) What is the minimum distance of a code consisting of the following code words:
001010, 011100, 010111, 011110, 101001? What kind of error can be detected?(3 marks) 8 (d) The encoding function E: Z₂²→Z₂⁵ is given by the generator matrix [ G=?egin{pmatrix}1 &0 &1 &1 &0 \0 &1 &0 &1 &1end{pmatrix} ] what is the error detection capacity of the code?(5 marks)