RGU Question Paper Mathematics Semester VI 2021: Discrete Mathematics

 June-2021

B.A/B. Sc. (VI Semester) Examination

MATHEMATICS

Paper: MATH-363 (N/C)

(Discrete Mathematics)

Full Marks : 80

Pass Marks : 35%

Time : Three Hours

Notes: (i) Answer all questions.

(ii) The figures in the margin indicate full marks for the questions.

I. Answer any five parts: 2x5=10

(a) Let $A=\left\{a,b,c\right\}$ and $P\left(A\right)$ be the it’s power set. Let $\subseteq$ be the inclusion relation on $P\left(A\right)$. Draw the Hasse diagram of the partial ordered set ($\left(\mathrm{P}\left(\mathrm{A}\right),\subseteq )\right)$ .

(b) Let B be a Boolean algebra and 𝑎 be any element in B. Prove that 𝑥=a if 𝑎 +x= 1 and 𝑎 ∗ 𝑥 = 0.

(c)Express the Boolean expression $E=x\left(y\text{'}z\right)\text{'}$ in the disjunctive normal form.

(d) Construct the truth table of the proposition $\sim (p\wedge q)$.

(e)What is the probability of getting a number greater than 2 or an even number in a single through of a fair dice?

(f) Define complete graph and connected graph.

(g) Distinguish between permutation and combination.

II. Answer any four parts: 5x4=20

(a) Define a bounded lattice. Prove that for a bounded distributive lattice, the complements are unique.

(b) What do you mean by logically equivalent statements? Check whether the propositions $\sim (\left(p\vee (\left(\sim p\wedge \mathrm{q))}\right)\right)$ and $\sim p\wedge \sim q$ are equivalent or not.

(c) Draw the logic circuit corresponding to the Boolean expression $y=\overline{a+b.c}+b$.

(d) Define degree of a vertex in a graph. Show that number of odd degree vertices in a graph is always even.

(e)Define mutually exclusive and independent events. Let 𝐴 and 𝐵 be two events such that 𝑃(𝐴) = 0.42, 𝑃(𝐵) = 0.48 and 𝑃(𝐴 𝑎𝑛𝑑 𝐵) = 0.16. Determine 𝑃(A or B) and P(neither A nor B).

(f)How many permutations can be made out of letter in the word COMPUTER ? How many of these (i) begin with letter C, (ii) begin with C and ends with R, and (iii) C and R occupy last two end places?

(g) Let ($\left(L,\wedge ,\vee ,\le )\right)$ be a lattice. Prove that

$a\le c\iff a\vee (\left(b\wedge \mathrm{c)}\right)\le (\left(a\vee \mathrm{b)}\right)\wedge c,\forall a,b,c\in L$

III. Answer any five parts: 10x5=50

(a) (i) Distinguish between tautology and contradiction statements. Check whether the statement $p\vee \sim (p\vee q)$ is a tautology or a contradiction.

(ii) Show that $1^3+2^3+3^3+...+n^3={\left(\frac{n(n+1)}{2}\right)}^{\mathrm{2 }}$by induction. (5+5)

(b) Let $D=\{\left\{1,2,5,7,10,14,35,\mathrm{70\}}\right\}$ be the set of all divisors of 70. If ($\left(D,+,·,\text{'},0,\mathrm{1)}\right)$ be a Boolean algebra, where $a+b=lcm(a,b)$, $a*b=gcd(a,b)$ and $a\text{'}=70/a$. Find the value of the expressions

(i) $x=35*(2+7\text{'}), y=(35*10)+14\text{'}$ and $z=(2+7)*(14+10)\text{'}$.

(ii)Determine whether the $W=\{1,5,10,70\}$ is a Boolean subalgebra of $D_{70}$. Justify. (6+4)

(c) (i) If 𝐴 and 𝐵 are any two events, the prove that

$P(A\cup B)=P\left(A\right)+P\left(B\right)-P(A\cap B)$.

(ii) If ${{18}_C}_r={{18}_C}_{r+2}$, find ${r_C}_5$. (5+5)

(d)(i) Define order and size of a graph. What is the size of a 𝑟-regular graph of order 𝑝?

(ii) Define walk, path and circuit. Show that a tree cannot have a circuit.

(iii) Define a spanning tree and its branch and chords. Find the number of chords of with respect to a spanning tree in a graph of order 𝑛. (2+4+3)

(e) (i) What do you mean by logic gates. ? Describe the operations of OR and NOT gates with two input devices. Give their equivalent electrical circuits.

(ii) Let $E=xy\text{'}+xyz\text{'}+x\text{'}yz\text{'}$ be a Boolean expression. Show that $xz\text{'}+E=E$ and $x+E\ne E$.

(f)(i)Define a well-ordered set. Give an example.

(ii) Define dual of a statement in a lattice 𝐿. Write the dual of the statement $(a\wedge b)\vee c=(b\vee c)\wedge (c\vee a)$.

(iii) Let 𝐿 be a lattice. Show that $a\wedge b=a$ if and only if $a\vee b=b$. (2+3+5)

(g) Define a tree. Show that a tree with 𝑛 vertices has n-1 edges.