Explore the concept of proof by contradiction in discrete structures with examples illustrating its application. Understand the method, rationale, and implications of proving statements through logical contradictions. Discover the effectiveness and potential pitfalls associated with this proof technique.
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Proof by Contradiction Discrete Structures (CS 173) Adapted from Derek Hoiem, University of Illinois 1
Proof by Contradiction Sometimes you want to show that something is impossible 2 cannot be written as a ratio of integers There is no compression algorithm that reduces the size of all files A cycle with an odd number of nodes can t be colored with two colors Difficult to prove non-existence directly, and can t prove by example Solution: show that the negation of the claim leads to a contradiction 2
Contradiction A set of propositions is a contradiction if their conjunction is always false Contradiction? ? ? ? ? (? > 5) (? > 21) ? = 20 and ? is odd (? > 5) (? < 21) (? < 5) (? > 21) ? is negative number and ? is real 3
Proof by contradiction Claim: There are infinitely many prime numbers Equivalent claim: There is not a finite set of primes. 4
Basic form of proof by contradiction 1. I need to show proposition ? 2. Suppose, instead, that ? is false. 3. Then, we can see that both ? and ?, which is a contradiction. 4. Therefore, ? must be true. 5
Why proof by contradiction works We need to prove proposition ? Instead, we show ? ?, i.e., that we can conclude a contradiction from not ? By contrapositive, ? ? ? ? ? 6
Another explanation We need to prove proposition ? = ? Instead, we show ? ?, i.e., that we can conclude a contradiction from ? But ? ? means that ? = ?, so ? = ? 7
Danger of proof by contradiction: a mistake in the proof might also lead to a contradiction See this blog post about P=NP problem http://rjlipton.wordpress.com/2011/01/08/proofs-by-contradiction-and-other-dangers/ 8
Proof by contradiction Claim: 2 is irrational Equivalent claim: There does not exist a pair of integers ?,? without common factors such that ? ?= 2 9
Proof by contradiction Claim: No lossless compression algorithm can reduce the size of every file. 10
When to use each type of proof Match the situation to the proof type Situation 1. Can see how conclusion directly follows from hypothesis Proof type a) Direct proof 2. Need to demonstrate claim for an unbounded set of integers b) Proof by example or counter-example 3. Easier to show that negation of hypothesis follows from negation of conclusion c) Proof by contrapositive (or logical equivalence) 4. Need to show that something doesn t exist d) Induction e) Proof by contradiction 5. Need to show that something exists 14
When to use each type of proof Match the situation to the proof type Situation 1. Can see how conclusion directly follows from claim (a) Proof type a) Direct proof 2. Need to demonstrate claim for an unbounded set of integers (d) b) Proof by example or counter-example 3. Easier to show that negation of hypothesis follows from negation of conclusion (c) c) Proof by contrapositive (or logical equivalence) 4. Need to show that something doesn t exist (e) d) Induction e) Proof by contradiction 5. Need to show that something exists (b) 15
When to use each type of proof Match the claim to the suitable proof type Proof type Claim 1. 2. 3. 4. 5. 6. There is no real ?, such that ?2< 0. If ?2 is odd, then ? is odd. There is an integer ?, such that ?2= 0. If ? is odd, then ?2 is odd. All trees have more nodes than edges. A wheel graph can t be colored with two colors. Not every natural number is a square. The sum of two rational numbers is rational. An even number can t be created from the product of odd numbers. a) Direct proof b) Proof by example or counter-example c) Proof by contrapositive (or logical equivalence) 7. 8. d) Induction 9. e) Proof by contradiction 16
Transition functions and state diagrams States: Village, Rock, Snake, Chasm, Gold, Desert Transitions: (Village, North) Desert (Village, East) Snake (Desert, South) Village (Desert, East) Rock (Rock, West) Desert (Snake, West) Village (Snake, East) Chasm (Snake, South) Gold (Gold, North) Snake 19
Transition functions and state diagrams Input sequence to beat the game: N, E, E, E, E, N, E, N, W, GET ROCK, N, W, N, W, N, W, N, THROW ROCK, N, DRINK WATER, E, GET STICK, THROW STICK, W, N, THROW STICK, LOOK HOLE, GET NOTE, N, W, LIFT ROCK, N, GET NOTE, E, GET LOCKET, E, E, S, W, W, LOOK HOLE, GET CRACKER, E, N, N, W, N, W, N, SAY HOCUS, N, GO HOUSE, GET APPLE, W, N, LOOK GNOME, N, E, SAY HISS, GO CREVICE, S, S, S, GET BREAD, GET LOCKET, GET CRACKER, UNLOCK DOOR, OPEN DOOR, GO DOOR, U, GO HOLE, N, E, S, GIVE CRACKER, GET VIAL, N, W, S, W, W, THROW BREAD, N, GET ROPE, GO BOAT USE BLANKET, N, N, DRINK WATER, N, E, E, E, GO BEACH, N, N, E, GET ANCHOR, W, TIE ROPE, TO ANCHOR, THROW ANCHOR, UP, GET SHOVEL, DOWN, S, S, DIG X, LOOK TREASURE, GRAB CHEST, LEAVE, E, N, W, GO CAVE, OPEN CHEST, LOOK CHEST, GET HARP, N, E, N, DRINK VIAL, FLY NORTH, N, GET RING, N, W, FOLLOW RAINBOW, GET COIN, N, SAY LUCY, W, W, N, GO CAVE, GET ALL, N, S, W, PLAY HARP, N, N, BUY HORN, N, N, BLOW HORN, N, U, E, OPEN CLOSET, LOOK CLOSET, GET SHOES, LOOK SHOES, W, D, W, W, LOOK THRONE, THROW APPLE, N, E, LOOK CABINET, PICK LOCK, WITH KNIFE, OPEN DOOR, E, U, D, U, WEAR RING, RUB RING, D, E, KISS FROG, WEAR SHOES, SAY WHOOSH Adventures in Serenia 20
