### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Honors Discrete Mathematics MAD 2104

FAU

GPA 3.65

### View Full Document

## 13

## 0

## Popular in Course

## Popular in Mathematics Discrete

This 8 page Class Notes was uploaded by Chaya Botsford II on Monday October 12, 2015. The Class Notes belongs to MAD 2104 at Florida Atlantic University taught by Jorge Viola-Prioli in Fall. Since its upload, it has received 13 views. For similar materials see /class/221637/mad-2104-florida-atlantic-university in Mathematics Discrete at Florida Atlantic University.

## Similar to MAD 2104 at FAU

## Reviews for Honors Discrete Mathematics

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/12/15

19CONTRADICTION AND CONTRAPOSITIVE We address once again the question of how to prove a mathematical statement of the form quotif A then B We have used so far the template for a direct proof unravel A unravel B produce the link from A to B So in a direct proof no negation is involved We will introduce now two more ways to prove quotif A then B called Contrapositive and Contradiction They are actually two versions of a similar approach and we will underscore their differences at the end of this discussion ADVICE Since we will need to negate sentences it is important to review sections 6 and 11 before proceeding J Viola Prioli It is a simple veri cation and a good way to review Truth Tables that x gt y and y gt x have the same truth tables and so they are equivalent Boolean expressions Therefore to prove quotif A then B we can equivalently prove quotif NOT B then NOT A Thus the scheme or quottemplatequot to prove a statement quotif A then B by contrapositive boils down to Unravel NOT B Unravel NOTA Produce the link from NOT B to NOT A Proofs by contrapositive and by contradiction are particular useful when trying to show that some set is empty As a simple illustration we have J Viola Prioli Prove that if A H C Q B then C B A Q Proof Let us state and prove the contrapositive that is if C B H A a Q then A n C is not contained in B Unravel the hypothesis C B n A Q means there is an element x in C B H A Therefore x E C x EB and x E A Unravel the conclusion A 0 C is not contained in B means we must exhibit an element ofA n C that is not an element of B Link From we have that x E C and x E A so x E A n C At the same time by x E B Hence this element x satis es our requirement in The proof is complete A proof by Contradiction is the other indirect technique to be considered Recall that in trying to proof quotif A then B we can never assume the conclusion B to be true However the truth table of A gt B shows that the only possibility for the end result to be false is that A be true and B be false J Viola Prioli The template to prove by contradiction quotif A then B is as follows Assume A to be true B to be false and try to arrive to something impossible that is to a contradiction NOTE a A contradiction might be a violation of a principle a violation ofA which was assumed to be true a violation of a result previously shown etc b Once we arrive to a contradiction we have shown that the negation of quotif A then B is false and so the statement quotif A then B is true Usually a proof by contradiction begins with the sentence lssume for sake of a contradiction that ILLUSTRATIONS J Viola Prioli 1 Prove that no integer is simultaneously even and odd Proof This is rephrased as ifx E Z then x can not be both even and odd Notice that this is A B where A XEZ B x can not be both even and odd Assume for sake of a contradiction that A is true and B is false Hence x is an integer that can be written simultaneously as x 2k some integer k and x 2w 1 some integer w Therefore 2k 2w 1 and so 2k w 1 which gives that k w is 12 This is a contradiction since k w is an integer and 12 is not Having arrived to a contradiction we have proved that the original statement is true J Viola Prioli 2 Prove by contradiction that if 4 divides a2 b2 then a and b are even Proof This is A B where A 4 divides a2 b2 B a is even and b is even Assume for sake of a contradiction that A is true and B is false A true means that a2 b2 4k for some integer k We negate B so a is odd Kb is odd Let us consider for instance that a is odd Then a2 is odd Since a2 b2 4 k we have b2 a2 b2 a2 4k a2 so b must be odd also because quoteven odd is odd Thus b must be odd Therefore we have a 2t1 and b 2w1 with t and w integers 50 4k a2 b2 2t12 2w12 4t2 4t 1 4w2 4w 1 4t2 t w2 w 2 4y2ifwesetyt2tw2w J Viola Prioli Therefore 4k 4y 2 with y an integer and so 2k 2y1 This equality shows that we have arrived to an integer that is simultaneously even and odd This is a contradiction 3 Prove that if a b and a b are prime then a 2 or b 2 Proof Assume for sake of a contradiction that the hypothesis holds but the conclusion is false Thus neither a nor b equals 2 Being prime numbers according to the hypothesis and different from 2 they must be odd and greater than or equal to 3 Thus a b 2 6 Since a and b are odd a b is even But by hypothesis a b is prime so we arrive to the following a b is prime a b 2 6 and a b is even This is a contradiction because the only even prime is 2 How do these two methods compare Observe that in a contrapositive we have only one starting point NOT B and must arrive to NOT A That is done through a link Hence not much information but a clear goal J Viola Prioli On the other hand in a proof by contradiction we have more information A and NOT B which means an edge over the contrapositive However we must arrive to a contradiction but a priori we ignore which contradiction we will end up with Hence more information but the goal is somehow undefined CAUTION Do not confuse quotprove by contradiction with quot nd a counterexample DISCUSSION PROBLEM Suppose we paint each point of the xyplane by using one of either three given colors Blue Red and Yellow Prove that given any positive real number d there exist two points of the same color exactly d units apart J Viola Prioli

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "I made $350 in just two days after posting my first study guide."

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.