Discrete Structure

Part 1: Core Concepts (2 Marks)

• Proposition: A declarative statement that is either definitively True ($T$) or False ($F$), but not both simultaneously.
• Tautology vs. Contradiction: A tautology is a compound proposition that evaluates to True for all possible truth values of its propositional variables (e.g., $p \lor \neg p$); a contradiction evaluates to False in every circumstance ($p \land \neg p$).
• Modus Ponens: A foundational rule of inference stating: If premise $p$ is true and implication $p \to q$ is true, then conclusion $q$ must be true:

  Swipe to see the full formula↔

  $$p, \quad p \to q \implies q$$
• Proof by Contradiction (Reductio ad Absurdum): A proof method where to prove proposition $p$, one assumes its negation $\neg p$ is true and derives a logical contradiction ($r \land \neg r$), proving $p$ must be true.

Part 2: Structural Frameworks (10 Marks)

Rules of Inference Matrix for Mathematical Proofs

Part 3: Distinction Tables

Part 4: Worked Problems & Exam Traps

Worked Proof: Irrationality of $\sqrt{2}$ by Contradiction

1. Assume the contrary: Suppose $\sqrt{2}$ is rational.

   Swipe to see the full formula↔

   $$\sqrt{2} = \frac{a}{b} \quad (a, b \in \mathbb{Z}, b \ne 0, \gcd(a, b) = 1)$$
2. Square both sides:

   Swipe to see the full formula↔

   $$2 = \frac{a^2}{b^2} \implies a^2 = 2b^2$$
3. Since $a^2$ is even, $a$ must be even. Let $a = 2k$.

   Swipe to see the full formula↔

   $$(2k)^2 = 2b^2 \implies 4k^2 = 2b^2 \implies b^2 = 2k^2$$
4. Since $b^2$ is even, $b$ must also be even.
5. Contradiction: Both $a$ and $b$ share a common factor of 2, contradicting $\gcd(a, b) = 1$.

   Swipe to see the full formula↔

   $$\therefore \sqrt{2} \text{ is irrational.}$$

TU Exam Trap: Do not confuse the converse ($q \to p$) or inverse ($\neg p \to \neg q$) with the contrapositive ($\neg q \to \neg p$). Only the contrapositive is logically equivalent to the original conditional statement $p \to q$.