计算机科学中的数学证明及其应用

需积分: 9 45 浏览量更新于2024-07-18 收藏 13.03MB PDF 举报

"《数学与计算机科学》是一本专门探讨如何运用数学模型和方法来解决计算机科学中遇到的问题的教材。该书强调证明在理解中的核心地位，作者们秉持大多数数学家的观点，认为证明是真正理解的基础。在计算机科学领域，证明的作用日益增强，它被用来确保软件和硬件的正确性，这是任何测试都无法完全替代的。在书中，证明被定义为确立真理的一种手段。不同领域对真理的理解各有侧重：法律领域依赖于法庭上呈现的证据，商业领域则由权威人士或组织指定，物理学和生物学则依赖实验来确认科学真理，而统计学则是通过样本数据分析来建立可能的真理。哲学证明则更侧重于逻辑推理，如笛卡尔的名言“我思故我在”，通过一系列合理的小论据展示论证过程。章节1详细介绍了证明的基本概念，包括命题、谓词、公理化方法以及如何证明蕴含关系、充要条件等。证明的方法多种多样，如分情况讨论、反证法等。此外，书中还讨论了良好的证明实践和技巧，如归结法的应用。第二部分深入探讨了序贯原理，即任何集合都可以通过某种方式进行有序排列，这对于证明算法和数据结构的性质至关重要。书中提供了使用序法证明的模板，并展示了如何利用这个原理来分解质因数和研究有序集。第三章关注逻辑公式，阐述了如何从一个命题推导出另一个命题，以及如何构建复杂的逻辑表达式。这为理解编程语言中的逻辑结构和算法设计提供了理论基础。《数学与计算机科学》将数学的严谨性和计算机科学的实际应用紧密结合，让读者在学习过程中不仅能掌握数学工具，还能理解这些工具在实际问题中的应用价值。通过阅读这本书，读者可以提升自己的逻辑思维能力，以及在解决计算机科学问题时的证明技能。"

“mcs” — 2017/3/6 — 12:54 — page 8 — #16

Chapter 1 What is a Proof?8

For a computer scientist, some of the most important things to prove are the

correctness of programs and systems—whether a program or system does what it’s

supposed to. Programs are notoriously buggy, and there’s a growing community

of researchers and practitioners trying to ﬁnd 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 some notorious past mistakes.

Developing mathematical methods to verify programs and systems remains an

active research area. We’ll illustrate some of these methods in Chapter 5.

1.2 Predicates

A predicate can be understood as a proposition whose truth depends on the value

of one or more variables. So “n is a perfect square” describes a predicate, since you

can’t say if it’s true or false until you know what the value of the variable n happens

to be. Once you know, for example, that n equals 4, the predicate becomes the true

proposition “4 is a perfect square”. Remember, nothing says that the proposition

has to be true: if the value of n were 5, you would get the false proposition “5 is a

perfect square.”

Like other propositions, predicates are often named with a letter. Furthermore, a

function-like notation is used to denote a predicate supplied with speciﬁc variable

values. For example, we might use the name “P ” for predicate above:

P .n/ WWD “n is a perfect square”;

and repeat the remarks above by asserting that P.4/ is true, and P .5/ is false.

This notation for predicates is confusingly similar to ordinary function notation.

If P is a predicate, then P.n/ is either true or false, depending on the value of n.

On the other hand, if p is an ordinary function, like n

C1, then p.n/ is a numerical

quantity. Don’t confuse these two!

1.3 The Axiomatic Method

The standard procedure for establishing truth in mathematics was invented by Eu-

clid, a mathematician working in Alexandria, Egypt around 300 BC. His idea was

to begin with ﬁve assumptions about geometry, which seemed undeniable based on

direct experience. (For example, “There is a straight line segment between every

“mcs” — 2017/3/6 — 12:54 — page 9 — #17

1.4. Our Axioms 9

pair of points”.) Propositions like these that are simply accepted as true are called

axioms.

Starting from these axioms, Euclid established the truth of many additional propo-

sitions by providing “proofs.” A proof is a sequence of logical deductions from

axioms and previously proved statements that concludes with the proposition in

question. You probably wrote many proofs in high school geometry class, and

you’ll see a lot more in this text.

There are several common terms for a proposition that has been proved. The

different terms hint at the role of the proposition within a larger body of work.

 Important true propositions are called theorems.

 A lemma is a preliminary proposition useful for proving later propositions.

 A corollary is a proposition that follows in just a few logical steps from a

theorem.

These deﬁnitions are not precise. In fact, sometimes a good lemma turns out to be

far more important than the theorem it was originally used to prove.

Euclid’s axiom-and-proof approach, now called the axiomatic method, remains

the foundation for mathematics today. In fact, just a handful of axioms, called the

Zermelo-Fraenkel with Choice axioms (ZFC), together with a few logical deduction

rules, appear to be sufﬁcient to derive essentially all of mathematics. We’ll examine

these in Chapter 8.

1.4 Our Axioms

The ZFC axioms are important in studying and justifying the foundations of math-

ematics, but for practical purposes, they are much too primitive. Proving theorems

in ZFC is a little like writing programs in byte code instead of a full-ﬂedged pro-

gramming language—by one reckoning, a formal proof in ZFC that 2 C 2 D 4

requires more than 20,000 steps! So instead of starting with ZFC, we’re going to

take a huge set of axioms as our foundation: we’ll accept all familiar facts from

high school math.

This will give us a quick launch, but you may ﬁnd this imprecise speciﬁcation

of the axioms troubling at times. For example, in the midst of a proof, you may

start to wonder, “Must I prove this little fact or can I take it as an axiom?” There

really is no absolute answer, since what’s reasonable to assume and what requires

proof depends on the circumstances and the audience. A good general guideline is

simply to be up front about what you’re assuming.

剩余986页未读，继续阅读

THESUMMERE

粉丝: 23
资源: 328

计算机科学中的数学证明及其应用

Mathematics for Computer Science(MIT)

Mathematics for Computer Science 2017版

Mathematics for Computer Science.pdf

mathematics for computer science

Mathematics for Computer Science 2015

Mathematics for Computer Science, Fall 2002

Mathematics for Computer Science主要内容

Mathematics for Computer Science 17 pdf 附带视频地址

王五的绩效考核.xml

FA_HyperLink.xls

最新资源