“mcs”-2018/6/6一13：43一page3一#11 Introduction This text explains how to use mathematical models and methods to analyze prob- lems that arise in computer science.Proofs play a central role in this work because the authors share a belief with most mathematicians that proofs are essential for genuine understanding.Proofs also play a growing role in computer science;they are used to certify that software and hardware will always behave correctly,some- thing that no amount of testing can do. 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, or maybe just your boss.In fields such as physics or 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."This phrase 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 for it,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 IActually,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” — 2018/6/6 — 13:43 — page 3 — #11 Introduction This text explains how to use mathematical models and methods to analyze prob￾lems that arise in computer science. Proofs play a central role in this work because the authors share a belief with most mathematicians that proofs are essential for genuine understanding. Proofs also play a growing role in computer science; they are used to certify that software and hardware will always behave correctly, some￾thing that no amount of testing can do. 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, or maybe just your boss. In fields such as physics or biology, scientific truth is confirmed by experiment.1 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.” This phrase 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 for it, 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 1Actually, 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