 MORE IN Discrete Mathematical Structures
VTU Computer Science (Semester 3)
Discrete Mathematical Structures
December 2011
Total marks: --
Total time: --
INSTRUCTIONS
(1) Assume appropriate data and state your reasons
(2) Marks are given to the right of every question
(3) Draw neat diagrams wherever necessary

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, x2+4=6}
iii) {x|x∈R, x2+3x+3=0}
4 M
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 M
1 (c) Simplify the following:
i) A∩(B-A)
ii) (A∩B)∪(A∩B)∪(A∩B∩C∩D).
5 M
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 M

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 M
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 M
2 (c) Define tautology. Show that [(p∨q)∧(p→r)∧(q→r)]→r is a tautology, by constructing a truth table.
5 M
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 M

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 M
3 (b) Prove that for all real numbers x and y, if x+y>100, then x>50 or y>50
5 M
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 M
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 M

4 (a) Define the following:
i) Well ordering principle
ii) Principle of mathematical induction.
4 M
4 (b) Establish the following by mathematical induction:
[ sum^{n}_{t=1}i(2^i)=2+(n-1)2^{n+1} ]
5 M
4 (c) Find a unique solution for the recurrence relation:
4an-5an-1=0, n≥1, a0=1
5 M
4 (d) Let Fn denote the nth Fibonacci number: Prove that [ sum^{n}_{i=1}dfrac{F_{(i-1)}}{2^i}=1 - dfrac {F_{n+2}}{2^n} ]
6 M

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 M
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)=x3-x
6 M
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 M
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 M

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, l1Rl2 if line l1 is perpendicular to live l2
ii) On Z, xRy if x-y is even.
5 M
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 R2 and find the matrix M(R2).
5 M
6 (c) Draw the Hasse diagram for all the positive integer division of 72.
5 M
6 (d) Let A={1,2,3,4,5,6} × {1,2,3,4,5,6}. Define R on A by (x1, y1) R(x2, y2) if x1y1. Verify that R is an equivalence relation on A.
5 M

7 (a) For a group(G1'), prove that it is abelian if (a,b)2=a2,b2 for all a, b∈G.
5 M
7 (b) [ Let A=egin {pmatrix}0&1\-1&0 end{pmatrix} ] Verify that (A, A2, A3, A4) form an abelian group under matrix multiplication.
6 M
7 (c) Define a cyclic group. Verify that (Z:,⋅) is cyclic. Find a generator of this group. Examine if it has any subgroups.
9 M

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 M
8 (b) The (5m, m) five times repetition code has encoding function E:Z2m→Z25m. Decoding with D:Z25m → Z2m is done by majority rule. With p=0.05, what is the probability for the transmission and correct decoding of the signal 110.
6 M
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 M
8 (d) The encoding function E: Z22→Z25 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 M

More question papers from Discrete Mathematical Structures