{"id":23257,"date":"2023-03-28T01:47:14","date_gmt":"2023-03-28T01:47:14","guid":{"rendered":"https:\/\/www.booksofall.com\/vi\/?post_type=product&p=23257"},"modified":"2023-03-28T01:55:20","modified_gmt":"2023-03-28T01:55:20","slug":"mathematics-for-computer-science","status":"publish","type":"product","link":"https:\/\/www.booksofall.com\/vi\/mathematics-for-computer-science\/","title":{"rendered":"Mathematics for Computer Science"},"content":{"rendered":"

1 What is a Proof?<\/h2>\n

1.1 Propositions<\/h3>\n

Definition<\/strong>. A proposition<\/a> is a statement (communication) that is either true or false.<\/p>\n

For example, both of the following statements are propositions. The first is true, and the second is false.<\/p>\n

Proposition 1.1.1.<\/strong> 2 + 3 = 5.<\/p>\n

Proposition 1.1.2.<\/strong> 1 + 1 = 3.<\/p>\n

Being true or false doesn\u2019t sound like much of a limitation, but it does exclude statements such as \u201cWherefore art thou Romeo?\u201d and \u201cGive me an A!\u201d It also excludes statements whose truth varies with circumstance such as, \u201cIt\u2019s five o\u2019clock,\u201d or \u201cthe stock market will rise tomorrow.\u201d<\/p>\n

Unfortunately it is not always easy to decide if a claimed proposition is true or false:<\/p>\n

Claim 1.1.3.<\/strong> For every nonnegative integer n the value of n2 C nC 41 is prime<\/a>.<\/p>\n

(A prime is an integer greater than 1 that is not divisible by any other integer greater than 1. For example, 2, 3, 5, 7, 11, are the first five primes.) Let\u2019s try some numerical experimentation to check this proposition. Let<\/p>\n

\"\"<\/p>\n

We begin with p.0\/ D 41, which is prime; then<\/p>\n

\"\"<\/p>\n

are each prime. Hmmm, starts to look like a plausible claim. In fact we can keep checking through n D 39 and confirm that p.39\/ D 1601 is prime.<\/p>\n

But \"\" , which is not prime. So Claim 1.1.3 is false since it\u2019s not true that \"\" is prime for all nonnegative integers n. In fact, it\u2019s not hard to show that no polynomial with integer coefficients can map all nonnegative numbers into prime numbers, unless it\u2019s a constant (see Problem 1.25). But this example highlights the point that, in general, you can\u2019t check a claim about an infinite set by checking a finite sample of its elements, no matter how large the sample.<\/p>\n

By the way, propositions like this about all numbers or all items of some kind are so common that there is a special notation for them. With this notation, Claim 1.1.3 would be<\/p>\n

\"\"<\/p>\n

Here the symbol 8 is read \u201cfor all.\u201d The symbol N stands for the set of nonnegative integers<\/a>: 0, 1, 2, 3, . . . (ask your instructor for the complete list). The symbol \u201c2\u201d is read as \u201cis a member of,\u201d or \u201cbelongs to,\u201d or simply as \u201cis in.\u201d The period after the N is just a separator between phrases.<\/p>\n

Here are two even more extreme examples:<\/p>\n

Conjecture.<\/strong> [Euler] The equation<\/p>\n

\"\"<\/p>\n

has no solution when a; b; c; d are positive integers<\/a>. Euler (pronounced \u201coiler\u201d) conjectured this in 1769. But the conjecture was proved false 218 years later by Noam Elkies<\/a> at a liberal arts school up Mass Ave. The solution he found was a D 95800; b D 217519; c D 414560; d D 422481.<\/p>\n

In logical notation, Euler\u2019s Conjecture could be written,<\/p>\n

\"\"<\/p>\n

Here, ZC is a symbol for the positive integers. Strings of 8\u2019s like this are usually abbreviated for easier reading:<\/p>\n

\"\"<\/p>\n

Here\u2019s another claim which would be hard to falsify by sampling: the smallest<\/p>\n

possible x; y; z that satisfy the equality each have more than 1000 digits!<\/p>\n

False Claim.<\/strong> \"\" has no solution when \"\".<\/p>\n

It\u2019s worth mentioning a couple of further famous propositions whose proofs were sought for centuries before finally being discovered:<\/p>\n

Proposition 1.1.4<\/strong> (Four Color Theorem). Every map can be colored with 4 colors so that adjacent2 regions have different colors.<\/p>\n","protected":false},"excerpt":{"rendered":"