GTU 3140708 Discrete Mathematics (DM) Summer 2026 Solved Paper & Solutions

Let $A$, $B$, $C$ be the numbers in 1 to 1000 divisible by 3, 5 and 7. Use the inclusion-exclusion principle.

Numbers divisible by two of them are divisible by the product (15, 21, 35). Numbers divisible by all three are divisible by 105.

Numbers divisible by none of 3, 5, 7: $1000 - 543 = 457$.

• Complete graph: a simple graph in which every two distinct vertices are joined by an edge. A complete graph on $n$ vertices has $\frac{n(n-1)}{2}$ edges. Example: $K_4$ has 4 vertices and 6 edges.
• Tree: a connected graph with no cycle. It has exactly one path between any two vertices, and a tree with $n$ vertices has $n-1$ edges. Example: a path $a - b - c$ with a branch $b - d$.
• Adjacency matrix: for a graph with $n$ vertices, an $n \times n$ matrix whose entry $a_{ij}$ is 1 if $v_i$ and $v_j$ are joined by an edge, and 0 otherwise. It tells at a glance which vertices are neighbours. Example: for the path $v_1 - v_2 - v_3$:

• Strongly connected graph: a directed graph in which there is a directed path from every vertex to every other vertex. Example: a directed triangle $a \to b \to c \to a$.

A partition of a set $S$ is a collection of non-empty, pairwise disjoint subsets of $S$ whose union is $S$. Every element of $S$ lies in exactly one of the subsets. Example: $\{\{1,2\},\{3\},\{4,5\}\}$ is a partition of $\{1,2,3,4,5\}$, because the three subsets do not overlap and together contain all five numbers.

Here $R$ is defined on the set of integers $\mathbb{Z}$ by $xRy$ if and only if $5 \mid (x-y)$. In words, two integers are related when their difference is a multiple of 5. For example, $17 R 2$ because $17 - 2 = 15$.

R is an equivalence relation

An equivalence relation is reflexive, symmetric and transitive.

1. Reflexive: for any $x$, $x - x = 0$, and $5 \mid 0$. So $xRx$.
2. Symmetric: let $xRy$. Then $x - y = 5k$ for some integer $k$. So $y - x = 5(-k)$, which is divisible by 5. So $yRx$.
3. Transitive: let $xRy$ and $yRz$. Then $x - y = 5m$ and $y - z = 5n$. Adding, $x - z = 5(m+n)$, which is divisible by 5. So $xRz$.

$R$ is reflexive, symmetric and transitive, so it is an equivalence relation.

Distinct equivalence classes

The class of $a$ is $[a] = \{x : 5 \mid (x-a)\}$. Two integers are in one class when they leave the same remainder on division by 5. The possible remainders are 0, 1, 2, 3 and 4, and each one gives a different class, so there are exactly 5 classes.

These classes do not overlap, and together they cover all of $\mathbb{Z}$. This is a general fact: the equivalence classes of any equivalence relation form a partition of the set. So the partition for $R$ is $\{[0],[1],[2],[3],[4]\}$, and there is no other distinct partition for this relation.

A rectangle on the chessboard is fixed by choosing 2 of the horizontal lines and 2 of the vertical lines.

An 8 by 8 board has 9 horizontal and 9 vertical grid lines.

• Partial ordered relation: a relation on a set that is reflexive, antisymmetric and transitive. It orders some pairs of elements, not necessarily all. Example: "$\le$" on the set of integers. Here $a \le a$, if $a \le b$ and $b \le a$ then $a = b$, and if $a \le b$ and $b \le c$ then $a \le c$.
• Complemented lattice: a lattice with a least element $0$ and a greatest element $1$, in which every element $a$ has a complement $a'$ such that $a \vee a' = 1$ and $a \wedge a' = 0$. Example: the subsets of $\{x, y\}$ ordered by inclusion, where $\{x\}$ and $\{y\}$ are complements of each other, and $\emptyset$ and $\{x,y\}$ are complements of each other.
• Maximal element: an element $a$ of a POSET is maximal if no other element $b$ of the POSET satisfies $a \prec b$. A POSET may have more than one maximal element. Example: in $\{2,3,4,6\}$ under divisibility, 4 and 6 are maximal, because no other element of the set is a multiple of them.

The relation divisibility on $D_{12} = \{1, 2, 3, 4, 6, 12\}$ is defined as $a \le b$ if and only if $a \mid b$.

(i) Partial order

1. Reflexive: $a \mid a$ for every $a$.
2. Antisymmetric: if $a \mid b$ and $b \mid a$, then $a = b$, because both are positive.
3. Transitive: if $a \mid b$ and $b \mid c$, then $a \mid c$.

So divisibility is a partial order and $(D_{12}, \mid)$ is a POSET. Note that $a \mid b$ means $b$ is a multiple of $a$, and the order is partial because, for example, 2 and 3 do not divide each other.

(ii) Hasse diagram

In a Hasse diagram, we draw a point for each element, a line upward from $a$ to $b$ when $b$ covers $a$, and we omit loops and lines that follow from transitivity. The covering pairs here are 1-2, 1-3, 2-4, 2-6, 3-6, 4-12, 6-12.

The line 1-4 is not drawn, because 1 to 4 already goes through 2.

(iii) Is it a lattice?

Yes. For any two elements $a, b$ of $D_{12}$, the greatest lower bound is $\gcd(a,b)$ and the least upper bound is $\text{lcm}(a,b)$. Both divide 12, so both lie in $D_{12}$. For example, $\gcd(4,6) = 2$ and $\text{lcm}(4,6) = 12$. Every pair has a meet and a join, so it is a lattice. A lattice is a POSET in which every two elements have both a greatest lower bound and a least upper bound.

(iv) Least and greatest element

The least element is 1, because 1 divides every element of $D_{12}$ and lies below all of them in the diagram. The greatest element is 12, because every element divides 12 and it lies above all of them in the diagram.

(v) Two chains

A chain is a subset in which every two elements are comparable.

• $1 \mid 2 \mid 4 \mid 12$
• $1 \mid 3 \mid 6 \mid 12$

One-one: let $f(a) = f(b)$. Then $4a + 8 = 4b + 8$, so $4a = 4b$ and $a = b$. Different inputs give different outputs, so $f$ is one-one.

Onto: take any real number $y$. Solve $y = 4x + 8$ for $x$.

This $x$ is a real number and $f(x) = 4\cdot\frac{y-8}{4} + 8 = y$. Every $y$ has a pre-image, so $f$ is onto.

Inverse: since $f$ is one-one and onto, the inverse exists.

(i) A semigroup is a non-empty set $S$ with a binary operation $\ast$ that is closed on $S$ and associative: $(a \ast b) \ast c = a \ast (b \ast c)$ for all $a, b, c$ in $S$.

Example: $(\mathbb{Z}, +)$ is a semigroup, because the sum of integers is an integer and addition is associative.

(ii) A monoid is a semigroup that also has an identity element.

Example of a semigroup that is not a monoid: the set of positive integers $\mathbb{N} = \{1, 2, 3, \dots\}$ under addition.

• It is closed, because the sum of two positive integers is positive.
• It is associative, because addition is associative.
• It has no identity. The identity for addition would be 0, and 0 is not in the set.

So $(\mathbb{N}, +)$ is a semigroup but not a monoid.

Two graphs $G$ and $H$ are isomorphic if there is a one-one and onto function $f$ from the vertices of $G$ to the vertices of $H$ such that $u$ and $v$ are adjacent in $G$ if and only if $f(u)$ and $f(v)$ are adjacent in $H$.

Edges read from the figure

$G$ has the edges $u_1u_2,\ u_2u_3,\ u_3u_4,\ u_4u_1,\ u_4u_5,\ u_5u_6,\ u_6u_2$.

$H$ has the edges $v_1v_2,\ v_2v_3,\ v_3v_4,\ v_4v_5,\ v_5v_1,\ v_5v_6,\ v_6v_3$.

Check what must match

Both graphs have 6 vertices and 7 edges. The degrees in both are 3, 3, 2, 2, 2, 2.

• In $G$, the degree 3 vertices are $u_2$ and $u_4$. They are not adjacent.
• In $H$, the degree 3 vertices are $v_3$ and $v_5$. They are not adjacent.

One-one correspondence

Each edge of $G$ must go to an edge of $H$.

All 7 images are edges of $H$, and these are all 7 edges of $H$.

Prove the distributive law by cases on $p$.

When $p$ is true, both sides are true. When $p$ is false, $p \vee x$ is just $x$, so the left side is $q \wedge r$ and the right side is $q \wedge r$.

The two sides have the same truth value in every case, so $p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)$.

A group is a set with a binary operation that is closed, associative, has an identity, and gives every element an inverse. It is a commutative (abelian) group if also $a \ast b = b \ast a$ for all elements. Check the five conditions for $(\mathbb{Z}, +)$, where $\mathbb{Z}$ is the set of all integers.

1. Closure: the sum of two integers is an integer.
2. Associative: $(a + b) + c = a + (b + c)$ for all integers.
3. Identity: 0 is an integer and $a + 0 = 0 + a = a$.
4. Inverse: for any integer $a$, $-a$ is an integer and $a + (-a) = 0$.
5. Commutative: $a + b = b + a$ for all integers.

All five conditions hold, so $(\mathbb{Z}, +)$ is a commutative group. The same check fails for multiplication, because 2 has no integer inverse.

A field is a commutative ring with unity in which every non-zero element has a multiplicative inverse. In $\mathbb{Z}_5$, addition $+_5$ and multiplication $\times_5$ mean: add or multiply, then keep the remainder on division by 5. For example, $3 +_5 4 = 2$ and $3 \times_5 4 = 2$. So we check three things.

(1) Addition modulo 5

• The table has only elements of $\mathbb{Z}_5$, so it is closed.
• Addition of integers is associative, so this is too.
• The identity is $[0]$.
• The inverses are $[0] \to [0]$, $[1] \to [4]$, $[2] \to [3]$, $[3] \to [2]$, $[4] \to [1]$.
• The table is symmetric, so addition is commutative.

So $(\mathbb{Z}_5, +_5)$ is an abelian group. Each row of the table contains every element once, which is another way to see that every element has an inverse.

(2) Multiplication modulo 5

• The table is closed, and the multiplication of integers is associative and commutative.
• The unity is $[1]$.
• Every non-zero element has an inverse: $[1] \cdot [1] = [1]$, $[2] \cdot [3] = [1]$, $[4] \cdot [4] = [1]$.
• So the non-zero elements $[1],[2],[3],[4]$ form an abelian group under multiplication.
• There are no zero divisors, because 5 is a prime number. This is the reason $\mathbb{Z}_5$ works as a field, while $\mathbb{Z}_6$ does not.

(3) Distributive law

The two operations must be linked by the distributive law.

$a(b + c) = ab + ac$ holds for integers, and reducing both sides modulo 5 keeps it true, because the remainder of a sum or a product depends only on the remainders of the numbers. So it holds in $\mathbb{Z}_5$.

The expression is $\neg(p \wedge q) \vee (\neg p \wedge q) \vee (q \wedge r)$.

A PCNF (principal conjunctive normal form) is a product of maxterms, one for each row where the expression is false.

The expression is an OR of three parts, so it is false only if all three parts are false.

• $\neg(p \wedge q)$ is false only when $p$ and $q$ are both true.
• With $p$ true, $\neg p \wedge q$ is false.
• With $q$ true, $q \wedge r$ is false only when $r$ is false.

So the only row where the expression is false is $p = T$, $q = T$, $r = F$. The maxterm for this row negates the true variables.

Subgroup: a non-empty subset $H$ of a group is a subgroup if it is closed under the group operation and contains the inverse of each of its elements. Here the operation is addition and $H$ is the set of all multiples of 5.

$H = \{5n : n \in \mathbb{Z}\}$.

1. Non-empty: $0 = 5 \cdot 0$ is in $H$.
2. Closed: $5m + 5n = 5(m + n)$ is in $H$.
3. Inverse: the inverse of $5n$ is $-5n = 5(-n)$, which is in $H$.

So $H$ is a subgroup of $\mathbb{Z}$.

Cosets: the cosets of $H$ are $a + H$. Two cosets $a + H$ and $b + H$ are equal exactly when $a - b$ is in $H$, that is, when $a$ and $b$ leave the same remainder on division by 5. So there are 5 distinct cosets, one for each remainder 0, 1, 2, 3, 4.

• (i) Path: a sequence of vertices $v_0, v_1, \dots, v_k$ in which each consecutive pair is joined by an edge. The number of edges, $k$, is its length. Example: $a - b - c$ is a path of length 2.
• (ii) Strongly connected graph: a directed graph in which there is a directed path from every vertex to every other vertex. Example: a directed triangle $a \to b \to c \to a$.
• (iii) $k$-regular graph: a graph in which every vertex has degree exactly $k$. Example: a triangle is 2-regular, and $K_4$ is 3-regular.
• (iv) Indegree: in a directed graph, the indegree of a vertex is the number of edges that end at that vertex. Example: if edges $a \to c$ and $b \to c$ exist, the indegree of $c$ is 2.

Every node has degree 2, so with $n$ nodes the sum is $2n$.

Such a graph is a cycle of length 8.