Logic & Proofs Guide

Logic Basics

Mathematical logic provides the foundation for all proofs. Understanding logical operators and their truth values is essential.

�?/div>

AND (Conjunction)

True only when both statements are true

P �?Q: "It is raining AND I have an umbrella"

�?/div>

OR (Disjunction)

True when at least one statement is true

P �?Q: "I will walk OR take the bus"

¬

NOT (Negation)

Reverses the truth value

¬P: "It is NOT raining"

�?/div>

IMPLIES (Conditional)

False only when P is true and Q is false

P �?Q: "IF it rains THEN I'll bring an umbrella"

Key Insight

P �?Q �?¬P �?Q

"If P then Q" is logically equivalent to "Not P or Q". This is crucial for understanding proof by contrapositive.

Direct Proof

The most straightforward proof technique: assume the hypothesis is true and use logical steps to arrive at the conclusion.

Structure of Direct Proof

1 State what you want to prove: "If P, then Q"

2 Assume P is true

3 Use definitions, axioms, and theorems

4 Derive Q through logical steps

5 Conclude that P �?Q

Example: Sum of Two Even Numbers

Theorem: The sum of two even numbers is even.

1 Let a and b be even numbers. (Assumption)

2 By definition of even, a = 2m and b = 2n for some integers m, n. (Definition of even)

3 a + b = 2m + 2n = 2(m + n) (Algebra)

4 Since m + n is an integer, a + b = 2k where k = m + n (Closure of integers)

5 Therefore, a + b is even. �?/span> (Definition of even)

Proof by Contradiction

Assume the negation of what you want to prove and show that this leads to a logical impossibility.

The Approach

To prove P is true:

Assume ¬P (P is false)
Derive a contradiction (something both true and false)
Conclude that ¬P must be false, so P is true

Classic Example: �? is Irrational

Theorem: �? is irrational (cannot be expressed as a/b where a, b are integers).

1 Assume �? is rational, so �? = a/b in lowest terms (gcd(a,b) = 1) (Assumption for contradiction)

2 Then 2 = a²/b², so a² = 2b² (Squaring both sides)

3 Therefore a² is even, which means a is even (say a = 2k) (If a² even, then a even)

4 Substituting: (2k)² = 2b², so 4k² = 2b², thus b² = 2k² (Substitution)

5 Therefore b² is even, which means b is even (Same reasoning as step 3)

6 Both a and b are even, contradicting gcd(a,b) = 1 �?/span> (Contradiction!)

7 Our assumption was wrong. Therefore �? is irrational. �?/span> (Conclusion)

Mathematical Induction

Induction proves statements about all natural numbers by showing they work for the first case and that each case implies the next.

The Domino Effect

1Base Case

�?/div>

2

�?/div>

3

�?/div>

...

�?/div>

n

�?/div>

n+1Inductive Step

If the first domino falls (base case) and each domino knocks down the next (inductive step), all dominoes fall.

Structure of Induction

1 Base Case: Prove P(1) is true

2 Inductive Hypothesis: Assume P(k) is true for some k �?1

3 Inductive Step: Prove P(k+1) is true using the hypothesis

4 Conclusion: By induction, P(n) is true for all n �?1

Example: Sum of First n Natural Numbers

Theorem: 1 + 2 + 3 + ... + n = n(n+1)/2

Base Case (n = 1):

LHS = 1, RHS = 1(2)/2 = 1 �?/span>

Inductive Hypothesis:

Assume 1 + 2 + ... + k = k(k+1)/2 for some k �?1

Inductive Step (prove for k+1):

1 + 2 + ... + k + (k+1) = k(k+1)/2 + (k+1) (By hypothesis)

= (k+1)(k/2 + 1) = (k+1)(k+2)/2 (Factor out k+1)

This is exactly the formula with n = k+1. �?/span>

Writing Good Proofs

Be Clear About Goals

State what you're proving and what technique you're using upfront.

Justify Each Step

Cite definitions, theorems, or axioms that support each logical step.

Write for Readers

Use complete sentences and explain transitions between steps.

Check Edge Cases

Verify your proof works for boundary values and special cases.

Logic Basics

AND (Conjunction)

OR (Disjunction)

NOT (Negation)

IMPLIES (Conditional)

Key Insight

Direct Proof

Structure of Direct Proof

Example: Sum of Two Even Numbers

Proof by Contradiction

The Approach

Classic Example: �? is Irrational

Mathematical Induction

The Domino Effect

Structure of Induction

Example: Sum of First n Natural Numbers

Writing Good Proofs

Be Clear About Goals

Justify Each Step

Write for Readers

Check Edge Cases

Related Tools

DP Visualizer

Recursion Visualizer