DARTMOUTH COSC 030 - 04proofs (2 pages)

Previewing page 1 of 2 page document View the full content.
View Full Document

04proofs



Previewing page 1 of actual document.

View the full content.
View Full Document
View Full Document

04proofs

43 views


Pages:
2
School:
Dartmouth College
Course:
Cosc 030 - Discrete Math Computer Sci
Discrete Math Computer Sci Documents
Unformatted text preview:

A Direct Proof CS 30 Discrete Mathematics Amit Chakrabarti Styles of Proof Another Direct Proof Using Cases Theorem A B B A A B A B Proof Consider arbitrary x A B B A Then either x A B or x B A Case 1 x A B Then x A so x A B Also x B so x A B Therefore x A B A B Case 2 x B A Then x B so x A B Also x A so x A B Therefore x A B A B Thus in all cases x A B A B QED Theorem Function d Z Z given by d x 2x is injective Recall deDinition f A B is injective means for every x y A if x y then f x f y i e x y A x y f x f y i e x y A f x f y x y Proof Consider arbitrary x y Z Suppose d x d y Then 2x 2y Therefore x y Thus d is injective QED A Proof by Contradiction Theorem Function d Z Z given by d x 2x is injective Recall deDinition f A B is injective means x y A f x f y x y Proof Suppose to the contrary that d is not injective Then x y Z d x d y x y So x y Z d x d y x y So x y Z 2x 2y x y So x y Z x y x y But this is a contradiction QED Proof by Contradiction 2300 yr old Classic Another Classic Proof by Contradiction Theorem There are inDinitely many primes Proof Suppose to the contrary that of primes is Dinite Full list of primes 2 3 5 p Consider the integer n 2 3 5 p 1 Dividing n by 2 leaves remainder 1 so 2 is not a factor of n Dividing n by 3 leaves remainder 1 so 3 is not a factor of n Dividing n by p leaves remainder 1 so p is not a factor of n But n must have some prime factor possibly n itself This factor is a prime greater than p Contradiction QED Theorem 2 is irrational Proof Suppose to the contrary that 2 Q Then p q N s t 2 p q in lowest terms i e gcd p q 1 So p2 2q2 Thus p2 is even Therefore p is even Because if p were odd its square would be odd Exercise Prove this Let p 2r Substituting we get 2r 2 2q2 So 2r2 q2 Thus q2 is even Therefore q is even Since both p and q are even gcd p q 1 Contradiction QED


View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view 04proofs 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 04proofs 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?