{"id":12202,"date":"2022-07-05T07:09:50","date_gmt":"2022-07-05T07:09:50","guid":{"rendered":"https:\/\/www.booksofall.com\/ja\/?post_type=product&p=12202"},"modified":"2022-07-05T07:09:50","modified_gmt":"2022-07-05T07:09:50","slug":"mathematics-for-computer-science-lehman-leighton-and-meyer","status":"publish","type":"product","link":"https:\/\/www.booksofall.com\/ja\/mathematics-for-computer-science-lehman-leighton-and-meyer\/","title":{"rendered":"Mathematics for Computer Science (Lehman, Leighton, and Meyer)"},"content":{"rendered":"

In a book he was reading around 1630, Fermat claimed to have a proof for this proposition, but not enough space in the margin to write it down. Over the years, the Theorem<\/a> was proved to hold for all up to 4,000,000, but we\u2019ve seen that this shouldn\u2019t necessarily inspire confidence that it holds for all . There is, after all, a clear resemblance between Fermat\u2019s Last Theorem and Euler\u2019s false Conjecture. Finally, in 1994, British mathematician Andrew Wiles<\/a> gave a proof, after seven years of working in secrecy and isolation in his attic. His proof did not fit in any margin.<\/p>\n

Finally, let\u2019s mention another simply stated proposition whose truth remains unknown.<\/p>\n

Proposition 1.1.8 (Goldbach\u2019s Conjecture<\/a>). Every even integer greater than 2 is the sum of two primes. Goldbach\u2019s Conjecture dates back to 1742. It is known to hold for all numbers up to but to this day, no one knows whether it\u2019s true or false.<\/p>\n

For a computer scientist, some of the most important things to prove are the correctness of programs and systems\u2014 whether a program or system does what it\u2019s supposed to. Programs are notoriously buggy, and there\u2019s a growing community of researchers 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\u2019s. Developing mathematical methods to verify programs and systems remains an active research area. We\u2019ll illustrate some of these methods in Chapter 5.<\/p>\n

The symbol ::= means \u201cequal by definition.\u201d It\u2019s always ok simply to write \u201c=\u201d instead of ::=, but reminding the reader that an equality holds by definition can be helpful. 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.<\/p>\n

A predicate can be understood as a proposition whose truth depends on the value of one or more variables. So \u201c is a perfect square\u201d describes a predicate, since you can\u2019t say if it\u2019s true or false until you know what the value of the variable happens to be. Once you know, for example, that equals 4, the predicate becomes the true proposition \u201c4 is a perfect square\u201d. Remember, nothing says that the proposition has to be true: if the value of were 5, you would get the false proposition \u201c5 is a perfect square.\u201d Like other propositions, predicates are often named with a letter. Furthermore, a function-like notation is used to denote a predicate supplied with specific variable values.<\/p>\n","protected":false},"excerpt":{"rendered":"

.