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

Logical Equivalence

Two compound propositions $P$ and $Q$ are said to be logically equivalent if they have the same truth value for every possible assignment of truth values to their component propositions. Equivalently, $P$ and $Q$ are logically equivalent if and only if the biconditional $P \leftrightarrow Q$ is a tautology. We write $P \equiv Q$.

Proof using Laws of Logic

We show $\neg(p \lor (\neg p \land q)) \equiv \neg p \land \neg q$.

Hence $\neg(p \lor (\neg p \land q)) \equiv \neg p \land \neg q$. Q.E.D.

Function

A function $f$ from a set $A$ (the domain) to a set $B$ (the codomain), written $f : A \to B$, is a rule that assigns to each element $x \in A$ exactly one element $f(x) \in B$.

Types of Functions

One-to-one (Injective)

A function $f : A \to B$ is one-to-one if distinct elements of $A$ map to distinct elements of $B$:

Example: $f : \mathbb{R} \to \mathbb{R},\; f(x) = 2x+1$ is injective, since $2a_1+1 = 2a_2+1 \Rightarrow a_1 = a_2$.

Onto (Surjective)

A function $f : A \to B$ is onto if every element of $B$ is the image of at least one element of $A$: for all $y \in B$ there exists $x \in A$ with $f(x) = y$. Example: $f : \mathbb{R} \to \mathbb{R},\; f(x) = x^3$ is surjective (every real has a real cube root).

Bijective

A function is bijective if it is both one-to-one and onto. Then each element of $B$ corresponds to exactly one element of $A$. Example: $f : \mathbb{R} \to \mathbb{R},\; f(x) = 2x+3$ is bijective.

Existence of the Inverse

The inverse function $f^{-1} : B \to A$ exists if and only if $f$ is bijective (one-to-one and onto). It is defined by $f^{-1}(y) = x \iff f(x) = y$.

Inverse of $f(x) = 2x + 3$

Let $y = 2x + 3$. Solving for $x$:

Interchanging variables, the inverse is

Check: $f(f^{-1}(x)) = 2\!\left(\dfrac{x-3}{2}\right) + 3 = x.$

Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest (least-weight) path from a single source vertex to all other vertices in a weighted graph with non-negative edge weights. It maintains a set $S$ of vertices whose shortest distance from the source is finalized, and greedily adds the closest unprocessed vertex at each step.

Algorithm

Dijkstra(G, w, source):
    for each vertex v in G:
        dist[v] = infinity
        prev[v] = NULL
    dist[source] = 0
    Q = set of all vertices          // priority queue keyed by dist
    while Q is not empty:
        u = vertex in Q with minimum dist[u]
        remove u from Q
        for each neighbor v of u still in Q:
            alt = dist[u] + w(u, v)
            if alt < dist[v]:         // relaxation
                dist[v] = alt
                prev[v] = u
    return dist, prev

Time complexity: $O(V^2)$ with an array, or $O((V+E)\log V)$ with a binary heap.

Worked Example

Consider the weighted graph with source $A$ and edges: $A\!-\!B = 4,\; A\!-\!C = 1,\; C\!-\!B = 2,\; C\!-\!D = 5,\; B\!-\!D = 1,\; D\!-\!E = 3,\; B\!-\!E = 7.$

Final shortest distances from $A$

Following prev pointers, the shortest paths are: $A\to C$, $A\to C\to B$, $A\to C\to B\to D$, $A\to C\to B\to D\to E$.

Quantifiers turn a predicate (open statement) into a proposition by specifying the extent over which the predicate variable ranges.

• Universal quantifier $\forall$ ("for all"): $\forall x\, P(x)$ is true when $P(x)$ holds for every $x$ in the domain. Example: $\forall x \in \mathbb{R},\; x^2 \ge 0$ — "every real number has a non-negative square" (true).

• Existential quantifier $\exists$ ("there exists"): $\exists x\, P(x)$ is true when $P(x)$ holds for at least one $x$ in the domain. Example: $\exists x \in \mathbb{Z},\; x + 3 = 0$ — "there is an integer satisfying $x+3=0$" (true, $x=-3$).

Negation interchanges them: $\neg(\forall x\,P(x)) \equiv \exists x\,\neg P(x)$ and $\neg(\exists x\,P(x)) \equiv \forall x\,\neg P(x)$.

A recursive function is a function that is defined in terms of itself, i.e., its value for an input is expressed using its values at smaller inputs. A correct recursive definition has two parts:

1. Base case(s): the value for the smallest input(s), given directly.
2. Recursive (inductive) step: defines $f(n)$ in terms of $f$ at smaller arguments.

Example — Factorial:

int factorial(int n) {
    if (n == 0) return 1;        // base case
    return n * factorial(n - 1); // recursive call
}

Thus $4! = 4 \cdot 3 \cdot 2 \cdot 1 \cdot 1 = 24$. (Other examples: Fibonacci numbers, $\gcd$ via Euclid's algorithm.)

Cardinality

The cardinality of a set $A$, written $|A|$, is the number of elements it contains. For finite sets it is a non-negative integer; e.g. $|\{a,b,c\}| = 3$. Two sets $A$ and $B$ have the same cardinality if there exists a bijection $f : A \to B$.

Countable Sets

A set is countable if it is finite, or if it has the same cardinality as the set of natural numbers $\mathbb{N}$ (i.e. its elements can be listed in a sequence $a_1, a_2, a_3, \dots$). Such infinite sets are countably infinite, with cardinality $\aleph_0$. Examples: $\mathbb{N}$, the integers $\mathbb{Z}$, and the rationals $\mathbb{Q}$ are all countable.

Uncountable Sets

A set is uncountable if it is infinite but not countable — no bijection with $\mathbb{N}$ exists, so its elements cannot be enumerated in a list. Example: The set of real numbers $\mathbb{R}$ (and the interval $(0,1)$) is uncountable, as shown by Cantor's diagonal argument.

Sum (Addition) Rule

If a task can be done in one of two disjoint ways, where the first way can be performed in $m$ ways and the second in $n$ ways, and no way is common to both, then the task can be done in $m + n$ ways. (For mutually disjoint sets $A,B$: $|A \cup B| = |A| + |B|$.) Example: A student can pick one book — either from $5$ maths books or from $3$ physics books — in $5 + 3 = 8$ ways.

Product (Multiplication) Rule

If a task consists of a sequence of two independent subtasks, where the first can be done in $m$ ways and, for each, the second in $n$ ways, then the whole task can be done in $m \times n$ ways. (For a Cartesian product: $|A \times B| = |A|\cdot|B|$.) Example: Choosing one maths book and then one physics book can be done in $5 \times 3 = 15$ ways.

Key distinction: use the sum rule for an OR of mutually exclusive choices, and the product rule for an AND of successive independent choices.

Isomorphic Graphs

Two simple graphs $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$ are isomorphic if there exists a bijection $f : V_1 \to V_2$ that preserves adjacency:

Intuitively, the two graphs are structurally identical and differ only in the labelling/drawing of vertices.

Necessary conditions (invariants) — isomorphic graphs must have: the same number of vertices, the same number of edges, the same degree sequence, and the same number of components/cycles.

Example

Let $G_1$ have vertices $\{a,b,c,d\}$ with edges $a\!-\!b,\; b\!-\!c,\; c\!-\!d,\; d\!-\!a$ (a 4-cycle), and $G_2$ have vertices $\{1,2,3,4\}$ with edges $1\!-\!2,\; 2\!-\!3,\; 3\!-\!4,\; 4\!-\!1$ (also a 4-cycle).

Define $f(a)=1,\; f(b)=2,\; f(c)=3,\; f(d)=4$. Every edge of $G_1$ maps to an edge of $G_2$ and vice versa, so $f$ is an isomorphism and $G_1 \cong G_2$. Both have 4 vertices, 4 edges, and degree sequence $(2,2,2,2)$.

Binary Search Tree (BST)

A binary search tree is a binary tree in which each node stores a key, and for every node:

• all keys in its left subtree are less than the node's key, and
• all keys in its right subtree are greater than the node's key.

This ordering property holds recursively for every subtree, so an in-order traversal of a BST visits the keys in sorted (ascending) order. It supports search, insertion, and deletion in $O(h)$ time, where $h$ is the height ($O(\log n)$ when balanced).

Example

Inserting the keys $50, 30, 70, 20, 40, 60, 80$ in order gives:

          50
         /  \
       30    70
      /  \   /  \
    20   40 60   80

Here every left child is smaller and every right child is larger than its parent. Searching for $40$: compare with $50$ (go left), then $30$ (go right), then find $40$ — only 3 comparisons. In-order traversal yields $20, 30, 40, 50, 60, 70, 80$ (sorted).

Handshaking Theorem

Statement. In any undirected graph $G = (V, E)$, the sum of the degrees of all vertices equals twice the number of edges:

Consequently, the sum of degrees is always even.

Proof

Consider the total $\displaystyle \sum_{v \in V} \deg(v)$. The degree $\deg(v)$ counts the number of edge-endpoints incident on vertex $v$. Each edge $e = \{u, w\}$ has exactly two endpoints — one at $u$ and one at $w$ — and therefore contributes exactly $2$ to the total degree sum (it adds $1$ to $\deg(u)$ and $1$ to $\deg(w)$).

Summing this contribution over all $|E|$ edges,

Since $|E|$ is a non-negative integer, $2|E|$ is even. Hence the sum of the degrees of all vertices in a graph is even. Q.E.D.

Corollary: the number of vertices of odd degree must be even.

Modular Arithmetic

Modular arithmetic is arithmetic of integers with respect to a fixed positive integer $m$ called the modulus. For $a \bmod m$ we take the remainder $r$ when $a$ is divided by $m$, where the remainder is chosen so that $0 \le r < m$ (i.e. $a = qm + r$ with integer $q$). Two integers $a$ and $b$ are congruent modulo $m$, written $a \equiv b \pmod{m}$, if $m \mid (a - b)$.

Computations

1. $17 \bmod 5$:

2. $-7 \bmod 3$: We need $r$ with $0 \le r < 3$ and $-7 = 3q + r$. Taking $q = -3$:

Answers: $17 \bmod 5 = 2$ and $-7 \bmod 3 = 2$.

Rules of inference are valid argument forms used to derive conclusions from premises in propositional logic.

Modus Ponens (Law of Detachment)

If a conditional and its hypothesis are both true, the conclusion is true.

The form $\big((p \rightarrow q) \land p\big) \rightarrow q$ is a tautology. Example: "If it rains, the ground is wet. It is raining. $\therefore$ The ground is wet."

Modus Tollens

If a conditional is true and its conclusion is false, then its hypothesis is false.

The form $\big((p \rightarrow q) \land \neg q\big) \rightarrow \neg p$ is a tautology. Example: "If it rains, the ground is wet. The ground is not wet. $\therefore$ It is not raining."