Discrete Structure 2023 Board Question Paper

Step-by-Step Solutions: Brief Answer Questions

a. Negation of “Some persons are loyal”:

Let $P(x)$ be “$x$ is a person” and $L(x)$ be “$x$ is loyal”. Statement: $\exists x (P(x) \land L(x))$.

$$\mathbf{\neg \exists x (P(x) \land L(x)) \equiv \forall x (P(x) \to \neg L(x)) \quad \text{("No person is loyal" or "All persons are disloyal")}}$$

b. Definition of Cryptology:

Cryptology is the overarching mathematical and computer science discipline that encompasses both cryptography (the study and design of secret codes and secure communication protocols) and cryptanalysis (the science of deciphering and breaking cryptographic codes without authorized keys).

c. Boolean Matrix Representation of a Relation:

For relation $R \subseteq A \times B$ with $|A|=m, |B|=n$, the $m \times n$ matrix $M_R = [m_{ij}]$ has $m_{ij} = 1$ if $(a_i, b_j) \in R$, else $0$.

d. Value of $\lceil 2.1 \rceil$:

$$\lceil 2.1 \rceil = \mathbf{3}$$

e. Order and Size of Complete Graph $K_{15}$:

• Order (number of vertices $n$): $\mathbf{15}$
• Size (number of edges $|E|$): $\frac{n(n-1)}{2} = \frac{15 \times 14}{2} = \mathbf{105 \text{ edges}}$

f. Definition of Connected Graph:

An undirected graph is connected if there exists a path between every pair of distinct vertices in the graph.

g. Unilaterally Connected Directed Graph:

A directed graph is unilaterally connected if for every pair of distinct vertices $u$ and $v$, there exists at least one directed path from $u$ to $v$ OR from $v$ to $u$.

h. Pigeonhole Principle:

If $n$ items are put into $m$ containers and $n > m$, then at least one container must contain more than one item ($\lceil n/m \rceil$).

i. Steps in Mathematical Induction:

1. Basis Step: Verify the proposition $P(n_0)$ is true for the base integer.
2. Inductive Hypothesis: Assume $P(k)$ is true for an arbitrary integer $k \ge n_0$.
3. Inductive Step: Prove that $P(k) \implies P(k + 1)$ is true.

j. Pendant Vertices in Full Binary Tree with 15 Vertices:

For a full binary tree with $n$ vertices, internal vertices $i = \frac{n - 1}{2} = \frac{15 - 1}{2} = 7$. Pendant vertices (leaves) $L = i + 1 = 7 + 1 = \mathbf{8 \text{ pendant vertices}}$.

Translation into Logical Expressions

a. “All living things who can fly are birds.”

Let $L(x)$: $x$ is a living thing, $F(x)$: $x$ can fly, $B(x)$: $x$ is a bird:

$$\mathbf{\forall x ((L(x) \land F(x)) \to B(x))}$$

b. “Fish can swim.”

Let $F(x)$: $x$ is a fish, $S(x)$: $x$ can swim:

$$\mathbf{\forall x (F(x) \to S(x))}$$

c. “All file systems can be backed up.”

Let $FS(x)$: $x$ is a file system, $B(x)$: $x$ can be backed up:

$$\mathbf{\forall x (FS(x) \to B(x))}$$

d. “Some children don’t like math.”

Let $C(x)$: $x$ is a child, $M(x)$: $x$ likes math:

$$\mathbf{\exists x (C(x) \land \neg M(x))}$$

Big-O, Big-Omega & Insertion Sort Trace for [12, 5, 7, 18, 10]

• Big-O ($O$): Provides an asymptotic upper bound on runtime (worst-case performance).
• Big-Omega ($\Omega$): Provides an asymptotic lower bound on runtime (best-case performance).

Insertion Sort Trace:

• Initial: [12, 5, 7, 18, 10]
• Pass 1 (insert 5): Compare with 12 $\to$ shift 12: [5, 12, 7, 18, 10]
• Pass 2 (insert 7): Compare with 12 $\to$ shift 12; compare with 5 $\to$ insert: [5, 7, 12, 18, 10]
• Pass 3 (insert 18): Compare with 12 $\to$ already in place: [5, 7, 12, 18, 10]
• Pass 4 (insert 10): Shift 18 and 12; insert after 7: [5, 7, 10, 12, 18]

Final Sorted Output: [5, 7, 10, 12, 18]

Divisibility Definition & Proof: If $a \mid b$ and $a \mid c$, then $a \mid (b + c)$

• Divisibility: Integer $a$ divides integer $b$ ($a \mid b$) if there exists an integer $k$ such that $b = a \cdot k$.

Proof:

1. Since $a \mid b$, by definition $b = a \cdot k_1$ for some integer $k_1$.
2. Since $a \mid c$, by definition $c = a \cdot k_2$ for some integer $k_2$.
3. Adding the two expressions:
   $$b + c = a \cdot k_1 + a \cdot k_2 = a(k_1 + k_2)$$
4. Since $k_1$ and $k_2$ are integers, their sum $(k_1 + k_2) = m$ is an integer.
5. Thus, $b + c = a \cdot m$, which proves by definition that $\mathbf{a \mid (b + c)}$. $\blacksquare$

Source/Sink Vertices & Word Permutations of “ANIMAL”

• Source Vertex: In a directed graph, a vertex with in-degree equal to 0 ($\text{indeg}(v) = 0$) and positive out-degree.
• Sink Vertex: A vertex with out-degree equal to 0 ($\text{outdeg}(v) = 0$) and positive in-degree.

Permutations of “ANIMAL”:

The word has 6 letters: A, N, I, M, A, L (Letter ‘A’ occurs 2 times).

$$\text{Total Words} = \frac{6!}{2!} = \frac{720}{2} = \mathbf{360 \text{ words}}$$

Domain vs. Range & Invertibility of $f(x) = x^2$

• Domain: The set of all permissible input values for which the function is defined.
• Range: The actual set of all resulting output values produced by the function ($f(\text{Domain})$).

Evaluation of $f(x) = x^2$ over $\mathbb{R}$:

• Not One-to-One: $f(-3) = f(3) = 9$ but $-3 \neq 3$.
• Not Onto: Negative real numbers (e.g., $-5$) have no pre-image in $\mathbb{R}$.
• Not Bijection (Correspondence): Since it is neither one-to-one nor onto, it is not a one-to-one correspondence.

Adjacency & Incidence Matrices for Digraphs

In the adjacency matrix $A = [a_{ij}]$ of a directed graph:

• Out-degree of vertex $v_i$: Equal to the sum of entries in row $i$:
  $$\text{outdeg}(v_i) = \sum_{j=1}^n a_{ij}$$
• In-degree of vertex $v_j$: Equal to the sum of entries in column $j$:
  $$\text{indeg}(v_j) = \sum_{i=1}^n a_{ij}$$

Spanning Trees of Wheel Graph $W_3$ Using Kirchhoff’s Theorem

• Spanning Tree: A subgraph of $G$ that is a tree and includes every vertex of $G$.
• Wheel Graph $W_3$: Consists of a 3-cycle ($C_3$) connected to a central hub vertex; isomorphic to the complete graph $K_4$.
• Number of Spanning Trees: By Cayley’s formula for $K_n$, the number of spanning trees is $n^{n-2}$.
  $$\text{For } K_4: \quad 4^{4-2} = 4^2 = \mathbf{16 \text{ spanning trees}}$$

Graph Isomorphism Determination

To verify if a given pair of graphs $G_1$ and $G_2$ are isomorphic:

1. Check that both have equal numbers of vertices and edges.
2. Verify degree sequences match.
3. Establish a bijective mapping $f: V_1 \to V_2$ such that $(u, v) \in E_1 \iff (f(u), f(v)) \in E_2$. If all vertex adjacency preservation tests hold, the graphs are isomorphic.

Proof: A Tree with $n$ Vertices Has $n - 1$ Edges

Proof by Mathematical Induction:

1. Base Case ($n = 1$): A tree with 1 vertex has 0 edges ($1 - 1 = 0$). True.
2. Inductive Hypothesis: Assume any tree with $k$ vertices has $k - 1$ edges.
3. Inductive Step: Consider a tree $T$ with $k + 1$ vertices.
   • Every tree with $k + 1 \ge 2$ vertices contains at least one leaf vertex $v$ with $\deg(v) = 1$.
   • Removing leaf $v$ and its incident edge leaves a smaller subgraph $T'$.
   • $T'$ is connected and acyclic, meaning it is a tree with $k$ vertices.
   • By our hypothesis, $T'$ has $k - 1$ edges.
   • Adding back vertex $v$ and its 1 incident edge gives:
     $$|E(T)| = (k - 1) + 1 = k = (k + 1) - 1$$

Therefore, any tree with $n$ vertices has exactly $n - 1$ edges. $\blacksquare$

Truth Table Proof: Equivalence of Inverse and Converse

For implication $p \to q$:

• Converse: $q \to p$
• Inverse: $\neg p \to \neg q$$\begin{array}{|c|c|c|c|c|c|c|} \hline p & q & \neg p & \neg q & q \to p \text{ (Converse)} & \neg p \to \neg q \text{ (Inverse)} \ \hline T & T & F & F & \mathbf{T} & \mathbf{T} \ T & F & F & T & \mathbf{T} & \mathbf{T} \ F & T & T & F & \mathbf{F} & \mathbf{F} \ F & F & T & T & \mathbf{T} & \mathbf{T} \ \hline \end{array}$$

The truth values in columns 5 and 6 are identical for all cases, proving that the converse and inverse are logically equivalent ($(q \to p) \equiv (\neg p \to \neg q)$).

Proof: Equivalence Relation for $R = \{(a, b): |a - b| \text{ is even}\}$

1. Reflexivity: $|a - a| = 0 = 2(0)$, which is even. $(a, a) \in R$.
2. Symmetry: If $|a - b|$ is even, $|b - a| = |-(a - b)| = |a - b|$ is also even. $(b, a) \in R$.
3. Transitivity: If $|a - b| = 2k_1$ and $|b - c| = 2k_2$, then $(a - c) = (a - b) + (b - c) = 2(k_1 + k_2)$, so $|a - c|$ is even. $(a, c) \in R$. Hence, $R$ is an equivalence relation.

Algebraic Proof of Pascal’s Identity: $\binom{n+1}{r} = \binom{n}{r-1} + \binom{n}{r}$$\binom{n}{r-1} + \binom{n}{r} = \frac{n!}{(r-1)!(n - r + 1)!} + \frac{n!}{r!(n - r)!}$$

Factoring out common terms $\frac{n!}{(r-1)!(n-r)!}$:

$$= \frac{n!}{(r-1)!(n-r)!} \left[ \frac{1}{n - r + 1} + \frac{1}{r} \right] = \frac{n!}{(r-1)!(n-r)!} \left[ \frac{r + (n - r + 1)}{r(n - r + 1)} \right]$$

$$= \frac{n!}{(r-1)!(n-r)!} \left[ \frac{n + 1}{r(n - r + 1)} \right] = \frac{(n + 1) n!}{(r \cdot (r - 1)!) \cdot ((n - r + 1) \cdot (n - r)!)}$$

$$= \frac{(n + 1)!}{r! (n + 1 - r)!} = \mathbf{\binom{n+1}{r}} \quad \blacksquare$$

First Five Terms of Recurrence Relation: $a_n = 2a_{n-1} + 3a_{n-2}$ with $a_0 = 3, a_1 = -2$

• $a_0 = \mathbf{3}$
• $a_1 = \mathbf{-2}$
• $a_2 = 2(-2) + 3(3) = -4 + 9 = \mathbf{5}$
• $a_3 = 2(5) + 3(-2) = 10 - 6 = \mathbf{4}$
• $a_4 = 2(4) + 3(5) = 8 + 15 = \mathbf{23}$

The first five terms of the sequence are: 3, -2, 5, 4, 23.

Expression Tree Construction & Traversal

• Tree Traversal: The algorithmic process of visiting every node in a tree data structure exactly once in a systematic order (Pre-order, In-order, Post-order).
• Expression: $a \times b + (c / d \times e - f) \text{ \textasciicircum } g$
• The root of the tree is +, with left subtree evaluating a * b and right subtree evaluating the exponentiation operation.
• In-order traversal reconstructs the fully parenthesized infix expression.

Handshaking Theorem Statement & Verification

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

Each edge connects two vertices and adds 1 to the degree of each incident vertex, contributing a total of 2 to the sum of degrees. This guarantees that the sum of degrees in any graph is always even.

Necessary and Sufficient Condition for an Eulerian Circuit

Euler’s Theorem: A connected undirected graph $G = (V, E)$ contains an Eulerian Circuit (a closed walk that traverses every edge exactly once) if and only if:

1. The graph is connected (except for isolated vertices of degree 0).
2. Every vertex in the graph has an even degree ($\deg(v) \equiv 0 \pmod 2 \quad \forall v \in V$).