Mathematics for Computer Science
1.6. Proving an “If and Only If ” 13 1.5.2 Method #2 - Prove the Contrapositive An implication (“PIMPLIESQ”) is logically equiva ...
Chapter 1 What is a Proof?14 1.6.1 Method #1: Prove Each Statement Implies the Other The statement “PIFFQ” is equivalent to the ...
1.7. Proof by Cases 15 Now since zero is the only number whose square root is zero, equation (1.4) holds iff .x 1 /^2 C.x 2 /^ ...
Chapter 1 What is a Proof?16 Case 1.1: No pair among those people met each other. Then these people are a group of at least 3 st ...
1.9. Good Proofs in Practice 17 Example We’ll prove by contradiction that p 2 is irrational. Remember that a number isra- tional ...
Chapter 1 What is a Proof?18 Keep a linear flow. Sometimes proofs are written like mathematical mosaics, with juicy tidbits of i ...
1.10. References 19 Creating a good proof is a lot like creating a beautiful work of art. In fact, mathematicians often refer to ...
Chapter 1 What is a Proof?20 triangle, andcis the length of its hypotenuse, then a^2 Cb^2 Dc^2 : This theorem is so fundamental ...
1.10. References 21 about the shape of these particular triangles and square that makes the rearranging possible—for example, su ...
Chapter 1 What is a Proof?22 (b)Bogus proof: 1 ¢D$0:01D.$0:1/^2 D.10¢/^2 D 100 ¢D$1: (c) Bogus Claim: Ifaandbare two equal rea ...
1.10. References 23 Problem 1.5. Albert announces to his class that he plans to surprise them with a quiz sometime next week. Hi ...
Chapter 1 What is a Proof?24 Problems for Section 1.8 Practice Problems Problem 1.8. Prove that for anyn > 0, ifanis even, th ...
1.10. References 25 least integer,q > 0, such that p 2 1 qis a nonnegative integer. Letq^0 WWD p 2 1 q. Clearly0 < ...
Chapter 1 What is a Proof?26 Problem 1.17. FornD 40 , the value of polynomialp.n/WWDn^2 CnC 41 is not prime, as noted in Section ...
2 The Well Ordering Principle Everynonemptyset ofnonnegative integershas asmallestelement. This statement is known as TheWell Or ...
Chapter 2 The Well Ordering Principle28 so any way of expressing the left hand fraction in lowest terms would also work for m 0 ...
2.2. Template for Well Ordering Proofs 29 Theorem 2.2.1. 1 C 2 C 3 CCnDn.nC1/=2 (2.1) for all nonnegative integers,n. First, ...
Chapter 2 The Well Ordering Principle30 Sincecis the smallest counterexample, we know that (2.1) is false fornDcbut true for all ...
2.4. Well Ordered Sets 31 primesq 1 ql. Therefore,nDp 1 pkq 1 qlcan be written as a product of primes, contradicting th ...
Chapter 2 The Well Ordering Principle32 Definition 2.4.2.Alower bound(respectively,upper bound) for a set,S, of real numbers is ...
«
1
2
3
4
5
6
7
8
9
10
»
Free download pdf
