Unit 1: Logic and Proofs — IT 235 Discrete Structure Study Notes

Pass path: Master truth tables, converse/contrapositive/inverse, De Morgan laws, and direct vs contradiction proofs. Top path: Construct formal proofs using inference rules (Modus Ponens, Resolution), handle nested quantifiers with negations, and pinpoint common fallacies (affirming the consequent, begging the question).

Part 1: Core Concepts (2 Marks)

★ Proposition: A declarative statement that is either true ( $T$ ) or false ( $F$ ), but not both. Example: $P: 2 + 3 = 5$ is a proposition; $x + 1 = 2$ is an open sentence, not a proposition until $x$ is bound.
★ Tautology and Contradiction: A compound proposition is a tautology if it evaluates to true for all truth assignments of its variables (e.g., $P \lor \neg P$ ). It is a contradiction if it is always false (e.g., $P \land \neg P$ ). A formula that is neither is a contingency.
★ Conditional Statement Equivalences: For implication $P \rightarrow Q$ :
- Converse: $Q \rightarrow P$
- Contrapositive: $\neg Q \rightarrow \neg P$ (logically equivalent to $P \rightarrow Q$ )
- Inverse: $\neg P \rightarrow \neg Q$ (equivalent to converse)

Part 2: Structural Frameworks (10 Marks)

1. Systematic Construction of Formal Proofs

When TU exam prompts ask to prove theorems (e.g., “Prove that $\sqrt{2}$ is irrational” or “If $3n + 2$ is odd, then $n$ is odd”):

Identify the Hypothesis and Conclusion: Explicitly state $P$ (given) and $Q$ (claim to establish).
Select Proof Technique:
- Direct Proof: Assume $P$ is true. Use algebra, definitions, and inference rules to deduce $Q$ .
- Proof by Contraposition: Assume $\neg Q$ is true. Prove that $\neg P$ must hold. Essential when $Q$ involves negation or division.
- Proof by Contradiction (Reductio ad Absurdum): Assume both $P$ and $\neg Q$ hold. Derive a logical impossibility (e.g., $R \land \neg R$ , or $1 = 0$ ). Conclude $\neg Q$ is false, hence $Q$ holds.
Formal Verification of Negations:
$\neg (\forall x P(x)) \equiv \exists x \neg P(x)$

$\neg (\exists x P(x)) \equiv \forall x \neg P(x)$
When negating nested quantifiers like $\forall x \exists y (x < y)$ , systematically flip quantifiers and negate the predicate: $\exists x \forall y (x \ge y)$ .
Conclusion Statement: Conclude with a rigorous statement: “Since assuming $\neg Q$ yields a contradiction, the original statement $P \rightarrow Q$ must be true. Q.E.D.”

Part 3: Distinction Tables

Logic and Proof Method Comparisons

Dimension	Propositional Logic	Predicate Logic
Atomic Unit	Complete declarative propositions ( $P, Q$ )	Predicates and arguments ( $P(x), Q(x, y)$ )
Quantification	Cannot express “all” or “some”	Supports universal ( $\forall$ ) and existential ( $\exists$ ) quantifiers
Expressive Power	Finite, truth-functional combinations	Infinite domains, relational assertions
Decidability	Strictly decidable via truth tables	Undecidable in first-order logic (Church-Turing)

Dimension	Proof by Contraposition	Proof by Contradiction
Target Implication	Specifically proves conditional $P \rightarrow Q$	Proves any proposition $S$ (conditional or direct)
Assumption	Assumes only $\neg Q$	Assumes $P \land \neg Q$ (or $\neg S$ )
Goal	Directly derive $\neg P$	Derive any impossible contradiction ( $R \land \neg R$ )
Structural Output	Direct chain: $\neg Q \Rightarrow \dots \Rightarrow \neg P$	Impossibility trap: $0 = 1$ or integer simultaneously even and odd

Part 4: Worked Problems & Exam Traps

Problem 1 (Standard): Contrapositive Proof

Prove that if $n$ is an integer and $3n + 2$ is odd, then $n$ is odd.

Step 1 (Setup): Implication is $P(n) \rightarrow Q(n)$ where $P(n): 3n + 2$ is odd, $Q(n): n$ is odd.
Step 2 (Contrapositive): Prove $\neg Q(n) \rightarrow \neg P(n)$ , i.e., “If $n$ is even, then $3n + 2$ is even.”
Step 3 (Proof): Assume $n$ is even. By definition of even integers, $n = 2k$ for some integer $k$ . Substitute $n$ :
$3n + 2 = 3(2k) + 2 = 6k + 2 = 2(3k + 1)$
Since $k$ is an integer, $m = 3k + 1$ is an integer. Thus, $3n + 2 = 2m$ , which is even by definition.
Step 4 (Conclusion): Because the contrapositive is true, the original conditional statement is true.

Problem 2 (TU Classic): Proof by Contradiction

Prove that $\sqrt{2}$ is irrational.

Step 1: Assume for contradiction that $\sqrt{2}$ is rational. Then $\sqrt{2} = \frac{a}{b}$ where $a, b \in \mathbb{Z}, b \neq 0$ , and $\gcd(a, b) = 1$ (fraction in irreducible lowest terms).
Step 2: Squaring both sides: $2 = \frac{a^2}{b^2} \implies a^2 = 2b^2$ .
Step 3: This means $a^2$ is even. Since the square of an odd number is odd, $a$ must be even. Thus, $a = 2k$ for some integer $k$ .
Step 4: Substitute $a = 2k$ into $a^2 = 2b^2$ :
$(2k)^2 = 2b^2 \implies 4k^2 = 2b^2 \implies b^2 = 2k^2$
This implies $b^2$ is even, so $b$ must also be even.
Step 5: If both $a$ and $b$ are even, they share a common factor of 2. This directly contradicts the assumption that $\gcd(a, b) = 1$ .
Step 6: Hence, the assumption is false; $\sqrt{2}$ is irrational.

Students lose marks here because they negate $P \rightarrow Q$ as $\neg P \rightarrow \neg Q$ instead of $P \land \neg Q$ . Remember that an implication is false only when the antecedent is true and the consequent is false. Students also forget to state that $\gcd(a, b) = 1$ when setting up rational fractions in contradiction proofs, invalidating the contradiction step.

Discrete Structure

Chapter notes

Unit 1: Logic and Proofs· 8 LHs· ~10 marks