CS-302 Discrete Structure - Jun 2024 Question Paper

Under each question, How to answer lists the points an answer should cover, outlined by CampusPrep from the syllabus. Check the details against your textbook.

1. 7 Marks
   aExplain the following: i) Euler Graph ii) Isomorphic graphs iii) Minimal spanning tree iv) Height of the tree
   How to answer

   • Euler graph: definition, condition on vertex degrees, example
   • Isomorphic graphs: definition of bijection preserving adjacency, invariants
   • Minimal spanning tree (MST): definition, connected weighted graph, algorithms mentioned
   • Height of a tree: definition as maximum depth / length of longest path from root to leaf
2. 7 Marks
   bLet $Z$ be the group of integers with binary operation $*$ defined by $a * b = a + b - 2$, for all $a, b \in Z$. Find the identity element of the group $\langle Z, * \rangle$.
   How to answer

   • State definition of identity element: $a * e = e * a = a$ for all $a \in Z$
   • Apply operation definition: $a + e - 2 = a$
   • Solve for $e$: $e - 2 = 0 \implies e = 2$
   • Verify left identity: $e * a = 2 + a - 2 = a$
3. 7 Marks
   aProve that the Complement of each element in a Boolean Algebra B is unique.
   How to answer

   • Define complement: $a \wedge a' = 0$ and $a \vee a' = 1$
   • Assume two complements $b_1$ and $b_2$ for element $a$
   • Write $b_1 = b_1 \wedge 1 = b_1 \wedge (a \vee b_2) = (b_1 \wedge a) \vee (b_1 \wedge b_2) = 0 \vee (b_1 \wedge b_2) = b_1 \wedge b_2$
   • Similarly show $b_2 = b_2 \wedge b_1 = b_1 \wedge b_2$
   • Conclude $b_1 = b_2$, proving uniqueness
4. 7 Marks
   bLet $A$ be any finite set and $P(A)$ be the power set of $A$. $\subseteq$ be the inclusion relation on the elements of $P(A)$. Draw the Hasse diagrams of $(P(A), \subseteq)$ for the following: i) $A = \{a\}$ ii) $A = \{a, b\}$ iii) $A = \{a, b, c\}$ iv) $A = \{a, b, c, d\}$
   How to answer

   • Identify elements of $P(A)$ for each case
   • Draw 2-element chain for $A=\{a\}$
   • Draw 4-element diamond/square lattice for $A=\{a,b\}$
   • Draw 8-element 3D cube lattice for $A=\{a,b,c\}$
   • Draw 16-element 4D hypercube/layered Hasse diagram for $A=\{a,b,c,d\}$
5. 7 Marks
   ai) Prove that $p \wedge q \implies q \vee p$ is a Tautology. ii) Show that $(p \vee q) \wedge (\sim p) \wedge (\sim q)$ is a contradiction.
   How to answer

   • For (i): Construct truth table for variables p, q showing $p \wedge q \implies q \vee p$ is True for all combinations (or use logical equivalence: $\sim(p \wedge q) \vee (q \vee p)$)
   • For (ii): Using De Morgan's laws, $(\sim p) \wedge (\sim q) = \sim(p \vee q)$
   • Hence $(p \vee q) \wedge \sim(p \vee q) = \mathbf{F}$ (Contradiction), or prove via 4-row truth table
6. 7 Marks
   bExplain complete digraph and Euler Graph using suitable example of both.
   How to answer

   • Complete digraph: definition (directed graph where every pair of distinct vertices has directed edges between them in both directions, or exactly one if asymmetric complete), sketch an example with $n=3$ or $4$
   • Euler graph: definition (contains an Eulerian circuit traversing every edge exactly once), necessary and sufficient conditions (in-degree = out-degree for directed, all even degrees for undirected), sketch an example
7. 7 Marks
   aDefine planar graph. Prove that for any connected planar graph, $v - e + r = 2$ Where $v, e, r$ is the number of vertices, edges, and regions of the graph respectively.
   How to answer

   • Definition of planar graph (can be embedded in the plane without edges crossing)
   • State Euler's formula: $v - e + r = 2$
   • Base case: Tree with $e = v - 1$ and $r = 1$, so $v - (v - 1) + 1 = 2$
   • Inductive step: Add an edge connecting two existing vertices, forming a new cycle/region, increasing $e$ by 1 and $r$ by 1, leaving $v - e + r$ unchanged
   • Conclude formula holds for all connected planar graphs
8. 7 Marks
   bProve that the relation R defined by "$a$ is congruent to $b$ modulo $m$" on the set of integers is an equivalence relation.
   How to answer

   • Define relation: $a \equiv b \pmod m \iff m \mid (a - b)$
   • Reflexive: $a - a = 0 = 0 \cdot m \implies a \equiv a \pmod m$
   • Symmetric: $a \equiv b \implies m \mid (a - b) \implies a - b = km \implies b - a = (-k)m \implies b \equiv a \pmod m$
   • Transitive: $a \equiv b$ and $b \equiv c \implies a - b = k_1 m, b - c = k_2 m \implies a - c = (k_1 + k_2)m \implies a \equiv c \pmod m$
   • Conclude relation is an equivalence relation
9. 7 Marks
   aProve that $5^{2n} - 1$ is divisible by 24, where $n$ is any positive integer.
   How to answer

   • Base step: For $n = 1$, $5^2 - 1 = 25 - 1 = 24$, which is divisible by 24
   • Inductive hypothesis: Assume $5^{2k} - 1 = 24m$ for some integer $m$
   • Inductive step: For $n = k + 1$, $5^{2(k+1)} - 1 = 5^{2k} \cdot 25 - 1 = 25(24m + 1) - 1 = 25 \cdot 24m + 24 = 24(25m + 1)$
   • Conclude by mathematical induction that $5^{2n} - 1$ is divisible by 24 for all $n \in \mathbb{Z}^+$
10. 7 Marks
    bDraw the Hasse diagram representing the positive divisors of 36 and 45.
    How to answer

    • List positive divisors of 36: $D_{36} = \{1, 2, 3, 4, 6, 9, 12, 18, 36\}$
    • Draw Hasse diagram for $D_{36}$ ordered by divisibility with 1 at bottom, intermediate levels, and 36 at top
    • List positive divisors of 45: $D_{45} = \{1, 3, 5, 9, 15, 45\}$
    • Draw Hasse diagram for $D_{45}$ ordered by divisibility (a 6-element lattice) with 1 at bottom and 45 at top
11. 7 Marks
    aShow that the relation 'R' defined by $(a, b) \text{ R } (c, d)$ iff $a + d = b + c$ is an equivalence relation.
    How to answer

    • Reflexive: $(a, b) \text{ R } (a, b)$ since $a + b = b + a$
    • Symmetric: If $(a, b) \text{ R } (c, d)$, then $a + d = b + c \implies c + b = d + a \implies (c, d) \text{ R } (a, b)$
    • Transitive: If $(a, b) \text{ R } (c, d)$ and $(c, d) \text{ R } (e, f)$, then $a + d = b + c$ and $c + f = d + e$. Adding gives $(a + d) + (c + f) = (b + c) + (d + e) \implies a + f = b + e \implies (a, b) \text{ R } (e, f)$
    • Conclude R is an equivalence relation
12. 7 Marks
    bExplain various Rules of Inference for Propositional Logic.
    How to answer

    • Define rule of inference in propositional logic
    • List and write symbolic forms for Modus Ponens ($p, p \implies q \vdash q$) and Modus Tollens ($\sim q, p \implies q \vdash \sim p$)
    • Hypothetical Syllogism ($p \implies q, q \implies r \vdash p \implies r$)
    • Disjunctive Syllogism ($p \vee q, \sim p \vdash q$)
    • Addition, Simplification, Conjunction, and Resolution
13. 7 Marks
    aShow that every Cyclic group is Abelian. Prove that a lattice with 5 elements is not a Boolean algebra.
    How to answer

    • Cyclic group is Abelian: Let $G = \langle a \rangle$. Any elements $x, y \in G$ can be written as $x = a^m, y = a^n$. Then $xy = a^m a^n = a^{m+n} = a^{n+m} = a^n a^m = yx$, hence Abelian
    • Lattice with 5 elements: A finite Boolean algebra must be isomorphic to a power set lattice $\mathcal{P}(S)$, so its cardinality must be $2^n$ for some integer $n \ge 0$
    • Since $5 \ne 2^n$ for any integer $n$, no 5-element lattice can be a Boolean algebra (or show by non-complementation / non-distributivity in $N_5$ and $M_5$)
14. 7 Marks
    bDefine Pigeon hole Principle. Write the contra positive of the implication: "if it is Sunday then it is a holiday."
    How to answer

    • State Pigeonhole Principle: If $k + 1$ or more objects are placed into $k$ boxes, then at least one box contains two or more objects
    • Identify components of implication $p \implies q$: $p$: "It is Sunday", $q$: "It is a holiday"
    • State definition of contrapositive: $\sim q \implies \sim p$
    • Write contrapositive: "If it is not a holiday, then it is not Sunday."
15. 7 Marks
    aProve that $G = \{0, 1, 2, 3, 4, 5, 6\}$ is an abelian group of order 7 with respect to addition modulo 7.
    How to answer

    • Construct the $7 \times 7$ Cayley addition table for $+_7$
    • Closure: All table entries belong to $G$
    • Associativity: Inherited from integer addition modulo 7
    • Identity element: 0 is the identity element since $a +_7 0 = a$
    • Inverse: Inverse of each element $a$ is $(7 - a) \pmod 7 \in G$
    • Commutativity: $a +_7 b = b +_7 a$ (symmetry across principal diagonal)
    • State order is $|G| = 7$
16. 7 Marks
    bProve or disprove that intersection of two normal subgroups of a group $G$ is again a normal subgroup of $G$. Define subgroup, normal subgroup, Quotient group, with an example for each.
    How to answer

    • Definitions with examples: Subgroup (subset forming group under induced operation), Normal subgroup ($gNg^{-1} = N$), Quotient group ($G/N = \{gN \mid g \in G\}$)
    • Proof of intersection normality: Let $H, K \triangleleft G$. Since $H, K$ are subgroups, $H \cap K$ is a subgroup
    • Let $x \in H \cap K$ and $g \in G$. Since $x \in H \triangleleft G$, $gxg^{-1} \in H$. Since $x \in K \triangleleft G$, $gxg^{-1} \in K$
    • Therefore $gxg^{-1} \in H \cap K$, proving $H \cap K \triangleleft G$