Discrete Structure (CS-302) Unit 1 Notes

How unit 1 is examined

Sets, relations, functions, pigeonhole and proof methods; equivalence relations, induction, pigeonhole, set identities and composition carry the marks.

Set Theory: Definition of sets, countable and uncountable sets

High weight

Definition. A set is a well-defined collection of distinct objects; it is countable if finite or in one-to-one correspondence with $N$, and uncountable otherwise.

Key points.

The Cartesian product $A\times B=\{(a,b): a\in A, b\in B\}$ has $|A||B|$ ordered pairs.
The power set $P(A)$ is the set of all subsets of $A$, and $|P(A)|=2^{|A|}$.
$Z$ and $Q$ are countable, while $R$ and $(0,1)$ are uncountable (Cantor).
Inclusion-exclusion: $|A\cup B\cup C|=\sum|A|-\sum|A\cap B|+|A\cap B\cap C|$.

Proof: $Q$ is countable.

Write positive rationals $p/q$ in an array (row $q$, column $p$).
Traverse diagonals $p+q=2,3,4,\dots$ skipping fractions not in lowest terms: $1,\frac12,2,3,\frac13,\dots$
This lists all of $Q^+$, so $Q^+\leftrightarrow N$; interleave $0,r_1,-r_1,r_2,-r_2,\dots$ for zero and negatives.
Hence $Q$ is in bijection with $N$ and is countable.

Proof: $P(A)\subseteq P(B)\iff A\subseteq B$. ($\Rightarrow$) For $x\in A$, $\{x\}\in P(A)\subseteq P(B)$, so $x\in B$. ($\Leftarrow$) For $X\in P(A)$, $X\subseteq A\subseteq B$, so $X\in P(B)$.

Example. Integers 1 to 500 divisible by none of 2, 3, 5: singles $250+166+100$, pairs $83+50+33$, triple $16$. Divisible by some $=516-166+16=366$. Not divisible $=500-366=\mathbf{134}$ (the key's 133 excludes 1, since "between 1 and 500"; state both).

Example. $A\times B=\{(1,4),(1,5),(4,4),(4,5)\}$, $A\times C=\{(1,5),(1,7),(4,5),(4,7)\}$. (i) Union $=\{(1,4),(1,5),(1,7),(4,4),(4,5),(4,7)\}$. (ii) Intersection $=\{(1,5),(4,5)\}$.

Answer frame. Define countable and uncountable; for $Q$ draw the $p/q$ array with diagonal arrows and give steps 1-4; for numericals write the formula, counts and boxed value.

Asked: [7 marks] (Nov 2019, Dec 2025) Find the number of integers between 1 and 500 not divisible by any of 2, 3 and 5. Asked: [7 marks] (May 2019) Show that the set Q of rational numbers is countable. Asked: [7 marks] (Jun 2020) For $A=\{1,4\}$, $B=\{4,5\}$, $C=\{5,7\}$ find $(A\times B)\cup(A\times C)$ and $(A\times B)\cap(A\times C)$. Asked: [7 marks] (Jun 2023) Prove that $P(A)\subseteq P(B)$ iff $A\subseteq B$. Asked: [7 marks] (Dec 2025) Define countable and uncountable sets. Prove that the set of rational numbers is countable.

Venn Diagrams

Definition. A Venn diagram shows sets as overlapping regions inside a rectangle for the universal set $U$, each combination of membership being one region.

Key points.

Three sets give eight regions; shade an expression from the innermost bracket outwards.
Two expressions are equal only if their shaded regions, or listed elements, are identical.
For counting, fill the centre $|A\cap B\cap C|$ first, then pairwise-only regions (pair minus centre), then single-only regions.

Example (Jun 2025). $B\cap C=\{5\}$, so $(A\cup B)\cap(B\cap C)=\{5\}$. $B\cup C=\{1,3,4,5,6,7\}$, so $A\cap(B\cup C)=\{1,3,4,5\}$. Not equal, so not equivalent.

Example (Dec 2023). $F=20,E=50,H=70$, $EF=5,EH=20,HF=10$, all three $=3$.

Required	Working	Answer
Hindi alone	$70-20-10+3$	43
French alone	$20-5-10+3$	8
English, not Hindi	$50-20$	30
Hindi, not French	$70-10$	60

Answer frame. Open with the definition; draw three overlapping circles inside $U$ with counts in each region; compute in table order; close with boxed answers.

Asked: [7 marks] (Dec 2023) Of 120 students: F=20, E=50, H=70, E&F=5, E&H=20, H&F=10, all three 3; find Hindi alone, French alone, English not Hindi, Hindi not French. Asked: [7 marks] (Jun 2025) For $A=\{1,2,3,4,5\}$, $B=\{3,4,5,6\}$, $C=\{1,5,7\}$, shade $(A\cup B)\cap(B\cap C)$ and $A\cap(B\cup C)$ and check equivalence by listing elements.

Proofs of some general identities on sets

Definition. ==To prove $X=Y$, take an arbitrary $x$ and show $X\subseteq Y$ and $Y\subseteq X$, using $A-B=A\cap B'$.==

Key points.

Chain equivalences from the left side to the right side; if a step is not reversible, write the two inclusions separately.
A Venn proof is only a demonstration, so add the element proof.
De Morgan: $(A\cup B)'=A'\cap B'$ and $(A\cap B)'=A'\cup B'$.

Proof: $A\cap(B\cup C)=(A\cap B)\cup(A\cap C)$. $x\in$ LHS $\iff x\in A$ and ($x\in B$ or $x\in C$) $\iff(x\in A,x\in B)$ or $(x\in A,x\in C)\iff x\in$ RHS.

Proof: $(A\cup B)'=A'\cap B'$. $x\in(A\cup B)'\iff x\notin A$ and $x\notin B\iff x\in A'\cap B'$.

Proof: (i) $A-(B\cap C)=(A-B)\cup(A-C)$. $x\in A$ and $x\notin B\cap C\iff x\in A$ and ($x\notin B$ or $x\notin C$) $\iff(x\in A-B)$ or $(x\in A-C)$.

Proof: (ii) $A-(B\cup C)=(A-B)\cap(A-C)$. $x\in A$ and $x\notin B$ and $x\notin C\iff(x\in A-B)$ and $(x\in A-C)$.

Diagram. Venn proof: shade $B\cup C$, intersect with $A$; separately shade $A\cap B$ and $A\cap C$ and join; the regions match.

Answer frame. Open with the law; write "Let $x$ be arbitrary" and the chain; add the three-circle Venn if asked; close "hence LHS = RHS". In the 14-mark question do (i) and (ii) separately.

Asked: [7 marks] (May 2019) Prove that intersection is distributive over union: $A\cap(B\cup C)=(A\cap B)\cup(A\cap C)$. Asked: [7 marks] (Jun 2020) Prove $(A\cup B)'=A'\cap B'$. Asked: [14 marks] (Jun 2020) Prove (i) $A-(B\cap C)=(A-B)\cup(A-C)$ and (ii) $A-(B\cup C)=(A-B)\cap(A-C)$. Asked: [7 marks] (Dec 2025) Using a Venn diagram, prove $A\cap(B\cup C)=(A\cap B)\cup(A\cap C)$.

Relation: Definition, types of relation

Definition. A relation $R$ from $A$ to $B$ is a subset of $A\times B$; a relation on $A$ is a subset of $A\times A$.

Key points.

The domain is the set of first components and the range the set of second components.
Reflexive: $(a,a)\in R$ for all $a$; irreflexive: $(a,a)\notin R$ for every $a$.
Symmetric: $(a,b)\in R\Rightarrow(b,a)\in R$; antisymmetric: $(a,b),(b,a)\in R\Rightarrow a=b$; asymmetric: $(a,b)\in R\Rightarrow(b,a)\notin R$.
Transitive: $(a,b),(b,c)\in R\Rightarrow(a,c)\in R$.
Equivalence = reflexive + symmetric + transitive; partial order = reflexive + antisymmetric + transitive.

Formula. On $n$ elements there are $2^{n^2}$ relations, $2^{n(n-1)}$ reflexive, $2^{n(n+1)/2}$ symmetric, and $2^{n(n-1)/2}$ reflexive and symmetric (diagonal forced, off-diagonal pairs free).

Example. $A=\{2,3,4\}$, $B=\{3,\dots,7\}$, $x$ divides $y$: $R=\{(2,4),(2,6),(3,3),(3,6),(4,4)\}$; domain $\{2,3,4\}$, range $\{3,4,6\}$.

Answer frame. Open with the definition and an example; list types in the order above with one example each; add the count formula if asked; close with domain and range.

Asked: [7 marks] (Nov 2018) Define relation with example. Explain various types of relations with example. Asked: [14 marks] (Jun 2020) For $A=\{2,3,4\}$, $B=\{3,4,5,6,7\}$ and $(x,y)\in R$ when $x$ divides $y$, determine $R$, its domain and range. Asked: [7 marks] (Dec 2024) Define various types of functions. How many symmetric and reflexive relations are possible on a set of $n$ elements? Asked: [7 marks] (Dec 2025) Define relation. Explain equivalence relation and partial ordering relation with suitable examples.

Composition of relations

Definition. ==For $R\subseteq A\times B$ and $S\subseteq B\times C$, $S\circ R=\{(a,c):\exists b,\ (a,b)\in R,\ (b,c)\in S\}$.==

Key points.

$R=\{(1,2),(2,3)\}$, $S=\{(2,4),(3,5)\}$ give $S\circ R=\{(1,4),(2,5)\}$.
In matrices, $M_{S\circ R}$ is the Boolean product of $M_R$ and $M_S$.
Composition is associative but not commutative, and $R$ is transitive iff $R\circ R\subseteq R$.

Pictorial representation of relation

Definition. A relation on a finite set is drawn as a digraph, with a vertex per element and an arrow $a\to b$ for each $(a,b)\in R$, or written as a Boolean matrix.

Key points.

The matrix has $M_{ij}=1$ if $(i,j)\in R$, else $0$.
A loop at $a$ is $(a,a)$; symmetric means the matrix equals its transpose.
$x<y$ on $\{1,2,3,4\}$ gives $R=\{(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)\}$.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u1-01" viewBox="0 0 338 338" width="338" height="338" role="img" aria-label="Digraph of x < y on {1,2,3,4}"><style>#dsfig-u1-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u1-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u1-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u1-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u1-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u1-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u1-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u1-01 .t{fill:#16181D;font-weight:500}#dsfig-u1-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u1-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u1-01 .dot{fill:#16181D}#dsfig-u1-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u1-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u1-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u1-01 .ah{fill:#454C5A}#dsfig-u1-01 .ah.hi{fill:#2340B8}#dsfig-u1-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u1-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u1-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u1-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u1-01 .e{stroke:#B1B7C3}html.dark #dsfig-u1-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u1-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u1-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u1-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u1-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u1-01 .t{fill:#E6E8ED}html.dark #dsfig-u1-01 .t.inv{fill:#0F1115}html.dark #dsfig-u1-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u1-01 .dot{fill:#E6E8ED}html.dark #dsfig-u1-01 .ann{fill:#8FA3FF}html.dark #dsfig-u1-01 .lbl{fill:#858D9C}html.dark #dsfig-u1-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u1-01 .ah{fill:#B1B7C3}html.dark #dsfig-u1-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u1-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u1-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u1-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah1" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh1" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M59,40 L277,40" marker-end="url(#ah1)"/><path class="e" d="M53.4,53.4 L283.2,283.2" marker-end="url(#ah1)"/><path class="e" d="M40,59 L40,277" marker-end="url(#ah1)"/><path class="e" d="M298,59 L298,277" marker-end="url(#ah1)"/><path class="e" d="M284.6,53.4 L54.8,283.2" marker-end="url(#ah1)"/><path class="e" d="M279,298 L61,298" marker-end="url(#ah1)"/><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">1</text><circle class="n" cx="298" cy="40" r="18"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">2</text><circle class="n" cx="298" cy="298" r="18"/><text class="t" x="298" y="298" dy=".35em" text-anchor="middle">3</text><circle class="n" cx="40" cy="298" r="18"/><text class="t" x="40" y="298" dy=".35em" text-anchor="middle">4</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Digraph of x < y on {1,2,3,4}</figcaption></figure>

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

Asked: [7 marks] (Nov 2022) If $X=\{1,2,3,4\}$ and $R=\{(x,y): x<y\}$, draw the graph of $R$ and give its matrix.

Equivalence relation

Definition. A relation on a set is an equivalence relation if it is reflexive, symmetric and transitive.

Key points.

Reflexive: $aRa$. Symmetric: $aRb\Rightarrow bRa$. Transitive: $aRb$, $bRc\Rightarrow aRc$.
To disprove, one failing property suffices.
The class $[a]=\{x: xRa\}$; classes are disjoint and cover the set, so an equivalence gives a partition.

Proof: $(a,b)R(c,d)$ iff $a+d=b+c$. Reflexive: $a+b=b+a$. Symmetric: $a+d=b+c\Rightarrow c+b=d+a$. Transitive: $a+d=b+c$ and $c+f=d+e$; adding, $a+f=b+e$.

Proof: $x\equiv y\pmod m$ on $Z$ ($m=3$). Reflexive: $x-x=0=0\cdot m$. Symmetric: $x-y=km\Rightarrow y-x=(-k)m$. Transitive: $x-y=k_1m$, $y-z=k_2m\Rightarrow x-z=(k_1+k_2)m$.

Proof: equal area (triangles) or equal length (strings), $f$ = area or $l$. Reflexive: $f(a)=f(a)$. Symmetric: $f(a)=f(b)\Rightarrow f(b)=f(a)$. Transitive: $f(a)=f(b)=f(c)\Rightarrow f(a)=f(c)$.

Proof: $R^{-1}$ with $(b,a)\in R^{-1}\iff(a,b)\in R$. Reflexive: $(a,a)\in R\Rightarrow(a,a)\in R^{-1}$. Symmetric: $(a,b)\in R^{-1}\Rightarrow(b,a)\in R\Rightarrow(a,b)\in R\Rightarrow(b,a)\in R^{-1}$. Transitive: $(a,b),(b,c)\in R^{-1}\Rightarrow(b,a),(c,b)\in R\Rightarrow(c,a)\in R\Rightarrow(a,c)\in R^{-1}$.

Example (Dec 2025). $R=\{(1,1),(2,2),(3,3),(1,2),(2,1)\}$ on $\{1,2,3\}$: loops present; $(1,2),(2,1)$ both present; chains $1\to2\to1$, $2\to1\to2$ give $(1,1),(2,2)\in R$. Equivalence, with classes $[1]=[2]=\{1,2\}$, $[3]=\{3\}$.

Example (Jun 2025). Same remainder mod 3 on $\{1,\dots,6\}$: classes $[1]=\{1,4\}$, $[2]=\{2,5\}$, $[0]=\{3,6\}$; $R$ has 12 pairs: six loops plus $(1,4),(4,1),(2,5),(5,2),(3,6),(6,3)$.

Answer frame. Open with the three properties; prove them in order, one line each; close "hence $R$ is an equivalence relation". For "illustrate", add classes and pairs.

Pitfall: Transitivity needs both premises written and combined; skipping it loses marks.

Asked: [14 marks] (Jun 2020, Jun 2023) For the set of triangles in a plane, $aRb$ iff area of $a$ = area of $b$; prove $R$ is an equivalence relation. Asked: [7 marks] (Nov 2022, Jun 2024) Show that $(a,b)R(c,d)$ if $a+d=b+c$ is an equivalence relation. Asked: [7 marks] (Nov 2022) If $R$ is an equivalence relation on $A$, show that $R^{-1}$ is also one. Asked: [7 marks] (Jun 2023) On strings of English letters, $aRb$ iff $l(a)=l(b)$. Is $R$ an equivalence relation? Asked: [7 marks] (Dec 2023, Jun 2024) $R=\{(x,y): x-y$ is a multiple of 3$}$ on $Z$ (also congruence modulo $m$): show it is an equivalence relation. Asked: [7 marks] (Jun 2025) Define and illustrate an equivalence relation on $S=\{1,\dots,6\}$ with the same remainder mod 3. Asked: [7 marks] (Dec 2025) For $A=\{1,2,3\}$, $R=\{(1,1),(2,2),(3,3),(1,2),(2,1)\}$, check whether $R$ is an equivalence relation and find the classes.

Partial ordering relation

Definition. A partial order is a relation that is reflexive, antisymmetric and transitive; the set with it is a poset $(A,\preceq)$.

Key points.

Examples: $\le$ on numbers, $\subseteq$ on sets, divisibility on positive integers.
In a total order every two elements are comparable.
A Hasse diagram draws only covering edges, no loops, larger elements higher.
Divisibility on $\{1,2,3,6\}$ is not total, since 2 and 3 are incomparable.

Job-Scheduling problem

Definition. Jobs with precedence constraints form a partial order, and a topological sort is a linear order of the jobs that respects every constraint.

Key points.

$a\prec b$ means job $a$ must finish before $b$ starts.
Repeatedly output a minimal job (no unfinished predecessor) and delete it.
Incomparable jobs can run in parallel, so the order is not unique: with $A\prec C$, $B\prec C$, both $A,B,C$ and $B,A,C$ are valid.

Function: Definition, type of functions, one to one, into and onto function

Definition. A function $f:A\to B$ assigns to every element of $A$ exactly one element of $B$.

Key points.

One-one (injective): $f(x_1)=f(x_2)\Rightarrow x_1=x_2$.
Onto (surjective): every $y\in B$ is $f(x)$ for some $x$, so range $=B$; otherwise $f$ is into.
Bijective: one-one and onto, e.g. $f(x)=x+1$ on $Z$; two sets of size $n$ have $n!$ bijections.
Other types: constant, identity, many-one (not injective); reflexive and symmetric relations on $n$ elements number $2^{n(n-1)/2}$.

Example (Dec 2023). $f=3x-12\ (x>3)$; $2x^2+3\ (-2<x\le3)$; $3x^2-7\ (x\le-2)$.

Value	Branch 1	Branch 2	Branch 3	$f^{-1}$
3	$x=5$ ok	$x=0$ ok	$x=-1.83$ reject	$\{0,5\}$
0	$x=4$ ok	none	$x=-1.53$ reject	$\{4\}$
$-2$	$x=10/3$ ok	none	$x=-1.29$ reject	$\{10/3\}$

Answer frame. Open with the definition; give injective, surjective, bijective with condition and example; solve every branch; close with the pre-image sets.

Pitfall: A root outside its branch's interval must be rejected.

Asked: [7 marks] (Dec 2023) For the piecewise $f:R\to R$ find $f^{-1}(3)$, $f^{-1}(0)$, $f^{-1}(-2)$. Asked: [7 marks] (Dec 2024) Define various types of functions. How many symmetric and reflexive relations on a set of $n$ elements?

Inverse function

Definition. ==The inverse of $f:A\to B$ is $f^{-1}:B\to A$ with $f^{-1}(f(x))=x$ and $f(f^{-1}(y))=y$; it exists iff $f$ is bijective.==

Key points.

$f^{-1}(b)=a\iff f(a)=b$.
$(f^{-1})^{-1}=f$ and $(g\circ f)^{-1}=f^{-1}\circ g^{-1}$.

Proof: inverse exists iff bijective. ($\Rightarrow$) $f(x_1)=f(x_2)\Rightarrow x_1=f^{-1}(f(x_1))=f^{-1}(f(x_2))=x_2$, so one-one; for any $y$, $f(f^{-1}(y))=y$, so onto. ($\Leftarrow$) Onto gives each $y$ a pre-image and one-one makes it unique; define $f^{-1}(y)$ as that $x$.

Example. $f(x)=x+1$ on $Z$. One-one: $x_1+1=x_2+1\Rightarrow x_1=x_2$. Onto: $x=y-1\in Z$ gives $f(x)=y$. Bijective, so $f^{-1}(y)=y-1$.

Answer frame. Open with the definition and the bijective condition; prove one-one and onto; state the inverse; for the theorem give both directions.

Asked: [7 marks] (Jun 2023) Illustrate the inverse function. Is $f:Z\to Z$, $f(x)=x+1$ invertible? Find its inverse. Asked: [7 marks] (Dec 2025) Define one-one, onto and bijective functions. Prove that the inverse exists iff the function is bijective.

Composition of functions

Definition. ==For $f:A\to B$ and $g:B\to C$, $g\circ f:A\to C$ is defined by $(g\circ f)(x)=g(f(x))$.==

Key points.

Apply $f$ first and $g$ second; the range of $f$ must lie in the domain of $g$.
Composition is associative: $h\circ(g\circ f)=(h\circ g)\circ f$.
It is generally not commutative: $g\circ f\ne f\circ g$.
Composing two one-one, onto or bijective functions gives a one-one, onto or bijective function.

Example 1. $f=2x+3$, $g=3x+4$, $h=4x$.

Composition	Working	Result
$g\circ f$	$3(2x+3)+4$	$6x+13$
$f\circ g$	$2(3x+4)+3$	$6x+11$
$f\circ h$	$2(4x)+3$	$8x+3$
$g\circ h$	$3(4x)+4$	$12x+4$

Example 2. $f(a)=a+1$, $g(b)=b^2+2$: $(g\circ f)(-2)=g(-1)=\mathbf3$; $(f\circ g)(x)=x^2+3$; $(g\circ g)(y)=(y^2+2)^2+2=y^4+4y^2+6$; $(g\circ f)(x)=(x+1)^2+2=x^2+2x+3$.

Answer frame. Open with $g\circ f(x)=g(f(x))$; substitute inner into outer in a table and simplify; close with the results, noting $g\circ f\ne f\circ g$.

Pitfall: $g\circ f$ means $f$ first; swapping the order swaps the answers.

Asked: [14 marks] (Nov 2018, Jun 2020) Let $f(x)=2x+3$, $g(x)=3x+4$, $h(x)=4x$; find $g\circ f$, $f\circ g$, $f\circ h$, $g\circ h$. With $f(a)=a+1$, $g(b)=b^2+2$, find $(g\circ f)(-2)$, $(f\circ g)(x)$, $(g\circ g)(y)$, $(g\circ f)(x)$.

Recursively defined functions

Definition. A recursively defined function has a base case (initial value) and a recursive step defining $f(n)$ from earlier values.

Key points.

Both parts are needed: the base stops the recursion, the step generates the rest, e.g. $n!=n\,(n-1)!$, $0!=1$.
To solve, unroll until the base case appears, then confirm by induction.
$f(n)=f(n-1)+3$, $f(0)=2$: $f(n)=f(n-2)+2\cdot3=\dots=f(0)+3n$, so $f(n)=\mathbf{3n+2}$. Check: $f(k+1)=3k+2+3=3(k+1)+2$.

Asked: [7 marks] (Jun 2025) Explain a recursively defined function. Solve $f(n)=f(n-1)+3$ with $f(0)=2$.

Pigeonhole principle

Definition. If $n+1$ or more pigeons are placed in $n$ pigeonholes, some pigeonhole contains at least two pigeons.

Key points.

Generalised form: $N$ objects in $k$ boxes force some box to hold at least $\lceil N/k\rceil$.
It proves existence only; to apply it name the pigeons and holes and check pigeons outnumber holes.
The contrapositive of $p\to q$ is $\neg q\to\neg p$.

Proof by contradiction. If each of the $n$ holes had at most one pigeon, the total would be at most $n<n+1$, a contradiction.

Proof by induction on $n$. Base $n=1$: one hole holds all $\ge2$ pigeons. Assume true for $k$ holes; put $k+2$ pigeons in $k+1$ holes. If some hole has $\ge2$, done; else each has at most one, so removing one occupied hole leaves $\ge k+1$ pigeons in $k$ holes, and the hypothesis gives a hole with two, contradicting that each has at most one.

Example. 15 people (pigeons), 12 months (holes): $15>12$, so at least $\lceil15/12\rceil=2$ share a birth month.

Proof: six people give three mutual friends or three mutual strangers. People are vertices of $K_6$; edge red if friends, blue if strangers. A person $v$ has 5 edges in 2 colours, so at least 3 share a colour, say red, to $a,b,c$. If any of $ab,bc,ca$ is red it makes a red triangle with $v$; otherwise $abc$ is blue. Either way the claim holds.

Answer frame. Open with the statement; prove by contradiction (induction if asked); name pigeons and holes in the example; close with the generalised form. For six people draw $K_6$ with $v$ and its five edges.

Asked: [7 marks] (Nov 2018, Jun 2025) State and prove the pigeonhole principle with an example. Asked: [7 marks] (May 2019) Briefly explain the application of the pigeonhole principle using an example. Asked: [7 marks] (Dec 2020) Prove that among six people at least three are mutual friends or at least three are mutual strangers. Asked: [7 marks] (Jun 2024, Dec 2024) Define the pigeonhole principle. Write the contrapositive of "if it is Sunday then it is a holiday" (answer: "if it is not a holiday, then it is not Sunday"). Asked: [7 marks] (Jun 2025, Dec 2025) What is the pigeonhole principle? Prove it by induction and show that among 15 people two share a birth month.

Theorem proving Techniques: Mathematical induction

Definition. Mathematical induction proves $P(n)$ for all $n\ge n_0$ by showing the base case $P(n_0)$ and that $P(k)\Rightarrow P(k+1)$ for every $k\ge n_0$.

Steps.

Step 1: Base step: verify P(n0), usually n = 1 (or n = 0).
Step 2: Hypothesis: assume P(k) is true for some k >= n0.
Step 3: Inductive step: prove P(k+1) using P(k).
Step 4: Conclude by the principle of mathematical induction.

Key points.

For sums, add the $(k+1)$th term to the hypothesis; for divisibility, assume $f(k)=mN$ and write $f(k+1)$ as a multiple of $N$.

Proof: $\sum_{1}^{n}k^2=\frac{n(n+1)(2n+1)}6$. $n=1$: $1=\frac{1\cdot2\cdot3}6$. Adding $(k+1)^2$: $\frac{k(k+1)(2k+1)}6+(k+1)^2=\frac{(k+1)(2k^2+7k+6)}6=\frac{(k+1)(k+2)(2k+3)}6$.

Proof: $1+2+\dots+n=\frac{n(n+1)}2$. $n=1$: $1=1$. Adding $k+1$: $\frac{k(k+1)}2+(k+1)=\frac{(k+1)(k+2)}2$.

Proof: $1+4+\dots+(3n-2)=\frac{n(3n-1)}2$. The printed "$2n(3n-1)$" fails at $n=1$ ($1\ne4$); say so and prove the correct form. $n=1$: $1=\frac{1\cdot2}2$. Adding $3k+1$: $\frac{k(3k-1)}2+3k+1=\frac{3k^2+5k+2}2=\frac{(k+1)(3(k+1)-1)}2$.

Proof: $\sum_{r=0}^{n}3^r=\frac{3^{n+1}-1}2$. $n=0$: $1=\frac{3-1}2$. Adding $3^{k+1}$: $\frac{3^{k+1}-1}2+3^{k+1}=\frac{3^{k+2}-1}2$.

Proof: $\sum\frac1{(2i-1)(2i+1)}=\frac n{2n+1}$. $n=1$: $\frac13=\frac13$. Adding $\frac1{(2k+1)(2k+3)}$: $\frac{k(2k+3)+1}{(2k+1)(2k+3)}=\frac{(2k+1)(k+1)}{(2k+1)(2k+3)}=\frac{k+1}{2k+3}$.

Proof: $\sum i\cdot i!=(n+1)!-1$. $n=1$: $1=2!-1$. Adding $(k+1)(k+1)!$: $(k+1)!-1+(k+1)(k+1)!=(k+2)!-1$.

Proof: $n^3+2n$ divisible by 3. $n=1$: 3. Assume $k^3+2k=3m$: $(k+1)^3+2(k+1)=3m+3(k^2+k+1)=3(m+k^2+k+1)$.

Proof: $5^{2n}-1$ divisible by 24. $n=1$: 24. Assume $5^{2k}-1=24m$: $5^{2k+2}-1=25(24m+1)-1=24(25m+1)$.

Answer frame. Open by defining induction in three steps; write "Let $P(n)$: ..." and the base case with numbers; state the hypothesis, then the $k+1$ step as one chain ending at the target; close with the conclusion sentence.

Pitfall: Use the hypothesis and reach the exact $k+1$ form; never assume $P(k+1)$.

Asked: [7 marks] (Nov 2018, Dec 2023) Show by induction $\sum_{k=1}^{n}k^2=\frac{n(n+1)(2n+1)}6$. Asked: [7 marks] (May 2019) Prove by induction $1+4+7+\dots+(3n-2)=2n(3n-1)$ (correct form $\frac{n(3n-1)}2$). Asked: [7 marks] (Dec 2020) Show by induction $\sum_{r=0}^{n}3^r=\frac{3^{n+1}-1}2$. Asked: [7 marks] (Dec 2020) Prove by induction that $n^3+2n$ is divisible by 3. Asked: [7 marks] (Jun 2020) Prove by induction $\frac1{1\cdot3}+\frac1{3\cdot5}+\dots+\frac1{(2n-1)(2n+1)}=\frac n{2n+1}$. Asked: [7 marks] (Nov 2022) What is mathematical induction? Prove $1\cdot1!+2\cdot2!+\dots+n\cdot n!=(n+1)!-1$. Asked: [7 marks] (Jun 2024) Prove that $5^{2n}-1$ is divisible by 24 for every positive integer $n$. Asked: [7 marks] (Dec 2025) Prove by induction $1+2+3+\dots+n=\frac{n(n+1)}2$.

Proof by contradiction

Definition. To prove $P\to Q$ by contradiction, assume $P$ is true and $Q$ is false and derive a statement $R\wedge\neg R$.

Key points.

Direct: assume $P$ and show $Q$, e.g. $n=2k\Rightarrow n^2=2(2k^2)$.
Indirect (contraposition): prove $\neg Q\to\neg P$, e.g. $n$ odd gives $n^2$ odd, so $n^2$ even implies $n$ even.
Contradiction: assume the negation of the claim and reach an impossibility.
By cases: split into exhaustive cases and prove each, e.g. $n(n+1)$ is even whether $n$ is even or odd.

Proof: $\sqrt2$ is irrational. Suppose $\sqrt2=p/q$ with $\gcd(p,q)=1$. Squaring, $2q^2=p^2$, so $p^2$ and hence $p$ is even; put $p=2k$. Then $q^2=2k^2$, so $q$ is even. Both are even, contradicting $\gcd(p,q)=1$. Hence $\sqrt2$ is irrational.

Answer frame. For $\sqrt2$: open "assume $\sqrt2$ is rational", give the steps, close "contradiction, hence irrational". For the four methods: definition and example each, in the order above.

Asked: [7 marks] (Dec 2020) Show that $\sqrt2$ is irrational. Asked: [7 marks] (Nov 2022) Explain the method of proving theorems by direct, indirect, contradiction and by cases. Asked: [7 marks] (Dec 2025) Prove by contradiction that $\sqrt2$ is irrational.

Last-minute revision

Countable: finite or in bijection with $N$; $Q$ yes, $R$ no; $|P(A)|=2^{|A|}$.
Numbers 1 to 500 not divisible by 2, 3, 5: 134 (133 excluding 1).
Equivalence = reflexive + symmetric + transitive; partial order = reflexive + antisymmetric + transitive.
Inverse exists iff $f$ is bijective; $g\circ f=6x+13$, $f\circ g=6x+11$, $f\circ h=8x+3$, $g\circ h=12x+4$.
Pigeonhole: $N$ objects in $k$ boxes give a box with $\ge\lceil N/k\rceil$; six people force a monochromatic triangle.

Memory hooks

Equivalence = R-S-T; swap symmetric for antisymmetric to get a poset.
Pigeons, holes, more-than: name both, then check $N>k$.
Induction is a domino row: first falls (base), each knocks the next (step).
Composition reads right to left: $g\circ f$ is "$f$ then $g$".

Coverage checklist

Set Theory (Q20-Q24).
Venn Diagrams (Q34, Q35).
proofs of some general identities on sets (Q4, Q43-Q45).
Relation (Q2, Q17-Q19).
composition of relations (no past question)
Pictorial representation of relation (Q13).
Equivalence relation (Q1, Q5-Q10).
Partial ordering relation (no past question)
Job-Scheduling problem (no past question)
Function (Q11, Q12).
inverse function (Q36, Q37).
composition of functions (Q3).
recursively defined functions (Q46).
pigeonhole principle (Q38-Q42).
Theorem proving Techniques (Q25-Q33).
Proof by contradiction (Q14-Q16).

Account

Discrete Structure (CS-302) - Unit 1 Short Notes

How unit 1 is examined

Set Theory: Definition of sets, countable and uncountable sets

Venn Diagrams

Proofs of some general identities on sets

Relation: Definition, types of relation

Composition of relations

Pictorial representation of relation

Equivalence relation

Partial ordering relation

Job-Scheduling problem

Function: Definition, type of functions, one to one, into and onto function

Inverse function

Composition of functions

Recursively defined functions

Pigeonhole principle

Theorem proving Techniques: Mathematical induction

Proof by contradiction

Last-minute revision

Memory hooks

Coverage checklist