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

Proposition

A proposition (or statement) is a declarative sentence that is either true or false, but not both. For example, "$2 + 3 = 5$" is a true proposition, while "$7$ is even" is a false proposition. Sentences that are questions, commands, or have no definite truth value are not propositions.

Truth Table for $(p \rightarrow q) \leftrightarrow (\neg q \rightarrow \neg p)$

The implication $p \rightarrow q$ is false only when $p$ is true and $q$ is false. $\neg q \rightarrow \neg p$ is the contrapositive of $p \rightarrow q$.

Conclusion

The last column is true in every row. Therefore the compound proposition $(p \rightarrow q) \leftrightarrow (\neg q \rightarrow \neg p)$ is a tautology. This confirms the logical equivalence $(p \rightarrow q) \equiv (\neg q \rightarrow \neg p)$, i.e. an implication is logically equivalent to its contrapositive.

Mathematical Induction

Mathematical induction is a proof technique used to prove that a statement $P(n)$ holds for all positive integers $n$. It consists of two steps:

1. Basis step: Show that $P(1)$ (or the smallest value) is true.
2. Inductive step: Assume $P(k)$ is true (the inductive hypothesis) and use it to prove that $P(k+1)$ is true.

If both steps hold, then by the principle of mathematical induction $P(n)$ is true for all $n \geq 1$.

Proof that $1 + 2 + 3 + \dots + n = \dfrac{n(n+1)}{2}$

Let $P(n): \; 1 + 2 + \dots + n = \dfrac{n(n+1)}{2}$.

Basis step ($n = 1$):

Since LHS = RHS, $P(1)$ is true.

Inductive step: Assume $P(k)$ holds for some positive integer $k$:

We must show $P(k+1)$ holds, i.e. $1 + 2 + \dots + k + (k+1) = \dfrac{(k+1)(k+2)}{2}$.

Adding $(k+1)$ to both sides of the hypothesis:

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

Conclusion

The basis step and inductive step both hold, so by the principle of mathematical induction,

Definition of a Graph

A graph $G = (V, E)$ consists of a non-empty set of vertices (nodes) $V$ and a set of edges $E$, where each edge connects a pair of vertices. Graphs are used to model pairwise relationships between objects.

Types of Graphs (with examples)

• Null/Empty graph: A graph with vertices but no edges. Example: $V = \{a,b,c\}, E = \emptyset$.
• Simple graph: No self-loops and no parallel (multiple) edges between the same pair of vertices.
• Multigraph: Allows multiple (parallel) edges between the same pair of vertices.
• Directed graph (digraph): Each edge has a direction, represented as an ordered pair $(u,v)$. Example: a one-way road network.
• Undirected graph: Edges have no direction; $\{u,v\}$ is unordered.
• Weighted graph: Each edge is assigned a weight/cost. Example: a road map with distances.
• Complete graph $K_n$: Every pair of distinct vertices is joined by an edge; it has $\dfrac{n(n-1)}{2}$ edges.
• Bipartite graph: Vertices split into two disjoint sets with edges only between the sets. Example: $K_{2,3}$.
• Regular graph: Every vertex has the same degree.

Adjacency Matrix

For a graph with $n$ vertices, the adjacency matrix $A$ is an $n \times n$ matrix where

For an undirected graph $A$ is symmetric. Example: for a triangle with vertices $\{1,2,3\}$ and edges $\{1\text{-}2, 2\text{-}3, 1\text{-}3\}$:

Incidence Matrix

For a graph with $n$ vertices and $m$ edges, the incidence matrix $M$ is an $n \times m$ matrix where

Each column has exactly two 1's (the endpoints of that edge). For the triangle above with edges $e_1 = 1\text{-}2$, $e_2 = 2\text{-}3$, $e_3 = 1\text{-}3$:

Convert $245_{10}$ to binary, octal and hexadecimal by repeated division.

Binary (divide by 2):

$245 \div 2 = 122$ r $1$; $122 \div 2 = 61$ r $0$; $61 \div 2 = 30$ r $1$; $30 \div 2 = 15$ r $0$; $15 \div 2 = 7$ r $1$; $7 \div 2 = 3$ r $1$; $3 \div 2 = 1$ r $1$; $1 \div 2 = 0$ r $1$.

Reading remainders bottom-up: $245_{10} = 11110101_2$.

Octal (divide by 8):

$245 \div 8 = 30$ r $5$; $30 \div 8 = 3$ r $6$; $3 \div 8 = 0$ r $3$.

So $245_{10} = 365_8$. (Check: group the binary as $011\,110\,101 = 3\,6\,5$.)

Hexadecimal (divide by 16):

$245 \div 16 = 15$ r $5$; $15 \div 16 = 0$ r $15 = \text{F}$.

So $245_{10} = \text{F5}_{16}$. (Check: group the binary as $1111\,0101 = \text{F}\,5$.)

Result: $245_{10} = 11110101_2 = 365_8 = \text{F5}_{16}$.

Let $p$ and $q$ be propositions.

Conjunction ($p \wedge q$): "$p$ AND $q$". It is true only when both $p$ and $q$ are true.

Disjunction ($p \vee q$): "$p$ OR $q$" (inclusive). It is true when at least one of $p$, $q$ is true.

Negation ($\neg p$): "NOT $p$". It reverses the truth value of $p$.

Bijective Function

A function $f: A \rightarrow B$ is bijective (a one-to-one correspondence) if it is both:

• Injective (one-to-one): distinct elements of $A$ map to distinct elements of $B$, i.e. $f(x_1) = f(x_2) \implies x_1 = x_2$.
• Surjective (onto): every element of $B$ is the image of some element of $A$, i.e. range $= B$.

A bijective function has an inverse $f^{-1}: B \rightarrow A$.

Example

Let $f: \mathbb{R} \rightarrow \mathbb{R}$ be defined by $f(x) = 2x + 3$.

• Injective: If $2x_1 + 3 = 2x_2 + 3$ then $x_1 = x_2$.
• Surjective: For any $y \in \mathbb{R}$, choose $x = \dfrac{y-3}{2}$; then $f(x) = y$.

Hence $f$ is bijective, with inverse $f^{-1}(y) = \dfrac{y-3}{2}$.

Principle of Inclusion and Exclusion

For two finite sets $A$ and $B$:

For three finite sets $A$, $B$, $C$:

In general, the cardinality of a union of $n$ sets is obtained by adding the sizes of single sets, subtracting the sizes of all pairwise intersections, adding back the triple intersections, and so on, alternating signs:

The principle corrects for over-counting of elements that lie in more than one set.

In a graph, these terms describe sequences of vertices and edges:

• Walk: A finite alternating sequence of vertices and edges $v_0, e_1, v_1, e_2, \dots, e_k, v_k$ where each edge $e_i$ joins $v_{i-1}$ and $v_i$. Vertices and edges may be repeated. Its length is the number of edges.

• Path: A walk in which no vertex is repeated (and hence no edge is repeated). It is an open walk (start vertex $\neq$ end vertex).

• Circuit (closed trail): A closed walk that starts and ends at the same vertex ($v_0 = v_k$) and in which no edge is repeated (vertices other than the start/end may repeat).

Summary table:

(A cycle is a closed path: a circuit with no repeated vertices except the start = end.)

Equivalence Relation

A relation $R$ on a set $A$ is an equivalence relation if it is:

1. Reflexive: $aRa$ for all $a \in A$.
2. Symmetric: if $aRb$ then $bRa$.
3. Transitive: if $aRb$ and $bRc$ then $aRc$.

An equivalence relation partitions the set $A$ into disjoint equivalence classes.

Example

Define the relation "congruent modulo 3" on the set of integers $\mathbb{Z}$: $a \, R \, b \iff 3 \mid (a - b)$.

• Reflexive: $3 \mid (a - a) = 0$, so $aRa$.
• Symmetric: if $3 \mid (a-b)$ then $3 \mid (b-a)$.
• Transitive: if $3 \mid (a-b)$ and $3 \mid (b-c)$, then $3 \mid (a-c)$.

Hence it is an equivalence relation, partitioning $\mathbb{Z}$ into three classes $\{[0], [1], [2]\}$ (remainders mod 3).

Solving $a_n = 2a_{n-1},\; a_0 = 3$

This is a first-order linear homogeneous recurrence (a geometric progression with common ratio $2$). Expanding:

Substituting $a_0 = 3$:

Verification: $a_0 = 3\cdot 2^0 = 3$ ✓, $a_1 = 3\cdot 2 = 6 = 2a_0$ ✓, $a_2 = 12 = 2a_1$ ✓.

Planar Graph

A planar graph is a graph that can be drawn (embedded) in the plane so that no two of its edges cross each other except at common vertices. Such a drawing is called a plane graph. For example, $K_4$ is planar, whereas $K_5$ and $K_{3,3}$ are not planar (by Kuratowski's theorem).

Euler's Formula

For a connected planar graph with $V$ vertices, $E$ edges and $F$ faces (regions, including the unbounded outer face):

For a connected simple planar graph with $V \geq 3$, this also gives the bound $E \leq 3V - 6$.

Example: A cube graph has $V = 8$, $E = 12$, $F = 6$: $8 - 12 + 6 = 2$ ✓.

Selecting 3 Students from 10

Since order does not matter, this is a combination problem, $\binom{n}{r}$ with $n = 10$, $r = 3$:

Result: There are $\boxed{120}$ ways to select 3 students from a group of 10.