Mathematics for Computer Science
1.5. Proving an Implication 13 way instead; we’re just giving you something youcouldsay so that you’re never at a complete loss. ...
Chapter 1 What is a Proof?14 So far, so good. But we still have to replace all those “seems like” phrases with solid, logical ar ...
1.6. Proving an “If and Only If ” 15 Example Theorem 1.5.2.Ifris irrational, then p ris also irrational. A number isrationalwhen ...
Chapter 1 What is a Proof?16 1.6.2 Method #2: Construct a Chain of Iffs In order to prove thatPis true iffQis true: Write, “We ...
1.7. Proof by Cases 17 1.7 Proof by Cases Breaking a complicated proof into cases and proving each case separately is a use- ful ...
Chapter 1 What is a Proof?18 Case 2.1: Every pair among those people met each other. Then these people are a club of at least 3 ...
1.9. Good Proofs in Practice 19 2d^2 is a multiple of 4 and sod^2 is a multiple of 2. This implies thatdis a multiple of 2. So t ...
Chapter 1 What is a Proof?20 explanation, making it very hard to follow. This is bad. A good proof usually looks like an essay w ...
1.9. Good Proofs in Practice 21 Throughout the text there are also examples ofbogus proofs—arguments that look like proofs but a ...
Chapter 1 What is a Proof?22 Homework Problems Problem 1.4. FornD 40 , the value of polynomialp.n/WWDn^2 CnC 41 is not prime, as ...
1.9. Good Proofs in Practice 23 teammates for a few minutes and summarize your team’s answers on your white- board. Problem 1.7. ...
...
2 The Well Ordering Principle Everynonemptyset ofnonnegative integershas asmallestelement. This statement is known as TheWell Or ...
Chapter 2 The Well Ordering Principle26 m 0 =n 0 , which implies the fraction m 0 =p n 0 =p cannot be in written in lowest terms ...
2.3. Summing the Integers 27 Theorem 2.3.1. 1 C 2 C 3 CCnDn.nC1/=2 (2.1) for all nonnegative integers,n. First, we better add ...
Chapter 2 The Well Ordering Principle28 meansc 1 is a nonnegative integer, and since it is less thanc, equation (2.1) is true fo ...
2.4. Factoring into Primes 29 Problems for Section 2.2 Practice Problems Problem 2.1. For practice using the Well Ordering Princ ...
Chapter 2 The Well Ordering Principle30 LetCbe the set ofcounterexamplesto (*), namely^3 CWWDfnj:::g Assume for the purpose of o ...
2.4. Factoring into Primes 31 Exam Problems Problem 2.5. The (flawed) proof below uses the Well Ordering Principle to prove that ...
Chapter 2 The Well Ordering Principle32 F.0/WWD0; (2.3) F.1/WWD1; (2.4) F.n/WWDF.n1/CF.n2/ forn2: (2.5) Indicate exactly which ...
«
1
2
3
4
5
6
7
8
9
10
»
Free download pdf
