斯坦福大学计算机基础：数学基础知识与计算理论

需积分: 9 197 浏览量更新于2024-07-17 收藏 2.3MB PDF 举报

"Mathematical Foundations of Computing.pdf 是一本关于计算科学数学基础的教材，源自斯坦福大学，它涵盖了算法、人工智能、图像处理等领域的重要理论知识。" 这篇教材主要探讨了计算机科学中的数学基础，包括集合论、 Cantor's 定理以及数学证明等核心概念。以下是这些主题的详细阐述： 1. **集合论**：集合是数学的基础，第1章深入介绍了集合的概念。集合可以包含任何对象，而1.1节"什么是集合?"定义了集合的基本属性。1.2节讨论了集合上的操作，如并集、交集和差集。1.3节和1.4节涉及特殊集合和集合构造记法，包括过滤和变换集合的方法。1.5节讲解了关系，如集合间的等价和包含关系。1.6节介绍了幂集（Power Set），即原集合的所有子集构成的集合。1.7节则引入了基数的概念，用于衡量集合的大小，区分有限集合和无限集合。1.8节是 Cantor's 定理的介绍，它揭示了无穷集合的基数可以有不同级别。1.9节解释了 Cantor's 定理的重要性，并在1.10节中讨论了其对计算能力的限制。 2. **Cantor's 定理**：Cantor's 定理是数学中的一个关键结果，它表明任何集合的幂集的基数总是大于原集合的基数。32页开始详细介绍了这个定理，通过 Cantor 的对角线论证方法来证明。这个论证展示了如何构造一个不在任何集合列表中的元素，从而证明不存在将集合与其幂集一一对应的关系。 3. **数学证明**：第2章深入讨论了数学证明的逻辑和结构。2.1节定义了什么是证明，明确了我们在证明中可以假设什么。2.2节讲解了直接证明，以及如何通过案例分析进行证明。此外，本章还涉及了证明中的技巧，如选择字母的策略（A Quick Aside: Choosing Letters）以及关于集合的证明。51页开始，引入了引理（Lemmas），这些是辅助性的定理，常用于构建更复杂的证明。这些内容构成了计算机科学数学基础的基石，对于理解和应用算法、人工智能和图像处理等领域的理论至关重要。通过学习这些概念，读者能够建立坚实的数学思维，进一步探索计算机科学的深度。

Chapter 1: Sets and Cantor's Theorem

When reading a statement like x aloud, it's perfectly fine to read it as “∈ ℤ x in Z,” but it's more

common to read such a statement as “x is an integer,” abstracting away from the set-theoretic

definition to an (equivalent) but more readable version.

Since really is the set of all integers, all of the set operations we've developed so far apply toℤ

it. For example, we could consider the set ∩ {1, 1.5, 2, 2.5}, which is the set {1, 2}. We canℤ

also compute the union of and some other set. For example, {1, 2, 3} is the set , since 1ℤ ℤ ∪ ℤ

, 2 , and 3∈ ℤ ∈ ℤ ∈ .ℤ

You might be wondering – why ? This is from the German word “zahlen,” meaning “numℤ -

bers.” Much of modern mathematics has its history in Germany, so many terms that we'll en-

counter in the course of this book (for example, “Entscheidungsproblem”) come from German.

Much older terms tend to come from Latin or Greek, while results from the 8

through 13

cen-

turies are often Arabic (for example, “algebra” derives from

 ok written in the 9

century by Persian mathematician al-Khwarizmi, whose name

is the source of the word “algorithm.”) It's interesting to see how the languages used in mathe-

matics align with major world intellectual centers.

While in mathematics the integers appear just about everywhere, in computer science they don't

arise as frequently as you might expect. Most languages don't allow for negative array indices.

Strings can't have a negative number of characters in them. A loop never runs -3 times. More

commonly, in computer science, we find ourselves working with just the numbers 0, 1, 2, 3, …,

etc. These numbers are called the natural numbers, and represent answers to questions of the

form “how many?” Because natural numbers are so ubiquitous in computing, the set of all natu-

ral numbers is particularly important:

The set of all natural numbers, denoted ℕ, is the set ℕ = {0, 1, 2, 3, …}

For example, 0 ∈ ℕ, 137 ∈ ℕ, but -3 ∉ ℕ, 1.1 ∉ ℕ, and {1, 2} ∉ ℕ. As with , we mightℤ

read x as either “x in N” or as “∈ ℕ x is a natural number.”

The natural numbers arise frequently in computing as ways of counting loop iterations, the num-

ber of nodes in a binary tree, the number of instructions executed by a program, etc.

Before we move on, I should point out that while there is a definite consensus on what is, thereℤ

is not a universally-accepted definition of ℕ. Some mathematicians treat 0 as a natural number,

while others do not. Thus you may find that some authors consider

ℕ = {0, 1, 2, 3, … }

while others treat ℕ as

ℕ = {1, 2, 3, … }

For the purposes of this course, we will treat 0 as a natural number, so

• the smallest natural number is 0, and (appropriately)

• 0 ∈ !ℕ

"#$%&$$'%('#&#$)*$#+*#+% *$*#,*!-').

#$$ℕ

⁺

17 / 347

The set of positive natural numbers ℕ⁺ is the set ℕ⁺ = {1, 2, 3, …}

Thus 137 ∈ / +0 ℕ ∉ ℕ⁺.

There are other important sets that arise frequently in mathematics and that will appear from time

to time in our exploration of the mathematical foundations of computing. We should consider

the set of real numbers, numbers representing arbitrary measurements. For example, you might

be 1.7234 meters tall, or weigh 70.22 kilograms. Numbers like 1#)e**#+% *$/$*

#+% *$2$3+**'!4$*#+% *$$$%5*##%%&$

'67$5&$(% !

4set of all real numbers$)#)ℝ!

4$$ℕ/ /#) *3+)*#*%*$$'87$#$*#(&#ℤ ℝ .

###(%#(%#$!-'*+*#$5&*/ +')#)##5*

)##$9

:finite set$$&###6#(#(%#(%#$!:#infinite set$$&##.

#6##(%#(%#$!

1.4 Set-Builder Notation

1.4.1 Filtering Sets

So far, we have seen how to use the primitive set operations (union, intersection, difference, and

symmetric difference) to combine together sets into other sets. However, more commonly, we

are interested in defining a set not by combining together existing sets, but by gathering together

all objects that share some common property. It would be nice, for example, to be able to just

say something like “the set of all even numbers” or “the set of legal C programs.” For this, we

have a tool called set-builder notation which allows us to define a set by describing some prop-

erty common to all of the elements of that set.

Before we go into a formal definition of set-builder notation, let's see some examples. First,

here's how we might define the set of even natural numbers:

{ n | n ∈ ℕ and n is even }

You can read this aloud as “the set of all n, where n is a natural number and n is even.” Simi-

larly, we could define the set of positive real numbers like this:

{ x | x and ∈ ℝ x > 0 }

This would be read as “the set of all x, where x is a real number and x is greater than 0.”

Chapter 1: Sets and Cantor's Theorem

Leaving the realm of pure mathematics, we could also consider a set like this one:

{ p | p is a legal Java program }

If you'll notice, each of these sets is defined using the following pattern:

{ variable | conditions on that variable }

Let's dissect each of the above sets one at a time to see what they mean and how to read them.

First, we defined the set of even natural numbers this way:

{ n | n ∈ ℕ and n is even }

Here, this definition says that this is the set formed by taking every choice of n where n ∈ ℕ

(that is, n is a natural number) and n is even. Consequently, this is the set {0, 2, 4, 6, 8, …}.

The set

{ x | x and ∈ ℝ x > 0 }

Can similarly be read off as “the set of all x where x is a real number and x is greater than zero,”

which filters the set of real numbers down to just the positive real numbers.

Of the sets listed above, this set was the least mathematically precise:

{ p | p is a legal C program }

However, it's a perfectly reasonable way to define a set: we just gather up all the legal C pro-

grams (of which there are infinitely many) and put them into a single set.

When using set-builder notation, the name of the variable chosen does not matter. This means

that all of the following are equivalent to one another:

{ x | x and ∈ ℝ x > 0 }

{ y | y and ∈ ℝ y > 0 }

{ z | z and ∈ ℝ z > 0 }

Using set-builder notation, it's actually possible to define many of the special sets from the previ-

ous section in terms of one another. For example, we can define the set ℕ as follows:

ℕ = { x | x and ∈ ℤ x ≥ 0 }

That is, the set of all natural numbers (ℕ) is the set of all x such that x is an integer and x is non-

negative. This precisely matches our intuition about what the natural numbers ought to be. Sim-

ilarly, we can define the set ℕ as⁺

ℕ⁺ = { n | n ∈ ℕ and n ≠ 0 }

Since this describes the set of all n such that n is a nonzero natural number.

So far, all of the examples above with set-builder notation have started with an infinite set and

ended with an infinite set. However, set-builder notation can be used to construct finite sets as

well. For example, the set

{ n | n ∈ ℕ, n is even, and n < 10 }

has just five elements: 0, 2, 4, 6, and 8.

19 / 347

To formalize our definition of set-builder notation, we need to introduce the notion of a predi-

cate:

A predicate is a statement about some object x that is either true or false.

For example, the statement “x < 0” is a predicate that is true if x is less than zero and false other-

wise. The statement “x is an even number” is a predicate that is true if x is an even number and

is false otherwise. We can build far more elaborate predicates as well – for example, the predi-

cate “p is a legal C program that prints out a random number” would be true for C programs that

print random numbers and false otherwise. Interestingly, it's not required that a predicate be

checkable by a computer program. As long as a predicate always evaluates to either true or false

– regardless of how we'd actually go about verifying which of the two it was – it's a valid predi-

cate.

Given our definition of a predicate, we can formalize the definition of set-builder notation here:

The set { x | P(x) } is the set of all x such that P(x) is true.

It turns out that allowing us to define sets this way can, in some cases, lead to paradoxical sets,

sets that cannot possibly exist. We'll discuss this later on when we talk about Russell's Paradox.

However, in practical usage, it's almost universally safe to just use this simple set-builder nota-

tion.

1.4.2 Transforming Sets

You can think of this version of set-builder notation as some sort of filter that is used to gather

together all of the objects satisfying some property. However, it's also possible to use set-builder

notation as a way of applying a transformation to the elements of one set to convert them into a

different set. For example, suppose that we want to describe the set of all perfect squares – that

is, natural numbers like 0 = 0

, 1 = 1

, 4 = 2

, 9 = 3

, 16 = 4

, etc. Using set-builder notation, we

can do so, though it's a bit awkward:

{ n | there is some m ∈ ℕ such that n = m

}

That is, the set of all numbers n where, for some natural number m, n is the square of m. This

feels a bit awkward and forced, because we need to describe some property that's shared by all

the members of the set, rather than the way in which those elements are generated. As a com-

puter programmer, you would probably be more likely to think about the set of perfect squares

more constructively by showing how to build the set of perfect squares out of some other set. In

fact, this is so common that there is a variant of set-builder notation that does just this. Here's an

alternative way to define the set of all perfect squares:

{ n

| n ∈ ℕ }

Chapter 1: Sets and Cantor's Theorem

This set can be read as “the set of all n

, where n is a natural number.” In other words, rather

than building the set by describing all the elements in it, we describe the set by showing how to

apply a transformation to all objects matching some criterion. Here, the criterion is “n is a natu-

ral number,” and the transformation is “compute n

.”

As another example of this type of notation, suppose that we want to build up the set of the num-

bers 0, ½, 1,

, 2,

, etc. out to infinity. Using the simple version of set-builder notation, we

could write this set as

{ x | there is some n ∈ ℕ such that x = n / 2 }

That is, this set is the set of all numbers x where x is some natural number divided by two. This

feels forced, and so we might use this alternative notation instead:

{ n / 2 | n ∈ ℕ }

That is, the set of numbers of the form n / 2, where n is a natural number. Here, we transform the

set ℕ by dividing each of its elements by two.

It's possible to perform transformations on multiple sets at once when using set-builder notation.

For example, let's let the set A = {1, 2, 3} and the set B = {10, 20, 30}. Then consider the fol-

lowing set:

C = { a + b | a ∈ A and b ∈ B }

This set is defined as follows: for any combination of an element a ∈ A and an element b ∈ B,

the set C contains the number a + b. For example, since 1 ∈ A and 10 ∈ B, the number

1 + 10 = 11 must be an element of C. It turns out that since there are three elements of A and

three elements of B, there are nine possible combinations of those elements:

10 20 30

1 ;; <; =;

2 ;< << =<

3 ;= <= ==

This means that our set C is

C = { a + b | a ∈ A and b ∈ B } = { 11, 12, 13, 21, 22, 23, 31, 32, 33 }

1.5 Relations on Sets

1.5.1 Set Equality

We now have ways of describing collections and of forming new collections out of old ones.

However, we don't (as of yet) have a way of comparing different collections. How do we know

if two sets are equal to one another?

As mentioned earlier, a set is an unordered collection of distinct elements. We say that two sets

are equal if they have exactly the same elements as one another.

剩余346页未读，继续阅读

hemouse

粉丝: 3
资源: 1

斯坦福大学计算机基础：数学基础知识与计算理论

计算机网络数学基础--Mathematical.Foundations.of.Computer.Networking

Mathematical Foundations of Computer

annals of mathematics怎么样？

mathematical explanation of diagonal loading

from torch import Tensor

scalarfunction

Integral library based on C++

TypeError: 'PdfReader' object cannot be interpreted as an integer

k=float("INF")

最新资源