Logical Thinking Advanced

Predicate logic extends propositional logic by introducing variables and predicates. A predicate P(x) is a statement whose truth depends on the value of x. Quantifiers bind variables:

• Universal quantifier ∀x P(x): "For all x, P(x) holds."
• Existential quantifier ∃x P(x): "There exists an x such that P(x) holds."

Example over integers:
  ∀x (x² ≥ 0)        — true (squares are non-negative)
  ∃x (x + 3 = 5)     — true (x = 2 is a witness)
  ∀x (x + 1 = x)     — false (no integer satisfies this)

The domain of discourse specifies what values variables range over; always state it clearly.

The negation of a quantified statement switches the quantifier and negates the predicate:

• ¬(∀x P(x)) ≡ ∃x ¬P(x)
• ¬(∃x P(x)) ≡ ∀x ¬P(x)

These are the quantifier equivalents of De Morgan's laws. To disprove a universal statement it suffices to find one counterexample; to disprove an existential statement you must show no witness exists.

Negate: "All students passed the exam."
  ∀x P(x) becomes ∃x ¬P(x):
  "There exists a student who did not pass the exam."

A direct proof of p → q assumes p is true and, through a chain of logical steps, derives q.

A proof by contraposition instead proves the contrapositive ¬q → ¬p: assume ¬q and derive ¬p. Since the contrapositive is equivalent to the original, this is a valid proof of p → q.

Direct proof: "If n is even, then n² is even."
  Assume n is even ⟹ n = 2k for some integer k.
  Then n² = (2k)² = 4k² = 2(2k²), which is even. □

Contrapositive: "If n² is odd, then n is odd."
  Assume n is even ⟹ n² is even (by above) — so ¬q ⟹ ¬p holds. □

In proof by contradiction (reductio ad absurdum), assume the negation of what you want to prove and show this leads to a contradiction (⊥).

Mathematical induction proves statements of the form ∀n P(n) in two steps:

1. Base case: verify P(1) (or the smallest n).
2. Inductive step: assume P(k) (inductive hypothesis) and prove P(k+1).

Contradiction — √2 is irrational:
  Assume √2 = a/b in lowest terms. Then 2 = a²/b², so a² = 2b² (even),
  so a is even ⟹ a = 2m ⟹ 4m² = 2b² ⟹ b² = 2m² (even) ⟹ b is even.
  But a/b was in lowest terms — contradiction. □

Induction — sum of first n natural numbers = n(n+1)/2:
  Base: n=1: sum = 1 = 1(2)/2. ✓
  Step: assume true for k; show for k+1:
    k(k+1)/2 + (k+1) = (k+1)(k+2)/2. ✓ □

Boolean algebra is the algebraic system that formalises logic. Key laws (where 0 = ⊥, 1 = ⊤):

• Identity: p ∧ ⊤ ≡ p, p ∨ ⊥ ≡ p
• Annihilation: p ∧ ⊥ ≡ ⊥, p ∨ ⊤ ≡ ⊤
• Idempotent: p ∧ p ≡ p, p ∨ p ≡ p
• Absorption: p ∧ (p ∨ q) ≡ p, p ∨ (p ∧ q) ≡ p
• Distributive: p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
• Complement: p ∧ ¬p ≡ ⊥, p ∨ ¬p ≡ ⊤

These laws are used to simplify digital circuit designs (logic gates) and optimise boolean expressions in software.

In Knights-and-Knaves puzzles (introduced by Raymond Smullyan), every inhabitant is either a Knight (always tells the truth) or a Knave (always lies). The solver must determine who is who from their statements.

Strategy: assume a character is a Knight; verify all their statements are consistent under that assumption. If contradiction arises, they must be a Knave.

Puzzle: A says "B is a Knave." B says "A and I are both Knights."

Case 1 — A is a Knight:
  A's claim "B is a Knave" is true ⟹ B is a Knave.
  B (Knave) says "A and I are both Knights" — this is false. ✓ Consistent.

Case 2 — A is a Knave:
  A's claim is false ⟹ B is a Knight.
  B (Knight) says "A and I are both Knights" — A is a Knave, so this is false.
  But Knights cannot lie. Contradiction. ✗

Conclusion: A is a Knight, B is a Knave.

Propositional and predicate logic mirror set-theoretic operations precisely:

• p ∧ q corresponds to set intersection A ∩ B.
• p ∨ q corresponds to set union A ∪ B.
• ¬p corresponds to set complement A′ (or Ā).
• p → q corresponds to set subset A ⊆ B.

De Morgan's laws hold identically: (A ∩ B)′ = A′ ∪ B′ and (A ∪ B)′ = A′ ∩ B′. Universal statements ∀x P(x) can be read as "the domain is a subset of the set of all x satisfying P."

∀x (x ∈ A → x ∈ B)  ≡  A ⊆ B
∃x (x ∈ A ∧ x ∈ B)  ≡  A ∩ B ≠ ∅