怎样证明数学题(英文影印版.第2版)

　　本书介绍了数学证明的基本要点，内容通俗而不失严谨，可以帮助高中以上程度的学生熟悉数学语言，迈入数学殿堂。新版添加了200多个练习题，附录中给出部分练习的答案或提示。
　　 本书适用于任何对逻辑和证明感兴趣的人，数学、计算机科学、哲学、语言学专业的读者都可以从中获益匪浅。

introduction
1　sentential logic
　1.1 deductive reasoning and logical connectives
　1.2 truth tables
　1.3 variables and sets
　1.4 operations on sets
　1.5 the conditional and biconditional connectives
2　quantificational logic
　2.1 quantifiers
　2.2 equivalences involving quantifiers
　2.3 more operations on sets
3　proofs
　3.1 proof strategies
　3.2 proofs involving negations and conditionals
　3.3 proofs involving quantifiers
　3.4 proofs involving conjunctions and biconditionals
　3.5 proofs involving disjunctions
　3.6 existence and uniqueness proofs
　3.7 more examples of proofs
4　relations

　　Introduction
　　Whatismathematics?Highschoolmathematicsisconcernedmostlywithsolv-ing equations and computing answers to numerical questions. College mathe-matics deals with a wider variety of questions, involving not only numbers, but also sets, functions, and other mathematical objects. What ties them together is the use of deductive reasoning to find the answers to questions. When you solve an equation for x you are using the information given by the equation to deduce what the value of x must be. Similarly, when mathematicians solve other kinds of mathematical problems, they always justify their conclusions with deductive reasoning.
　　Deductive reasoning in mathematics is usually presented in the form of a proof. One of the main purposes of this book is to help you develop your mathematical reasoning ability in general, and in particular your ability to read and write proofs. In later chapters we’ll study how proofs are constructed in detail, but ?rst let’s take a look at a few examples of proofs.
　　Don’t worry if you have trouble understanding these proofs. They’re just intended to give you a taste of what mathematical proofs are like. In some cases you may be able to follow many of the steps of the proof, but you may be puzzled about why the steps are combined in the way they are, or how anyone could have thought of the proof. If so, we ask you to be patient. Many of these questions will be answered later in this book, particularly in Chapter 3.
　　All of our examples of proofs in this introduction will involve prime num-bers. Recall that an integer larger than 1 is said to be prime if it cannot be written as a product of two smaller positive integers. For example, 6 is not a prime number, since 6 = 2 · 3, but 7 is a prime number.
　　Before we can give an example of a proof involving prime numbers, we need to find something to prove – some fact about prime numbers whose correctness can be verified with a proof. Sometimes you can find interesting patterns in mathematics just by trying out a calculation on a few numbers. Forexample, consider the table in Figure 1. For each integer n from 2 to 10, the table shows whether or not both n and 2n - 1 are prime, and a surprising pattern emerges. It appears that 2n - 1is prime in precisely those cases in which n is prime!
　　Figure 1
　　Will this pattern continue? It is tempting to guess that it will, but this is only a guess. Mathematicians call such guesses conjectures. Thus, we have the following two conjectures:
　　Conjecture 1. Suppose n is an integer larger than 1 and n is prime. Then 2n - 1 is prime.
　　Conjecture 2. Suppose n is an integer larger than 1 and n is not prime. Then 2n - 1 is not prime.
　　Unfortunately, if we continue the table in Figure 1, we immediately find that Conjecture 1 is incorrect. It is easy to check that 11 is prime, but 211 ? 1 = 2047 = 23 · 89, so 211 ? 1is not prime. Thus, 11 is a counterexample to Conjecture 1. The existence of even one counterexample establishes that the conjecture is incorrect, but it is interesting to note that in this case there are many counterexamples. If we continue checking numbers up to 30, we ?nd two more counterexamples to Conjecture 1: Both 23 and 29 are prime, but 223 ? 1 = 8,388,607 = 47 · 178,481 and 229 ? 1 = 536,870,911 = 2, 089 · 256,999. However, no number up to 30 is a counterexample to Conjecture 2.
　　Do you think that Conjecture 2 is correct? Having found counterexamples to Conjecture 1, we know that this conjecture is incorrect, but our failure to ?nd a
　　Introduction
　　counterexample to Conjecture 2 does not show that it is correct. Perhaps there arecounterexamples,butthesmallestoneislargerthan30.Continuingtocheck examples might uncover a counterexample, or, if it doesn’t, it might increase our con?dence in the conjecture. But we can never be sure that the conjecture is correct if we only check examples. No matter how many examples we check, there is always the possibility that the next one will be the ?rst counterexample. The only way we can be sure that Conjecture 2 is correct is to prove it.
　　In fact, Conjecture 2 is correct. Here is a proof of the conjecture:
　　Proof of Conjecture 2. Since n is not prime, there are positive integers a and b such that a [ n, b [ n, and n =ab. Let x =2b ?1 and y = 1 +2b +22b +···+2(a?1)b. Then
　　xy =(2b ?1) ·(1 +2b +22b +···+2(a?1)b) =2b ·(1 +2b +22b +···+2(a?1)b) ?(1 +2b +22b +···+2(a?1)b) =(2b +22b +23b +···+2ab) ?(1 +2b +22b +···+2(a?1)b) =2ab ?1 =2n ?1.
　　Since b [ n,we can conclude that x =2b ?1 [ 2n ?1. Also, since ab =n ] a,it follows that b ] 1. Therefore, x =2b ?1 ] 21 ?1 =1, so y [ xy =2n ?1. Thus, we have shown that 2n ?1 can be written as the prod-uct of two positive integers x and y, both of which are smaller than 2n ?1, so 2n ?1is not prime. ?
　　Now that the conjecture has been proven, we can call it a theorem. Don’t worry if you ?nd the proof somewhat mysterious. We’ll return to it again at the end of Chapter 3 to analyze how it was constructed. For the moment, the most important point to understand is that if n is any integer larger than 1 that can be written as a product of two smaller positive integers a and b, then the proof gives a method (admittedly, a somewhat mysterious one) of writing 2n ?1asa product of two smaller positive integers x and y. Thus, if n is not prime, then 2n ?1 must also not be prime. For example, suppose n =12, so 2n ?1 =4095. Since 12 =3 ·4, we could take a =3 and b =4in the proof. Then according to the formulas for x and y given in the proof, we would have x =2b ?1 =24 ?1 =15, and y =1 +2b +22b +···+2(a?1)b = 1 +24 +28 =273. And, just as the formulas in the proof predict, we have xy =15 ·273 =4095 =2n ?1. Of course, there are other ways of factoring 12 into a product of two smaller integers, and these might lead to other ways of 4 Introduction factoring 4095. For example, since 12 =2 ·6, we could use the values a =2 and b =6. Try computing the corresponding values of x and y and make sure their product is 4095.
　　Although we already know that Conjecture 1 is incorrect, there are still inter-esting questions we can ask about it. If we continue checking prime numbers n to see if 2n ?1is prime, will we continue to ?nd counterexamples to the conjecture – examples for which 2n ?1is not prime? Will we continue to ?nd examples for which 2n ?1is prime? If there were only ?nitely many prime numbers, then we might be able to investigate these questions by simply check-ing2n ?1foreveryprimenumber n.Butinfacttherearein?nitelymanyprime numbers. Euclid (circa 350 b.c.) gave a proof of this fact in Book IX of his Elements. His proof is one of the most famous in all of mathematics:

　　“本书行文简洁，通俗易懂……习题如此丰富，而且难度各异，层次错落有致……强烈推荐!”
　　 —— MAA Reviews
　　“本书介绍了数学证明的基本要点，非常有价值。”
　　 —— SIAM Review
　　“非常好的一本书！全面而清晰的解释、丰富的例子、附有解答的习题，使它出类拔萃，但凡你要写证明，就应该选择它， 无论是自学还是课堂学习。”
　　——Brent Smith, SIGACT News