BE Computer Engineering (IOE, TU) Discrete Structure (IOE, CT 551) Question Paper 2078 Nepal

(a) Relations and Equivalence Relation

A relation $R$ on a set $A$ is any subset of the Cartesian product $A \times A$; i.e. $R \subseteq A \times A$. We write $aRb$ (or $(a,b)\in R$) to mean $a$ is related to $b$.

Properties: For all $a,b,c \in A$,

• (i) Reflexive: $(a,a) \in R$ for every $a \in A$.
• (ii) Symmetric: if $(a,b) \in R$ then $(b,a) \in R$.
• (iii) Anti-symmetric: if $(a,b) \in R$ and $(b,a) \in R$ then $a = b$.
• (iv) Transitive: if $(a,b) \in R$ and $(b,c) \in R$ then $(a,c) \in R$.

Checking $R = \{(1,1),(1,2),(2,1),(2,2),(3,3),(4,4)\}$ on $A=\{1,2,3,4\}$:

• Reflexive: $(1,1),(2,2),(3,3),(4,4)$ are all present. ✔
• Symmetric: The only off-diagonal pairs are $(1,2)$ and $(2,1)$, which occur together. ✔
• Transitive: $(1,2)\&(2,1)\Rightarrow(1,1)$ ✔; $(2,1)\&(1,2)\Rightarrow(2,2)$ ✔; all other chains stay within reflexive pairs. ✔

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

Partition (equivalence classes):

$$[1] = \{1,2\} = [2], \quad [3] = \{3\}, \quad [4] = \{4\}.$$

The corresponding partition of $A$ is $\{\,\{1,2\},\ \{3\},\ \{4\}\,\}$.

(b) Distributive Law $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$

Proof by membership (mutual inclusion):

Let $x$ be arbitrary.

$$x \in A \cap (B \cup C) \iff x \in A \ \wedge\ x \in (B \cup C) \iff x \in A \ \wedge\ (x \in B \ \vee\ x \in C).$$

Applying the distributive law of logic $p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)$:

$$\iff (x \in A \wedge x \in B) \ \vee\ (x \in A \wedge x \in C) \iff x \in (A \cap B) \ \vee\ x \in (A \cap C) \iff x \in (A \cap B) \cup (A \cap C).$$

Since every step is an equivalence, the two sets contain exactly the same elements, hence

$$A \cap (B \cup C) = (A \cap B) \cup (A \cap C). \qquad \blacksquare$$

Venn diagram verification: Draw three overlapping circles $A$, $B$, $C$. Shade $B \cup C$ (everything inside $B$ or $C$); intersecting with $A$ leaves the parts of $A$ that overlap $B$ or $C$. Separately shade $A\cap B$ and $A\cap C$ and take their union — the same regions are shaded. Both diagrams shade identical regions, confirming the identity.

(a) $(p \rightarrow q) \wedge (p \rightarrow r) \equiv p \rightarrow (q \wedge r)$

Starting from the left-hand side and using the conditional-disjunction equivalence $p \rightarrow x \equiv \neg p \vee x$:

$$\begin{aligned} (p \rightarrow q) \wedge (p \rightarrow r) &\equiv (\neg p \vee q) \wedge (\neg p \vee r) && \text{(Conditional–disjunction / Implication law)}\\ &\equiv \neg p \vee (q \wedge r) && \text{(Distributive law)}\\ &\equiv p \rightarrow (q \wedge r). && \text{(Conditional–disjunction law, reverse)} \end{aligned}$$

Hence the two propositions are logically equivalent. $\blacksquare$

(b) Tautology, Contradiction and Quantified Translation

• A tautology is a compound proposition that is true for every assignment of truth values to its variables (e.g. $p \vee \neg p$).
• A contradiction is a compound proposition that is false for every assignment of truth values (e.g. $p \wedge \neg p$).

Translation of: "Every student in the class has solved at least one problem."

• Universe of discourse: $S$ = set of students in the class; $P$ = set of problems.
• Predicate: $\text{Solved}(x, y)$ = "student $x$ has solved problem $y$."

Logical expression:

$$\forall x \in S \;\big(\exists y \in P\;\; \text{Solved}(x, y)\big).$$

Negation:

$$\neg \forall x\,\exists y\;\text{Solved}(x,y) \equiv \exists x\,\forall y\;\neg\text{Solved}(x,y).$$

In words: "There is at least one student in the class who has not solved any problem (has solved none of the problems)."

(a) Solve $a_n = 5a_{n-1} - 6a_{n-2}$, $a_0=1,\ a_1=0$

Characteristic equation: assume $a_n = r^n$:

$$r^2 - 5r + 6 = 0 \;\Rightarrow\; (r-2)(r-3)=0 \;\Rightarrow\; r = 2,\ 3.$$

Distinct roots, so the general solution is

$$a_n = A\,2^n + B\,3^n.$$

Apply initial conditions:

$$a_0 = A + B = 1, \qquad a_1 = 2A + 3B = 0.$$

From the first, $A = 1 - B$. Substituting: $2(1-B) + 3B = 0 \Rightarrow 2 + B = 0 \Rightarrow B = -2$, hence $A = 3$.

$$\boxed{a_n = 3\cdot 2^n - 2\cdot 3^n.}$$

(Check: $a_0 = 3-2 = 1$ ✔, $a_1 = 6-6 = 0$ ✔.)

(b) Solve $a_n - 3a_{n-1} = 2^n$, $a_0 = 1$

Homogeneous solution: characteristic root of $a_n - 3a_{n-1}=0$ is $r = 3$, so $a_n^{(h)} = C\,3^n$.

Particular solution: since $2$ is not a characteristic root, try $a_n^{(p)} = D\,2^n$. Substituting:

$$D\,2^n - 3D\,2^{n-1} = 2^n \;\Rightarrow\; 2^{n-1}(2D - 3D) = 2^n \;\Rightarrow\; -D\,2^{n-1} = 2^n.$$

Thus $-D = 2$, giving $D = -2$, so $a_n^{(p)} = -2\cdot 2^n = -2^{n+1}$.

General solution:

$$a_n = C\,3^n - 2^{n+1}.$$

Apply $a_0 = 1$: $C - 2 = 1 \Rightarrow C = 3$.

$$\boxed{a_n = 3^{\,n+1} - 2^{\,n+1}.}$$

(Check: $a_0 = 3-2 = 1$ ✔; $a_1 = 9-4 = 5$, and recurrence gives $3a_0 + 2^1 = 3+2 = 5$ ✔.)

(a) Euler and Hamiltonian Circuits

• An Euler circuit is a closed walk that traverses every edge of the graph exactly once and returns to the starting vertex.
• A Hamiltonian circuit is a closed walk that visits every vertex exactly once (except the start/end vertex) and returns to the starting vertex.

Necessary and sufficient condition (Euler's theorem): A connected graph has an Euler circuit if and only if every vertex has even degree.

Justification: In a closed trail, each time the walk enters a vertex through one edge it must leave through another unused edge, so edges at every vertex pair up — every vertex must have even degree. Conversely, if the graph is connected and all degrees are even, such a circuit can always be constructed (e.g. by Fleury's/Hierholzer's algorithm).

Is there an Euler circuit in $K_5$? In $K_5$ every vertex is joined to the other 4 vertices, so each vertex has degree $4$, which is even. $K_5$ is connected and all degrees are even, therefore $K_5$ has an Euler circuit. ✔

(b) Chromatic Number

The chromatic number $\chi(G)$ is the minimum number of colours needed to colour the vertices of $G$ so that no two adjacent vertices share the same colour.

$\chi(K_{3,3})$: $K_{3,3}$ is bipartite with parts $X = \{x_1,x_2,x_3\}$ and $Y = \{y_1,y_2,y_3\}$; edges join $X$ to $Y$ only. Colour all of $X$ with colour 1 and all of $Y$ with colour 2 — no edge joins two same-coloured vertices. Since the graph has edges, 1 colour is impossible, so

$$\chi(K_{3,3}) = 2.$$

In general every bipartite graph with at least one edge is 2-chromatic.

Injective, Surjective, Bijective

For a function $f: A \rightarrow B$:

• Injective (one-to-one): distinct inputs give distinct outputs — $f(x_1) = f(x_2) \Rightarrow x_1 = x_2$.
• Surjective (onto): every $y \in B$ has some $x \in A$ with $f(x) = y$.
• Bijective: both injective and surjective (a one-to-one correspondence), and therefore invertible.

$f(x) = 3x - 5$, $f:\mathbb{R}\to\mathbb{R}$ is a bijection

Injective: Suppose $f(x_1) = f(x_2)$. Then

$$3x_1 - 5 = 3x_2 - 5 \Rightarrow 3x_1 = 3x_2 \Rightarrow x_1 = x_2.$$

Hence $f$ is injective.

Surjective: Take any $y \in \mathbb{R}$. Choose $x = \dfrac{y+5}{3} \in \mathbb{R}$. Then

$$f(x) = 3\!\left(\tfrac{y+5}{3}\right) - 5 = (y+5) - 5 = y.$$

So every $y$ is attained, and $f$ is surjective.

Being both injective and surjective, $f$ is a bijection.

Inverse function: Let $y = 3x - 5 \Rightarrow x = \dfrac{y+5}{3}$. Therefore

$$f^{-1}(x) = \frac{x+5}{3}.$$

Proof by Mathematical Induction

Claim: $P(n):\ 1^2 + 2^2 + \cdots + n^2 = \dfrac{n(n+1)(2n+1)}{6}$ for all integers $n \ge 1$.

Basis step ($n=1$):

$$\text{LHS} = 1^2 = 1, \qquad \text{RHS} = \frac{1\cdot 2 \cdot 3}{6} = 1.$$

So $P(1)$ holds.

Inductive step: Assume $P(k)$ is true for some $k \ge 1$:

$$1^2 + 2^2 + \cdots + k^2 = \frac{k(k+1)(2k+1)}{6}. \quad \text{(inductive hypothesis)}$$

We show $P(k+1)$:

$$\sum_{i=1}^{k+1} i^2 = \frac{k(k+1)(2k+1)}{6} + (k+1)^2 = (k+1)\left[\frac{k(2k+1)}{6} + (k+1)\right].$$

Combine the bracket over 6:

$$= (k+1)\cdot \frac{k(2k+1) + 6(k+1)}{6} = (k+1)\cdot \frac{2k^2 + 7k + 6}{6}.$$

Factor $2k^2 + 7k + 6 = (k+2)(2k+3)$:

$$= \frac{(k+1)(k+2)(2k+3)}{6} = \frac{(k+1)\big((k+1)+1\big)\big(2(k+1)+1\big)}{6}.$$

This is exactly $P(k+1)$.

Conclusion: By the principle of mathematical induction, the formula holds for every positive integer $n$. $\blacksquare$

(a) Pigeonhole Principle

Statement: If $n$ objects are placed into $m$ boxes and $n > m$, then at least one box contains two or more objects. (More generally, some box holds at least $\lceil n/m \rceil$ objects.)

Application: Treat the 12 months as boxes (pigeonholes) and the 13 people as objects (pigeons). Since $13 > 12$, by the pigeonhole principle at least one month must contain at least two people. Hence among any 13 people, at least two are born in the same month. $\blacksquare$

(b) Committee Selection

Choose 3 men from 7 and 2 women from 5 (independent choices, multiply):

$$\binom{7}{3}\binom{5}{2} = \frac{7!}{3!\,4!}\cdot\frac{5!}{2!\,3!} = 35 \times 10 = 350.$$

There are $\boxed{350}$ ways to form the committee.

(a) Coefficient of $x^5 y^3$ in $(2x - y)^8$

By the Binomial Theorem, the general term of $(2x + (-y))^8$ is

$$\binom{8}{k}(2x)^{8-k}(-y)^{k}.$$

For $x^5 y^3$ we need $8-k = 5$ and $k = 3$, so $k = 3$:

$$\binom{8}{3}(2x)^{5}(-y)^{3} = 56 \cdot 2^5 x^5 \cdot (-1)^3 y^3 = 56 \cdot 32 \cdot (-1)\, x^5 y^3 = -1792\, x^5 y^3.$$

The coefficient of $x^5 y^3$ is $\boxed{-1792}$.

(b) Arrangements of "MISSISSIPPI"

The word has 11 letters with repetitions: $M$ = 1, $I$ = 4, $S$ = 4, $P$ = 2. The number of distinct arrangements is

$$\frac{11!}{1!\,4!\,4!\,2!} = \frac{39\,916\,800}{1\cdot 24\cdot 24\cdot 2} = \frac{39\,916\,800}{1152} = 34\,650.$$

There are $\boxed{34{,}650}$ distinct arrangements.

Spanning Tree and Minimum Spanning Tree

• A spanning tree of a connected graph $G$ is a subgraph that is a tree (connected, acyclic) and includes all vertices of $G$. For $n$ vertices it has exactly $n-1$ edges.
• A minimum spanning tree (MST) of a weighted connected graph is a spanning tree whose total edge weight is the smallest among all spanning trees.

Kruskal's Algorithm

Vertices $\{A,B,C,D,E\}$ (so the MST will have $5-1 = 4$ edges). Sort edges by weight:

Process in increasing order, adding an edge only if it does not form a cycle:

1. DE (1) — add. Components: {D,E}, ... ✔
2. BC (2) — add. Components: {B,C}, {D,E} ✔
3. AC (3) — add (joins A to {B,C}). ✔ → {A,B,C}
4. AB (4) — A and B already connected → forms a cycle, reject.
5. CE (4) — add (joins {A,B,C} to {D,E}). ✔ → all 5 vertices connected.

Now 4 edges selected; stop.

MST edges (in order selected): $DE,\ BC,\ AC,\ CE$.

Total weight: $1 + 2 + 3 + 4 = \boxed{10}$.

Basic Postulates of Boolean Algebra

For a Boolean algebra over $\{0,1\}$ with operations $+$ (OR), $\cdot$ (AND) and $'$ (NOT):

• Identity: $x + 0 = x$, $\;x \cdot 1 = x$.
• Complement: $x + x' = 1$, $\;x \cdot x' = 0$.
• Commutative: $x + y = y + x$, $\;x \cdot y = y \cdot x$.
• Distributive: $x(y + z) = xy + xz$, $\;x + yz = (x+y)(x+z)$.
• (Derived) Identity element existence $0$ and $1$, and closure under $+,\cdot,'$.

Simplify $F = x'y'z + x'yz + xy'$

$$\begin{aligned} F &= x'y'z + x'yz + xy'\\ &= x'z(y' + y) + xy' && \text{(factor }x'z\text{)}\\ &= x'z(1) + xy' && (y' + y = 1)\\ &= x'z + xy'. \end{aligned}$$ $$\boxed{F = x'z + xy'.}$$

Logic Circuit (described)

The simplified expression $F = x'z + xy'$ uses two NOT gates, two 2-input AND gates and one 2-input OR gate:

• NOT gate 1: input $x$ → output $x'$.
• NOT gate 2: input $y$ → output $y'$.
• AND gate 1: inputs $x'$ and $z$ → output $x'z$.
• AND gate 2: inputs $x$ and $y'$ → output $xy'$.
• OR gate: inputs $x'z$ and $xy'$ → output $F$.

x ──┬─────────────────┐
    │                 │
    └─[NOT]─x'─┐    [AND]──xy'──┐
z ────────────┴[AND]─x'z─┐     │
                         └──[OR]── F
y ──[NOT]─y'─────────────────────┘

(a) Adjacency Matrix

The adjacency matrix of a simple undirected graph on $n$ vertices is the $n \times n$ matrix $A = [a_{ij}]$ where $a_{ij} = 1$ if there is an edge between $v_i$ and $v_j$, and $a_{ij} = 0$ otherwise. For a simple undirected graph it is symmetric with zero diagonal.

Edges: $\{v_1v_2,\ v_2v_3,\ v_3v_4,\ v_4v_1,\ v_1v_3\}$. Adjacencies:

• $v_1$: $v_2, v_3, v_4$
• $v_2$: $v_1, v_3$
• $v_3$: $v_1, v_2, v_4$
• $v_4$: $v_1, v_3$

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

(rows/columns ordered $v_1,v_2,v_3,v_4$).

(b) Conditions for Graph Isomorphism

Two graphs $G_1 = (V_1,E_1)$ and $G_2 = (V_2,E_2)$ are isomorphic if there exists a bijection $f: V_1 \rightarrow V_2$ that preserves adjacency: $(u,v) \in E_1 \iff (f(u), f(v)) \in E_2$.

Necessary conditions (must all match — used to test isomorphism):

1. Same number of vertices.
2. Same number of edges.
3. Same degree sequence (same number of vertices of each degree).
4. Preservation of structural invariants (e.g. same number of cycles/connected components, corresponding subgraphs).

If an adjacency-preserving bijection exists, the graphs are isomorphic.

Partially Ordered Set (Poset)

A poset is a set $S$ together with a relation $\preceq$ that is reflexive, anti-symmetric and transitive:

• Reflexive: $a \preceq a$;
• Anti-symmetric: $a \preceq b$ and $b \preceq a \Rightarrow a = b$;
• Transitive: $a \preceq b$ and $b \preceq c \Rightarrow a \preceq c$.

It is denoted $(S, \preceq)$.

Hasse Diagram of $(D_{12}, \mid)$

Divisors of 12: $D_{12} = \{1, 2, 3, 4, 6, 12\}$, ordered by "$a \mid b$" ($a$ divides $b$).

Covering relations (draw $b$ above $a$ with an edge when $a \mid b$ and nothing lies strictly between):

• $1$ is covered by $2$ and $3$.
• $2$ is covered by $4$ and $6$.
• $3$ is covered by $6$.
• $4$ is covered by $12$.
• $6$ is covered by $12$.

Hasse diagram (bottom = 1, top = 12):

          12
         /  \
        4    6
        |   / \
        |  /   3
        | /   /
        2    /
         \  /
          1

More precisely, edges are: $1\!-\!2$, $1\!-\!3$, $2\!-\!4$, $2\!-\!6$, $3\!-\!6$, $4\!-\!12$, $6\!-\!12$. The least element is $1$ and the greatest element is $12$.