VTU Computer Science (Semester 3)
Discrete Mathematical Structures
June 2013
Total marks: --
Total time: --
(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) Define a set proper subset and power set, with an example for each.
6 M
1 (b) A survey of 500 television viewers of a sports channel produced the following information: 285 watch cricket, 195 watch hockey, 115 watch football, 45 watch cricket and football, 70 watch cricket and hockey, 50 watch hokey and football and 50 do any of the three kinds of games.
i) How many viewers in the survay watch all three games?
ii) How many watch exactly one of the sports?
7 M
1 (c) The probability that a contractor will get a plumbing contract is 2/3 and the probability that he will not get an electric contract is 5/9. If the probability of getting at least one contract is 4/5. What is the probability that he will get both the contracts?
7 M

2 (a) Define a tautology and contradiction. Prove that the proposition [(p→r) ∧ (q→r)] → (p∨q) → r] is a tautology.
6 M
2 (b) Prove the following logical equivalences using laws of logic
i) [(∼p∨∼q) → (p∧q∧r)] ⇔ p∧q
ii) p→ (q→r)⇔(p∧q)→r.
7 M
2 (c) Define converse, inverse and countrapositive of a conditional with truth table. Also state the converse, inverse and contrapositive of the following statement.
"If a triangle is not isosceles, then it is not equilateral".
7 M

3 (a) Write down the following proposition in symbolic form find its negation:
"All integers are rational numbers and some rational numbers are not integers".
6 M
3 (b) Show that the following argument is valid. NO engineering student of first or second semester studies logic
Anil is an engineering student who studies logic
Therefore Anil is not in second semester.
7 M
3 (c) Give i) direct proof ii) an indirect proof iii) proof by contradiction for the following statement:
"If n is an odd integer, then n + g is an even integer".
7 M

4 (a) State the induction principle. Prove the following result by mathematical induction: "For every positive integer n, 5 divides n5-n".
6 M
4 (b) Find an explicit definition of the sequence defined by a1=7, an=2an+1+1 for n≥2.
7 M
4 (c) If L0, L1, L2??. Are Lucas numbers, prove that
[ L_n=left [ dfrac {1+sqrt{5}}{2} ight ]^n + left [ dfrac {1-sqrt{5}}{2} ight ]^n ]
7 M

5 (a) For any non-empty A, B, C prove the following:
i) (A∩B)×C=(A×C)∩(B×C)
ii) A×(B-C)=(A×B)-(A×B).
6 M
5 (b) Define a binary relation. Let A={1,2,3,4,6} and R a relation on A defined by aRb if and only if a is a multiple of b. Represent R as a set ordered pairs. Draw the digraph of R. Write the matrix of R.
7 M
5 (c) Define an equivalence relation. Let N be the set of all natural numbers, On N×N, the relation R is defined as (a,b)R (c,d) if and only if a+b=d+c, show that R is an equivalence relation. Find the equivalence class of the element (2,5).
7 M

6 (a) Let f:z→z be defined by f(a)=a+1 for a∈z. Show that f is a bijection.
6 M
6 (b) Find the number of ways of distributing four district objects among three identical containers with some containers (s) possibly empty.
7 M

7 (c) The word C=1010110 is sent through a binary symmetric channel. If p=0.02 is the probability of incorrect receipt of a signal, find the probability that C is received as r=1011111. Determine the error pattern.
7 M

8 (a) The parity check matrix for an encoding function E: z23 → z26 given by [ H=egin{bmatrix} 1&0 &1 &1 &0 &0 \1 &1 &0 &0 &1 &0 \1 &0 &1 &0 &0 &1 end{bmatrix} ] i) Determine the associated generator matrix
ii) Does this code correct all single errors in transmissions?
6 M
8 (b) For the following encoding function, find the minimum distance between the code words. Indicate the error-detecting and error-correcting capabilities of each code.
E:z23 → z26 defined by
E(0 0 0)=000111
E(0 0 1)=001001
E(0 1 0)=010010
E(0 1 1)=011100
E(1 0 0)=100100
E(1 0 1)=101010
E(1 1 0)=110001
E(1 1 1)=111000
7 M
8 (c) Prove that the set z with binary operation ⊕ and ⊙ defined by x⊕y=x+y-1, x⊙y=x+y-xy is commutative ring.
7 M

More question papers from Discrete Mathematical Structures