Untitled Flashcards Set

Comprehensive Reviewer on Proofs (ICS2603-02)

1. Basic Concepts

• Argument – A sequence of statements leading to a conclusion.

• Valid Argument – Conclusion logically follows from true hypotheses.

• Proof – A valid argument.

• Fallacy – An invalid argument.

2. Important Terminologies

• Axiom (Postulate, Law) – A statement assumed to be true.

• Conjecture – A statement proposed to be true.

• Theorem – A statement proven to be true.

• Lemma – A preliminary theorem.

• Corollary – A theorem that follows directly from another theorem.

3. Rules of Inference

Modus Ponens (Law of Detachment)

• If p→qp \to q and pp is true, then qq is true.

• Example: If it rains, it floods. It rains. Therefore, it floods.

Universal Modus Ponens

• If "All xx have property PP", and aa is an xx, then aa has property PP.

• Example: All dogs go to heaven. Poochie is a dog. Poochie will go to heaven.

Universal Modus Tollens

• If "All xx have property PP", but aa does not have PP, then aa is not an xx.

• Example: It is hard to teach old dogs new tricks. Poochie learns tricks easily. Poochie is not an old dog.

4. Methods of Proof

1. Vacuous Proof – Proving p→qp \to q by showing pp is false.

2. Trivial Proof – Proving p→qp \to q by showing qq is always true.

3. Direct Proof – Assuming pp and logically deriving qq.

4. Indirect Proof (Contraposition) – Proving p→qp \to q by proving ¬q→¬p\neg q \to \neg p.

5. Proof by Contradiction – Assuming pp is false and deriving a contradiction.

6. Proof of Equivalence – Proving p↔qp \leftrightarrow q by proving both p→qp \to q and q→pq \to p.

7. Proof by Counterexample – Showing that a universal claim is false by finding a counterexample.

8. Proof of Existence

   • Constructive Proof – Explicitly finding an example.

   • Non-Constructive Proof – Proving existence without identifying an example.

9. Uniqueness Proof – Proving that a solution exists and is unique.

5. Special Proof Techniques

• Exhaustive Proof – Checking all possible cases.

• Proof by Cases – Breaking a proof into multiple scenarios.

• Pigeonhole Principle – If k+1k+1 objects are placed into kk containers, at least one container has more than one object.

6. Exercises

1. Prove that the sum of two odd numbers is even.

2. Prove that 2\sqrt{2} is irrational.

3. Show that at least 4 of 22 different days fall on the same weekday.

This reviewer covers key concepts and proof techniques essential for mastering mathematical proofs. Keep practicing the exercises to solidify your understanding!