BCS405A – Set-1 Solved Model Question Paper

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

Module 1

1.a) Show that the compound proposition
(p \leftrightarrow q) \land (q \leftrightarrow r) \land (r \leftrightarrow p) \equiv (p \rightarrow q) \land (q \rightarrow r) \land (r \rightarrow p)
is logically equivalent for primitive statements p, q, r.

1.b) Establish the validity of the argument using the Rules of Inference:
{p \land (p \rightarrow q) \land (s \lor r) \land (r \rightarrow \sim q)} \rightarrow (s \lor t).

1.c) Let the universe be all integers. Define:
p(x): x > 0,\quad q(x): x\text{ is even},\quad r(x): x\text{ is a perfect square},\quad s(x): x \text{ divisible by } 3,\quad t(x): x \text{ divisible by } 7
Write in symbolic form:

• i) At least one integer is even.
• ii) There exists a positive integer that is even.
• iii) If x is even, then x is not divisible by 3.
• iv) No even integer is divisible by 7.
• v) There exists an even integer divisible by 3.

---

OR

2.a) Define tautology. Prove the proposition is a tautology:
{(p \rightarrow q) \land (q \rightarrow r)} \rightarrow (p \rightarrow r).

2.b) Use laws of logic to prove:
p \rightarrow (q \rightarrow r) \equiv (p \land q) \rightarrow r.

2.c) Prove by:

i) Direct proof

ii) Indirect proof

iii) Contradiction
that “If n is an odd integer, then n + 9 is even”.

Answer

---

Module 2

3.a) Prove by mathematical induction:
1^2 + 3^2 + 5^2 + \cdots + (2n-1)^2 = \frac{n(2n+1)(2n-1)}{3}.

3.b) Let a_0 = 1,\ a_1 = 2,\ a_2 = 3 and
a_n = a_{n-1} + a_{n-2} + a_{n-3} for n \geq 3.
Prove that a_n \leq 3^n\ \forall n \in \mathbb{Z}^+.

3.c) Find number of arrangements of letters in TALLAHASSEE such that no two A’s are adjacent.

---

OR

4.a) Determine the coefficient of xyz^2 in (2x - y - z)^4.

4.b) Distribute 8 identical marbles into 4 distinct containers such that:
i) No container is empty
ii) The 4th container has an odd number of marbles

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

---

Module 3

5.a) 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}(0),\ f^{-1}(1),\ f^{-1}(-1),\ f^{-1}(3),\ f^{-1}(6),\ f^{-1}([-6, 5]),\ f^{-1}([-5, 5])

5.b) State the Pigeonhole Principle.
Prove: Among 29 people, at least 5 share a birthday on the same weekday.

5.c) Let A = {1, 2, 3, 4, 6}. Define relation R on A:
aRb \iff a \text{ is a multiple of } b
Represent R as a matrix, draw the digraph.

---

OR

6.a) If f:A \rightarrow B,\ g:B \rightarrow C,\ h:C \rightarrow D,
prove: h \circ (g \circ f) = (h \circ g) \circ f

6.b) Prove: Among any n + 1 numbers chosen from 1 to 2n, at least one pair adds up to 2n + 1.

6.c) Draw the Hasse diagram for positive divisors of 72.

---

Module 4

7.a) How many permutations of 26 letters avoid patterns CAR, DOG, PUN, BYTE?

7.b) Define Derangement. In how many ways can 10 people each select one left and one right glove from 10 pairs such that no person gets a matching pair?

7.c) Solve the recurrence: C_n = 3C_{n-1} - 2C_{n-2},\quad C_1 = 5,\ C_2 = 3

---

OR

8.a) How many ways to arrange letters in CORRESPONDENTS:

• i) Exactly 2 pairs of consecutive identical letters
• ii) At least 3 such pairs
• iii) No such pairs

8.b) Find rook polynomial of the given board (include image in actual paper)

8.c) Solve: a_{n+2} - 3a_{n+1} + 2a_n = 0,\quad a_0 = 1,\ a_1 = 6

---

Module 5

9.a) Let H, K be subgroups of G. Prove:
H \cap K is also a subgroup. Is H \cup K a subgroup?

9.b) Define Klein-4 group. Verify: A = {1, 3, 5, 7} is a Klein-4 group.

9.c) State and prove Lagrange’s Theorem.

---

OR

10.a) Show that:

• i) The identity of G is unique.
• ii) The inverse of each element of G is unique.

10.b) Prove (A, \cdot) is an abelian group where: A = {a \in \mathbb{Q} \mid a \neq -1},\quad a \cdot b = a + b + ab

10.c) Let G = S_4, \alpha = (1\ 2\ 3\ 4)
Find:

• Subgroup H = \langle \alpha \rangle
• Left cosets of H in G