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

Quantifiers

A quantifier specifies the quantity of objects in a domain for which a predicate is true.

• Universal quantifier $\forall x\, P(x)$ — read "for all $x$, $P(x)$"; true when $P(x)$ holds for every element of the domain.
• Existential quantifier $\exists x\, P(x)$ — read "there exists an $x$ such that $P(x)$"; true when $P(x)$ holds for at least one element of the domain.

Let the domain be the students in this class. Define predicates:

• $C(x)$: "$x$ has studied calculus."
• $D(x)$: "$x$ owns a computer."

(a) Every student in this class has studied calculus.

Translation:

Negation:

In words: "There is a student in this class who has not studied calculus."

(b) Some student in this class owns a computer.

Translation:

Negation:

In words: "No student in this class owns a computer" (i.e., every student does not own a computer).

Note

These negations use De Morgan's laws for quantifiers: $\neg\forall x\,P(x)\equiv\exists x\,\neg P(x)$ and $\neg\exists x\,P(x)\equiv\forall x\,\neg P(x)$.

Pigeonhole Principle

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

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

Explanation: If every box held at most one object, the total would be at most $k$, contradicting $n>k$. The generalized form follows because if every box held fewer than $\lceil N/k\rceil$ objects, the total would be less than $N$.

Cards Problem

We want to guarantee at least three cards of the same suit. There are $k = 4$ suits (boxes). We need the smallest $N$ such that $\left\lceil \dfrac{N}{4} \right\rceil \ge 3$.

The worst case: we pick 2 cards of each suit $= 2 \times 4 = 8$ cards, still no suit having three. The very next ($9^{th}$) card must complete a third in some suit.

Answer: 9 cards must be selected.

Check: $\left\lceil \dfrac{9}{4} \right\rceil = \lceil 2.25 \rceil = 3.$ ✓

Generalized Example

How many cards must be drawn to guarantee at least five cards of the same suit?

Worst case: 4 of each suit $= 16$ cards. The next card forces a fifth in some suit:

Check: $\lceil 17/4 \rceil = 5.$ ✓

Relation

A relation $R$ from a set $A$ to a set $B$ is a subset of the Cartesian product $A \times B$. A relation on a set $A$ is a subset $R \subseteq A \times A$. We write $a\,R\,b$ (or $(a,b)\in R$) when $a$ is related to $b$.

Properties of a relation on $A$

• Reflexive: every element relates to itself.
• Symmetric: if $a$ relates to $b$, then $b$ relates to $a$.
• Antisymmetric: the only way both $(a,b)$ and $(b,a)$ hold is $a=b$.
• Transitive: relation chains compose.

Equivalence Relation

A relation $R$ on $A$ is an equivalence relation if it is reflexive, symmetric, and transitive. It partitions $A$ into disjoint equivalence classes.

Congruence Modulo $m$ is an Equivalence Relation

Define $a \equiv b \pmod{m}$ iff $m \mid (a-b)$, where $m$ is a fixed positive integer, on the set $\mathbb{Z}$.

1. Reflexive: For any $a$, $a - a = 0 = m \cdot 0$, so $m \mid (a-a)$. Hence $a \equiv a \pmod m$.

2. Symmetric: Suppose $a \equiv b \pmod m$, so $m \mid (a-b)$, i.e. $a-b = mk$ for some integer $k$. Then $b - a = m(-k)$, so $m \mid (b-a)$, giving $b \equiv a \pmod m$.

3. Transitive: Suppose $a \equiv b$ and $b \equiv c \pmod m$. Then $a-b = mk$ and $b-c = ml$ for integers $k,l$. Adding: $a - c = m(k+l)$, so $m \mid (a-c)$, giving $a \equiv c \pmod m$.

Since all three properties hold, congruence modulo $m$ is an equivalence relation. $\blacksquare$

De Morgan's Laws

For sets (with universal set $U$, complement denoted by a bar):

The complement of a union is the intersection of the complements, and vice versa.

For logic (propositions $p, q$):

The negation of a disjunction is the conjunction of the negations, and the negation of a conjunction is the disjunction of the negations.

One-to-One (Injective) Function

A function $f: A \to B$ is one-to-one (injective) if distinct elements of the domain map to distinct elements of the codomain:

Example: $f(x) = 2x$ on $\mathbb{R}$ is one-to-one.

Onto (Surjective) Function

A function $f: A \to B$ is onto (surjective) if every element of the codomain is the image of at least one element of the domain:

That is, the range of $f$ equals the codomain $B$. Example: $f(x) = x^3$ from $\mathbb{R}$ to $\mathbb{R}$ is onto.

A function that is both one-to-one and onto is called a bijection.

Solving the Recurrence

Given $a_n = a_{n-1} + 2n$ with $a_0 = 1$. Compute iteratively:

• $a_1 = a_0 + 2(1) = 1 + 2 = 3$
• $a_2 = a_1 + 2(2) = 3 + 4 = 7$
• $a_3 = a_2 + 2(3) = 7 + 6 = 13$

Verification by closed form: Telescoping, $a_n = a_0 + 2\sum_{k=1}^{n} k = 1 + 2 \cdot \dfrac{n(n+1)}{2} = 1 + n(n+1)$. For $n=3$: $a_3 = 1 + 3\cdot 4 = 13.$ ✓

Degree of a Vertex

The degree of a vertex $v$ in an undirected graph, written $\deg(v)$, is the number of edges incident to $v$, with each self-loop (an edge from $v$ to itself) counted twice.

For a directed graph, $v$ has an in-degree $\deg^-(v)$ (number of edges entering $v$) and an out-degree $\deg^+(v)$ (number of edges leaving $v$).

Handshaking Theorem

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

Consequence: the number of vertices of odd degree is always even. (Directed analogue: $\sum_{v}\deg^-(v) = \sum_{v}\deg^+(v) = |E|$.)

Subgroup

Let $(G, *)$ be a group. A non-empty subset $H \subseteq G$ is a subgroup of $G$, written $H \le G$, if $H$ itself forms a group under the same operation $*$. Equivalently, $H$ is a subgroup iff:

1. Closure: $a, b \in H \implies a * b \in H$.
2. Identity: the identity $e$ of $G$ belongs to $H$.
3. Inverses: $a \in H \implies a^{-1} \in H$.

(One-step test: $H \ne \emptyset$ is a subgroup iff $a, b \in H \implies a * b^{-1} \in H$.)

Example

Consider the group of integers $(\mathbb{Z}, +)$. The set of even integers

is a subgroup: it is closed under addition (even + even = even), contains the identity $0$, and the additive inverse of an even number is even. Hence $2\mathbb{Z} \le \mathbb{Z}$.

Tree vs. Graph

A graph $G = (V, E)$ is a set of vertices $V$ together with a set of edges $E$ connecting pairs of vertices. A tree is a special kind of graph: a connected, acyclic, undirected graph.

In short: every tree is a graph, but not every graph is a tree. A tree on $n$ vertices is minimally connected and adding any edge creates a cycle, while removing any edge disconnects it.

Conditional and its Variants

Let $p$: "it rains" and $q$: "the ground is wet". The original statement is the conditional $p \rightarrow q$: "If it rains then the ground is wet."

• Converse $(q \rightarrow p)$: "If the ground is wet then it rains."
• Inverse $(\neg p \rightarrow \neg q)$: "If it does not rain then the ground is not wet."
• Contrapositive $(\neg q \rightarrow \neg p)$: "If the ground is not wet then it does not rain."

Note: A conditional is logically equivalent to its contrapositive ($p\to q \equiv \neg q \to \neg p$), and the converse is equivalent to the inverse. The conditional is not equivalent to its converse or inverse.

Bit Strings of Length 8 with Exactly Three 1's

A bit string of length 8 has 8 positions. Choosing which three positions hold a $1$ (the rest are $0$) is a combination problem — we count the number of ways to choose 3 positions out of 8:

Adjacency Matrix of a Directed Graph

For a directed graph $G = (V, E)$ with $n$ vertices ordered $v_1, v_2, \dots, v_n$, the adjacency matrix is the $n \times n$ matrix $A = [a_{ij}]$ where

Unlike the undirected case, this matrix is generally not symmetric, because edge direction matters: $a_{ij}=1$ does not imply $a_{ji}=1$.

Example

Let $V = \{1, 2, 3\}$ with directed edges $E = \{(1,2),\ (2,3),\ (3,1),\ (1,3)\}$.

The adjacency matrix (rows = from, columns = to) is:

For instance, row 1 has $a_{12}=1$ and $a_{13}=1$ because vertex 1 has directed edges to vertices 2 and 3. The row sum gives the out-degree of each vertex and the column sum gives its in-degree.