CS-302 Discrete Structure - Nov 2022 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
   aShow that the relation 'R' defined by $(a, b)\ R\ (c, d)$ if $a + d = b + c$ is an equivalence relation.
   How to answer

   • Define reflexive, symmetric, and transitive properties of relations
   • Show reflexivity: $(a, b) R (a, b) \implies a + b = b + a$
   • Show symmetry: $(a, b) R (c, d) \implies a + d = b + c \implies c + b = d + a \implies (c, d) R (a, b)$
   • Show transitivity: $(a, b) R (c, d)$ and $(c, d) R (e, f) \implies a + d = b + c$ and $c + f = d + e$; add equations to get $a + f = b + e$
   • Conclude that R is an equivalence relation
2. 7 Marks
   bIf $X = \{1, 2, 3, 4\}$ and $R = \{(x, y) / x < y\}$. Draw the graph of 'R' and also give its matrix.
   How to answer

   • List the ordered pairs in $R$: $(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)$
   • Draw a directed graph (digraph) with 4 vertices labeled 1, 2, 3, 4 and directed edges corresponding to the ordered pairs
   • Construct the $4 \times 4$ Boolean relation matrix $M_R$ with entries $M_{ij} = 1$ if $(i,j) \in R$ else $0$
3. 7 Marks
   aProve that if R is an equivalence relation on a set A, show that $R^{-1}$ is also an equivalence relation on A.
   How to answer

   • Define inverse relation: $(b, a) \in R^{-1} \iff (a, b) \in R$
   • Reflexivity: For all $a \in A$, $(a, a) \in R \implies (a, a) \in R^{-1}$
   • Symmetry: $(a, b) \in R^{-1} \implies (b, a) \in R \implies (a, b) \in R \implies (b, a) \in R^{-1}$
   • Transitivity: $(a, b) \in R^{-1} \text{ and } (b, c) \in R^{-1} \implies (b, a) \in R \text{ and } (c, b) \in R \implies (c, a) \in R \implies (a, c) \in R^{-1}$
   • Conclude that $R^{-1}$ is an equivalence relation
4. 7 Marks
   bWhat is Mathematical induction? Use mathematical induction to prove that $1.1! + 2.2! + ... + n.n! = (n + 1)! - 1$, wherever n is a positive integer.
   How to answer

   • Define principle of mathematical induction (base step, induction hypothesis, inductive step)
   • Base step: verify for $n = 1$: $LHS = 1 \cdot 1! = 1$, $RHS = (1 + 1)! - 1 = 2 - 1 = 1$, true
   • Inductive hypothesis: assume true for $n = k$, i.e., $\sum_{i=1}^k i \cdot i! = (k + 1)! - 1$
   • Inductive step: evaluate for $n = k + 1$: $\sum_{i=1}^{k+1} i \cdot i! = (k+1)! - 1 + (k+1)(k+1)! = (k+1)!(1 + k + 1) - 1 = (k+2)! - 1$
   • Conclusion: true for all positive integers $n$
5. 7 Marks
   aFind the explicit formula for the Fibonacci numbers. Use $f_n = f_{n-1} + f_{n-2}$ as recursive condition and $f_0 = 0$ and $f_1 = 1$ as initial condition.
   How to answer

   • Write characteristic equation: $r^2 - r - 1 = 0$
   • Find characteristic roots: $r_1 = \frac{1+\sqrt{5}}{2}$, $r_2 = \frac{1-\sqrt{5}}{2}$
   • Write general solution: $f_n = c_1 r_1^n + c_2 r_2^n$
   • Apply initial conditions $f_0 = 0 \implies c_1 + c_2 = 0$ and $f_1 = 1 \implies c_1 r_1 + c_2 r_2 = 1$
   • Solve for constants: $c_1 = \frac{1}{\sqrt{5}}$, $c_2 = -\frac{1}{\sqrt{5}}$
   • State explicit formula: $f_n = \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n\right]$
6. 7 Marks
   bDraw the Hasse diagram representing the positive divisors of 36.
   How to answer

   • Find all divisors of 36: $D_{36} = \{1, 2, 3, 4, 6, 9, 12, 18, 36\}$
   • Determine the cover relations (immediate predecessors) for divisibility
   • Draw levels: Level 0: 1; Level 1: 2, 3; Level 2: 4, 6, 9; Level 3: 12, 18; Level 4: 36
   • Connect elements with directed upward edges according to cover relations
7. 7 Marks
   aProve that the set $G = \{0, 1, 2, 3, 4, 5, 6\}$ is a finite abelian group of order 7 with respect to multiplication modulo 7 as the composition in G.
   How to answer

   • Construct the Cayley table for $G = \{0, 1, 2, 3, 4, 5, 6\}$ under $\times_7$
   • Check Closure, Associativity, Identity element ($1$)
   • Check Inverse: Note that $0$ has no multiplicative inverse in $G$ (point out problem/conventional typo: $G$ without 0 for group under multiplication modulo 7, or addition modulo 7 for order 7)
   • Check Commutativity: $a \times_7 b = b \times_7 a$
   • Conclude status of group axioms based on standard interpretation
8. 7 Marks
   bState the Lagrange's Theorem with example. Also explain Permutation and Symmetric Group.
   How to answer

   • State Lagrange's Theorem: Order of any subgroup $H$ of a finite group $G$ divides the order of $G$ ($|G| = |H| \cdot [G : H]$)
   • Provide a concrete example of Lagrange's theorem (e.g., $G = \mathbb{Z}_6$, subgroup $H = \{0, 2, 4\}$)
   • Define Permutation of a set
   • Define Symmetric Group $S_n$ of degree $n$ and its order $n!$
9. 7 Marks
   aFind PDNF by constructing its PCNF of $(Q \lor P) \land (Q \lor R) \land (\sim (P \lor R) \lor \sim Q)$.
   How to answer

   • Simplify the given expression using logical equivalences and De Morgan's laws
   • Express into canonical product of sums (maxterms) by expanding missing variables to form PCNF
   • List all maxterm indices $M_i$
   • Obtain PDNF by taking the sum of remaining minterms $m_j$ not present in PCNF
10. 7 Marks
    bProve that for any three propositions P, Q, R the compound proposition $(P \to (Q \to R)) \to ((P \to Q) \to (P \to R))$ is a tautology by laws of logic.
    How to answer

    • Replace conditional operators using $A \to B \equiv \sim A \lor B$
    • Express antecedent: $P \to (Q \to R) \equiv \sim P \lor (\sim Q \lor R)$
    • Express consequent: $(P \to Q) \to (P \to R) \equiv \sim (\sim P \lor Q) \lor (\sim P \lor R) \equiv (P \land \sim Q) \lor \sim P \lor R$
    • Simplify the entire implication: $\sim [\text{antecedent}] \lor [\text{consequent}]$
    • Use associative, distributive, and complement laws to simplify the expression to $\mathbf{T}$ (True)
11. 7 Marks
    aExplain Tautologies, Contradiction and Contingencies with suitable examples.
    How to answer

    • Define Tautology: a compound proposition that is always true for all truth assignments; give example (e.g., $P \lor \sim P$)
    • Define Contradiction: a compound proposition that is always false for all truth assignments; give example (e.g., $P \land \sim P$)
    • Define Contingency: a proposition that is neither a tautology nor a contradiction; give example (e.g., $P \to Q$)
    • Provide corresponding truth tables illustrating each concept
12. 7 Marks
    bExplain the method of proving theorems by direct, indirect, contradiction and by cases.
    How to answer

    • Direct Proof: Assume hypothesis $P$ is true, show that conclusion $Q$ must be true, with a short example
    • Indirect Proof (Proof by Contraposition): Prove $P \to Q$ by proving $\sim Q \to \sim P$, with an example
    • Proof by Contradiction: Assume $P$ is true and $Q$ is false, derive a logical impossibility ($R \land \sim R$), with an example
    • Proof by Cases: Partition domain/condition into mutually exhaustive cases and prove the statement for each case
13. 7 Marks
    aGive a simple condition on the weights of a graph that will guarantee that there is a unique maximal spanning tree for the graph.
    How to answer

    • State the condition: all edge weights in the graph are distinct (all weights are strictly different)
    • Explain why this guarantees uniqueness using Kruskal's or Prim's algorithm logic (no ties at any selection step)
    • Show that any replacement of an edge in the maximal spanning tree would result in a strictly smaller total weight
    • Conclude that distinct edge weights ensure a unique maximal (and minimal) spanning tree
14. 7 Marks
    bDefine Isomorphism of graphs. What are the steps followed in discovering the Isomorphism?
    How to answer

    • Define graph isomorphism: A bijection $f: V_1 \to V_2$ such that $(u, v) \in E_1 \iff (f(u), f(v)) \in E_2$
    • Step 1: Check necessary conditions / invariants (same number of vertices, edges, degree sequence)
    • Step 2: Check preservation of subgraphs, cycle lengths, and connectivity
    • Step 3: Establish a candidate one-to-one correspondence between vertices preserving degrees
    • Step 4: Verify that adjacency/non-adjacency is preserved for all vertex pairs (or check adjacency matrices)
15. 7 Marks
    aExplain Eulerian and Hamiltonian graphs with examples, also draw the graphs of the following: i) Eulerian but not Hamiltonian ii) Hamiltonian but not Eulerian
    How to answer

    • Define Eulerian graph: contains a closed trail visiting every edge exactly once (Euler's theorem: all vertices have even degrees)
    • Define Hamiltonian graph: contains a closed cycle visiting every vertex exactly once
    • Provide and draw an example of an Eulerian graph that is not Hamiltonian (e.g., two triangles sharing a single cut-vertex / bow-tie graph)
    • Provide and draw an example of a Hamiltonian graph that is not Eulerian (e.g., cycle $C_4$ with a diagonal, or complete graph $K_4$ where all vertices have odd degree 3)
16. 7 Marks
    bProve that the sum of the degree of all the vertices in a graph G is equal to twice the number of edges in G.
    How to answer

    • State the Handshaking Theorem formula: $\sum_{v \in V} \deg(v) = 2|E|$
    • Explain that each edge contributes exactly 1 to the degree of each of its two endpoint vertices
    • If an edge is a loop, it contributes 2 to the degree of that single vertex
    • Summing the degrees over all vertices counts both ends of every edge exactly once
    • Therefore, the total degree sum must be $2 \times |E|$