BCS405A – Set-2 Solved Model Question Paper

BCS405A – Discrete Mathematical Structures Set-2 Solved Model Question Paper with Answer

Module 1

1.a) Define tautology. Show that the proposition
[(p \lor q) \land (p \rightarrow r) \land (q \rightarrow r)] \rightarrow r
is a tautology using a truth table.

1.b) Prove using laws of logic: (\lnot p \land (\lnot q \land r)) \lor ((q \land r) \lor (p \land r)) \Leftrightarrow r

1.c) For any two odd integers m and n, prove:

• i) m + n is even
• ii) m \cdot n is odd

---

OR

2.a) Define:- Open Statement , Quantifiers

2.b) Represent the following argument symbolically and establish validity: “If A gets the Supervisor’s position and works hard, then he will get a raise. If he gets a raise, then he will buy a car. He has not purchased a car. Therefore, he did not get the Supervisor’s position or he did not work hard.”

2.c) Universe:- Non-zero integers Determine truth value of

a) \exists x\ \exists y\ (xy = 1)

b) \exists x\ \forall y\ (xy = 1)

c) \forall x\ \exists y\ (xy = 1)

d) \exists x\ \exists y\ ((2x + y = 5) \land (x - 3y = -8))

e) \exists x\ \exists y\ ((3x - y = 7) \land (2x + 4y = 3))

---

Module 2

3.a) Define Well Ordering Principle. Prove using induction: n! \geq 2^{n - 1},\quad \forall n \geq 1

3.b) Prove: Every positive integer n \geq 24 can be expressed as a sum of 5’s and/or 7’s.

3.c) How many numbers n > 5,000,000 can be formed using digits 3, 4, 4, 5, 5, 6, 7?

---

OR

4.a) Prove by mathematical induction: 1 \cdot 3 + 2 \cdot 4 + \cdots + n(n + 2) = \frac{n(n + 1)(2n + 7)}{6}

4.b) Find permutations of MASSASAUGA:

• i) Total
• ii) When all four A’s are together
• iii) That begin with S

4.c) i) Find coefficient of a^5b^2 in (2a - 3b)^7
ii) Find coefficient of x^5y^2 in (x + y)^7 using Binomial Theorem

---

Module 3

5.a) State the Pigeonhole Principle. Prove: From numbers 1 to 8, any selection must include two that sum to 9.

5.b) Let f: \mathbb{R} \rightarrow \mathbb{R} be defined by: f(x) =\begin{cases}3x - 5 & \text{if } x > 0 \ 1 - 3x & \text{if } x \leq 0 \end{cases}

Find f^{-1}([-6, 5]) and f^{-1}([-5, 5]).

5.c) Let A = B = C = \mathbb{R},
f(a) = 2a + 1,\quad g(b) = \frac{1}{3}b
Find g \circ f, show it is invertible, and find (g \circ f)^{-1}.

---

OR

6.a) Let f(x) = ax + b,\quad g(x) = 1 - x + x^2. If (g \circ f)(x) = 9x^2 - 9x + 3, find values of a and b.

6.b) Draw the Hasse diagram for the positive divisors of 36.

6.c) Let A = {1, 2, 3, 4, 6}, and R is defined by:
aRb \iff a \text{ is a multiple of } b
Write relation R, matrix M(R), digraph, and find in-degree, out-degree of each node.

---

Module 4

7.a) Find count of positive integers n such that 1 \leq n \leq 100 and n is not divisible by 2, 3, or 5.

7.b) In how many ways can 26 letters be arranged such that CAR, DOG, PUN, BYTE are avoided?

7.c) Solve: a_n = n \cdot a_{n - 1},\quad a_0 = 1

---

OR

8.a) In how many ways can letters: 5 a’s, 4 b’s, 3 c’s be arranged such that all identical letters are not in a single block?

8.b) 5 teachers (T₁ to T₅) are to be assigned to 5 classes (C₁ to C₅). Restrictions:

• T₁, T₂ not for C₁ or C₂
• T₃, T₄ not for C₄ or C₅
• T₅ not for C₃, C₄, or C₅
  Find the number of valid assignments.

8.c) Solve: F_{n+2} = F_{n+1} + F_n,\quad F_0 = 0,\ F_1 = 1

---

Module 5

9.a) Define a group. Prove: The fourth roots of unity form an Abelian group.

9.b) Let G = \mathbb{R} \setminus {0}, and define operation:
a * b = \frac{ab}{2}
Show that (G, *) is an Abelian group.

9.c) Define Klein 4-group. Verify:
A = {e, a, b, c} is a Klein-4 group.

---

OR

10.a) Define cyclic group. Given the following multiplication table, show that (G, \cdot) is cyclic:

*	a	b	c	d	e	f
a	a	b	c	d	e	f
b	b	c	d	e	f	a
c	c	d	e	f	a	b
d	d	e	f	a	b	c
e	e	f	a	b	c	d
f	f	a	b	c	d	e

10.b) State and prove Lagrange’s Theorem.

10.c) Let group G have subgroups H and K such that:
|G| = 660,\quad |K| = 66,\quad K \subseteq H \subseteq G
Find possible values for |H|.