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 \subseteq B$ (every element of A is in B)
2. Prove $B \subseteq 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 \leq B$

2. Prove $A \geq B$

Proof Techniques in FIT2014

Direct Proof

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

Example: Prove that DOUBLEWORD $\subseteq$ EVEN-EVEN

• Let w be any word in $\Sigma^*$
• Let ww be the corresponding doubleword
• If w has $n_a$ 'a's and $n_b$ 'b's, then ww has $2n_a$ 'a's and $2n_b$ 'b's
• Since $2n_a$ and $2n_b$ are even, $ww \in$ 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 $\sqrt{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) \to 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_1 \subseteq L_2$ and $L_2 \subseteq L_1$

2. Language Subset: $L_1 \subseteq L_2$

• Take arbitrary $w \in L_1$, show $w \in L_2$

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

Example: Even-Odd Language Properties

Theorem

Words in ODD-ODD have odd length.

Proof: Let $w \in$ ODD-ODD with $n_a$ 'a's and $n_b$ 'b's.

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

Predicate Logic Proofs

Working with Quantifiers

Universal ($\forall$)logic

Must hold for ALL elements in domain

Strategy: Take arbitrary element from domain

Existential ($\exists$)logic

Must hold for AT LEAST ONE element

Strategy: Construct specific example

Example: Proving Universal Statements

Universal Statement Proof

Theorem: $\forall w \in \Sigma^*$, if $w \in$ 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_a = 2k$, $n_b = 2m$ for integers k, m
• $|w| = n_a + n_b = 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 \cap B) \cup C = (A \cup C) \cap (B \cup C)$

Start with set equality proof strategy: prove both directions of inclusion.

Language Properties: Prove that if $w \in$ PALINDROMES, then $w^R \in$ PALINDROMES

Use the definition of palindromes and properties of string reversal.

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

Base case: n=1, then use inductive step with algebraic manipulation.

Contradiction: Prove that there is no largest prime number

Assume there exists a largest prime, then construct a larger one.

Quantifiers: Prove $\exists w \in \Sigma^*$ such that $w \in$ EVEN-EVEN and $|w| > 0$

Construct an explicit example word with even counts of all symbols.

Language Operations: Prove that $L_1 \cap L_2 \subseteq L_1$ for any languages $L_1, L_2$

Use the definition of set intersection and subset relations.

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

Use the definition of even numbers and properties of multiplication.

Changelog

8/8/25, 4:17 AM

View All Changelog

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

Copyright

Copyright Ownership:WARREN Y.F. LONG

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