DOC PREVIEW
UCF COT 3100 - Intro to Discrete Structures

This preview shows page 1-2-16-17-18-34-35 out of 35 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Intro to Discrete Structures Lecture 8 Pawel M Wocjan School of Electrical Engineering and Computer Science University of Central Florida wocjan eecs ucf edu Intro to Discrete StructuresLecture 8 p 1 35 Proof Strategy We have seen two important methods for proving theorems of the form x P x Q x These two methods are the direct proof and the indirect proof methods It takes some practice solving homework problems to learn to recognize quickly the correct approach Try first the direct approach If it does not work then try the indirect approach Intro to Discrete StructuresLecture 8 p 2 35 Produced with a Trial Version of PDF Annotator www PDFAnnotator com Direct or Indirect Proof Definition The real number r is rational if there exist integers p and q with q 6 0 such that r p q Example 7 Prove that the sum of two rational numbers is rational Intro to Discrete StructuresLecture 8 p 3 35 Produced with a Trial Version of PDF Annotator www PDFAnnotator com Direct or Indirect Proof Example 8 Prove that if n is an integer and n2 is odd then n is odd Intro to Discrete StructuresLecture 8 p 4 35 Produced with a Trial Version of PDF Annotator www PDFAnnotator com Proof by Contradiction I Suppose we want to prove that p is true Furthermore suppose that we can find a contradiction q such that p q is true Because q is false but p is true we can conclude that p is false which means that p is true Intro to Discrete StructuresLecture 8 p 5 35 Proof by Contradiction II The statement r r is a contradiction whenever r is a proposition Therefore we can prove that p is true if we can show that p r r is true for some proposition r Intro to Discrete StructuresLecture 8 p 6 35 Proof by Contradiction III Example 9 Show that at least four of any 22 days must fall on the same day of the week Intro to Discrete StructuresLecture 8 p 7 35 Proof by Contradiction IV p At least four of 22 days chosen fall on the same day of the week Suppose p is true This means that at most three days of the 22 days fall on the same day This implies that at most 21 days could have been chosen This contradicts the hypothesis that we have 22 days under consideration r 22 days are chosen p r r Intro to Discrete StructuresLecture 8 p 8 35 Produced with a Trial Version of PDF Annotator www PDFAnnotator com 2 is irrational Intro to Discrete StructuresLecture 8 p 9 35 2 is irrational Intro to Discrete StructuresLecture 8 p 10 35 Reading Assignment Examples 11 14 Subsection Mistakes in Proofs Intro to Discrete StructuresLecture 8 p 11 35 Produced with a Trial Version of PDF Annotator www PDFAnnotator com Exhaustive Proof Prove that n 1 2 3n if n is a positive integer with n 4 Intro to Discrete StructuresLecture 8 p 12 35 Produced with a Trial Version of PDF Annotator www PDFAnnotator com Proof by Cases Based on the logical equivalence p1 p2 pn q p1 q p2 q pn q Intro to Discrete StructuresLecture 8 p 13 35 Produced with a Trial Version of PDF Annotator www PDFAnnotator com Proof by Cases Example 3 Prove that if n is an integer then n2 n Intro to Discrete StructuresLecture 8 p 14 35 Produced with a Trial Version of PDF Annotator www PDFAnnotator com Proof by Cases Example 4 Use a proof by cases to show that xy x y where x and y are real numbers Intro to Discrete StructuresLecture 8 p 15 35 Produced with a Trial Version of PDF Annotator www PDFAnnotator com Proof by Cases Example 5 Formulate a conjecture about the decimal digits that occur as the final digit of the square of an integer and prove your result Intro to Discrete StructuresLecture 8 p 16 35 Existence Proofs Many theorems are assertions that objects of a particular type exist A theorem of this type is a proposition of the form xP x where P is a predicate A proof of a proposition of the form xP x is called existence proof Intro to Discrete StructuresLecture 8 p 17 35 Constructive vs Nonconstructive Constructive Existence Proof Sometimes an existence proof can be given by finding a concrete element a such that P a is T Nonconstructive Existence Proof We do not find an element a such that P a is T but rather prove that xP x is true in some other way One common method of give a nonconstructive proof is to use proof by contradiction and show the negation of the existential quantifier implies a contradiction Intro to Discrete StructuresLecture 8 p 18 35 A Constructive Existence Proof Show that there is a positive integer that can be written as the sum of cubes of positive integers in two different ways Intro to Discrete StructuresLecture 8 p 19 35 A Constructive Existence Proof Show that there is a positive integer that can be written as the sum of cubes of positive integers in two different ways Solution After considerable computation such as computer search we find that 1729 103 93 123 13 Because we have displayed a positive integer that can be written as the sum of cubes in two different ways we are done Intro to Discrete StructuresLecture 8 p 20 35 Produced with a Trial Version of PDF Annotator www PDFAnnotator com Nonconstructive Existence Proof Show that there exist irrational numbers x and y such that xy is rational Intro to Discrete StructuresLecture 8 p 21 35 Nonconstructive Existence Proof Show that there exist irrational numbers x and y such that xy is rational Recall that 2 is irrational Consider the number 2 2 2 If 2 is rational we have two irrational numbers x and y with xy rational namely x 2 and y 2 2 On the other hand if 2 is irrational then we can 2 let x 2 and y 2 so that x y 2 2 2 2 2 2 2 2 2 Intro to Discrete StructuresLecture 8 p 22 35 Produced with a Trial Version of PDF Annotator www PDFAnnotator com Chomp Intro to Discrete StructuresLecture 8 p 23 35 Uniqueness Proof Some theorems assert the existence of a unique element with a particular property The two parts of uniqueness proof are Existence We show that there is an element x with the desired property Uniqueness We show that if y 6 x then y does not have the desired property This is the same as showing that x P x y y 6 x P y is true Intro to Discrete StructuresLecture 8 p 24 35 Uniqueness Proof Example 13 Show that if a and b are real numbers and a 6 0 then there exists a unique real number r such that ar b 0 Intro to Discrete StructuresLecture 8 p 25 35 Reading Assignment Lab Read pages 93 end of Chapter 1 on your own The teaching assistants will go over material relevant to proofs …


View Full Document

UCF COT 3100 - Intro to Discrete Structures

Documents in this Course
Lab 1

Lab 1

11 pages

Functions

Functions

10 pages

Load more
Download Intro to Discrete Structures
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Intro to Discrete Structures and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Intro to Discrete Structures 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?