VTU Discrete Mathematical Structures - December 2014 Exam Question Paper

VTU Computer Science (Semester 3)
Discrete Mathematical Structures
December 2014

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) Simply the set expression

$\left (\overline{(A\cup B)\cap C \cup B} \right )$ with justification.

6 M

1(b) i) Use membership table to establish the set equality of :

$\overline { (A \cap B)\cup (\overline {A}\cap C) }=\left ( A\cap \overline {B} \right )\cup \left ( \overline {A} \cap \overline {C} \right )$
ii) IF a - { 1,2,3,4,5,6,7}, Determine the number of subsets of A containing elements,subsets of A 1,2, and subsets of A with even number of elements.

7 M

1(c) The sample space of an experiment is S-{a,b,c,d,e,f,g,h}. if event A= {a,b,c} and event B- {a,c,e,g}, determine

$P_{r}(A), P_{r}(B),P_{r}(A\cap B),P_{r} (A\cap B),P_{r}(A\cup B),P_{r}(\overline{A}),P_{r}(A\cap\overline {B}) \ and \ P_{r}(\overline {A}\cup B).$

7 M

2(a) Construct truth table for :

$i)\ [P{\wedge}(p\rightarrow q)]\rightarrow q \\ ii) \ [P\rightarrow q)\wedge(q\rightarrow r)]\rightarrow (p\rightarrow r)$

6 M

2(b) simplify the switching network using the laws of logic.

7 M

2(C) Establish the following argument by the methods of proof by contradiction.

$P\rightarrow (q\wedge r) \\ r\rightarrow s \\ \begin{matrix} \sim (q\wedge s) \\ \overline{\ \ \ \therefore \sim P \ \ \ } \end{matrix}$

7 M

3(a) Negate and simplify each of following :
i)\exists x,[p(x)\Lambda q(x)] \\ ii) \forall x,[p(x)\wedge\sim q(x)] \\ iii)\forall x,[p(x)\rightarrow q(x)] \\ iv)\exists x,[(p(x)\vee q (x)) \rightarrow r(x)\]

6 M

3(b) Find whether the following argument is valid. No engineering student of first and second semester studies logic.

$\dfrac{Anil \ is \ an \ engineering \ student \ who \ studies \ logic}{\therefore Anil \ is \ not \ in \ second \ semester }$

7 M

3(c) Give : i) a direct proof ii) an indirect proof and iii) proof by contradiction for the following statement.If m is an even integer

7 M

4(a)

$if H_{1}=1,H_{2}=1+\dfrac{1}{2}+;H_{N}=1+\dfrac{1}{2}+----+1/n$ are harmonic numbers,then prove that for all

$n\varepsilon z^{1} \sum_{1=1}^{n}H_{1}=(n+1)H_{n}-n$

6 M

4(b) find all

$n \varepsilon z^{+}$ prove that : \[\sum_{1=1}^{n}\frac{1}{i(i+1)} = \frac{n}{n+1}\\ \sum_{i=1}^{a}i(2^{i}) = 2+(n-1)2^{n+1}/]

7 M

4(c)

$IF A,B_{1,}B_{2}----,A_{n}\subseteq U, then prove that : \\ A_{1}\cap A_{2} \cap ----\cap A_{n}=\overline A \cup \overline A_{2}\cup ----\cup \overline A_{n} \\ ii)If A,B_{1},B_{2}----B_{n}\subseteq U \ than \ prove \ that \ A\cap B_{1} \cup B_{2} \ \cup---- \ \cup \ B_{n} )-(A \ \cap \ B_{1} )J \ (A \ \cap \ B_{2}\) \ \cup ----(A \ \cap \ B_{n}.$

7 M

5(a) Find the number of ways of distributing 6 objects among 4 identical containers with some containers possibly empty.

6 M

5(b) (i) Prove that the function :

$R \times R \rightarrow R$ defined by f(a,b)=[a+b] is commutative but not associative.
ii) prove that if 30 dictionaries in a library contains a total of 61,327 pages,then at least one of the dictionary must have at least 2045 pages.

7 M

5(c) Let f :

$R \rightarrow R$ be defined by

$f(\times)= \left\{\begin{matrix} 3\times- \ 5 & for \times > 0 \\ - \ 3 \ \times + \1 & for \times \leq 0 \end{matrix}\right.$
then determine

$f_{1}\ (-1),f^{-1} (3),f^{-1}(6),(-5,5).$

7 M

6(a) give a set A with A - n and a relation R on A,let M denote the relation matrix for R then prove that :
i) R is symmetric if and only if [M = M^{1}]
[R is transitive if and only if M.M = M^{2}leq M.]

6 M

6(b) I CT A - { 1,2,3,4,6,8,12} and R BE THE ORDERING ON A defined by a

$R_{b}$ if a divides b then
i) Draw the Hasse diagram of the Poset (A,R)
II) Determine the relation matrix for R
iii) Topologically sort the Poset (A, R)

7 M

6(C) Let A -[{1,2,3,4,5} imes {1,2,3,4,5}, and define R on A by (x_{1} y_{1})R (x_{2} y_{2}) if x_{1} + y_{1}= x_{2} - y_{2}] < br> i) Verify that R is an equivalence relation on A
ii) Determine the equivalence classes [(1,3)],[(2,4)] and [1,1)]
Determine the partition of A induced by R.

7 M

7(a) In a group

$s_{6}$ let

$\alpha =\begin{pmatrix} 1 &2 &3 &4 &5 &6 \\3 &1 &4 &6 &2 &5 \end{pmatrix}\\ \beta =\begin{pmatrix} 1&2 &3 &4 &5 &6 \\4 &2 &6 &1 &3 &5 \end{pmatrix} \\ Determine \ \alpha \beta ,\ \alpha ^{3},\beta ^{4},(\alpha \beta )^{^{-1}}$

6 M

7(b) Define cyclic group and prove that every subgroup of a cyclic group is cyclic.

7 M

7(c) Define the coding function [E: Zfrac{3}{2} ightarrow Zfrac{6}{2}] by means of parity - check
[H= egin{bmatrix} 1&0 &1 &1 &0 &0 \1 &1 &0 &0 &1 &0 \1 &0 &0 &0 &0 &1 end{bmatrix}] and determine all code words.

7 M

8(a) Let

$E : Z\frac{M}{2} \ \rightarrow Z\frac{n}{2}$ be an encoding function given by a generator matrix G or the ass parity check matrix H then prove that

$C = E :(Z\frac{M}{2})$ is a group code.

6 M

8(b) i) Define subring and ideal
ii)

$IF \ A - \left \{ \begin{bmatrix} a &o \\ b &c \end{bmatrix}a,b,c,e,z \right \}$ be the subset of the ring R =

$M_{2}(z)$ then prove that A is a subring but not ideal.

7 M

8(c) i) Prove that

$z_{n}$ is a field if and only if n is a prime.
ii) Prove that in

$z_{n,}[a]$ is a unit if and only if gcd (a,n) = 1

7 M

More question papers from Discrete Mathematical Structures

SPONSORED ADVERTISEMENTS