2022 question paper

Discrete Mathematics

29 questions

1. 1a. The statement (\sim P \leftrightarrow Q) \land \sim Q is true, when (i) P : True, Q : False (ii) P : True, Q : True (iii) P : False, Q : True (iv) P : False, Q : False20222m

   Module 3: Propositional Logic & Proof Techniques.

   The statement $(\sim P \leftrightarrow Q) \land \sim Q$ is true, when

   (i) $P$ : True, $Q$ : False
   (ii) $P$ : True, $Q$ : True
   (iii) $P$ : False, $Q$ : True
   (iv) $P$ : False, $Q$ : False

   View this question on its own page →

   CopySearch GoogleAsk AI
2. 1b. Which of the following statements regarding sets is false? (i) A \cap A = A (ii) A \cup A = A (iii) A - (B \cap C) = (A - B) \cup (A - C) (iv) (A \cup B)' = A' \cup B'20222m

   Module 1: Sets, Relation and Function.

   Which of the following statements regarding sets is false?

   (i) $A \cap A = A$
   (ii) $A \cup A = A$
   (iii) $A - (B \cap C) = (A - B) \cup (A - C)$
   (iv) $(A \cup B)' = A' \cup B'$

   View this question on its own page →

   CopySearch GoogleAsk AI
3. 1c. What is the induction hypothesis assumption for the inequality m! > 2^m where m \ge 4? (i) For m=k, k+1! > 2^k holds (ii) For m=k, k! > 2^k holds (iii) For m=k, k! > 3^k holds (iv) For m=k, k! > 2^{k+1} holds20222m

   Module 2: Mathematical Induction & Counting Techniques.

   What is the induction hypothesis assumption for the inequality $m! > 2^m$ where $m \ge 4$?

   (i) For $m=k$, $k+1! > 2^k$ holds
   (ii) For $m=k$, $k! > 2^k$ holds
   (iii) For $m=k$, $k! > 3^k$ holds
   (iv) For $m=k$, $k! > 2^{k+1}$ holds

   View this question on its own page →

   CopySearch GoogleAsk AI
4. 1d. A simple graph can have (i) multiple edges (ii) self-loops (iii) parallel edges (iv) no multiple edges, self-loops and parallel edges20222m

   Module 5: Graphs and Trees

   A simple graph can have
   (i) multiple edges
   (ii) self-loops
   (iii) parallel edges
   (iv) no multiple edges, self-loops and parallel edges

   View this question on its own page →

   CopySearch GoogleAsk AI
5. 1e. An undirected graph has 8 vertices labelled 1, 2, \dots, 8 and 31 edges. Vertices 1, 3, 5, 7 have degree 8 and vertices 2, 4, 6, 8 have degree 7. What is the degree of vertex 8? (i) 15 (ii) 8 (iii) 5 (iv) 2320222m

   Module 5: Graphs and Trees

   An undirected graph has 8 vertices labelled $1, 2, \dots, 8$ and 31 edges. Vertices $1, 3, 5, 7$ have degree 8 and vertices $2, 4, 6, 8$ have degree 7. What is the degree of vertex 8?

   (i) 15
   (ii) 8
   (iii) 5
   (iv) 23

   View this question on its own page →

   CopySearch GoogleAsk AI
6. 1f. A graph which has the same number of edges as its complement must have number of vertices congruent to \_\_\_\_\_\_ or \_\_\_\_\_\_ modulo 4 (for integral values of number of edges). (i) 6k, 6k-1 (ii) 4k, 4k+1 (iii) k, k+2 (iv) 2k+1, k20222m

   Module 5: Graphs and Trees

   A graph which has the same number of edges as its complement must have number of vertices congruent to ______ or ______ modulo 4 (for integral values of number of edges).

   (i) $6k, 6k-1$
   (ii) $4k, 4k+1$
   (iii) $k, k+2$
   (iv) $2k+1, k$

   View this question on its own page →

   CopySearch GoogleAsk AI
7. 1g. A graph which consists of disjoint union of trees is called (i) bipartite graph (ii) forest (iii) caterpillar tree (iv) labelled tree20222m

   Module 5: Graphs and Trees

   A graph which consists of disjoint union of trees is called
   (i) bipartite graph
   (ii) forest
   (iii) caterpillar tree
   (iv) labelled tree

   View this question on its own page →

   CopySearch GoogleAsk AI
8. 1h. Which of the following two sets are equal? (i) A = \{1, 2\} and B = \{1\} (ii) A = \{1, 2\} and B = \{1, 2, 3\} (iii) A = \{1, 2, 3\} and B = \{2, 1, 3\} (iv) A = \{1, 2, 4\} and B = \{1, 2, 3\}20222m

   Module 1: Sets, Relation and Function.

   Which of the following two sets are equal?

   (i) $A = \{1, 2\}$ and $B = \{1\}$
   (ii) $A = \{1, 2\}$ and $B = \{1, 2, 3\}$
   (iii) $A = \{1, 2, 3\}$ and $B = \{2, 1, 3\}$
   (iv) $A = \{1, 2, 4\}$ and $B = \{1, 2, 3\}$

   View this question on its own page →

   CopySearch GoogleAsk AI
9. 1i. If C_n is the nth cyclic graph, where n>3 and n is odd, determine the value of \chi(C_n). (i) 32572 (ii) 16631 (iii) 3 (iv) 31020222m

   Module 5: Graphs and Trees

   If $C_n$ is the $n$th cyclic graph, where $n>3$ and $n$ is odd, determine the value of $\chi(C_n)$.

   (i) 32572
   (ii) 16631
   (iii) 3
   (iv) 310

   View this question on its own page →

   CopySearch GoogleAsk AI
10. 1j. The number of edges in a regular graph of degree 46 and 8 vertices is (i) 347 (ii) 230 (iii) 184 (iv) 18620222m

    Module 5: Graphs and Trees

    The number of edges in a regular graph of degree 46 and 8 vertices is

    (i) 347
    (ii) 230
    (iii) 184
    (iv) 186

    View this question on its own page →

    CopySearch GoogleAsk AI
12. 2a. (a) Let D = \{-48, -14, -8, 0, 1, 3, 16, 23, 26, 32, 36\} Determine which of the following statements are true and which are false. Provide counterexamples for those statements that are false. (i) \forall x \in D, if x is odd, then x > 0 (ii) \forall x \in D, if x is less than 0, then x is even (iii) \forall x \in D, if x is even, then x \le 020226m

    Module 1: Sets, Relation and Function.

    (a) Let
    $D = \{-48, -14, -8, 0, 1, 3, 16, 23, 26, 32, 36\}$

    Determine which of the following statements are true and which are false. Provide counterexamples for those statements that are false.

    (i) $\forall x \in D$, if $x$ is odd, then $x > 0$
    (ii) $\forall x \in D$, if $x$ is less than 0, then $x$ is even
    (iii) $\forall x \in D$, if $x$ is even, then $x \le 0$

    View this question on its own page →

    CopySearch GoogleAsk AI
13. 2b. (b) Indicate which of the following statements are true and which are false. Justify your answers as best you can: (i) \forall x \in \mathbf{Z}^+, \exists y \in \mathbf{Z}^+ such that x = y+1 (ii) \forall x \in \mathbf{Z}, \exists y \in \mathbf{Z} such that x = y+1 (iii) \exists x \in \mathbf{R} such that \forall y \in \mathbf{R}, x = y+1 (iv) \forall x \in \mathbf{R}^+, \exists y \in \mathbf{R}^+ such that xy = 1 (v) \forall x \in \mathbf{R}, \exists y \in \mathbf{R} such that xy = 1 (vi) \forall x \in \mathbf{Z}^+ \text{ and } \forall y \in \mathbf{Z}^+, \exists z \in \mathbf{Z}^+ \text{ such that } z = x-y (vii) \forall x \in \mathbf{Z} \text{ and } \forall y \in \mathbf{Z}, \exists z \in \mathbf{Z} \text{ such that } z = x-y (viii) \exists u \in \mathbf{R}^+ \text{ such that } \forall v \in \mathbf{R}^+, uv < v20228m

    Module 1: Sets, Relation and Function.

    (b) Indicate which of the following statements are true and which are false. Justify your answers as best you can:

    (i) $\forall x \in \mathbf{Z}^+, \exists y \in \mathbf{Z}^+$ such that $x = y+1$
    (ii) $\forall x \in \mathbf{Z}, \exists y \in \mathbf{Z}$ such that $x = y+1$
    (iii) $\exists x \in \mathbf{R}$ such that $\forall y \in \mathbf{R}, x = y+1$
    (iv) $\forall x \in \mathbf{R}^+, \exists y \in \mathbf{R}^+$ such that $xy = 1$
    (v) $\forall x \in \mathbf{R}, \exists y \in \mathbf{R}$ such that $xy = 1$
    (vi) $\forall x \in \mathbf{Z}^+ \text{ and } \forall y \in \mathbf{Z}^+, \exists z \in \mathbf{Z}^+ \text{ such that } z = x-y$
    (vii) $\forall x \in \mathbf{Z} \text{ and } \forall y \in \mathbf{Z}, \exists z \in \mathbf{Z} \text{ such that } z = x-y$
    (viii) $\exists u \in \mathbf{R}^+ \text{ such that } \forall v \in \mathbf{R}^+, uv < v$

    View this question on its own page →

    CopySearch GoogleAsk AI
14. 3a. (a) Prove the following: (i) There is a real number x such that x > 1 and 2^x > x^{10}. (ii) There is an integer n such that 2n^2 - 5n + 2 is prime.202210m

    Module 3: Propositional Logic & Proof Techniques.

    (a) Prove the following:

    (i) There is a real number $x$ such that $x > 1$ and $2^x > x^{10}$.
    (ii) There is an integer $n$ such that $2n^2 - 5n + 2$ is prime.

    View this question on its own page →

    CopySearch GoogleAsk AI
15. 3b. Disprove that for all real numbers a and b, if a < b, then a^2 < b^2.20224m

    Module 3: Propositional Logic & Proof Techniques.

    Disprove that for all real numbers $a$ and $b$, if $a < b$, then $a^2 < b^2$.

    View this question on its own page →

    CopySearch GoogleAsk AI
16. 4a. (a) Show that p \lor (q \land r) and (p \lor q) \land (p \lor r) are logically equivalent. This is the distributive law of disjunction over conjunction.20225m

    Module 3: Propositional Logic & Proof Techniques.

    (a) Show that $p \lor (q \land r)$ and $(p \lor q) \land (p \lor r)$ are logically equivalent. This is the distributive law of disjunction over conjunction.

    View this question on its own page →

    CopySearch GoogleAsk AI
17. 4b. Find the greatest common divisor of 414 and 662 using the Euclidean algorithm.20224m

    Module 2: Mathematical Induction & Counting Techniques.

    Find the greatest common divisor of 414 and 662 using the Euclidean algorithm.

    View this question on its own page →

    CopySearch GoogleAsk AI
18. 4c. If a and b are positive integers, then prove that there exists integers s and t such that \text{gcd}(a, b) = sa + tb.20225m

    Module 2: Mathematical Induction & Counting Techniques.

    If $a$ and $b$ are positive integers, then prove that there exists integers $s$ and $t$ such that $\text{gcd}(a, b) = sa + tb$.

    View this question on its own page →

    CopySearch GoogleAsk AI
19. 5a. Use mathematical induction to prove this formula for the sum of a finite number of terms of a geometric progression with initial term a and common ratio r: \sum_{j=0}^{n} ar^j = a + ar + ar^2 + \dots + ar^n = \frac{ar^{n+1} - a}{r-1} when $r e 1 where n$ is a non-negative integer.20227m

    Module 2: Mathematical Induction & Counting Techniques.

    Use mathematical induction to prove this formula for the sum of a finite number of terms of a geometric progression with initial term $a$ and common ratio $r$:
    $$\sum_{j=0}^{n} ar^j = a + ar + ar^2 + \dots + ar^n = \frac{ar^{n+1} - a}{r-1}$$
    when $r
    e 1$where$n$ is a non-negative integer.

    View this question on its own page →

    CopySearch GoogleAsk AI
20. 5b. Write short notes on the following: (i) Forward proof (ii) Disjunctive and conjunctive normal form (iii) Fundamental theorem of arithmetic This question covers topics from different modules: * (i) Forward proof: This falls under Module 3: Propositional Logic & Proof Techniques. * (ii) Disjunctive and conjunctive normal form: This also falls under Module 3: Propositional Logic & Proof Techniques, as these are concepts in propositional logic. * (iii) Fundamental theorem of arithmetic: This is a concept from number theory, which is typically covered in Module 2: Mathematical Induction & Counting Techniques (as number theory is often grouped with induction and counting in discrete mathematics courses).20227m

    Module 3: Propositional Logic & Proof Techniques.

    Write short notes on the following:

    (i) Forward proof
    (ii) Disjunctive and conjunctive normal form
    (iii) Fundamental theorem of arithmetic

    This question covers topics from different modules:

    • (i) Forward proof: This falls under Module 3: Propositional Logic & Proof Techniques.
    • (ii) Disjunctive and conjunctive normal form: This also falls under Module 3: Propositional Logic & Proof Techniques, as these are concepts in propositional logic.
    • (iii) Fundamental theorem of arithmetic: This is a concept from number theory, which is typically covered in Module 2: Mathematical Induction & Counting Techniques (as number theory is often grouped with induction and counting in discrete mathematics courses).

    View this question on its own page →

    CopySearch GoogleAsk AI
21. 6a. An odd number of people stand in a yard at mutually distinct distances. At the same time each person throws a pie at their nearest neighbour, hitting this person. Use mathematical induction to show that there is at least one survivor, that is, at least one person who is not hit by a pie.20227m

    Module 2: Mathematical Induction & Counting Techniques.

    An odd number of people stand in a yard at mutually distinct distances. At the same time each person throws a pie at their nearest neighbour, hitting this person. Use mathematical induction to show that there is at least one survivor, that is, at least one person who is not hit by a pie.

    View this question on its own page →

    CopySearch GoogleAsk AI
23. 6b. Prove Bernoulli's inequality that if h > -1, then 1+nh \le (1+h)^n for all non-negative integers n.20227m

    Module 2: Mathematical Induction & Counting Techniques.

    Prove Bernoulli's inequality that if $h > -1$, then $1+nh \le (1+h)^n$ for all non-negative integers $n$.

    View this question on its own page →

    CopySearch GoogleAsk AI
24. 7a. What is pigeonhole principle? Using it, prove the following: (a) During a month with 30 days, a baseball team plays at least one game a day, but no more than 45 games. Show that there must be a period of some number of consecutive days during which the team must play exactly 14 games.20227m

    Module 2: Mathematical Induction & Counting Techniques.

    What is pigeonhole principle? Using it, prove the following:

    (a) During a month with 30 days, a baseball team plays at least one game a day, but no more than 45 games. Show that there must be a period of some number of consecutive days during which the team must play exactly 14 games.

    View this question on its own page →

    CopySearch GoogleAsk AI
25. 7b. The sequence 8, 11, 9, 1, 4, 6, 12, 10, 5, 7 contains 10 terms. Note that 10 = 3^2 + 1. There are four strictly increasing subsequences of length four, namely, 1, 4, 6, 12; 1, 4, 6, 7; 1, 4, 6, 10; and 1, 4, 5, 7. There is also a strictly decreasing subsequence of length four, namely, 11, 9, 6, 5.20227m

    Module 2: Mathematical Induction & Counting Techniques.

    The sequence $8, 11, 9, 1, 4, 6, 12, 10, 5, 7$ contains 10 terms. Note that $10 = 3^2 + 1$. There are four strictly increasing subsequences of length four, namely, $1, 4, 6, 12$; $1, 4, 6, 7$; $1, 4, 6, 10$; and $1, 4, 5, 7$. There is also a strictly decreasing subsequence of length four, namely, $11, 9, 6, 5$.

    View this question on its own page →

    CopySearch GoogleAsk AI
26. 8a. In a Round-Robin tournament, the Tigers beat the Blue Jays, the Tigers beat the Cardinals, the Tigers beat the Orioles, the Blue Jays beat the Cardinals, the Blue Jays beat the Orioles and the Cardinals beat the Orioles. Model this outcome with a directed graph.20223m

    Module 5: Graphs and Trees

    In a Round-Robin tournament, the Tigers beat the Blue Jays, the Tigers beat the Cardinals, the Tigers beat the Orioles, the Blue Jays beat the Cardinals, the Blue Jays beat the Orioles and the Cardinals beat the Orioles. Model this outcome with a directed graph.

    View this question on its own page →

    CopySearch GoogleAsk AI
27. 8b. Let G=(V, E) be a simple graph. Let R be the relation on V consisting of pairs of vertices (u,v) such that there is a path from u to v or such that u=v. Show that R is an equivalence relation.20223m

    Module 1: Sets, Relation and Function.

    Let $G=(V, E)$ be a simple graph. Let $R$ be the relation on $V$ consisting of pairs of vertices $(u,v)$ such that there is a path from $u$ to $v$ or such that $u=v$. Show that $R$ is an equivalence relation.

    View this question on its own page →

    CopySearch GoogleAsk AI
28. 8c. Determine whether the following given pair of directed graphs, shown in Fig. 1 and Fig. 2, are isomorphic or not. Exhibit an isomorphism or provide a rigorous argument that none exists.20228m

    Module 5: Graphs and Trees

    Determine whether the following given pair of directed graphs, shown in Fig. 1 and Fig. 2, are isomorphic or not. Exhibit an isomorphism or provide a rigorous argument that none exists.

    View this question on its own page →

    CopySearch GoogleAsk AI
29. 9a. Use pseudocode to describe an algorithm for determining the value of a game tree when both players follow a minimax strategy.20224m

    Module 5: Graphs and Trees

    Use pseudocode to describe an algorithm for determining the value of a game tree when both players follow a minimax strategy.

    View this question on its own page →

    CopySearch GoogleAsk AI
30. 9b. Suppose that T_1 and T_2 are spanning trees of a simple graph G. Moreover, suppose that e_1 is an edge in T_1 that is not in T_2. Show that there is an edge e_2 in T_2 that is not in T_1 such that T_1 remains a spanning tree if e_1 is removed from it and e_2 is added to it, and T_2 remains a spanning tree if e_2 is removed from it and e_1 is added to it.20225m

    Module 5: Graphs and Trees

    Suppose that $T_1$ and $T_2$ are spanning trees of a simple graph $G$. Moreover, suppose that $e_1$ is an edge in $T_1$ that is not in $T_2$. Show that there is an edge $e_2$ in $T_2$ that is not in $T_1$ such that $T_1$ remains a spanning tree if $e_1$ is removed from it and $e_2$ is added to it, and $T_2$ remains a spanning tree if $e_2$ is removed from it and $e_1$ is added to it.

    View this question on its own page →

    CopySearch GoogleAsk AI
31. 9c. Show that a degree-constrained spanning tree of a simple graph in which each vertex has degree not exceeding 2 consists of a single Hamiltonian path in the graph.20225m

    Module 5: Graphs and Trees

    Show that a degree-constrained spanning tree of a simple graph in which each vertex has degree not exceeding 2 consists of a single Hamiltonian path in the graph.

    View this question on its own page →

    CopySearch GoogleAsk AI