DISCRETE MATHEMATICAL STRUCTURES

BCS405A — Comprehensive Solved Question Bank (Exam Target: June/July 2026)

Exam Strategy Guide: This material is systematically grouped module-wise based on 7 separate paper
sets from VTU affiliates. Questions marked with ★ REPEATED ★ have shown 70% to 100% repetition
rates and represent mandatory core knowledge blocks.

MODULE 1 — MATHEMATICAL LOGIC

★ REPEATED ★ Q1. Define Tautology and prove that the following compound proposition is a
Tautology:
{ (p → q) ∧ (q → r) } → (p → r)

SOLUTION:

Definition: A compound proposition that is always true for all possible truth values of its component
propositions is called a Tautology.

Let us construct the Truth Table to verify the conditional statement:

p q r p→q q→r (p → q) ∧ (q → r) p→r { (p → q) ∧ (q → r) } → (p → r)

T T T T T T T T

T T F T F F F T

T F T F T F T T

T F F F T F F T

F T T T T T T T

F T F T F F T T

F F T T T T T T

F F F T T T T T

Since the final column consists entirely of True (T) values, the proposition is a Tautology.

BCS405A - Exam Preparation Pack Page 1

★ REPEATED ★ Q2. Prove the following logical equivalence using Laws of Logic (Without
Truth Table):
p → (q → r) ⇔ (p ∧ q) → r

SOLUTION:

We start from the Left-Hand Side (LHS) and transform it step-by-step:

1. LHS = p → (¬q ∨ r) — By Conditional Identity: x → y ⇔ ¬x ∨ y

2. = ¬p ∨ (¬q ∨ r) — By Conditional Identity applied again
3. = (¬p ∨ ¬q) ∨ r — By Associative Law
4. = ¬(p ∧ q) ∨ r — By De Morgan's Law
5. = (p ∧ q) → r — By Conditional Identity

Hence LHS = RHS. Proved.

★ REPEATED ★ Q3. Verify the validity of the following argument using Rules of Inference:
"If a triangle has two equal sides, then it is isosceles. If it is isosceles, then it has two equal
angles. Triangle PQR does not have two equal angles. Therefore, triangle PQR does not have
two equal sides."

SOLUTION:

Let us define primitive propositions:

• p: Triangle has two equal sides.

• q: Triangle is isosceles.
• r: Triangle has two equal angles.

The premises are: (1) p → q, (2) q → r, (3) ¬r. The conclusion is ¬p.

Formal Derivation:

1. p → q (Premise 1)
2. q → r (Premise 2)
3. p → r (From 1 and 2 by Syllogism)
4. ¬r (Premise 3)
5. ¬p (From 3 and 4 by Modus Tollens)

Since the conclusion matches our formal derivation, the argument is Valid.

BCS405A - Exam Preparation Pack Page 2

★ REPEATED ★ Q4. Prove by Contradiction that "If n is an odd integer, then n + 9 is an even
integer."

SOLUTION:

Let the hypothesis be p: n is an odd integer, and conclusion be q: n + 9 is an even integer.

To prove by contradiction, we assume the negation of the conclusion is true along with the premise. That is,
assume n is odd AND n + 9 is odd.

• Since n is odd, we can write n = 2k + 1 for some integer k.

• Then, substitute n into the expression: n + 9 = (2k + 1) + 9 = 2k + 10 = 2(k + 5).
• Let m = k + 5. Since k is an integer, m is an integer, so n + 9 = 2m.
• This means n + 9 must be an even integer.

This directly contradicts our assumption that n + 9 is odd. Thus, the original statement is true.

★ REPEATED ★ Q5. Determine the truth values of the following statements if the universe
consists of all non-zero integers:
(i) ∃x ∃y [xy = 1] (ii) ∃x ∀y [xy = 1] (iii) ∀x ∃y [xy = 1]

SOLUTION:

• (i) ∃x ∃y [xy = 1]: True. There exists at least one pair. For example, choose x = 1, y = 1. Then 1 × 1 = 1.
• (ii) ∃x ∀y [xy = 1]: False. This claims there is a fixed integer x that when multiplied by ANY integer y equals
1. If x = 1, then for y = 2, 1 × 2 ≠ 1.
• (iii) ∀x ∃y [xy = 1]: False. This claims every non-zero integer has an integer multiplicative inverse. If we pick
x = 2, the required y would be 1/2, which is not an integer.

BCS405A - Exam Preparation Pack Page 3

 MODULE 2 — MATHEMATICAL INDUCTION & COMBINATORICS

★ REPEATED ★ Q1. Prove by mathematical induction for all positive integers n:

1^2 + 2^2 + 3^2 + ... + n^2 = rac{n(n+1)(2n+1)}{6}

SOLUTION:

Let S(n) be the given statement.

Base Step: For n = 1:

LHS = 1^2 = 1
RHS = rac{1(1+1)(2(1)+1)}{6} = rac{1 imes 2 imes 3}{6} = 1. Since LHS = RHS, S(1) is true.

Inductive Step: Assume S(k) is true for some positive integer k:

1^2 + 2^2 + ... + k^2 = rac{k(k+1)(2k+1)}{6}

We must show S(k+1) is true, i.e., 1^2 + 2^2 + ... + k^2 + (k+1)^2 = rac{(k+1)(k+2)(2k+3)}{6}

Adding (k+1)^2 to both sides of our induction hypothesis:

LHS = rac{k(k+1)(2k+1)}{6} + (k+1)^2 = (k+1)\left[ rac{k(2k+1)}{6} + (k+1) ight] = (k+1)\left[ rac{2k^2 + k + 6k
+ 6}{6} ight]
= rac{(k+1)(2k^2 + 7k + 6)}{6} = rac{(k+1)(k+2)(2k+3)}{6} = RHS.
Therefore, S(n) is true for all n \ge 1.

★ REPEATED ★ Q2. Find the number of permutations of the letters in the word
MASSASAUGA under the following conditions:
(i) No restrictions. (ii) All four A's are together. (iii) Begins with letter S.

SOLUTION:

Total letters = 10. Counts: A = 4, S = 3, M = 1, G = 1, U = 1.

• (i) No restrictions: Total arrangements = rac{10!}{4! imes 3!} = rac{3628800}{24 imes 6} = 25,200.
• (ii) All four A's together: Treat the four A's as a single mega-element [AAAA]. Now we have 7 items to
arrange ([AAAA], S, S, S, M, G, U), where S repeats 3 times.
Arrangements = rac{7!}{3!} = 840.
• (iii) Begins with S: Fix the first letter as S. We are left with 9 positions to fill with the remaining letters
(A=4, S=2, M=1, G=1, U=1).
Arrangements = rac{9!}{4! imes 2!} = rac{362880}{24 imes 2} = 7,560.

BCS405A - Exam Preparation Pack Page 4

★ REPEATED ★ Q3. Find the coefficient of a^2 b^3 c^2 d^5 in the expansion of (a + 2b - 3c + 2d +
5)^{16}.

SOLUTION:

By the Multinomial Theorem, the general term in the expansion of (x_1 + x_2 + x_3 + x_4 + x_5)^{n} is:
rac{n!}{n_1! n_2! n_3! n_4! n_5!} (x_1)^{n_1} (x_2)^{n_2} (x_3)^{n_3} (x_4)^{n_4} (x_5)^{n_5}

Here, x_1=a, x_2=2b, x_3=-3c, x_4=2d, x_5=5 and n = 16.

We require powers: n_1=2, n_2=3, n_3=2, n_4=5. Since \sum n_i = 16, the remaining power is n_5 = 16 -
(2+3+2+5) = 4.

The term is: rac{16!}{2! imes 3! imes 2! imes 5! imes 4!} (a)^2 (2b)^3 (-3c)^2 (2d)^5 (5)^4
= rac{16!}{2! 3! 2! 5! 4!} imes [1 imes 8 imes 9 imes 32 imes 625] imes a^2 b^3 c^2 d^5
= 2,522,520 × 1,440,000 × a^2 b^3 c^2 d^5 = 3,632,428,800,000 a^2 b^3 c^2 d^5.

BCS405A - Exam Preparation Pack Page 5

 MODULE 3 — RELATIONS & FUNCTIONS

★ REPEATED ★ Q1. If f(x) = ax + b and g(x) = 1 - x + x^2 such that (g \circ f)(x) = 9x^2 - 9x + 3, find
the values of a and b.

SOLUTION:

First compute the composition expression algebraically:

(g \circ f)(x) = g(f(x)) = g(ax + b) = 1 - (ax + b) + (ax + b)^2

= 1 - ax - b + (a^2x^2 + 2abx + b^2) = a^2x^2 + (2ab - a)x + (1 - b + b^2)

We are given that this is identically equal to 9x^2 - 9x + 3. Equating the coefficients:

1. For x^2: a^2 = 9 \implies a = \pm 3

2. For x: 2ab - a = -9

Case 1: If a = 3
2(3)b - 3 = -9 \implies 6b = -6 \implies b = -1.
Check constant term: 1 - (-1) + (-1)^2 = 1 + 1 + 1 = 3. This matches perfectly.

Case 2: If a = -3
2(-3)b - (-3) = -9 \implies -6b + 3 = -9 \implies -6b = -12 \implies b = 2.
Check constant term: 1 - 2 + 2^2 = 3. This also matches.

Thus, the acceptable pairs are (a = 3, b = -1) or (a = -3, b = 2).

★ REPEATED ★ Q2. Let A = \{1, 2, 3, 4\} and a relation R on A be defined by "xRy if and only if x
divides y". Write down the relation set, draw the digraph, and determine the in-degrees and
out-degrees.

SOLUTION:

Relation Set: Evaluating divisibility on A imes A:

R = \{(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4)\}

Degrees Matrix computation:

• Node 1: Out-going edges to 1,2,3,4 → Out-degree = 4. In-coming edges only from 1 → In-degree = 1.
• Node 2: Out-going edges to 2,4 → Out-degree = 2. In-coming edges from 1,2 → In-degree = 2.
• Node 3: Out-going edges to 3 → Out-degree = 1. In-coming edges from 1,3 → In-degree = 2.
• Node 4: Out-going edges to 4 → Out-degree = 1. In-coming edges from 1,2,4 → In-degree = 3.

BCS405A - Exam Preparation Pack Page 6

★ REPEATED ★ Q3. Draw the Hasse Diagram for the POSET (A, R) where A is the set of all
positive divisors of 36 and the relation is "divides".

SOLUTION:

The elements of set A are the divisors of 36: A = \{1, 2, 3, 4, 6, 9, 12, 18, 36\}.

To establish levels for the Hasse diagram, we stack elements according to vertical chain layers:

• Level 1 (Bottom): 1
• Level 2: 2, 3 (both divided by 1)
• Level 3: 4, 6, 9 (2 divides 4,6; 3 divides 6,9)
• Level 4: 12, 18 (4,6 divide 12; 6,9 divide 18)
• Level 5 (Top): 36 (12,18 divide 36)

The structure forms a symmetric grid graph matching the lattice properties of divisors.

MODULE 4 — COMBINATORICS (INCLUSION-EXCLUSION &

RECURRENCE)

★ REPEATED ★ Q1. Find the number of integers between 1 and 100 (inclusive) that are not
divisible by 2, 3, or 5.

SOLUTION:

Let the total universe size N = 100. Let properties P_1, P_2, P_3 denote divisibility by 2, 3, and 5 respectively.

By floor division, the counts are:

• N(P_1) = \lfloor 100/2 floor = 50, N(P_2) = \lfloor 100/3 floor = 33, N(P_3) = \lfloor 100/5 floor = 20
• N(P_1 P_2) = \lfloor 100/LCM(2,3) floor = \lfloor 100/6 floor = 16
• N(P_2 P_3) = \lfloor 100/LCM(3,5) floor = \lfloor 100/15 floor = 6
• N(P_1 P_3) = \lfloor 100/LCM(2,5) floor = \lfloor 100/10 floor = 10
• N(P_1 P_2 P_3) = \lfloor 100/LCM(2,3,5) floor = \lfloor 100/30 floor = 3

Using the Principle of Inclusion-Exclusion (PIE):

\overline{N} = N - [N(P_1)+N(P_2)+N(P_3)] + [N(P_1 P_2)+N(P_2 P_3)+N(P_1 P_3)] - N(P_1 P_2 P_3)
\overline{N} = 100 - [50 + 33 + 20] + [16 + 6 + 10] - 3 = 100 - 103 + 32 - 3 = 26.
There are exactly 26 integers.

BCS405A - Exam Preparation Pack Page 7

★ REPEATED ★ Q2. List and count all the derangements of the set \{1, 2, 3, 4\}.

SOLUTION:

A derangement is a permutation where no element appears in its original position. For n = 4, the formula
gives:
d_4 = 4! \left( rac{1}{2!} - rac{1}{3!} + rac{1}{4!} ight) = 24 \left( rac{1}{2} - rac{1}{6} + rac{1}{24} ight) = 12 -
4 + 1 = 9.

The 9 explicit derangements are:

Index Derangement Permutation

1 (2, 1, 4, 3)

2 (2, 3, 4, 1)

3 (2, 4, 1, 3)

4 (3, 1, 4, 2)

5 (3, 4, 1, 2)

6 (3, 4, 2, 1)

7 (4, 1, 2, 3)

8 (4, 3, 1, 2)

9 (4, 3, 2, 1)

BCS405A - Exam Preparation Pack Page 8

★ REPEATED ★ Q3. Solve the non-homogeneous recurrence relation:
a_n - 3a_{n-1} = 5 imes 3^n with initial condition a_0 = 2.

SOLUTION:

Step 1: Homogeneous Solution (a_n^{(h)})

The characteristic equation is r - 3 = 0 \implies r = 3. Thus, a_n^{(h)} = C \cdot 3^n.

Step 2: Particular Solution (a_n^{(p)})

The RHS forcing function is f(n) = 5 imes 3^n. Since the base 3 is a simple root of the characteristic equation,
we assume a particular solution of the form: a_n^{(p)} = A \cdot n \cdot 3^n.

Substitute this form back into the main relation:

A \cdot n \cdot 3^n - 3 \left( A \cdot (n-1) \cdot 3^{n-1} ight) = 5 imes 3^n
A \cdot n \cdot 3^n - A \cdot (n-1) \cdot 3^n = 5 imes 3^n
Factor out 3^n: A[n - (n - 1)] = 5 \implies A(1) = 5 \implies A = 5.
So, a_n^{(p)} = 5n \cdot 3^n.

Step 3: Total Solution & Boundary Condition

a_n = a_n^{(h)} + a_n^{(p)} = C \cdot 3^n + 5n \cdot 3^n
Apply initial condition a_0 = 2: 2 = C \cdot 3^0 + 0 \implies C = 2.
Hence, the explicit complete solution is: a_n = 2 \cdot 3^n + 5n \cdot 3^n = (2 + 5n)3^n.

BCS405A - Exam Preparation Pack Page 9

 MODULE 5 — GROUP THEORY

★ REPEATED ★ Q1. State and Prove Lagrange's Theorem in Group Theory.

SOLUTION:

Statement: The order of every subgroup of a finite group divides the order of the group. Mathematically, if H
is a subgroup of a finite group G, then |H| divides |G|.

Proof:

• Let G be a finite group of order n (|G| = n), and let H be a subgroup of order m (|H| = m). We need to prove
that n/m is an integer.
• Consider the collection of left cosets of H in G. A left coset determined by a \in G is defined as aH = \{ah : h
\in H\}.
• We exploit two fundamental properties of cosets:
1. Any two left cosets are either identical or completely disjoint.
2. The union of all left cosets equals G because every element a \in G belongs to its own coset aH (e \in H
\implies a = ae \in aH).
• Let there be k distinct left cosets, say a_1H, a_2H, ..., a_kH. Since they are mutually disjoint and cover G,
we can partition G:
|G| = |a_1H| + |a_2H| + ... + |a_kH|
• Next, we show that every coset contains exactly m elements. Define a mapping \phi: H ightarrow aH by
\phi(h) = ah.
◦ If \phi(h_1) = \phi(h_2) \implies ah_1 = ah_2 \implies h_1 = h_2 (Left cancellation law). Thus, \phi is 1-1.
◦ By definition, \phi is onto. Hence, it is a bijection, meaning |aH| = |H| = m for every coset.
• Substituting this back into the partition equation:
n = m + m + ... + m ext{ (k times)} \implies n = k \cdot m.
• Thus, k = rac{n}{m} = rac{|G|}{|H|}, proving that the subgroup order divides the group order. The integer k
is called the index of H in G (denoted as [G:H]).

BCS405A - Exam Preparation Pack Page 10

★ REPEATED ★ Q2. Let \mathbb{Z} be the set of all integers. Define a binary operation \star on
\mathbb{Z} by x \star y = x + y + 1. Prove that (\mathbb{Z}, \star) is an Abelian Group.

SOLUTION:

To establish that (\mathbb{Z}, \star) is an abelian group, we verify all 5 foundational algebraic axioms:

1. Closure Property: For any x, y \in \mathbb{Z}, x \star y = x + y + 1. Since addition of integers is closed,
(x+y+1) \in \mathbb{Z}. Holds.
2. Associative Property: For any x, y, z \in \mathbb{Z}:
LHS: (x \star y) \star z = (x + y + 1) \star z = (x + y + 1) + z + 1 = x + y + z + 2
RHS: x \star (y \star z) = x \star (y + z + 1) = x + (y + z + 1) + 1 = x + y + z + 2
Since LHS = RHS, associative law holds.
3. Existence of Identity: Let e \in \mathbb{Z} be the identity element. Then x \star e = x.
x + e + 1 = x \implies e + 1 = 0 \implies e = -1. Since -1 \in \mathbb{Z}, identity exists.
4. Existence of Inverse: Let x' be the unique inverse of x. Then x \star x' = e = -1.
x + x' + 1 = -1 \implies x' = -x - 2. Since x \in \mathbb{Z} \implies (-x - 2) \in \mathbb{Z}, every element has an
inverse.
5. Commutative Property: x \star y = x + y + 1 = y + x + 1 = y \star x. Holds.

Since all axioms are valid, (\mathbb{Z}, \star) is an Abelian Group.

BCS405A - Exam Preparation Pack Page 11

★ REPEATED ★ Q3. Let G = S_4 be the symmetric group of permutations on 4 elements. Given
the cyclic permutation permutation element lpha = egin{pmatrix} 1 & 2 & 3 & 4 \ 2 & 3 & 4 & 1
\end{pmatrix}. Find the cyclic subgroup H = \langle lpha angle and determine all its distinct left
cosets in G.

SOLUTION:

Step 1: Determine Subgroup H

We compute powers of the permutation element until we reach the identity mapping ho_0:

• lpha^1 = (1\ 2\ 3\ 4 ightarrow 2\ 3\ 4\ 1)

• lpha^2 = lpha \circ lpha = (1\ 2\ 3\ 4 ightarrow 3\ 4\ 1\ 2)
• lpha^3 = lpha^2 \circ lpha = (1\ 2\ 3\ 4 ightarrow 4\ 1\ 2\ 3)
• lpha^4 = lpha^3 \circ lpha = (1\ 2\ 3\ 4 ightarrow 1\ 2\ 3\ 4) = ho_0 (Identity)

Thus, H = \{ ho_0, lpha, lpha^2, lpha^3\}. Order of subgroup |H| = 4.

Step 2: Distinct Left Cosets

The order of the full group is |S_4| = 4! = 24. By Lagrange's theorem, the number of distinct cosets is ext{index}
= |G|/|H| = 24/4 = 6.

Let's find them sequentially by choosing a permutation element not yet accounted for in previous cosets:

1. First coset is H itself: ho_0 H = H = \{ ho_0, lpha, lpha^2, lpha^3\}.

2. Choose transposition eta = (1\ 2) = egin{pmatrix} 1 & 2 & 3 & 4 \ 2 & 1 & 3 & 4 \end{pmatrix}:
eta H = \{ eta \circ ho_0, eta \circ lpha, eta \circ lpha^2, eta \circ lpha^3\}. These yield four new unique
permutations.
3. Continue choosing unselected permutation elements until 6 mutually exclusive sets of size 4 are
constructed, partitioning the entire 24 elements of S_4.

BCS405A - Exam Preparation Pack Page 12