Theory Of Computer Science - Proof Techniques.pdf

Theory of Computer Science - A3. Proof Techniques

This section covers various proof techniques used in theoretical computer science.

Key Concepts:

Mathematical Statement: Consists of preconditions and conclusions. A statement is true if the conclusions hold when the preconditions are met.
Proof: Sequence of logical steps demonstrating the validity of a mathematical statement based on axioms and previously proven statements.
Disproof: Demonstrates a mathematical statement is false by providing a counterexample where preconditions are met but the conclusion fails.

Common Proof Strategies:

1. Direct Proof: Directly shows that if preconditions hold, then conclusions follow.
2. Indirect Proof (Proof by Contradiction): Assumes the negation of the statement, derives a contradiction, and concludes the original statement must be true.
3. Contraposition: Proves the contrapositive of the original statement: If not conclusion, then not preconditions.
4. Mathematical Induction:

Complete Induction: Proves a property for all natural numbers by induction over the set.
* Structural Induction: Uses the structure of the object being proven (e.g., trees, graphs) to perform induction.

5. Other Techniques: There are additional techniques like proof by cases and reducibility arguments not detailed here.

Example:

Theorem (Distributivity): For all sets A, B, C: A ∩(B ∪C) = (A ∩B) ∪(A ∩C).

Direct Proof is presented with a step-by-step demonstration showing the equality of the two sets. An alternative approach using set definitions and logical connectives is also shown.