Lecture notes on Mathematical foundation of Computer science

mathematical foundation of computer science pdf free
AustinCraig Profile Pic
Published Date:09-07-2017
Your Website URL(Optional)
“mcs-ftl” — 2010/9/8 — 0:40 — page i — 1 Mathematics for Computer Science th revised Wednesday 8 September, 2010, 00:40 Eric Lehman Google Inc. F Thomson Leighton Department of Mathematics and CSAIL, MIT Akamai Technologies Albert R Meyer Massachusets Institute of Technology Copyright © 2010, Eric Lehman, F Tom Leighton, Albert R Meyer . All rights reserved.“mcs-ftl” — 2010/9/8 — 0:40 — page ii — 2“mcs-ftl” — 2010/9/8 — 0:40 — page iii — 3 Contents I Proofs 1 Propositions 5 1.1 Compound Propositions 6 1.2 Propositional Logic in Computer Programs 10 1.3 Predicates and Quantifiers 11 1.4 Validity 19 1.5 Satisfiability 21 2 Patterns of Proof 23 2.1 The Axiomatic Method 23 2.2 Proof by Cases 26 2.3 Proving an Implication 27 2.4 Proving an “If and Only If” 30 2.5 Proof by Contradiction 32 2.6 Proofs about Sets 33 2.7 Good Proofs in Practice 40 3 Induction 43 3.1 The Well Ordering Principle 43 3.2 Ordinary Induction 46 3.3 Invariants 56 3.4 Strong Induction 64 3.5 Structural Induction 69 4 Number Theory 81 4.1 Divisibility 81 4.2 The Greatest Common Divisor 87 4.3 The Fundamental Theorem of Arithmetic 94 4.4 Alan Turing 96 4.5 Modular Arithmetic 100 4.6 Arithmetic with a Prime Modulus 103 4.7 Arithmetic with an Arbitrary Modulus 108 4.8 The RSA Algorithm 113“mcs-ftl” — 2010/9/8 — 0:40 — page iv — 4 iv Contents II Structures 5 Graph Theory 121 5.1 Definitions 121 5.2 Matching Problems 128 5.3 Coloring 143 5.4 Getting fromA toB in a Graph 147 5.5 Connectivity 151 5.6 Around and Around We Go 156 5.7 Trees 162 5.8 Planar Graphs 170 6 Directed Graphs 189 6.1 Definitions 189 6.2 Tournament Graphs 192 6.3 Communication Networks 196 7 Relations and Partial Orders 213 7.1 Binary Relations 213 7.2 Relations and Cardinality 217 7.3 Relations on One Set 220 7.4 Equivalence Relations 222 7.5 Partial Orders 225 7.6 Posets and DAGs 226 7.7 Topological Sort 229 7.8 Parallel Task Scheduling 232 7.9 Dilworth’s Lemma 235 8 State Machines 237 III Counting 9 Sums and Asymptotics 243 9.1 The Value of an Annuity 244 9.2 Power Sums 250 9.3 Approximating Sums 252 9.4 Hanging Out Over the Edge 257 9.5 Double Trouble 269 9.6 Products 272“mcs-ftl” — 2010/9/8 — 0:40 — page v — 5 v Contents 9.7 Asymptotic Notation 275 10 Recurrences 283 10.1 The Towers of Hanoi 284 10.2 Merge Sort 291 10.3 Linear Recurrences 294 10.4 Divide-and-Conquer Recurrences 302 10.5 A Feel for Recurrences 309 11 Cardinality Rules 313 11.1 Counting One Thing by Counting Another 313 11.2 Counting Sequences 314 11.3 The Generalized Product Rule 317 11.4 The Division Rule 321 11.5 Counting Subsets 324 11.6 Sequences with Repetitions 326 11.7 Counting Practice: Poker Hands 329 11.8 Inclusion-Exclusion 334 11.9 Combinatorial Proofs 339 11.10 The Pigeonhole Principle 342 11.11 A Magic Trick 346 12 Generating Functions 355 12.1 Definitions and Examples 355 12.2 Operations on Generating Functions 356 12.3 Evaluating Sums 361 12.4 Extracting Coefficients 363 12.5 Solving Linear Recurrences 370 12.6 Counting with Generating Functions 374 13 Infinite Sets 379 13.1 Injections, Surjections, and Bijections 379 13.2 Countable Sets 381 13.3 Power Sets Are Strictly Bigger 384 13.4 Infinities in Computer Science 386 IV Probability 14 Events and Probability Spaces 391 14.1 Let’s Make a Deal 391 14.2 The Four Step Method 392“mcs-ftl” — 2010/9/8 — 0:40 — page vi — 6 vi Contents 14.3 Strange Dice 402 14.4 Set Theory and Probability 411 14.5 Infinite Probability Spaces 413 15 Conditional Probability 417 15.1 Definition 417 15.2 Using the Four-Step Method to Determine Conditional Probability 418 15.3 A Posteriori Probabilities 424 15.4 Conditional Identities 427 16 Independence 431 16.1 Definitions 431 16.2 Independence Is an Assumption 432 16.3 Mutual Independence 433 16.4 Pairwise Independence 435 16.5 The Birthday Paradox 438 17 Random Variables and Distributions 445 17.1 Definitions and Examples 445 17.2 Distribution Functions 450 17.3 Bernoulli Distributions 452 17.4 Uniform Distributions 453 17.5 Binomial Distributions 456 18 Expectation 467 18.1 Definitions and Examples 467 18.2 Expected Returns in Gambling Games 477 18.3 Expectations of Sums 483 18.4 Expectations of Products 490 18.5 Expectations of Quotients 492 19 Deviations 497 19.1 Variance 497 19.2 Markov’s Theorem 507 19.3 Chebyshev’s Theorem 513 19.4 Bounds for Sums of Random Variables 516 19.5 Mutually Independent Events 523 20 Random Walks 533 20.1 Unbiased Random Walks 533 20.2 Gambler’s Ruin 542 20.3 Walking in Circles 549“mcs-ftl” — 2010/9/8 — 0:40 — page 1 — 7 I Proofs“mcs-ftl” — 2010/9/8 — 0:40 — page 2 — 8“mcs-ftl” — 2010/9/8 — 0:40 — page 3 — 9 Introduction This text explains how to use mathematical models and methods to analyze prob- lems that arise in computer science. The notion of a proof plays a central role in this work. Simply put, a proof is a method of establishing truth. Like beauty, “truth” some- times depends on the eye of the beholder, and it should not be surprising that what constitutes a proof differs among fields. For example, in the judicial system, legal truth is decided by a jury based on the allowable evidence presented at trial. In the business world, authoritative truth is specified by a trusted person or organization, 1 or maybe just your boss. In fields such as physics and biology, scientific truth is confirmed by experiment. In statistics, probable truth is established by statistical analysis of sample data. Philosophical proof involves careful exposition and persuasion typically based on a series of small, plausible arguments. The best example begins with “Cogito ergo sum,” a Latin sentence that translates as “I think, therefore I am.” It comes from the beginning of a 17th century essay by the mathematician/philosopher, Rene ´ Descartes, and it is one of the most famous quotes in the world: do a web search on the phrase and you will be flooded with hits. Deducing your existence from the fact that you’re thinking about your existence is a pretty cool and persuasive-sounding idea. However, with just a few more lines of argument in this vein, Descartes goes on to conclude that there is an infinitely beneficent God. Whether or not you believe in a beneficent God, you’ll probably agree that any very short proof of God’s existence is bound to be far-fetched. So 1 Actually, only scientific falsehood can be demonstrated by an experiment—when the experiment fails to behave as predicted. But no amount of experiment can confirm that the next experiment won’t fail. For this reason, scientists rarely speak of truth, but rather of theories that accurately predict past, and anticipated future, experiments.“mcs-ftl” — 2010/9/8 — 0:40 — page 4 — 10 4 Part I Proofs even in masterful hands, this approach is not reliable. Mathematics has its own specific notion of “proof.” Definition. A mathematical proof of a proposition is a chain of logical deductions leading to the proposition from a base set of axioms. The three key ideas in this definition are highlighted: proposition, logical de- duction, and axiom. These three ideas are explained in the following chapters, beginning with propositions in Chapter 1. We will then provide lots of examples of proofs and even some examples of “false proofs” (that is, arguments that look like a proof but that contain missteps, or deductions that aren’t so logical when exam- ined closely). False proofs are often even more important as examples than correct proofs, because they are uniquely helpful with honing your skills at making sure each step of a proof follows logically from prior steps. Creating a good proof is a lot like creating a beautiful work of art. In fact, mathematicians often refer to really good proofs as being “elegant” or “beautiful.” As with any endeavor, it will probably take a little practice before your fellow students use such praise when referring to your proofs, but to get you started in the right direction, we will provide templates for the most useful proof techniques in Chapters 2 and 3. We then apply these techniques in Chapter 4 to establish some important facts about numbers; facts that form the underpinning of one of the world’s most widely-used cryptosystems.“mcs-ftl” — 2010/9/8 — 0:40 — page 5 — 11 1 Propositions Definition. A proposition is a statement that is either true or false. For example, both of the following statements are propositions. The first is true and the second is false. Proposition 1.0.1. 2 + 3 = 5. Proposition 1.0.2. 1 + 1 = 3. Being true or false doesn’t sound like much of a limitation, but it does exclude statements such as, “Wherefore art thou Romeo?” and “Give me an A”. Unfortunately, it is not always easy to decide if a proposition is true or false, or even what the proposition means. In part, this is because the English language is riddled with ambiguities. For example, consider the following statements: 1. “You may have cake, or you may have ice cream.” 2. “If pigs can fly, then you can understand the Chebyshev bound.” 3. “If you can solve any problem we come up with, then you get an A for the course.” 4. “Every American has a dream.” What precisely do these sentences mean? Can you have both cake and ice cream or must you choose just one dessert? If the second sentence is true, then is the Chebyshev bound incomprehensible? If you can solve some problems we come up with but not all, then do you get an A for the course? And can you still get an A even if you can’t solve any of the problems? Does the last sentence imply that all Americans have the same dream or might some of them have different dreams? Some uncertainty is tolerable in normal conversation. But when we need to formulate ideas precisely—as in mathematics and programming—the ambiguities inherent in everyday language can be a real problem. We can’t hope to make an exact argument if we’re not sure exactly what the statements mean. So before we start into mathematics, we need to investigate the problem of how to talk about mathematics. To get around the ambiguity of English, mathematicians have devised a special mini-language for talking about logical relationships. This language mostly uses ordinary English words and phrases such as “or”, “implies”, and “for all”. But“mcs-ftl” — 2010/9/8 — 0:40 — page 6 — 12 6 Chapter 1 Propositions mathematicians endow these words with definitions more precise than those found in an ordinary dictionary. Without knowing these definitions, you might sometimes get the gist of statements in this language, but you would regularly get misled about what they really meant. Surprisingly, in the midst of learning the language of mathematics, we’ll come across the most important open problem in computer science—a problem whose solution could change the world. 1.1 Compound Propositions In English, we can modify, combine, and relate propositions with words such as “not”, “and”, “or”, “implies”, and “if-then”. For example, we can combine three propositions into one like this: If all humans are mortal and all Greeks are human, then all Greeks are mortal. For the next while, we won’t be much concerned with the internals of propositions— whether they involve mathematics or Greek mortality—but rather with how propo- sitions are combined and related. So we’ll frequently use variables such asP and Q in place of specific propositions such as “All humans are mortal” and “2C3D 5”. The understanding is that these variables, like propositions, can take on only the values T (true) and F (false). Such true/false variables are sometimes called Boolean variables after their inventor, George—you guessed it—Boole. 1.1.1 NOT, AND, and OR We can precisely define these special words using truth tables. For example, if P denotes an arbitrary proposition, then the truth of the proposition “NOT.P/” is defined by the following truth table: P NOT.P/ T F F T The first row of the table indicates that when propositionP is true, the proposition “NOT.P/” is false. The second line indicates that whenP is false, “NOT.P/” is true. This is probably what you would expect. In general, a truth table indicates the true/false value of a proposition for each possible setting of the variables. For example, the truth table for the proposition“mcs-ftl” — 2010/9/8 — 0:40 — page 7 — 13 1.1. Compound Propositions 7 “P ANDQ” has four lines, since the two variables can be set in four different ways: P Q P ANDQ T T T T F F F T F F F F According to this table, the proposition “P ANDQ” is true only whenP andQ are both true. This is probably the way you think about the word “and.” There is a subtlety in the truth table for “P ORQ”: P Q P ORQ T T T T F T F T T F F F The third row of this table says that “P ORQ” is true even if bothP andQ are true. This isn’t always the intended meaning of “or” in everyday speech, but this is the standard definition in mathematical writing. So if a mathematician says, “You may have cake, or you may have ice cream,” he means that you could have both. If you want to exclude the possibility of both having and eating, you should use “exclusive-or” (XOR): P Q P XORQ T T F T F T F T T F F F 1.1.2 IMPLIES The least intuitive connecting word is “implies.” Here is its truth table, with the lines labeled so we can refer to them later. P Q P IMPLIESQ T T T (tt) T F F (tf) F T T (ft) F F T (ff) Let’s experiment with this definition. For example, is the following proposition true or false?“mcs-ftl” — 2010/9/8 — 0:40 — page 8 — 14 8 Chapter 1 Propositions 2 “If the Riemann Hypothesis is true, thenx 0 for every real numberx.” The Riemann Hypothesis is a famous unresolved conjecture in mathematics —no one knows if it is true or false. But that doesn’t prevent you from answering the question This proposition has the formP IMPLIESQ where the hypothesis,P , is 2 “the Riemann Hypothesis is true” and the conclusion,Q, is “x 0 for every real numberx”. Since the conclusion is definitely true, we’re on either line (tt) or line (ft) of the truth table. Either way, the proposition as a while is true One of our original examples demonstrates an even stranger side of implications. “If pigs can fly, then you can understand the Chebyshev bound.” Don’t take this as an insult; we just need to figure out whether this proposition is true or false. Curiously, the answer has nothing to do with whether or not you can understand the Chebyshev bound. Pigs cannot fly, so we’re on either line (ft) or line (ff) of the truth table. In both cases, the proposition is true In contrast, here’s an example of a false implication: “If the moon shines white, then the moon is made of white cheddar.” Yes, the moon shines white. But, no, the moon is not made of white cheddar cheese. So we’re on line (tf) of the truth table, and the proposition is false. The truth table for implications can be summarized in words as follows: An implication is true exactly when the if-part is false or the then-part is true. This sentence is worth remembering; a large fraction of all mathematical statements are of the if-then form 1.1.3 IFF Mathematicians commonly join propositions in one additional way that doesn’t arise in ordinary speech. The proposition “P if and only ifQ” asserts thatP and Q are logically equivalent; that is, either both are true or both are false. P Q P IFFQ T T T T F F F T F F F T For example, the following if-and-only-if statement is true for every real number x: 2 x 40 iff jxj2 For some values of x, both inequalities are true. For other values of x, neither inequality is true . In every case, however, the proposition as a whole is true.“mcs-ftl” — 2010/9/8 — 0:40 — page 9 — 15 1.1. Compound Propositions 9 1.1.4 Notation Mathematicians have devised symbols to represent words like “AND” and “NOT”. The most commonly-used symbols are summarized in the table below. English Symbolic Notation NOT.P/ :P (alternatively,P ) P ANDQ PQ P ORQ P_Q P IMPLIESQ PQ ifP thenQ PQ P IFFQ P Q For example, using this notation, “IfP AND NOT.Q/, thenR” would be written: .PQ/R This symbolic language is helpful for writing complicated logical expressions com- pactly. But words such as “OR” and “IMPLIES” generally serve just as well as the symbols_ and, and their meaning is easy to remember. We will use the prior notation for the most part in this text, but you can feel free to use whichever con- vention is easiest for you. 1.1.5 Logically Equivalent Implications Do these two sentences say the same thing? If I am hungry, then I am grumpy. If I am not grumpy, then I am not hungry. We can settle the issue by recasting both sentences in terms of propositional logic. LetP be the proposition “I am hungry”, and letQ be “I am grumpy”. The first sentence says “P IMPLIES Q” and the second says “NOT.Q/ IMPLIES NOT.P/”. We can compare these two statements in a truth table: P Q P IMPLIESQ NOT.Q/ IMPLIES NOT.P/ T T T T T F F F F T T T F F T T Sure enough, the columns of truth values under these two statements are the same, which precisely means they are equivalent. In general, “NOT.Q/ IMPLIES NOT.P/”“mcs-ftl” — 2010/9/8 — 0:40 — page 10 — 16 10 Chapter 1 Propositions is called the contrapositive of the implication “P IMPLIESQ.” And, as we’ve just shown, the two are just different ways of saying the same thing. In contrast, the converse of “P IMPLIES Q” is the statement “Q IMPLIES P ”. In terms of our example, the converse is: If I am grumpy, then I am hungry. This sounds like a rather different contention, and a truth table confirms this suspi- cion: P Q P IMPLIESQ Q IMPLIESP T T T T T F F T F T T F F F T T Thus, an implication is logically equivalent to its contrapositive but is not equiva- lent to its converse. One final relationship: an implication and its converse together are equivalent to an iff statement. For example, If I am grumpy, then I am hungry, AND if I am hungry, then I am grumpy. are equivalent to the single statement: I am grumpy IFF I am hungry. Once again, we can verify this with a truth table: P Q .P IMPLIESQ/ .Q IMPLIESP/ .P IMPLIESQ/ AND.Q IMPLIESP/ P IFFQ T T T T T T T F F T F F F T T F F F F F T T T T 1.2 Propositional Logic in Computer Programs Propositions and logical connectives arise all the time in computer programs. For example, consider the following snippet, which could be either C, C++, or Java: if ( x 0 (x = 0 && y 100) ) : : : (further instructions)“mcs-ftl” — 2010/9/8 — 0:40 — page 11 — 17 1.3. Predicates and Quantifiers 11 The symbol denotes “OR”, and the symbol && denotes “AND”. The further instructions are carried out only if the proposition following the word if is true. On closer inspection, this big expression is built from two simpler propositions. LetA be the proposition thatx 0, and letB be the proposition thaty 100. Then we can rewrite the condition “A OR.NOT.A/ ANDB/”. A truth table reveals that this complicated expression is logically equivalent to “A ORB”. A B A OR.NOT.A/ ANDB/ A ORB T T T T T F T T F T T T F F F F This means that we can simplify the code snippet without changing the program’s behavior: if ( x 0 y 100 ) : : : (further instructions) Rewriting a logical expression involving many variables in the simplest form is both difficult and important. Simplifying expressions in software can increase the speed of your program. Chip designers face a similar challenge—instead of minimizing&& and symbols in a program, their job is to minimize the number of analogous physical devices on a chip. The payoff is potentially enormous: a chip with fewer devices is smaller, consumes less power, has a lower defect rate, and is cheaper to manufacture. 1.3 Predicates and Quantifiers 1.3.1 Propositions with Infinitely Many Cases Most of the examples of propositions that we have considered thus far have been straightforward in the sense that it has been relatively easy to determine if they are true or false. At worse, there were only a few cases to check in a truth table. Unfortunately, not all propositions are so easy to check. That is because some propositions may involve a large or infinite number of possible cases. For example, consider the following proposition involving prime numbers. (A prime is an integer greater than 1 that is divisible only by itself and 1. For example, 2, 3, 5, 7, and 11“mcs-ftl” — 2010/9/8 — 0:40 — page 12 — 18 12 Chapter 1 Propositions are primes, but 4, 6, and 9 are not. A number greater than 1 that is not prime is said to be composite.) 2 Proposition 1.3.1. For every nonnegative integer,n, the value ofn CnC41 is prime. It is not immediately clear whether this proposition is true or false. In such circumstances, it is tempting to try to determine its veracity by computing the value 1 of 2 p.n/WWDn CnC41: (1.1) for several values ofn and then checking to see if they are prime. If any of the computed values is not prime, then we will know that the proposition is false. If all the computed values are indeed prime, then we might be tempted to conclude that the proposition is true. We begin the checking by evaluatingp.0/D41, which is prime. p.1/D43 is also prime. So isp.2/D47,p.3/D53, . . . , andp.20/D461, all of which are prime. Hmmm. . . It is starting to look likep.n/ is a prime for every nonnegative integern. In fact, continued checking reveals thatp.n/ is prime for alln 39. The proposition certainly does seem to be true. 2 Butp.40/D 40 C40C41D 4141, which is not prime. So it’s not true that the expression is prime for all nonnegative integers, and thus the proposition is false Although surprising, this example is not as contrived or rare as you might sus- pect. As we will soon see, there are many examples of propositions that seem to be true when you check a few cases (or even many), but which turn out to be false. The key to remember is that you can’t check a claim about an infinite set by checking a finite set of its elements, no matter how large the finite set. Propositions that involve all numbers are so common that there is a special no- tation for them. For example, Proposition 1.3.1 can also be written as 8n2N:p.n/ is prime: (1.2) Here the symbol8 is read “for all”. The symbolN stands for the set of nonnegative integers, namely, 0, 1, 2, 3, . . . (ask your instructor for the complete list). The symbol “2” is read as “is a member of,” or “belongs to,” or simply as “is in”. The period after theN is just a separator between phrases. Here is another example of a proposition that, at first, seems to be true but which turns out to be false. 1 The symbolWWD means “equal by definition.” It’s always ok to simply write “=” instead ofWWD, but reminding the reader that an equality holds by definition can be helpful.“mcs-ftl” — 2010/9/8 — 0:40 — page 13 — 19 1.3. Predicates and Quantifiers 13 4 4 4 4 Proposition 1.3.2. a Cb Cc Dd has no solution whena;b;c;d are positive integers. Euler (pronounced “oiler”) conjectured this proposition to be true in 1769. It was checked by humans and then by computers for many values ofa,b,c, andd over the next two centuries. Ultimately the proposition was proven false in 1987 by Noam Elkies. The solution he found was a D 95800;b D 217519;c D 414560;d D 422481. No wonder it took 218 years to show the proposition is false In logical notation, Proposition 1.3.2 could be written, C C C C 4 4 4 4 8a2Z 8b2Z 8c2Z 8d2Z :a Cb Cc ¤d : C Here,Z is a symbol for the positive integers. Strings of8’s are usually abbrevi- ated for easier reading, as follows: C 4 4 4 4 8a;b;c;d2Z :a Cb Cc ¤d : The following proposition is even nastier. 3 3 3 C Proposition 1.3.3. 313.x Cy /Dz has no solution whenx;y;z2Z . This proposition is also false, but the smallest counterexample values forx,y, andz have more than 1000 digits Even the world’s largest computers would not be able to get that far with brute force. Of course, you may be wondering why anyone 3 3 3 would care whether or not there is a solution to313.x Cy /D z wherex,y, andz are positive integers. It turns out that finding solutions to such equations is important in the field of elliptic curves, which turns out to be important to the study of factoring large integers, which turns out (as we will see in Chapter 4) to be im- portant in cracking commonly-used cryptosystems, which is why mathematicians went to the effort to find the solution with thousands of digits. Of course, not all propositions that have infinitely many cases to check turn out to be false. The following proposition (known as the “Four-Color Theorem”) turns out to be true. 2 Proposition 1.3.4. Every map can be colored with 4 colors so that adjacent re- gions have different colors. The proof of this proposition is difficult and took over a century to perfect. Along the way, many incorrect proofs were proposed, including one that stood for 10 years 2 Two regions are adjacent only when they share a boundary segment of positive length. They are not considered to be adjacent if their boundaries meet only at a few points.“mcs-ftl” — 2010/9/8 — 0:40 — page 14 — 20 14 Chapter 1 Propositions in the late 19th century before the mistake was found. An extremely laborious proof was finally found in 1976 by mathematicians Appel and Haken, who used a complex computer program to categorize the four-colorable maps; the program left a few thousand maps uncategorized, and these were checked by hand by Haken and his assistants—including his 15-year-old daughter. There was a lot of debate about whether this was a legitimate proof: the proof was too big to be checked without a computer, and no one could guarantee that the computer calculated correctly, nor did anyone have the energy to recheck the four-colorings of the thousands of maps that were done by hand. Within the past decade, a mostly intelligible proof of the Four-Color Theorem was found, though a computer is still needed to check the 3 colorability of several hundred special maps. In some cases, we do not know whether or not a proposition is true. For exam- ple, the following simple proposition (known as Goldbach’s Conjecture) has been heavily studied since 1742 but we still do not know if it is true. Of course, it has been checked by computer for many values ofn, but as we have seen, that is not sufficient to conclude that it is true. Proposition 1.3.5 (Goldbach). Every even integern greater than 2 is the sum of two primes. While the preceding propositions are important in mathematics, computer scien- tists are often interested in propositions concerning the “correctness” of programs and systems, to determine whether a program or system does what it’s supposed to do. Programs are notoriously buggy, and there’s a growing community of re- searchers and practitioners trying to find ways to prove program correctness. These efforts have been successful enough in the case of CPU chips that they are now routinely used by leading chip manufacturers to prove chip correctness and avoid mistakes like the notorious Intel division bug in the 1990’s. Developing mathematical methods to verify programs and systems remains an active research area. We’ll consider some of these methods later in the text. 1.3.2 Predicates A predicate is a proposition whose truth depends on the value of one or more vari- ables. Most of the propositions above were defined in terms of predicates. For example, “n is a perfect square” 3 Seehttp://www.math.gatech.edu/˜thomas/FC/fourcolor.html The story of the Four-Color Proof is told in a well-reviewed popular (non-technical) book: “Four Colors Suffice. How the Map Problem was Solved.” Robin Wilson. Princeton Univ. Press, 2003, 276pp. ISBN 0-691-11533-8.

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.