数学在计算机科学中的应用

132 浏览量更新于2024-07-14 收藏 7.51MB PDF 举报

"Mathematics for Computer Science (2012)" 是一本由 Eric Lehman、F Thomson Leighton 和 Albert R Meyer 合著的教材，主要针对计算机科学中的数学基础进行阐述。这本书涵盖了证明方法、良序原则以及逻辑公式等多个关键概念，并在麻省理工学院的数学和计算机科学与人工智能实验室得到了应用。在书中，作者首先介绍了【证明】的基本概念，这是理解数学和计算机科学基础的关键。他们详细讨论了： 1. **命题**：这是逻辑推理的基本单位，是一个可以被判断为真或假的陈述。 2. **谓词**：谓词用于描述对象的属性或关系，它们比命题更灵活，可以包含一个或多个变量。 3. **公理化方法**：这是构建数学体系的基础，通过一组未经证明但被视为自明的公理开始，然后推导出其他定理。 4. **我们的公理**：书中可能会介绍特定的公理系统，如自然数的算术公理。 5. **证明蕴含**：展示了如何证明一个命题蕴含另一个命题。 6. **双向蕴含证明**：涉及证明两个命题之间的等价关系。 7. **案例分析**：一种通过考虑所有可能情况来证明的策略。 8. **反证法**：通过假设反命题为真，然后推导出矛盾来证明原命题的真实性。 9. **实践中良好的证明**：强调了构造清晰、简洁且无漏洞证明的重要性。接下来，书中探讨了【良序原则】，这是数论和集合论中的一个重要原理。它指出每个非空的良序集合都有一个最小元素。这一章节包括： 1. **良序证明**：展示了如何利用良序原则进行证明。 2. **良序证明模板**：提供了一种结构化的框架来构造良序相关的论证。 3. **因式分解成质数**：可能涉及到利用良序原则来分析整数的质因数分解问题。 4. **良序集**：讨论了满足良序性质的集合及其特性。最后，书中还涉及了【逻辑公式】，这是形式逻辑的核心部分，用于表示复杂的命题结构： 1. **从命题构造命题**：讲述了如何通过逻辑运算（如合取、析取、否定等）将基本命题组合成更复杂的命题。 2. **命题逻辑在计算机程序中的应用**：这部分可能解释了逻辑公式如何在编程语言和计算机系统设计中发挥重要作用。这本教材对于想要深入理解计算机科学背后的数学原理，特别是对逻辑、证明技巧和算法基础感兴趣的读者来说是一份宝贵的资源。

“mcs” — 2012/6/4 — 15:49 — page 8 — #16

Chapter 1 What is a Proof?8

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 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 illustrate some of these methods in Chapter 5.

1.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 deﬁned in terms of predicates. For example,

“n is a perfect square”

is a predicate whose truth depends on the value of n. The predicate is true for n D 4

since four is a perfect square, but false for n D 5 since ﬁve is not 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 name our earlier predicate P :

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

So 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

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

axioms.

“mcs” — 2012/6/4 — 15:49 — page 9 — #17

1.4. Our Axioms 9

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

axioms Zermelo-Frankel with Choice (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 7.

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.

剩余827页未读，继续阅读

weixin_38555019

粉丝: 10
资源: 921

数学在计算机科学中的应用

Mathematics for Computer Science

Mathematics for Computer Science, Fall 2002

mathematics for computer science

Discrete-Mathematics-for-Computer-Science

Mathematics for Computer Science 2015

Mathematics for Computer Science.pdf

Mathematics for Computer Science 2017版

MIT Press - Mathematics For Computer Science.pdf

UBB-Mathematics-and-Computer-Science

Mathematics for Computer Science(MIT)

最新资源