Discovering proofs is an art as well as a science. It requires:

• skill at logical thinking and reasoning
• understanding the objects you're working with
• practice and experience

General Proof Strategies

Set Equalitytheorem

To prove set equality, A = B (where A and B are sets):

1. Prove A ⊆ B (every element of A is in B)
2. Prove B ⊆ A (every element of B is in A)

Numerical Equalitytheorem

To prove numerical equality, A = B:

• If algebra can transform A to B, that's sufficient
• If not:
  1. Prove A ≤ B
  2. Prove A ≥ B

Proof Techniques in FIT2014

Direct Proof

Strategy: Start with assumptions and use logical deductions to reach the conclusion.

Example: Prove that DOUBLEWORD ⊆ EVEN-EVEN

• Let w be any word in Σ*
• Let ww be the corresponding doubleword
• If w has nₐ 'a's and nᵦ 'b's, then ww has 2nₐ 'a's and 2nᵦ 'b's
• Since 2nₐ and 2nᵦ are even, ww ∈ EVEN-EVEN ✓

Proof by Construction

Strategy: When proving existence, construct an explicit example.

Use Case: Proving that a language contains certain words or that a property holds.

Proof by Cases

Strategy: Identify a finite number of cases that cover all possibilities.

Example: Proving properties about languages based on word length or symbol counts.

Proof by Contradiction

Strategy: Assume the negation of what you want to prove and derive a contradiction.

Example: Proving that √2 is irrational (classic example covered in lectures).

Mathematical Induction

Strategy: Prove base case, then show if true for k, then true for k+1.

Structure:

Base Case: Prove S(1) is true

Inductive Hypothesis: Assume S(k) is true

Inductive Step: Show S(k) → S(k+1)

Application: Prove that 1² + 2² + ... + n² = n(n+1)(2n+1)/6

Language-Specific Proof Techniques

Proving Language Properties

1. Language Equality: L₁ = L₂

   • Prove L₁ ⊆ L₂ and L₂ ⊆ L₁

2. Language Subset: L₁ ⊆ L₂

   • Take arbitrary w ∈ L₁, show w ∈ L₂

3. Language Operations: Properties of union, intersection, concatenation

Example: Even-Odd Language Properties

Theorem

Words in ODD-ODD have odd length.

Proof: Let w ∈ ODD-ODD with nₐ 'a's and nᵦ 'b's.

• By definition, nₐ is odd and nᵦ is odd
• Length of w = nₐ + nᵦ
• Sum of two odd numbers is even
• Therefore, all words in ODD-ODD have even length ✓

Predicate Logic Proofs

Working with Quantifiers

Universal (∀)logic

Must hold for ALL elements in domain

Strategy: Take arbitrary element from domain

Existential (∃)logic

Must hold for AT LEAST ONE element

Strategy: Construct specific example

Example: Proving Universal Statements

Universal Statement Proof

Theorem: ∀w ∈ Σ*, if w ∈ EVEN-EVEN then |w| is even

Proof: Let w be an arbitrary word in EVEN-EVEN

• w has even number of 'a's and even number of 'b's
• Let nₐ = 2k, nᵦ = 2m for integers k, m
• |w| = nₐ + nᵦ = 2k + 2m = 2(k + m)
• Since k + m is integer, |w| is even ✓

Proof Organization and Structure

Standard Proof Format

1. Statement: Clearly state what you're proving
2. Approach: Indicate the proof method (direct, contradiction, etc.)
3. Body: Step-by-step logical reasoning
4. Conclusion: State what has been proven

Common FIT2014 Proof Patterns

Automata Equivalence

Show two machines accept same language

Language Regularity

Prove a language is/isn't regular

Grammar Properties

Show properties of context-free grammars

Pumping Lemma

Prove languages are not regular/context-free

Practice Exercises

Set Theory: Prove that (A ∩ B) ∪ C = (A ∪ C) ∩ (B ∪ C)

Language Properties: Prove that if w ∈ PALINDROMES, then wᴿ ∈ PALINDROMES

Induction: Prove by induction that the sum of first n odd numbers is n²

Contradiction: Prove that there is no largest prime number

Quantifiers: Prove ∃w ∈ Σ* such that w ∈ EVEN-EVEN and |w| > 0

Language Operations: Prove that L₁ ∩ L₂ ⊆ L₁ for any languages L₁, L₂

Direct Proof: Prove that if n is even, then n³ is even

Changelog

8/4/25, 11:40 AM

View All Changelog

• 2b7ff-web-deploy(Auto): Update base URL for web-pages branchon 8/4/25

Copyright

Copyright Ownership:WARREN Y.F. LONG

License under:Attribution-NonCommercial-NoDerivatives 4.0 International (CC-BY-NC-ND-4.0)