← 学习库 Discrete Mathematics (Levin) · 中英对照 目录

0.1 What is Discrete Mathematics 什么是离散数学

本页译自 LibreTexts · Discrete Mathematics (Levin) 第 0.1 章。公式经 MathJax 渲染，自定义宏已注入。

dis·crete / dis′krët.

dis·crete / dis'krët。（词条读音）

Adjective: Individually separate and distinct.

形容词：彼此分离、各不相同的。

Synonyms: separate - detached - distinct - abstract.

近义词：separate（分离）— detached（脱离）— distinct（有别）— abstract（抽象）。

Defining discrete mathematics is hard because defining mathematics is hard. What is mathematics? The study of numbers? In part, but you also study functions and lines and triangles and parallelepipeds and vectors and …. Or perhaps you want to say that mathematics is a collection of tools that allow you to solve problems. What sort of problems? Okay, those that involve numbers, functions, lines, triangles, …. Whatever your conception of what mathematics is, try applying the concept of “discrete” to it, as defined above. Some math fundamentally deals with stuff that is individually separate and distinct.

给离散数学（discrete mathematics）下一个定义并不容易，因为给数学（mathematics）下定义本就不易。数学是什么？是研究数吗？算是，但你同样研究函数、直线、三角形、平行六面体、向量等等。又或者你更愿意说，数学是一套帮助你解决问题的工具。什么样的问题？嗯，是那些涉及数、函数、直线、三角形……的问题。无论你对数学的本质作何理解，不妨把上文定义的「离散（discrete）」这一概念套用到它上面。有些数学研究的对象，本质上就是彼此分离、各不相同的东西。

In an algebra or calculus class, you might have found a particular set of numbers (maybe the set of numbers in the range of a function). You would represent this set as an interval: $[0,\infty)$ is the range of $f(x) = x^2$ since the set of outputs of the function are all real numbers 0 and greater. This set of numbers is NOT discrete. The numbers in the set are not separated by much at all. In fact, take any two numbers in the set and there are infinitely many more between them which are also in the set. Discrete math could still ask about the range of a function, but the set would not be an interval. Consider the function which gives the number of children of each person reading this. What is the range? I’m guessing it is something like $\{0, 1, 2, 3\}\text{.}$ Maybe 4 is in there too. But certainly there is nobody reading this that has 1.32419 children. This set is discrete because the elements are separate. Also notice that the inputs to the function are a discrete set as each input is an individual person. You would not consider fractional inputs (we don’t care about anything $2/3$ between a pair of readers).

在代数或微积分课上，你可能曾求出过某个特定的数集（比如某个函数值域中的那些数）。你会把这个集合表示成一个区间：$[0,\infty)$ 就是 $f(x) = x^2$ 的值域，因为该函数的所有输出都是不小于 0 的实数。这个集合不是离散的。集合中的数彼此相差极小。事实上，任取集合中的两个数，它们之间还存在着无穷多个同样属于该集合的数。离散数学当然也可以讨论函数的值域，但那样的集合就不会是一个区间了。考虑这样一个函数：它给出每位正在阅读本书的读者所拥有的孩子数量。它的值域是什么？我猜大概是像 $\{0, 1, 2, 3\}$ 这样。也许 4 也在其中。但可以肯定的是，不会有读者拥有 1.32419 个孩子。这个集合是离散的，因为它的元素彼此分离。还要注意到，该函数的输入本身也是一个离散集合，因为每个输入都是一个具体的人。你不会去考虑分数形式的输入（我们不在乎一对读者之间有什么 $2/3$ 这样的人）。

One way to get a feel for the subject is to consider the types of problems you solve in discrete math. Here are a few simple examples:

要对这门学科获得直观感受，一个办法是看看离散数学中求解的是哪类问题。下面举几个简单的例子：

Investigate! 探究！

Note: Throughout the text you will see Investigate! activities like this one. Answer the questions in these as best you can to give yourself a feel for what is coming next.

注：全书各处你都会看到像这样的探究！活动。请尽力回答其中的问题，以便对后续内容有所准备。
  1. The most popular mathematician in the world is throwing a party for all of his friends. As a way to kick things off, they decide that everyone should shake hands. Assuming all 10 people at the party each shake hands with every other person (but not themselves, obviously) exactly once, how many handshakes take place?
  2. At the warm-up event for Oscar’s All Star Hot Dog Eating Contest, Al ate one hot dog. Bob then showed him up by eating three hot dogs. Not to be outdone, Carl ate five. This continued with each contestant eating two more hot dogs than the previous contestant. How many hot dogs did Zeno (the 26th and final contestant) eat? How many hot dogs were eaten all together?
  3. After excavating for weeks, you finally arrive at the burial chamber. The room is empty except for two large chests. On each is carved a message (strangely in English):
    two chests
    You know exactly one of these messages is true. What should you do?
  4. Back in the days of yore, five small towns decided they wanted to build roads directly connecting each pair of towns. While the towns had plenty of money to build roads as long and as winding as they wished, it was very important that the roads not intersect with each other (as stop signs had not yet been invented). Also, tunnels and bridges were not allowed. Is it possible for each of these towns to build a road to each of the four other towns without creating any intersections?
  1. 世界上最受欢迎的数学家正在为他的所有朋友举办一场派对。作为开场，大家决定互相握手。假设派对上的 10 个人每人都与其他每个人恰好握手一次（显然不包括自己），一共会发生多少次握手？
  2. 在奥斯卡全明星吃热狗大赛的热身活动上，艾尔吃了 1 个热狗。鲍勃紧接着吃了 3 个，技压一筹。卡尔不甘示弱，吃了 5 个。如此继续，每位选手都比前一位多吃 2 个热狗。泽诺（第 26 位、也是最后一位选手）吃了多少个热狗？大家一共吃了多少个热狗？
  3. 经过数周的挖掘，你终于抵达墓室。房间里空空如也，只有两个大箱子。每个箱子上都刻着一句话（奇怪的是用的是英文）：
    两个箱子
    你确切地知道这两句话中只有一句为真。你该怎么做？
  4. 在久远的过去，五座小镇决定修建道路，把每两座小镇直接连通。尽管这些镇资金充裕，想修多长、多蜿蜒的道路都行，但至关重要的是道路彼此不能相交（因为当时还没有红绿灯）。而且，隧道和桥梁也不被允许。那么，这五座小镇能否各自与其他四座小镇都修一条路，而任何两条路都不相交？

One reason it is difficult to define discrete math is that it is a very broad description which encapsulates a large number of subjects. In this course we will study four main topics: combinatorics (the theory of ways things combine; in particular, how to count these ways), sequences, symbolic logic, and graph theory. However, there are other topics that belong under the discrete umbrella, including computer science, abstract algebra, number theory, game theory, probability, and geometry (some of these, particularly the last two, have both discrete and non-discrete variants).

离散数学之所以难以定义，原因之一在于它是一个极为宽泛的说法，涵盖大量学科。在本课程中，我们将学习四个主要主题：组合数学（研究事物组合方式的学问；具体而言，即如何计数这些组合方式）、数列、符号逻辑与图论。不过，还有不少其他主题也属于离散数学的范畴，包括计算机科学、抽象代数、数论、博弈论、概率论与几何学（其中最后两项尤其同时具有离散与非离散两种形态）。

Ultimately the best way to learn what discrete math is about is to do it. Let’s get started! Before we can begin answering more complicated (and fun) problems, we must lay down some foundation. We start by reviewing mathematical statements, sets, and functions in the framework of discrete mathematics.

归根结底，学习离散数学最好的方式就是去做。我们开始吧！在能够着手回答更复杂（也更有趣）的问题之前，必须先打下一些基础。我们将从离散数学的框架下回顾数学语句、集合与函数入手。