BSc CSIT (TU) Science Discrete Structure (BSc CSIT, CSC160) Question Paper 2075 Nepal

Rules of Inference

Rules of inference are valid argument forms (templates) used to derive new true statements (conclusions) from a set of given true statements (premises). They form the basis of formal proofs in propositional logic. Common rules include:

Proof that $p \rightarrow q$, $q \rightarrow r$, $p$ lead to $r$

Hence the conclusion $r$ is derived. Alternatively, applying Hypothetical Syllogism to (1) and (2) gives $p \rightarrow r$, and then Modus Ponens with premise $p$ again yields $r$. $\blacksquare$

Recurrence Relation

A recurrence relation for a sequence $\{a_n\}$ is an equation that expresses each term $a_n$ in terms of one or more of the preceding terms $a_{n-1}, a_{n-2}, \dots$, for all $n$ greater than some fixed value, together with initial conditions.

Solving $a_n = 5a_{n-1} - 6a_{n-2}$, $a_0 = 1$, $a_1 = 0$

Step 1 — Characteristic equation. Assume a solution $a_n = x^n$:

Step 2 — Find roots.

Step 3 — General solution (distinct roots):

Step 4 — Apply initial conditions.

• $a_0 = 1:\quad A + B = 1$
• $a_1 = 0:\quad 2A + 3B = 0$

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

Step 5 — Final solution.

Check: $a_0 = 3 - 2 = 1$ ✓, $a_1 = 6 - 6 = 0$ ✓.

Tree

A tree is a connected, undirected graph with no simple circuits (cycles). Equivalently, a tree on $n$ vertices is a connected graph with exactly $n-1$ edges, in which there is a unique simple path between every pair of vertices.

Spanning Tree

A spanning tree of a connected graph $G$ is a subgraph that is a tree and contains all the vertices of $G$. A minimum spanning tree (MST) of a weighted graph is a spanning tree whose sum of edge weights is the minimum possible.

Kruskal's Algorithm

Kruskal's algorithm builds an MST by repeatedly adding the smallest available edge that does not form a cycle.

Kruskal(G):
  Sort all edges in non-decreasing order of weight
  T = empty set (the MST)
  for each edge (u, v) in sorted order:
      if adding (u, v) to T does NOT form a cycle:
          add (u, v) to T          // use Union-Find to test
  until T has (n - 1) edges
  return T

Example

Consider a graph with vertices $\{A, B, C, D\}$ and weighted edges:

Sorted edges: AB(1), BC(2), AC(3), CD(4), BD(5).

1. Add A–B (1) → no cycle. ✓
2. Add B–C (2) → no cycle. ✓
3. Consider A–C (3) → forms cycle A–B–C–A. ✗ Skip.
4. Add C–D (4) → no cycle. ✓ Now we have $n-1 = 3$ edges. Stop.

MST edges: {A–B, B–C, C–D} with total weight $1 + 2 + 4 = 7$.

We show $p \rightarrow q \equiv \neg p \lor q$ using a truth table. Two propositions are logically equivalent if they have identical truth values for every assignment.

The columns for $p \rightarrow q$ and $\neg p \lor q$ are identical in every row. Therefore:

Power Set

The power set of a set $S$, denoted $P(S)$ or $2^S$, is the set of all subsets of $S$, including the empty set $\emptyset$ and $S$ itself. If $|S| = n$, then $|P(S)| = 2^n$.

Power set of $\{a, b, c\}$

Since $n = 3$, there are $2^3 = 8$ subsets:

Partial Order Relation

A relation $R$ on a set $A$ is a partial order (and $(A, R)$ is a poset) if it is:

1. Reflexive: $a\,R\,a$ for all $a \in A$.
2. Antisymmetric: if $a\,R\,b$ and $b\,R\,a$, then $a = b$.
3. Transitive: if $a\,R\,b$ and $b\,R\,c$, then $a\,R\,c$.

Example

The "less than or equal to" relation $\le$ on the set of integers $\mathbb{Z}$ is a partial order, because:

• $a \le a$ (reflexive),
• if $a \le b$ and $b \le a$ then $a = b$ (antisymmetric),
• if $a \le b$ and $b \le c$ then $a \le c$ (transitive).

Another common example is the divisibility relation $a \mid b$ on the positive integers, or the subset relation $\subseteq$ on the power set of a set.

Pigeonhole Principle

Statement: If $n$ objects (pigeons) are placed into $k$ boxes (pigeonholes) and $n > k$, then at least one box contains two or more objects.

Generalized form: If $n$ objects are placed into $k$ boxes, then at least one box contains at least $\left\lceil \dfrac{n}{k} \right\rceil$ objects.

Example

Among any 13 people, at least two must have been born in the same month. Here the 13 people are the objects and the 12 months are the boxes; since $13 > 12$, by the pigeonhole principle at least two people share a birth month.

Complete Graph

A complete graph $K_n$ is a simple undirected graph on $n$ vertices in which every pair of distinct vertices is joined by exactly one edge. It has $\dfrac{n(n-1)}{2}$ edges, and every vertex has degree $n-1$. For example, $K_4$ has 4 vertices and 6 edges.

Bipartite Graph

A graph $G = (V, E)$ is bipartite if its vertex set $V$ can be partitioned into two disjoint sets $V_1$ and $V_2$ such that every edge connects a vertex in $V_1$ to a vertex in $V_2$ (no edge lies within $V_1$ or within $V_2$). A graph is bipartite if and only if it contains no odd-length cycle. The complete bipartite graph $K_{m,n}$ joins every vertex of $V_1$ (size $m$) to every vertex of $V_2$ (size $n$).

The number of edges in a complete graph $K_n$ is

For $n = 6$:

Therefore, $K_6$ has 15 edges (and each of the 6 vertices has degree 5).

Tree

A tree is a connected, undirected graph that contains no simple circuits (cycles). Equivalently, it is a connected graph in which any two vertices are joined by a unique simple path.

Basic Properties

For a tree with $n$ vertices:

1. It has exactly $n - 1$ edges.
2. It is connected, but removing any single edge disconnects it (every edge is a bridge).
3. It is acyclic; adding any new edge between two existing vertices creates exactly one cycle.
4. There is a unique simple path between every pair of vertices.
5. A tree with $n \ge 2$ vertices has at least two leaves (vertices of degree 1).
6. A connected graph is a tree if and only if it has $n-1$ edges and is acyclic (any two of: connected, acyclic, $n-1$ edges imply the third).

Tautology

A tautology is a compound proposition that is always true, regardless of the truth values of its component propositions.

Example: $p \lor \neg p$ (the law of excluded middle).

The result is always T.

Contradiction

A contradiction is a compound proposition that is always false, regardless of the truth values of its components.

Example: $p \land \neg p$.

The result is always F.

(A proposition that is neither always true nor always false is called a contingency.)

Composition of Functions

If $f : A \rightarrow B$ and $g : B \rightarrow C$ are functions, their composition $g \circ f : A \rightarrow C$ is defined by

That is, $f$ is applied first, then $g$ is applied to the result. (Note $g \circ f$ is generally not the same as $f \circ g$.)

Example

Let $f(x) = x + 2$ and $g(x) = x^2$, both functions on $\mathbb{R}$.

• $(g \circ f)(x) = g(f(x)) = g(x+2) = (x+2)^2 = x^2 + 4x + 4.$
• $(f \circ g)(x) = f(g(x)) = f(x^2) = x^2 + 2.$

For instance, $(g \circ f)(3) = (3+2)^2 = 25$, whereas $(f \circ g)(3) = 3^2 + 2 = 11$, showing the two compositions differ.