Unit 1: Logic and Proofs

1. Propositional Logic

Logic is the foundational framework for rigorous mathematical reasoning, formal verification in computer science, and algorithmic design.

1.1 Propositions and Truth Values

A proposition is a declarative statement (a sentence that declares a fact) that is either strictly true ($T$ or $1$) or strictly false ($F$ or $0$), but not both simultaneously.

• Examples of Propositions:
  • "$\pi > 3$" (True)
  • "$2 + 2 = 5$" (False)
  • "LPU is a university in Punjab" (True)
• Non-Propositions:
  • "$x + 2 = 7$" (Contains a free variable; neither true nor false until $x$ is specified)
  • "Read this textbook carefully." (Imperative command)
  • "Is discrete mathematics difficult?" (Interrogative question)

1.2 Fundamental Logical Connectives and Truth Tables

Complex statements are constructed from atomic propositions using logical operators (connectives).

Master Truth Table

1.3 Conditional Statement Variants: Converse, Contrapositive, and Inverse

Given an implication $p \to q$ (where $p$ is the hypothesis/antecedent and $q$ is the conclusion/consequent):

[!IMPORTANT]
A conditional statement is always logically equivalent to its contrapositive, but is never guaranteed to be equivalent to its converse or inverse. Confusing an implication with its converse is a common logical fallacy.

2. Propositional Equivalences

2.1 Classification of Compound Propositions

• Tautology: A compound proposition that is always true for every possible truth assignment of its propositional variables (e.g., $p \lor \neg p$, $p \to p$).
• Contradiction: A compound proposition that is always false for every possible truth assignment (e.g., $p \land \neg p$).
• Contingency: A proposition that is neither a tautology nor a contradiction (its truth value depends on variable assignments).

2.2 Logical Equivalence ($\equiv$ or $\Longleftrightarrow$)

Two compound propositions $A$ and $B$ are logically equivalent, denoted $A \equiv B$, if $A \leftrightarrow B$ is a tautology. That is, $A$ and $B$ have identical truth values under every truth assignment.

2.3 Fundamental Laws of Logical Equivalences

Essential Conditional Equivalences:

1. $p \to q \equiv \neg p \lor q$ (Material Implication)
2. $p \to q \equiv \neg q \to \neg p$ (Contrapositive Equivalence)
3. $\neg(p \to q) \equiv p \land \neg q$ (Negation of Implication)
4. $p \leftrightarrow q \equiv (p \to q) \land (q \to p) \equiv (\neg p \lor q) \land (\neg q \lor p) \equiv (p \land q) \lor (\neg p \land \neg q)$

3. Predicates and Quantifiers

Propositional logic cannot express assertions about individual objects or categories (e.g., "Every prime number greater than 2 is odd"). First-order predicate logic extends propositional logic by introducing variables, predicates, and quantifiers.

3.1 Predicates and Truth Sets

• A predicate $P(x)$ is a statement containing a variable $x$. Once a specific value $a$ from the domain of discourse (universe of discourse $U$) is assigned to $x$, $P(a)$ becomes a proposition with a definite truth value.
• The truth set of $P(x)$ is the set of all elements $a \in U$ for which $P(a)$ is true:
  $\{ a \in U \mid P(a) \text{ is true} \}$

3.2 Quantifiers

3.3 Negation of Quantified Statements (Generalized De Morgan's Laws)

To negate a quantified statement, toggle the quantifier and negate the predicate:
$\neg \forall x P(x) \equiv \exists x \neg P(x)$
$\neg \exists x P(x) \equiv \forall x \neg P(x)$

3.4 Nested Quantifiers and Order Dependence

When multiple quantifiers are applied to a multi-variable predicate $Q(x, y)$:

• Commutativity of Identical Quantifiers:
  $\forall x \forall y Q(x, y) \equiv \forall y \forall x Q(x, y)$
  $\exists x \exists y Q(x, y) \equiv \exists y \exists x Q(x, y)$
• Non-Commutativity of Mixed Quantifiers:
  $\forall x \exists y Q(x, y) \not\equiv \exists y \forall x Q(x, y)$
  • $\forall x \exists y Q(x, y)$: For every $x$, there exists a $y$ (which may depend on $x$) such that $Q(x, y)$ holds.
  • $\exists y \forall x Q(x, y)$: There exists a single universal $y$ that simultaneously works for all $x$.
  • The second statement is strictly stronger: $\exists y \forall x Q(x, y) \implies \forall x \exists y Q(x, y)$, but the converse does not hold.

4. Rules of Inference

An argument is a sequence of statements ending in a conclusion. An argument is valid if the truth of all its premises guarantees the truth of its conclusion:
$(p_1 \land p_2 \land \dots \land p_k) \to q \text{ is a tautology}$

4.1 Common Fallacies (Invalid Reasoning)

1. Fallacy of Affirming the Conclusion:
   • Premises: $p \to q$ and $q$. Conclusion: $\therefore p$.
   • Invalid because $[(p \to q) \land q] \to p$ is a contingency, not a tautology.
2. Fallacy of Denying the Hypothesis:
   • Premises: $p \to q$ and $\neg p$. Conclusion: $\therefore \neg q$.
   • Invalid because $[(p \to q) \land \neg p] \to \neg q$ is a contingency.

5. Methods of Mathematical Proof

A proof is a valid mathematical argument that establishes the absolute truth of a statement.

5.1 Proof Terminology

• Axiom (Postulate): A statement assumed to be true without proof.
• Theorem: A mathematical statement that has been proven true.
• Proposition: A less significant or standalone mathematical statement.
• Lemma: A stepping-stone theorem proved primarily to assist in proving a broader theorem.
• Corollary: A theorem that follows directly from another theorem with minimal additional proof.
• Conjecture: A statement proposed to be true, but not yet verified or disproved.

5.2 Direct Proof

To prove a conditional statement $p \to q$ directly:

1. Assume the hypothesis $p$ is true.
2. Use definitions, axioms, previously established theorems, and valid rules of inference.
3. Deduce that the conclusion $q$ must be true.

Example:

Theorem: If $n$ is an odd integer, then $n^2$ is an odd integer.

• Proof:
  1. Let $n$ be an arbitrary odd integer.
  2. By definition of an odd integer, $n = 2k + 1$ for some integer $k \in \mathbb{Z}$.
  3. Compute $n^2$:
     $n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$
  4. Since $k$ is an integer, $m = 2k^2 + 2k$ is also an integer.
  5. Thus $n^2 = 2m + 1$, which by definition means $n^2$ is odd. $\blacksquare$

5.3 Proof by Contraposition (Indirect Proof)

Since $p \to q \equiv \neg q \to \neg p$, proving the contrapositive establishes the original implication:

1. Assume the negation of the conclusion: $\neg q$ is true.
2. Deduce through direct argument that the negation of the hypothesis: $\neg p$ is true.

Example:

Theorem: If $3n + 2$ is odd, then $n$ is odd (for integer $n$).

• Proof by Contraposition:
  1. The contrapositive statement is: "If $n$ is even, then $3n + 2$ is even."
  2. Assume $n$ is even. By definition, $n = 2k$ for some integer $k$.
  3. Substitute $n = 2k$ into $3n + 2$:
     $3n + 2 = 3(2k) + 2 = 6k + 2 = 2(3k + 1)$
  4. Let $m = 3k + 1$, which is an integer. Then $3n + 2 = 2m$, which is even.
  5. Since the contrapositive is true, the original theorem is true. $\blacksquare$

5.4 Proof by Contradiction (Reductio ad Absurdum)

To prove a proposition $p$:

1. Assume the negation $\neg p$ is true.
2. Deduce an impossible logical absurdity or contradiction: $r \land \neg r$ (a statement that is both true and false simultaneously).
3. Conclude that $\neg p$ must be false, which proves $p$ is true.

Classic Example: Irrationality of $\sqrt{2}$

Theorem: $\sqrt{2}$ is an irrational number.

• Proof:
  1. Assume for contradiction that $\sqrt{2}$ is rational.
  2. Then $\sqrt{2} = \frac{a}{b}$, where $a, b \in \mathbb{Z}^+$ have no common positive factors other than 1 ($\gcd(a, b) = 1$, i.e., the fraction is in lowest terms).
  3. Squaring both sides: $2 = \frac{a^2}{b^2} \implies a^2 = 2b^2$.
  4. This implies $a^2$ is even, which guarantees $a$ is even (as proved in Section 5.3).
  5. Since $a$ is even, write $a = 2k$ for some integer $k$.
  6. Substitute $a = 2k$ into $a^2 = 2b^2$:
     $(2k)^2 = 2b^2 \implies 4k^2 = 2b^2 \implies b^2 = 2k^2$
  7. This implies $b^2$ is even, which guarantees $b$ is even.
  8. Therefore, both $a$ and $b$ are even, meaning 2 divides both $a$ and $b$.
  9. This contradicts the initial premise that $\gcd(a, b) = 1$.
  10. Hence, the assumption that $\sqrt{2}$ is rational is false; $\sqrt{2}$ must be irrational. $\blacksquare$

5.5 Vacuous and Trivial Proofs

• Vacuous Proof: If hypothesis $p$ in $p \to q$ is demonstrably false, the conditional statement $p \to q$ is automatically true regardless of $q$.
  • Example: "If $0 > 1$, then discrete mathematics is trivial." True because $0 > 1$ is false.
• Trivial Proof: If conclusion $q$ in $p \to q$ is demonstrably true on its own, then $p \to q$ is automatically true regardless of $p$.
  • Example: "If $n$ is an integer, then $n^2 + 1 \geq 0$." True because $n^2 + 1 \geq 1 > 0$ for all real $n$.

5.6 Proof of Equivalence (Biconditional Proofs)

To prove a biconditional statement $p \leftrightarrow q$:
Prove both directions separately:

1. $p \implies q$ (forward direction).
2. $q \implies p$ (backward direction).

For a circular chain of equivalences $p_1 \leftrightarrow p_2 \leftrightarrow \dots \leftrightarrow p_n$:
Prove the cyclic chain of implications:
$p_1 \implies p_2 \implies p_3 \implies \dots \implies p_n \implies p_1$

5.7 Counterexamples

To disprove a universally quantified assertion $\forall x P(x)$, it suffices to find a single instance $c$ in the domain of discourse $U$ such that $P(c)$ is false. Such an instance is called a counterexample.

• Assertion: "Every odd number is a prime number."
  • Counterexample: Let $n = 9$. $n$ is odd, but $9 = 3 \times 3$, so $9$ is composite. Hence the universal assertion is disproved.
• Assertion: "$n^2 + n + 41$ is prime for all positive integers $n$."
  • Counterexample: At $n = 41$, $41^2 + 41 + 41 = 41(41 + 1 + 1) = 41 \times 43$, which is composite.

5.8 Mistakes and Pitfalls in Proofs

1. Begging the Question (Circular Reasoning): Using the statement to be proved (or an equivalent assumption) as a premise in the proof.
2. Division by Zero: Hiding an algebraic division by $(a - b)$ where $a = b$.
3. Misuse of Quantifiers: Assuming an existential witness $\exists x$ holds universally for all $x$.
4. Generalizing from Specific Examples: Showing a statement holds for $n = 1, 2, 3$ does not constitute a valid proof for all $n \in \mathbb{N}$.

6. Summary Comparison of Proof Techniques