Math for Robotics: Logic, Notation & Proof Techniques

This is pure mathematics, not applied robotics

The course focuses on mathematical methods and proof techniques with theorems and proofs every day, but never demonstrates anything on an actual robot. Students looking for practical robotics applications should reconsider enrollment.

Number systems hierarchy

Natural numbers (counting numbers starting at 1) form the foundation, followed by integers (including negatives and zero), rationals (ratios of integers with no common factors), reals (limits of rational sequences), and complex numbers (real plus imaginary parts where j² = -1). Complex numbers are necessary because polynomial roots are not always real even with real coefficients.

Number systems used in mathematics for robotics

Universal and existential quantifiers

The upside-down A (∀) means 'for every' or 'for all'; the backwards E (∃) means 'there exists' or 'for some'. The element symbol (∈) denotes membership in a set. These symbols allow precise translation of English statements into formal logic.

Core logical symbols

Existential quantifiers depend on preceding conditions

When a statement contains both universal and existential quantifiers, the element chosen by the existential quantifier can depend on all preceding universal variables. For example, in 'for every real x, there exists a rational q such that |x - q| < 1/n', the choice of q depends on both x and n.

Implication and logical equivalence

P implies Q (P → Q) means if P is true, then Q is true; if P is false, Q can be either. P if and only if Q (P ↔ Q) means P → Q and Q → P both hold, making them logically equivalent. This is critical vocabulary for distinguishing related but different logical relationships.

Contrapositive vs. converse (critical vocabulary)

The contrapositive of P → Q is ¬Q → ¬P, which is logically equivalent to the original statement. The converse of P → Q is Q → P, which is NOT logically equivalent. Confusing these is a common error that will result in lost points on exams.

Contrapositive is logically equivalent; converse is not

Direct proof: apply logic to assumptions and definitions

A direct proof derives a result by applying rules of logic to given assumptions, definitions, and known theorems. In homework, 'show' means 'prove' via direct calculation: compute the left-hand side, compute the right-hand side, and demonstrate they are equal.

In definitions, 'if' means 'if and only if'

Mathematicians use 'if' in definitions to mean 'if and only if' (↔) to avoid repetition. This convention applies only to definitions, not to theorems or corollaries. For example, 'n is even if n = 2k for some integer k' means n is even exactly when it can be written this way.

Example: sum of two odd integers is even

If a and b are odd, then a = 2k₁ + 1 and b = 2k₂ + 1 for integers k₁, k₂. Then a + b = 2k₁ + 2k₂ + 2 = 2(k₁ + k₂ + 1), which is even because k₁ + k₂ + 1 is an integer. This demonstrates how definitions and arithmetic properties combine in a direct proof.

Contrapositive proof strategy

To prove P → Q, instead prove the contrapositive ¬Q → ¬P. Since they are logically equivalent, proving one proves the other. Once the contrapositive is written down, the proof becomes a direct proof on the new statement.

Example: if n² is even, then n is even

Rather than assuming n² is even and proving n is even, prove the contrapositive: if n is odd, then n² is odd. If n = 2k + 1, then n² = 4k² + 4k + 1 = 2(2k² + 2k) + 1, which is odd. This contrapositive proof is often easier than the direct approach.

Writing down P and Q is half the battle

Half of failed proofs occur because students never write down what they are trying to prove. Explicitly stating the hypothesis (P) and conclusion (Q) often reveals the path to the proof and prevents getting stuck.

Proof by exhaustion: check all finite cases

Reduce a proof to a finite number of cases, then verify each one. The famous four-color theorem was proven this way: mathematicians reduced it to approximately 400,000 cases and used a computer program to verify each one. This method is valid but rarely used in this course.

First principle of induction structure

To prove P(n) is true for all natural numbers n ≥ 1: (1) prove the base case P(1) is true, and (2) prove that if P(k) is true for arbitrary k ≥ 1, then P(k+1) is true. If both hold, then P(n) is true for all n ≥ 1. This proves infinitely many statements with finite work.

First principle of mathematical induction

Example: sum of first n odd numbers equals n²

Claim: 1 + 3 + 5 + ... + (2n-1) = n². Base case: n=1 gives 1 = 1². Inductive step: assume 1 + 3 + ... + (2k-1) = k². Then 1 + 3 + ... + (2k-1) + (2k+1) = k² + (2k+1) = k² + 2k + 1 = (k+1)². Thus P(k) true implies P(k+1) true.

Common induction mistakes

Students often fail to check the base case or forget to write down the statement P(n) being proven. Writing down what you are inducting over (e.g., 'for all integers n ≥ 1, the formula holds') makes errors obvious and the proof much easier.

Adjusting induction for non-standard starting points

If you need to prove P(n) for n ≥ 19 instead of n ≥ 1, define P̃(k) = P(k+18) and do induction on P̃ starting at k=1. This converts any starting point into the standard form. You cannot use induction in both directions simultaneously (e.g., from -67,000 to +infinity), but forward or backward alone is fine.

Second principle of induction structure

To prove P(n) for all n ≥ 1: (1) prove base case P(1) is true, and (2) prove that if P(j) is true for all j where 1 ≤ j ≤ k, then P(k+1) is true. The key difference from first principle: you can use all previous cases, not just the immediately preceding one.

Second principle (strong induction)

Why strong induction is equivalent to first principle

Define P̃(k) = P(1) AND P(2) AND ... AND P(k). Then do ordinary induction on P̃(k). The base case is P̃(1) = P(1). The inductive step proves P̃(k) → P̃(k+1), which requires proving P(k+1) given that all of P(1) through P(k) are true. This shows the two methods are logically equivalent.

Strong induction is sometimes easier to apply

When proving P(k+1), sometimes you need to reference multiple earlier cases, not just P(k). Strong induction formalizes this by allowing you to use any P(j) with j ≤ k. Both methods are equivalent, but strong induction can organize your reasoning more naturally in certain problems.

Every integer ≥ 2 is a product of primes

The Fundamental Theorem of Arithmetic states that every natural number n ≥ 2 can be written as a product of one or more prime numbers. A prime is a natural number that cannot be factored (i.e., cannot be written as a product of two natural numbers both greater than 1). A composite number can be factored. One is neither prime nor composite.