## Discrete Mathematical Structures - May 2016

### VTU Computer Science (Semester 3)

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 marks

**1(b)** In a survey of 260 college strudents the following data were obtained:

64 had taken mathematics course, 94 had taken computer science, 58 had taken business, 26 had taken both mathematics and computer science, 28 had taken mathematics and business, 22 had taken computer science and business and 14 had taken all the types of courses.

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?
6 marks

**1(c)** Three students write an examination. Their chances of passing are 12,13 and 1412,13 and 14 \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.
6 marks

**2(a)** Define conjuction and disjunction with an example.
6 marks

**2(b)** Prove that (p→(q∨r))↔((p∧∼q)→r)(p→(q∨r))↔((p∧∼q)→r) (p\rightarrow (q\vee r))\leftrightarrow ((p\wedge \sim q)\rightarrow r) is a tautology using the truth table.
6 marks

**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 marks

**2(d)** Establish the validity of the argument

(q ∨ ∼ r) ∨ s

∼ q ∨ (r ∧ ∼ q)

∴ r → s.
6 marks

**3(a)** Write the open statement 'Some straight lines are parallel or all straight lines interest' in symbolic form and find its negation.
6 marks

**3(b)** Test the validity of the following argument:

All employers pay their employees

Anil is an employer

∴ Anil pays his employees.
6 marks

**3(c)** prove by contradiction that 'if n^{2} is an odd integer than n is odd'.
6 marks

**3(d)** prove that for all real numbers x and y if x + y ≥ 100 then x ≥ 50 or y ≥ 50.
6 marks

**4(a)** State the induction principle. Prove by induction that 6^{n+2} + 7^{2n+1} is divisible by 43 for each positive integer n.
6 marks

**4(b)** For the sequence {a_{n}} defined recursively by a_{1}=8, a_{2}=22, a_{n}=4 (a_{n-1} - a_{n-2}) for n ≥ 3 prove that a_{n} = (5+3_{n})2^{n-1} for n ≥ 1.
6 marks

**4(c)** If F_{0}, F_{1}, F_{2} - - - - - are Fibonacci numbers prove that ∑ni=0Fi=Fn+2−1.∑i=0nFi=Fn+2−1. \sum ^n_{i=0}F_i=F_{n+2}-1.
6 marks

**5(a)** Define Cartesian product of two sets. For non empty A, B, C prove that A × (B-C) = (A×B) ' (A×C).
6 marks

**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 R^{2} and R^{3}. Draw their digraphs.
6 marks

**5(c)** Find the number of equivalence relations that can be defined on a finite set A with |A|=6.
6 marks

**6(a)** Let A=R B={x/x is real and x ≥ 0}. Is the function f: A → B defined by f(a) = a^{2} an onto function? A one to one function?
6 marks

**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.
6 marks

**6(c)** Draw the Hasse diagram representing the positive divisors of 36.
6 marks

**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.
6 marks

**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 marks

**7(b)** The parity check matrix for an encoding function E:Z32→Z62E:Z23→Z26 E:Z_{2}^{3}\rightarrow Z_{2}^{6} is given by: <mi>H</mi><mo>=</mo><mrow><mo>(</mo><mtable rowspacing="4pt" columnspacing="1em"><mtr><mtd><mn>1</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>1</mn></mtd><mtd><mn>1</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mn>1</mn></mtd><mtd><mn>1</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>1</mn></mtd><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mn>1</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>1</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>1</mn></mtd></mtr></mtable><mo>)</mo></mrow></math>" role="presentation" style="font-size: 101%; text-align: center; position: relative;">H=⎛⎜⎝101100110010101001⎞⎟⎠<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><mi>H</mi><mo>=</mo><mrow><mo>(</mo><mtable rowspacing="4pt" columnspacing="1em"><mtr><mtd><mn>1</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>1</mn></mtd><mtd><mn>1</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mn>1</mn></mtd><mtd><mn>1</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>1</mn></mtd><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mn>1</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>1</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>1</mn></mtd></mtr></mtable><mo>)</mo></mrow></math><script type="math/tex; mode=display" id="MathJax-Element-5">H=\begin{pmatrix}
1 & 0 & 1 & 1 & 0 & 0\
1 & 1 & 0 & 0 & 1 & 0\
1 & 0 & 1 & 0 & 0 & 1
\end{pmatrix}</script>

i) Determine the associated generator matrix

ii) Does this code correct all single errors in transmission?
6 marks

**7(c)(i)** Define cyclic group
6 marks

**7(c)(ii)** Prove that the group (Z_{4}, +) is cyclic. Find all its generators.
6 marks

**8(a)** State and prove lagrange's theorem.
6 marks

**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.
6 marks

**8(c)** Prove that every finite integral domain is a field.
6 marks