BIT152 · TU past paper
Discrete Structure 2078 question paper
The complete TU 2078 exam paper for Discrete Structure (BIT152), all 12 questions with solved model answers written to the mark scheme.
Tap a question to open its answer.
- 110 marksDirect proofHideAnswer
Explain direct proof, indirect proof, and proof by contradiction. Use direct proof to show that 'If n is an odd integer, then n' is an odd integer'. Also use indirect proof to show that 'If n is an integer and n' then n is odd'.[10]
Proof Methods: Direct Proof, Indirect Proof, and Proof by Contradiction
A. Definitions of Proof Methods
i. Direct Proof
A direct proof is a method in which we assume the hypothesis p is true and then use logical steps, definitions, axioms, and previously proven theorems to directly establish that the conclusion q is true.
Structure:
Assume p → logical reasoning → conclude qWe move in a straight forward path from hypothesis to conclusion.
ii. Indirect Proof (Proof by Contrapositive)
An indirect proof proves a statement p → q by instead proving its contrapositive, which is:
$$\neg q \rightarrow \neg p$$
Since p → q is logically equivalent to ¬q → ¬p, proving the contrapositive is sufficient to prove the original statement.
Structure:
Assume ¬q → logical reasoning → conclude ¬p
iii. Proof by Contradiction
In proof by contradiction (also called Reductio ad Absurdum), we assume the negation of the entire statement we want to prove, i.e., we assume p ∧ ¬q, and then show that this assumption leads to a logical contradiction.
Structure:
Assume p ∧ ¬q → derive a contradiction → conclude p → q must be true
B. Direct Proof: "If n is an odd integer, then n² is an odd integer"
Statement: If n is odd, then n² is odd.
Proof:
Step 1: Assume n is an odd integer.
Step 2: By the definition of an odd integer: $$n = 2k + 1 \quad \text{for some integer } k$$
Step 3: Compute n²: $$n^2 = (2k + 1)^2 = 4k^2 + 4k + 1$$
Step 4: Factor out 2: $$n^2 = 2(2k^2 + 2k) + 1$$
Step 5: Let m = 2k² + 2k. Since k is an integer, m is also an integer.
Step 6: Therefore: $$n^2 = 2m + 1$$
This is exactly the form of an odd integer (an integer of the form 2m + 1).
Conclusion: Therefore, if n is an odd integer, then n² is an odd integer. $\blacksquare$
C. Indirect Proof: "If n is an integer and n² is odd, then n is odd"
Statement: If n² is odd, then n is odd.
Proof (by Contrapositive):
Step 1: Write the contrapositive of the statement:
Original: If n² is odd, then n is odd.
Contrapositive: If n is not odd (i.e., n is even), then n² is not odd (i.e., n² is even).
Step 2: Assume n is even.
Step 3: By the definition of an even integer: $$n = 2k \quad \text{for some integer } k$$
Step 4: Compute n²: $$n^2 = (2k)^2 = 4k^2 = 2(2k^2)$$
Step 5: Let m = 2k². Since k is an integer, m is also an integer.
Step 6: Therefore: $$n^2 = 2m$$
This is exactly the form of an even integer.
Step 7: So n² is even, which means n² is not odd.
Conclusion: The contrapositive is proven. Since p → q ≡ ¬q → ¬p, the original statement "If n² is odd, then n is odd" is also true. $\blacksquare$
D. Summary Table
Method What We Assume What We Show Basis Direct Proof p is true q is true p → q directly Indirect Proof ¬q is true ¬p is true ¬q → ¬p (contrapositive) Proof by Contradiction p ∧ ¬q is true A contradiction arises Negation leads to absurdity - 210 marksNumericalLinear nonhomogeneous recurrence relationsHideAnswer
What is linear nonhomogeneous recurrence relation of degree k with constant coefficients? Find all the solutions of the recurrence relation a, 4a+n. Also find the solution of the relation with initial condition a, 1.[10]
- Recurrence (interpreted): $an = 4a{n-1} + n$ - Initial condition: $a1 = 1$ Note: the question text is garbled ("a, 4a+n" and "a, 1"). The standard textbook reading is $an = 4a{n-1} + n$ with $a1 = 1$, which is used here. --- A linear n...
- 310 marksNumericalMinimum spanning treesHideAnswer
Define spanning tree and minimum spanning tree with suitable example. Use Kruskal's algorithms to find minimum spanning tree in the given graph[10]
The question refers to "the given graph," but no graph (vertices, edges and weights) is reproduced with the question text available here. The working below therefore uses the standard 9-vertex textbook MST example so that the method is d...
- 45 marksTautology and contradictionHideAnswer
What is tautology? Show $(p \land q) \rightarrow (p \lor q)$ is a tautology. [5]
A tautology is a propositional formula (compound statement) that is always true regardless of the truth values assigned to its component variables. In other words, every row of its truth table yields True (T). --- We need to evaluate (p ...
- 55 marksNumericalCartesian productHideAnswer
Define cartesian product. Find A3 for the set A = (a, b, c). [5]
- Set $A = {a, b, c}$, so $A = 3$ - Required: definition of Cartesian product, and $A^3$ --- The Cartesian product of two sets $A$ and $B$, denoted $A \times B$, is the set of all ordered pairs $(a, b)$ such that $a \in A$ and
- 65 marksNumericalRelation matricesHideAnswer
How can you represent relations using matrices? Suppose that $A = {1, 2, 3}$ and $B = {1, 2}$. Let $R$ be the relation from $A$ to $B$ containing $(a, b)$ if $a \in A$, $b \in B$, and $a > b$. What matrix representing $R$ if $a_1 = 1$, $a_2 = 2$, $a_3 = 3$, and $b_1 = 1$ and $b_2 = 2$? [5]
A relation $R$ from a set $A$ (with $m$ elements) to a set $B$ (with $n$ elements) can be represented by an $m \times n$ zero-one (Boolean) matrix $MR = [m{ij}]$, where: $$m{ij} = \begin{cases} 1 & \text{if } (ai, bj) \in R \ 0 & \text{...
- 75 marksMathematical inductionHideAnswer
Use mathematical induction to show that the sum of first n positive integers is n(n+1)/2. [5]
$$P(n): 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$$ for all positive integers $n \geq 1$. --- Left Hand Side (LHS): $$1$$ Right Hand Side (RHS): $$\frac{1(1+1)}{2} = \frac{1 \times 2}{2} = 1$$ Since LHS = RHS = 1, the statement P(1) is t...
- 85 marksNumericalCongruence moduloHideAnswer
What is congruent modulo? Determine whether 20 is congruent to 8 modulo 6 and 25 is congruent to 17 modulo 5. [5]
- Check 1: Is $20 \equiv 8 \pmod{6}$? - Check 2: Is $25 \equiv 17 \pmod{5}$? All values present; no missing data. Two integers $a$ and $b$ are congruent modulo $n$ (written $a \equiv b \pmod{n}$) if $n$ divides their difference: $$a \equ...
- 95 marksNumericalPrime numbers and trial divisionHideAnswer
Explain trial division with example? Using trial division, show that 101 is prime. [5]
- Number to test: $n = 101$ - Method required: trial division - Marks: 5 Trial division is a primality-testing method. To determine whether an integer $n 1$ is prime, we attempt to divide $n$ by successive integers starting from $2$. If ...
- 105 marksNumericalProduct ruleHideAnswer
Explain product rule. How many strings are there of four lowercase letters that have the letter x in them? [5]
- String length: 4 characters - Alphabet: 26 lowercase letters - Condition: the letter 'x' must appear at least once The Product Rule (Multiplication Principle) states: If a procedure consists of a sequence of $k$ tasks, where task 1 can...
- 115 marksGraph definition and typesHideAnswer
What is graph? Explain simple graph and pseudograph with example. [5]
A graph G is a mathematical structure consisting of a non-empty set of vertices (nodes) V and a set of edges E, where each edge connects two vertices. Formally: G = (V, E) - V = {v₁, v₂, v₃, ...} → set of vertices - E = {e₁, e₂, e₃, ...}...
- 125 marksEuler paths and circuitsHideAnswer
What is Euler path? Compare it with Hamilton path. [5]
An Euler path (also called an Eulerian path) is a path in a graph that visits every edge exactly once. If such a path starts and ends at the same vertex, it is called an Euler circuit (or Eulerian circuit). - A connected graph has an Eul...