NSF CARGO: Multi-scale Topological Analysis of Deforming ...

NSF CARGO: Multi-scale Topological Analysis of Deforming ...

CS1050: Understanding and Constructing Proofs Spring 2006 Lecture 09a: PROOF STRATEGIES Section 3.1 Jarek Rossignac Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 1 Lecture Objectives

Learn techniques for constructing proofs Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 2 How to cook 3 steaks? You have 3 steaks. Each one must be cooked for 1 mns on each side. The pan can hold only 2 steaks. Find the most time-effective strategy Prove that it works Prove that it is optimal

Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 3 What is forward reasoning? To prove an implication Start from the hypothesis Build a chain of implications that use the know axioms to lead to the conclusion Difficulty The path may not be obvious

Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 4 What is backward reasoning? Start with the conclusion. Build a chain of implications that use the know axioms backwards First the one that leads to the conclusion Then one that leads to this one Until you get to the hypothesis

Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 5 What is indirect reasoning? To prove an implication, Start the negation of the conclusion Build a chain of implications that use the know axioms to lead to the negation of the hypothesis Jarek Rossignac http://www.gvu.gatech.edu/~jarek

MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 6 How to win at Nim with 1 pile Pile of 15 stones. Each player removes 1, 2, or 3 stones from the pile. The person removing the last stone wins. Is there a winning strategy for player 1? Hint: Prove that if player 2 has to pick from a pile of 4, then

player 1 will win. Use backward reasoning to prove this for different (suitable) starting conditions. What should be the first move of player 1? Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 7 What are conjectures? You do not know whether a conjecture is true. Hence, you may try both proving it and looking for a counterexample.

Example: p(n)=n2+n+41, nN p(n) is prime (Euler 1772) N = {natural numbers, 0,1,2,3.} Prime: integer >1 and only divisible by itself and 1 (only 2 factors) Positive integer = product of primes (increasing order: canonical) It works! p(0)=41, p(1)=34, p(2)=47. P(3)=53p(39)=1601 are all prime! Does it? (Proof of contrary by counterexample) p(40)=402+40+41= 402+240+1=(40+1)2 =1681 is not prime Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006

8 Why are open problems important? They inspire research and sometimes lead to new branches in mathematics. Example of Fermats last theorem: The equation xn+yn = zn with integers x, y, z, n has no solution for n>2. Note that for n=2, we have Pythagorean triplets (3,4,5) Fermat claimed to have a proof. None could be found for about 300 years. Andrew Wiles developed a complex proof in 1990. Goldbach conjecture: Every even integer larger than 3 is the sum of two primes. Checked up to 1014 No proof or counterexample found yet! Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC

MAGIC Georgia Tech, IIC, GVU, 2006 9 What is the halting problem An example of an unsolvable problem, Let H(P,I) be a program which takes as input any program P and the input data I for P and returns true if P(I) is guaranteed to stop and false otherwise. Alan Touring has proven in 1936 that no such H exists. Proof by contradiction: Assume H exists. Make a program K(P) which loops forever if H(P,P) and halts otherwise. Consider K(K). If H(K,K) then K(K) loops forever, but H(K,K) indicates that it halts (contradiction). If !H(K,K) then K(K) halts, but !H(K,K) indicates that it loops forever (contradiction).

Conclusion, H does not exist. Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 10 Assigned Reading 3.1 Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC

MAGIC Georgia Tech, IIC, GVU, 2006 11 Assigned Exercises for the quiz Page 223-224: 1, 2, 20. 2: n=1+2k then n2 mod 8=1 Hint: direct proof develop n2 Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006

12 Assigned Project Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 13

Recently Viewed Presentations

  • Operations Research Approaches to Cyber Conflict

    Operations Research Approaches to Cyber Conflict

    Uncertainties in cyber conflict make problem difficult to parameterize. Approaches: Lanchester Equations. Game Theory. Attacker / Defender Modeling. Applied mathematics from other disciplines. Ultimate Goal: to integrate cyber conflict into Campaign Analysis to inform investment and tactical decisions for DoD....
  • Open Doors Bringing an Inclusive Service Model to

    Open Doors Bringing an Inclusive Service Model to

    • A label can lead to stereotypes. The person with the label often becomes "other" in the eyes of those applying the label. People may start to underestimate the individual's capabilities or intelligence. • Once a person acquires a label,...
  • A Study of Compliment Responses in English among Iraqi ...

    A Study of Compliment Responses in English among Iraqi ...

    Farghal and Al-Khatibb (2001) provides a preliminary analysis from a pragmatic and sociolinguistic point of view, of compliment responses in Jordanian Arabic as they are used by Jordanian college students. It focuses upon the relation of the individual's sexual identity...
  • Herpetology Lab - Mt. San Antonio College

    Herpetology Lab - Mt. San Antonio College

    Herpetology Lab Study of amphibians and reptiles Amphibians Frogs, toads, newts, salamanders Kingdom Animalia, Phylum Chordata, Class Amphibia Semi-terrestrial (double life) aquatic young, terrestrial adult Metamorphosis (frog life cyle) No amniotic egg Young have gills Cutaneous respiration No scales (skin...
  • Stori Dewi Sant Blwyddyn 2/Year 2 Ysgol Gymraeg

    Stori Dewi Sant Blwyddyn 2/Year 2 Ysgol Gymraeg

    Stori Dewi Sant Blwyddyn 2/Year 2 Ysgol Gymraeg Bro Allta Activities that led to the creation of the Powerpoint presentation. Research on the story of Saint David using books and internet - children used a circle map to note new...
  • Chapter 1 - Introduction to Computers and C++ Programming

    Chapter 1 - Introduction to Computers and C++ Programming

    IS 0020 Program Design and Software Tools Introduction to C++ Programming Lecture 5: Classes (continued) Feb 1, 2005 friend Functions and friend Classes friend function Defined outside class's scope Right to access non-public members Declaring friends Function Precede function prototype...
  • The 1905 Revolution - WordPress.com

    The 1905 Revolution - WordPress.com

    1893to 1903 Finance minister Witte, Tsar Nicholas II, 'Great spurt = industrialisation. 1904 War with Japan = strains Russia. 1905 Bloody Sunday, Revolution. 1905 October Manifesto = Duma, some elections. 1906 to 14 increasing reaction, crushing opposition. 1914World War I...
  • Clinical Response to PFAS Exposure - dhd2.org

    Clinical Response to PFAS Exposure - dhd2.org

    Clinical Response to PFAS Exposure. Susan Buchanan, MD, MPH. ... Should I order PFC levels on my exposed patients? ... For exposures at the reference level of a chemical the "chances" are 1:1,000,000