Discrete Structures for Computer Science

Discrete Structures for Computer Science Presented by: Andrew F. Conn Adapted from: Adam Lee Lecture #6: Proof Methods and Strategies September 19th, 2016 Announcements HW #1 is due Wednesday HW #2 will come out today. It is tentatively due next Wednesday 9/28 Proof Methods and Strategies

Last class we discussed 3 proof methods: 1. Direct Proof 2. Proof by Contraposition 3. Proof by Contradiction Today we will add 2 more proof methods: 4. Exhaustive Proof and Proof by Cases. 5. Existence Proof 6. Uniqueness Proof Then we will discuss 4 types of strategy: 7. Forward reasoning 8. Backward reasoning 9. Searching for counterexamples

10. Adapting existing proofs Sadly, not all theorems are of the form p q Sometimes, we need to prove a theorem of the form: Note: So, we might need to examine multiple cases! Exhaustive Proof: Try every possibility!

Prove that where is a positive integer with . Proof: , , , , and and and and Since we have verified each case, we have shown that where is a positive integer with .

With only 4 cases to consider, exhaustive proof was a good choice! Sometimes, exhaustive proof isnt an option, but we still need to examine multiple possibilities Example: Prove the triangle inequality. That is, if and are real numbers, then . Clearly, we cant use exhaustive proof here since there are infinitely many real numbers to consider. We also cant use a simple direct proof either, since our proof depends on the signs of and .

What should we do? Proof by Cases: Triangle Inequality Case 1: Assume . Then we can drop the absolute value and we have . Case 2: Assume The we can multiply everything by and get Case 3: Assume Then we have We need 2 more cases, and 3a) We can drop the absolute value from the right hand side

and we get , and we already have 3b) We can multiply the right hand side by to get . Since is positive, we have In both sub cases, we have as required. Case 4: Similar to Case 3. Making mistakes when using proof by cases is all too easy! Mistake 1: Proof by a few cases is not equivalent to proof by cases. These are there exists proofs, not a for all proof!

Example: Prove that all odd numbers are prime. Proof: Case 1: The number 3 is both odd and prime Case 2: The number 5 is both odd and prime Case 3: The number 7 is both odd and prime Thus, we have shown that odd numbers are prime. Making mistakes when using proof by cases is all too easy!

Mistake 2: Leaving out critical cases. Example: Prove that for all integers Proof: Case 1: Assume that . Since the product of two negative numbers is always positive, . Case 2: Assume that . Since the product of two positive numbers is always positive, . Since we have proven the claim for all cases, we can conclude that for all integers . What about the case in which x = 0? Sometimes we need to prove the existence of a given element

There are two ways to do this Prove the claim by showing how to construct an example The constructive approach Show that it is possible for such an element to exist The non-constructive approac A constructive existence proof Prove: Show that there is a positive integer that can be written as the sum of cubes of positive integers in two different ways.

Proof: 1729 = 103 + 93 = 123 + 13 Obviously, the claim has been proven because we have shown that a specific instance of the claim is valid. Constructive existence proofs are really just instances of existential generalization. A non-constructive existence proof Prove: Show that there exist two irrational numbers and such that is rational. Proof: We know that is irrational, so let If is rational, then we are done! (i.e., )

If is irrational, then let and , both of which are irrational Now, , which is rational (i.e., ) Note: We dont know whether 22 is rational or irrational. However, in either case, we can use it to construct a rational number. Sometimes, existence is not enough and we need to prove uniqueness This process has two steps: 1. Provide an existence proof 2. Show that any other solution to the problem is equivalent to the solution generated in step 1

Example: Prove that if a and b are real numbers, then there exists a unique real number such that Proof: Existence Note that is a solution to this equality since . Uniqueness Assume that Then , so , which is a contradiction The scientific process is not always

straightforward Conjecture Gather evidence, prove lemmas Prove theorem Proof strategies can help preserve your sanity Proof strategies help us

Organize our problem solving approach Effectively use all of the tools at our disposal Develop a coherent plan of attack Proof Strategies Convince yourself with examples or

counterexamples! Often times an example can expose a pattern that can be used in the proof. If you find a counterexample, youre done! Try to work forward from the premises Many proofs involve stepwise applications of basic logic. Try to work backwards from the result Sometimes the conclusion will yield a property that the premise implies to be true! Look for existing strategies that might fit this

problem What strategy might one use with even and odd integer proofs? Even Backwards Reasoning Forward reasoning can lead down multiple paths. In these cases, it is often helpful to reason backwards, starting with the goal that we want to prove. Example: Prove that given two distinct positive real numbers and , the arithmetic mean of and is always greater than the geometric mean of

and . + Try: and . Geometric vs Arithmetic? Try it: Since whenever , the final inequality is true.

Since all of these inequalities are the same, we can work backwards and it follows that . Searching for a counterexample Proof by counterexample is helpful if: Proof attempts repeatedly fail The conjecture to be proven looks funny Example: Prove that every positive integer is the sum of two squares. This seems strange to me, since other factorizations (e.g., prime factorizations) can be complex.

Counterexample: 3 is not the sum of two squares, so the claim is false. These four proof strategies are just a start! When trying to prove a new conjecture, a good meta strategy is to: 1. If possible, try to reuse an existing proof 2. If the conjecture looks fishy, check for a counterexample 3. Attempt a real proof a) Either apply the forward reasoning strategy b) Or, apply the backward reasoning strategy

Unfortunately, not every proof can be solved using this nice little meta strategy In fact, there are many, many proof strategies out there, and NONE of them can be guaranteed to find a proof!!! Group work! Problem 1: Prove that there exists a positive integer that is equal to the sum of all positive integers not exceeding it. Is your proof constructive or non-constructive? Problem 2: Prove that there is no positive integer n such that n2 + n3 = 100. Problem 3: Use proof by cases to show that

min(a, min(b,c) = min(min(a,b),c) whenever a, b, and c are real numbers. Final Thoughts Proving theorems is not always straightforward Having several proof strategies at your disposal will make a huge difference in your success rate! We are done with our intro to logic and proofs Next lecture: Intro to set theory Please read sections 2.1 and 2.2

Weve been doing forward reasoning all along! In the forward reasoning strategy, we begin with our premises and axioms and reason towards our goal Potential steps in the forward reasoning process: 1. Try a simple direct proof Could be of form p q Could be of form (p1 p2 pn) q

2. If direct proof fails, try proof by contraposition

Recently Viewed Presentations

  • The National Policy and the Rebirth of the CPR

    The National Policy and the Rebirth of the CPR

    National Policy. It was both his election . platform . and his vision for the future of Canada. The National Policy was based on three main ideas, a system of protective . tariffs, settling the . west, and finishing the...
  • Next-Generation Characterization An Update on the JHOVE2 Project

    Next-Generation Characterization An Update on the JHOVE2 Project

    Next-Generation Characterization An Update on the JHOVE2 Project JHOVE2 Project Team ... extraction Validation Message digesting Adler-32, CRC-32, MD2, MD5, SHA-1, SHA-256, SHA-384, SHA-512 Rules-based assessment JHOVE2 feature set Processing of objects spanning files and objects that are ...
  • Teacher directed integrative teaching in large group settings ...

    Teacher directed integrative teaching in large group settings ...

    The purpose of this session is to teach participants about the relationship between learning objectives and test questions. ... A HOTS objective mustrequire the student to generalize or apply what he or she knows to a new situation. Recall Sample...
  • Auxiliary clitics in coordinated subjects: AGREE - SPLIT - REPEAT

    Auxiliary clitics in coordinated subjects: AGREE - SPLIT - REPEAT

    Overview of the talk. We argue that examinations of configurations like (1) with different values of -features on the clitic (PL) and the first conjunct (SG) support a view of agreement on which:. It is not a monolithic phenomenon, but...
  • Chapter 1 Structure and Bonding - faculty.swosu.edu

    Chapter 1 Structure and Bonding - faculty.swosu.edu

    Integration is a calculus operation Integration of the first order rate law: Gives the Integrated first-order rate law: Integration and Differentiation are connected. If we know the integrated rate law, we could differentiate it to get the rate law If...
  • Principles of Anatomy and Physiology

    Principles of Anatomy and Physiology

    THIRD-ORDER NEURON. Primary somatosensory. area of cerebral cortex. Medulla. Midbrain. FIRST-ORDER NEURON. SECOND-ORDER NEURON. TRIGEMINOTHALAMIC TRACT. Trigeminal ganglion. Trigeminal (V) nerve. Receptors for touch, pain, and temperature in the face, nasal cavity, oral cavity, and teeth. Pons. Trigenminothalamic pathways. SECOND-ORDER...
  • A Walk in the Desert Spelling Words

    A Walk in the Desert Spelling Words

    A Walk in the Desert Spelling Words Inflected -ed and -ing Dropping and Doubling Rule What do you know about reading these words? rained raining -both of these have a base word and an ending -ed means it happened in...
  • The Age of Railroads - Pequannock Township High School

    The Age of Railroads - Pequannock Township High School

    Rapid Growth of Railroads. ... The Interstate Commerce Act, 1877. In 1886, the Supreme Court ruled that a state could not set rates on interstate commerce! In response to public outcry, Congress passed the Interstate Commerce Act in 1877.