MORE IN Discrete Mathematical Structures
VTU Computer Science (Semester 3)
Discrete Mathematical Structures
May 2016
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) Define subset, disjoint sets and complement of a set with an example for each
6 M
1(b) In a survey of 260 college strudents the following data were obtained:
i) How many students were surveyed who had taken none of the three types of courses?
ii) How many had taken only computer science course?
7 M
1(c) Three students write an examination. Their chances of passing are $$\dfrac{1}{2},\dfrac{1}{3}\ \text{and}\ \dfrac{1}{4}$$ respectively. Find the probability that : i) all of them pass ii) at leat one of them passes and iii) at least two of them pass.
7 M

2(a) Define conjuction and disjunction with an example.
4 M
2(b) Prove that $$(p\rightarrow (q\vee r))\leftrightarrow ((p\wedge \sim q)\rightarrow r)$$ is a tautology using the truth table.
5 M
2(c) Define converse of a conditional. State the converse and inverse of the following statement 'If Ram can solve the puzzle then Ram can solve the problem'.
6 M
2(d) Establish the validity of the argument
(q ∨ ∼ r) ∨ s
∼ q ∨ (r ∧ ∼ q)
∴ r → s.
5 M

3(a) Write the open statement 'Some straight lines are parallel or all straight lines interest' in symbolic form and find its negation.
4 M
3(b) Test the validity of the following argument:
All employers pay their employees
Anil is an employer
∴ Anil pays his employees.
6 M
3(c) prove by contradiction that 'if n2 is an odd integer than n is odd'.
5 M
3(d) prove that for all real numbers x and y if x + y ≥ 100 then x ≥ 50 or y ≥ 50.
5 M

4(a) State the induction principle. Prove by induction that 6n+2 + 72n+1 is divisible by 43 for each positive integer n.
6 M
4(b) For the sequence {an} defined recursively by a1=8, a2=22, an=4 (an-1 - an-2) for n ≥ 3 prove that an = (5+3n)2n-1 for n ≥ 1.
7 M
4(c) If F0, F1, F2 - - - - - are Fibonacci numbers prove that $$\sum ^n_{i=0}F_i=F_{n+2}-1.$$
7 M

5(a) Define Cartesian product of two sets. For non empty A, B, C prove that A × (B-C) = (A×B) ' (A×C).
7 M
5(b) If A={1, 2, 3, 4} and R is a relation on A defined by R={(1, 2) (1, 3) (2, 4) (3, 2) (3, 3) (3, 4)} find R2 and R3. Draw their digraphs.
6 M
5(c) Find the number of equivalence relations that can be defined on a finite set A with |A|=6.
7 M

6(a) Let A=R B={x/x is real and x ≥ 0}. Is the function f: A → B defined by f(a) = a2 an onto function? A one to one function?
5 M
6(b) Let A={1, 2, 3, 4} f and g be functions from A to A given by:
f={(1, 4) (2, 1) (3, 2) (4, 3)}     g={(1, 2) (2, 3) (3, 4) (4, 1)} prove that f and g are inverse of each other.
5 M
6(c) Draw the Hasse diagram representing the positive divisors of 36.
5 M
6(d) Let A = {1, 2, 3, 4, 5, 6, 7}. R be the equivalence relation on A that induces the partition A = {1, 2} ∪ {3} ∪ {4, 5, 7} ∪ {6}. Find R.
5 M

7(a) 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 triple error occurs?
6 M
7(b) The parity check matrix for an encoding function $$E:Z_{2}^{3}\rightarrow Z_{2}^{6}$$ is given by: $H=\begin{pmatrix} 1 & 0 & 1 & 1 & 0 & 0\\ 1 & 1 & 0 & 0 & 1 & 0\\ 1 & 0 & 1 & 0 & 0 & 1 \end{pmatrix}$
i) Determine the associated generator matrix
ii) Does this code correct all single errors in transmission?
7 M
7(c)(i) Define cyclic group
4 M
7(c)(ii) Prove that the group (Z4, +) is cyclic. Find all its generators.
4 M

8(a) State and prove lagrange's theorem.
6 M
8(b) Prove that the set Z with binary operations ⊕ and ⊙ defined by:
x ⊕ y = x + y - 1
x ⊙ y = x + y - xy
is a commutative ring with unity.
7 M
8(c) Prove that every finite integral domain is a field.
7 M

More question papers from Discrete Mathematical Structures