Discrete Structure 2022 Board Question Paper

Step-by-Step Solutions: Brief Answer Questions

a. Two Examples of Propositions:

1. “Kathmandu is the capital city of Nepal.” (True proposition)
2. “$2 + 5 = 12$” (False proposition)

b. State Absorption Law:

In Boolean algebra and propositional logic:

$$p \lor (p \land q) \equiv p \quad \text{and} \quad p \land (p \lor q) \equiv p$$

c. Quantifier Representation: “Not all politicians are bad”

Let $P(x)$ be “$x$ is a politician” and $B(x)$ be “$x$ is bad”:

$$\mathbf{\neg \forall x (P(x) \to B(x)) \quad \equiv \quad \exists x (P(x) \land \neg B(x))}$$

d. Two Ways to Represent a Relation:

1. Matrix Representation (Boolean / 0-1 Matrix $M_R$)
2. Directed Graph (Digraph) Representation

e. Ceiling Function Definition & Value for $\lceil x \rceil = -1$:

• The ceiling function $\lceil x \rceil$ assigns to real number $x$ the smallest integer greater than or equal to $x$.
• $\lceil x \rceil = -1 \iff \mathbf{-2 < x \le -1}$.

f. Complete Bipartite Graph ($K_{m,n}$):

A simple graph whose vertices can be partitioned into two disjoint subsets $V_1$ (size $m$) and $V_2$ (size $n$) such that every vertex in $V_1$ is connected by an edge to every vertex in $V_2$, and no edges connect vertices within the same partition.

g. Pairwise Relatively Prime:

A set of integers $\{a_1, a_2, \dots, a_k\}$ is pairwise relatively prime if $\gcd(a_i, a_j) = 1$ for all $i \neq j$.

• Example: The set $\{10, 17, 21\}$ is pairwise relatively prime since $\gcd(10, 17) = 1$, $\gcd(17, 21) = 1$, and $\gcd(10, 21) = 1$.

h. Arrangements of the Word “DISCRETE”:

The word has 8 letters: D, I, S, C, R, E, T, E (E occurs twice).

$$\text{Total Permutations} = \frac{8!}{2!} = \frac{40,320}{2} = \mathbf{20,160 \text{ arrangements}}$$

i. Euler Path vs. Hamilton Path:

• Euler Path: A path in a graph that visits every edge exactly once.
• Hamilton Path: A path in a graph that visits every vertex exactly once.

j. Pigeonhole Principle:

If $k$ is a positive integer and $k + 1$ or more objects are placed into $k$ boxes, then at least one box must contain two or more objects.

Proposition, Predicate, Inverse, and Converse

• Proposition: A declarative statement that is either definitively true or false, but not both.
• Predicate: A statement containing variables that becomes a proposition when values are assigned to those variables (e.g., $P(x): x > 3$).

Given Implication: $p \to q$

• Converse: $q \to p$
• Inverse: $\neg p \to \neg q$

---

a. “If you send me an email message ($p$), then I will finish writing the program ($q$).”

• Converse: “If I finish writing the program, then you sent me an email message.”
• Inverse: “If you do not send me an email message, then I will not finish writing the program.”

---

b. “If Aldo is Italian ($p$), then Bob is not English ($q$).”

• Converse: “If Bob is not English, then Aldo is Italian.”
• Inverse: “If Aldo is not Italian, then Bob is English.”

Recurrence Relation: First 5 Terms

A recurrence relation is an equation that recursively defines a sequence where each term is expressed as a function of preceding terms.

Given:

$$a_n = 2a_{n-1} + 3a_{n-2} \quad \text{with } a_0 = 1, \quad a_1 = 3$$

• $a_0 = \mathbf{1}$
• $a_1 = \mathbf{3}$
• $a_2 = 2a_1 + 3a_0 = 2(3) + 3(1) = 6 + 3 = \mathbf{9}$
• $a_3 = 2a_2 + 3a_1 = 2(9) + 3(3) = 18 + 9 = \mathbf{27}$
• $a_4 = 2a_3 + 3a_2 = 2(27) + 3(9) = 54 + 27 = \mathbf{81}$

The first 5 terms are: 1, 3, 9, 27, 81 (Notice the closed form is $a_n = 3^n$).

Proof: Equivalence Relation for $|a - b|$ is Even

Let $R = \{(a, b) \in \mathbb{Z}^+ \times \mathbb{Z}^+ : |a - b| \text{ is even}\}$.

1. Reflexive: For any $a \in \mathbb{Z}^+$, $|a - a| = 0 = 2(0)$, which is an even integer. Thus, $(a, a) \in R$.
2. Symmetric: Assume $(a, b) \in R \implies |a - b| = 2k$ for some integer $k$. Since $|b - a| = |-(a - b)| = |a - b| = 2k$, $|b - a|$ is also even. Hence, $(b, a) \in R$.
3. Transitive: Assume $(a, b) \in R$ and $(b, c) \in R \implies a - b = 2k_1$ and $b - c = 2k_2$. Adding both equations:
   $$(a - b) + (b - c) = a - c = 2k_1 + 2k_2 = 2(k_1 + k_2)$$
   Thus, $|a - c|$ is even, meaning $(a, c) \in R$.

Since $R$ is reflexive, symmetric, and transitive, $R$ is an equivalence relation.

Bubble Sort Algorithm & Trace for: [30, 20, 11, 45, 10]

Sorting is the algorithmic process of arranging an arbitrary collection of data elements into a specified order (ascending or descending).

Step-by-Step Trace:

• Initial Array: [30, 20, 11, 45, 10]
• Pass 1:
  • Compare (30, 20) $\to$ Swap: [20, 30, 11, 45, 10]
  • Compare (30, 11) $\to$ Swap: [20, 11, 30, 45, 10]
  • Compare (30, 45) $\to$ No Swap: [20, 11, 30, 45, 10]
  • Compare (45, 10) $\to$ Swap: [20, 11, 30, 10, 45]
• Pass 2:
  • Compare (20, 11) $\to$ Swap: [11, 20, 30, 10, 45]
  • Compare (20, 30) $\to$ No Swap: [11, 20, 30, 10, 45]
  • Compare (30, 10) $\to$ Swap: [11, 20, 10, 30, 45]
• Pass 3:
  • Compare (11, 20) $\to$ No Swap: [11, 20, 10, 30, 45]
  • Compare (20, 10) $\to$ Swap: [11, 10, 20, 30, 45]
• Pass 4:
  • Compare (11, 10) $\to$ Swap: [10, 11, 20, 30, 45]

Final Sorted Array: [10, 11, 20, 30, 45]

Binomial Theorem & Coefficient Calculation

The Binomial Theorem states that for any non-negative integer $n$:

$$(x + y)^n = \sum_{k=0}^n \binom{n}{k} x^{n-k} y^k$$

where $\binom{n}{k} = \frac{n!}{k!(n-k)!}$ are the binomial coefficients.

Coefficient of $x^2 y^3$ in $(x + y)^5$:

Here $n = 5$. We need the term where $x$ has power 2 and $y$ has power 3:

$$\text{Term} = \binom{5}{3} x^{5-3} y^3 = \binom{5}{3} x^2 y^3$$

$$\binom{5}{3} = \frac{5!}{3!(5-3)!} = \frac{5 \times 4 \times 3!}{3! \times 2 \times 1} = \frac{20}{2} = \mathbf{10}$$

The coefficient of $x^2 y^3$ is 10.

Growth of Functions & Big-O Proof

Analyzing the growth of functions allows computer scientists to characterize the scalability and resource efficiency of algorithms independent of machine hardware and compiler optimizations.

Proof: $f(x) = 3x^2 + 8x + 7$ is $O(x^2)$

By definition, $f(x)$ is $O(g(x))$ if there exist positive constants $C$ and $k$ such that:

$$|f(x)| \le C |g(x)| \quad \text{for all } x > k$$

For all $x \ge 1$:

$$8x \le 8x^2 \quad \text{and} \quad 7 \le 7x^2$$

Therefore:

$$3x^2 + 8x + 7 \le 3x^2 + 8x^2 + 7x^2 = 18x^2$$

Choosing witnesses $C = 18$ and $k = 1$:

$$|3x^2 + 8x + 7| \le 18 |x^2| \quad \forall x \ge 1$$

Hence, $3x^2 + 8x + 7 = \mathbf{O(x^2)}$. $\blacksquare$

Degree of a Vertex & Graph Invariants for Isomorphism

• Degree of a Vertex $\deg(v)$: The number of edges incident with vertex $v$, with self-loops counted twice.

Necessary Invariants for Graph Isomorphism:

Two graphs $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$ can be isomorphic only if they preserve:

1. Equal number of vertices ($|V_1| = |V_2|$)
2. Equal number of edges ($|E_1| = |E_2|$)
3. Identical degree sequence (multiset of vertex degrees)
4. Preservation of subgraphs and cycles of specific length $k$
5. Equal connected components and chromatic numbers

Adjacency Matrix vs. Incidence Matrix Representation

Let a simple undirected graph have vertices $V = \{v_1, v_2, v_3\}$ and edges $e_1 = (v_1, v_2), e_2 = (v_2, v_3)$:

1. Adjacency Matrix $A = [a_{ij}]$ (Size $n \times n$):

$a_{ij} = 1$ if an edge connects $v_i$ and $v_j$; otherwise $0$:

$$A = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix}$$

2. Incidence Matrix $M = [m_{ij}]$ (Size $n \times m$):

$m_{ij} = 1$ if vertex $v_i$ is incident with edge $e_j$; otherwise $0$:

$$M = \begin{pmatrix} 1 & 0 \\ 1 & 1 \\ 0 & 1 \end{pmatrix}$$

Mathematical Induction Proof: $n^3 + 2n$ is Divisible by 3

Let $P(n)$ be the proposition that $n^3 + 2n$ is divisible by 3 for all integers $n \ge 1$.

1. Base Step ($n = 1$):
   $$P(1): 1^3 + 2(1) = 1 + 2 = 3$$
   Since 3 is divisible by 3, $P(1)$ is true.
2. Inductive Hypothesis: Assume $P(k)$ is true for some integer $k \ge 1$, so $k^3 + 2k = 3m$ for some integer $m$.
3. Inductive Step ($n = k + 1$):
   $$(k + 1)^3 + 2(k + 1) = (k^3 + 3k^2 + 3k + 1) + (2k + 2)$$
   $$= (k^3 + 2k) + 3k^2 + 3k + 3 = 3m + 3(k^2 + k + 1) = 3(m + k^2 + k + 1)$$
   Since $(m + k^2 + k + 1)$ is an integer, $(k + 1)^3 + 2(k + 1)$ is divisible by 3.

Therefore, by mathematical induction, $n^3 + 2n$ is divisible by 3 for all $n \ge 1$. $\blacksquare$

Indirect Proof: If $n^2$ is Odd, Then $n$ is Odd

We prove the claim via proof by contraposition. The implication is $P \to Q$, where $P: n^2 \text{ is odd}$ and $Q: n \text{ is odd}$. The contrapositive is $\neg Q \to \neg P$: “If $n$ is even, then $n^2$ is even.”

1. Assume $n$ is an even integer.
2. By definition of an even integer, $n = 2k$ for some integer $k$.
3. Squaring both sides:
   $$n^2 = (2k)^2 = 4k^2 = 2(2k^2)$$
4. Since $2k^2$ is an integer (let $m = 2k^2$), we have $n^2 = 2m$, which is the definition of an even integer.

Since the contrapositive $\neg Q \to \neg P$ is true, the original statement $P \to Q$ is logically equivalent and true. $\blacksquare$

3-Character Lowercase Words Starting with ‘a’ or Ending with ‘c’

The English alphabet has 26 lowercase characters. Total 3-letter words = $26^3$.

1. Words starting with ‘a’: Form a _ _
   $$|A| = 1 \times 26 \times 26 = 26^2 = 676$$
2. Words ending with ‘c’: Form _ _ c
   $$|B| = 26 \times 26 \times 1 = 26^2 = 676$$
3. Words both starting with ‘a’ and ending with ‘c’: Form a _ c
   $$|A \cap B| = 1 \times 26 \times 1 = 26$$

Using the Principle of Inclusion-Exclusion:

$$|A \cup B| = |A| + |B| - |A \cap B| = 676 + 676 - 26 = \mathbf{1,326 \text{ words}}$$

Pascal’s Triangle & Expansion of $(2 - x)^6$

Pascal’s triangle row for $n = 6$:

$$\mathbf{1, \quad 6, \quad 15, \quad 20, \quad 15, \quad 6, \quad 1}$$

Using binomial expansion $(a + b)^6$ where $a = 2, b = -x$:

$$(2 - x)^6 = 1(2)^6 + 6(2)^5(-x) + 15(2)^4(-x)^2 + 20(2)^3(-x)^3 + 15(2)^2(-x)^4 + 6(2)(-x)^5 + 1(-x)^6$$

$$= 64 - 6(32)x + 15(16)x^2 - 20(8)x^3 + 15(4)x^4 - 12x^5 + x^6$$

$$\mathbf{= 64 - 192x + 240x^2 - 160x^3 + 60x^4 - 12x^5 + x^6}$$

Definition of Expression Tree with Example

An expression tree is a binary tree representation of an algebraic, arithmetic, or logical expression where:

• Leaf nodes correspond to operands (constants or variables, e.g., $a, b, 5$).
• Internal nodes correspond to operators (e.g., $+ , -, \times, /$).

         +
        / \
       *   c
      / \
     a   b

In-order traversal yields the infix expression $(a \times b) + c$.

Truth Table Proof of Tautology: $(p \land q) \to (p \land q)$$\begin{array}{|c|c|c|c|}

\hline p & q & p \land q & (p \land q) \to (p \land q) \ \hline T & T & T & \mathbf{T} \ T & F & F & \mathbf{T} \ F & T & F & \mathbf{T} \ F & F & F & \mathbf{T} \ \hline \end{array}$$

Since the final truth column evaluates to True ($T$) under every truth assignment, $(p \land q) \to (p \land q)$ is a tautology.

Handshaking Theorem Statement & Verification

Theorem: In any undirected graph $G = (V, E)$:

$$\sum_{v \in V} \deg(v) = 2 |E|$$

• Proof/Explanation: Every edge $e = (u, v)$ has two endpoints. When calculating the sum of degrees across all vertices, each edge is counted twice—once at vertex $u$ and once at vertex $v$. Therefore, the sum of all degrees is exactly twice the total number of edges.
• Corollary: The sum of degrees in any graph is always an even integer, which implies that every undirected graph must have an even number of vertices of odd degree.

Analysis of $f(x) = x^2$ Over the Set of Integers ($\mathbb{Z} \to \mathbb{Z}$)

1. One-to-One (Injective):
   • A function is injective if $f(a) = f(b) \implies a = b$.
   • Counterexample: For $a = 2$ and $b = -2$:
     $$f(2) = 2^2 = 4 \quad \text{and} \quad f(-2) = (-2)^2 = 4$$
     Since $f(2) = f(-2)$ but $2 \neq -2$, $f(x)$ is not one-to-one.
2. Onto (Surjective):
   • A function is surjective if for every $y \in \mathbb{Z}$, there exists $x \in \mathbb{Z}$ such that $f(x) = y$.
   • Counterexample: Consider $y = -3 \in \mathbb{Z}$. There is no real integer $x$ such that $x^2 = -3$.
   • Therefore, $f(x)$ is not onto.