Intro to Proofs – Complete Formula Sheet

Logical Statements

Propositions

A statement that is either true or false.

Example: "2 + 2 = 4" (true)

Example: "5 > 10" (false)

Logical Connectives

AND ($\land$): Both true

OR ($\lor$): At least one true

NOT ($\neg$): Reverses truth

IMPLIES ($\implies$): $P \implies Q$

IFF ($\iff$): Both directions

Truth Tables & Equivalence

Basic Truth Table

$P$	$Q$	$P \land Q$	$P \lor Q$
T	T	T	T
T	F	F	T
F	T	F	T
F	F	F	F

Logical Equivalence

Two formulas with same truth table

Denoted: $P \equiv Q$ or $P \Leftrightarrow Q$

Conditionals & Biconditionals

Conditional $P \implies Q$

"If P then Q" — only false when P true, Q false

$P$	$Q$	$P \implies Q$
T	T	T
T	F	F
F	T	T
F	F	T

Biconditional $P \iff Q$

True when both have same truth value

Both true OR both false

$P \iff Q \equiv (P \implies Q) \land (Q \implies P)$

Negations

De Morgan's Laws

$\neg(P \land Q) \equiv \neg P \lor \neg Q$

$\neg(P \lor Q) \equiv \neg P \land \neg Q$

Negating Conditionals

$\neg(P \implies Q) \equiv P \land \neg Q$

Quantified Statements

$\neg(\forall x, P(x)) \equiv \exists x, \neg P(x)$

$\neg(\exists x, P(x)) \equiv \forall x, \neg P(x)$

Switch quantifiers AND negate property

Direct Proof

Goal: Prove $P \implies Q$

Structure

Assume $P$ is true

Use definitions, axioms, theorems

Derive $Q$ is true

Example

Prove: If $n$ is even, then $n^2$ is even.

Assume $n$ is even

Then $n = 2k$ for some integer $k$

$n^2 = (2k)^2 = 4k^2 = 2(2k^2)$ ✓

Proof by Contraposition

Principle

$P \implies Q \equiv \neg Q \implies \neg P$

Prove negation of conclusion implies negation of hypothesis

When to Use

Original direction hard to prove

Negations easier to work with

Example

Prove: If $n^2$ is even, then $n$ is even.

Contrapositive: If $n$ is odd, then $n^2$ is odd

$n = 2k+1 \implies n^2 = 4k^2 + 4k + 1$ (odd) ✓

Proof by Contradiction

Structure

Assume $\neg P$ (negate what you want to prove)

Derive a contradiction

Conclude $P$ must be true

Classic Example

$\sqrt{2}$ is irrational:

Assume $\sqrt{2} = \frac{p}{q}$ (rational)

Leads to both $p,q$ even (contradiction)

Therefore $\sqrt{2}$ is irrational ✓

Often used for infinitude arguments (primes, etc.)

Proof by Cases

Structure

Partition domain into exhaustive cases

Prove statement for each case

Union of cases covers all inputs

Example

Prove: For all $n \in \mathbb{Z}$, $n(n+1)$ is even

Case 1: $n$ even: $n = 2k$, so $n(n+1) = 2k(2k+1)$ (even)

Case 2: $n$ odd: $n+1$ even, so product is even ✓

Existence Proofs

Constructive

Explicitly find/construct the object

Example: "Prove there exists a prime > 1000"

Provide: $p = 1009$ (show it's prime)

Non-Constructive

Show existence without finding object

Use pigeonhole, continuity, etc.

Example: Intermediate Value Theorem

Proving Uniqueness

Assume two objects $x, y$ satisfy property

Show $x = y$

Or: Show existence + uniqueness separately

Mathematical Induction

Goal: Prove $\forall n \in \mathbb{N}, P(n)$

Weak Form Structure

Base Case: Prove $P(1)$ (or $P(0)$)

Inductive Hypothesis (IH): Assume $P(k)$ is true for some $k \geq 1$

Inductive Step: Prove $P(k) \implies P(k+1)$

Example

Prove: $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$

Base: $n=1$: LHS $= 1$, RHS $= 1$ ✓

Step: Assume true for $k$. Then for $k+1$:

$\sum_{i=1}^{k+1} i = \frac{k(k+1)}{2} + (k+1) = \frac{(k+1)(k+2)}{2}$ ✓

Strong Induction

Goal: Prove $\forall n \in \mathbb{N}, P(n)$

Strong Form Structure

Base Case: Prove $P(1), \ldots, P(m)$

Inductive Hypothesis: Assume $P(1), P(2), \ldots, P(k)$ ALL true

Inductive Step: Prove $P(k+1)$

When to Use

Need previous values beyond just $P(k)$

Fibonacci, Fundamental Theorem of Arithmetic

Strong induction is at least as powerful as weak induction

Well-Ordering Principle

Every non-empty set of positive integers has a minimum element

Equivalent to Induction

WOP, weak induction, strong induction are equivalent

Proof by Minimum Counterexample

Assume $\neg P(n)$ for some $n$

Let $m$ be smallest counterexample

Show $m$ minimal contradicts the structure

Useful for: Divisibility arguments, algorithm termination

Set Proofs

Equality: $A = B$

Prove $A \subseteq B$: $x \in A \implies x \in B$

Prove $B \subseteq A$: $x \in B \implies x \in A$

Both directions: $x \in A \iff x \in B$

Subset: $A \subseteq B$

Show: If $x \in A$, then $x \in B$

Disjoint Sets

Prove $A \cap B = \emptyset$

Show: No element in both

Use element-chasing: "Let $x \in A$..." and show $x \in B$

Function Proofs

Injective (One-to-One)

If $f(a) = f(b)$, then $a = b$

No two inputs map to same output

Surjective (Onto)

$\forall y \in B, \exists x \in A: f(x) = y$

Every output is hit

Bijective

Both injective AND surjective

One-to-one correspondence

Inverse function exists

Strategies & Tips

General Strategies

Work backwards: What would imply the goal?

Try small cases: Test with $n=1,2,3$

Look for patterns: Iterate, see what happens

Common Pitfalls

Circular reasoning (using conclusion)

Assuming what you're proving

Not checking all cases

Organization

State goal clearly upfront

Label assumptions & hypotheses

End with QED or ∎

When stuck: switch proof technique (contrapositive, contradiction, cases)

Key Equivalences

Laws

$(P \implies Q) \equiv (\neg P \lor Q)$

$(P \implies Q) \equiv (\neg Q \implies \neg P)$

$(P \iff Q) \equiv (P \implies Q) \land (Q \implies P)$

De Morgan's

$\neg(P \land Q) \equiv \neg P \lor \neg Q$

$\neg(P \lor Q) \equiv \neg P \land \neg Q$

Distributive

$P \land (Q \lor R) \equiv (P \land Q) \lor (P \land R)$

INTRO TO PROOFS Complete Formula Sheet