1.1 离散数学研究什么

这是整门课程的起点。我们暂时不假设你知道集合、逻辑或证明。本节只建立四个最基本的词：对象、状态、模型和离散。后面所有符号都会从这四个词逐步生长出来。

学完本节，你应该能够：

• 判断一个简单问题更适合离散模型还是连续模型。

• 说清楚模型保留了现实中的哪些信息。

• 把一个小型现实系统拆成有限的状态变量。

• 发现离散化造成的信息损失，而不是把模型误认为现实本身。

先看一个没有公式的例子。假设你站在电梯门口，屏幕显示“3”。这里至少有三个不同层次：

• 对象是我们正在研究的东西，例如这部电梯。

• 状态是对象此刻的一种可区分情况，例如“显示第 3 层”。

• 模型是我们为了回答问题而保留的一组信息。例如，只想告诉乘客电梯在哪一层时，楼层编号可能已经足够。

现实电梯还有高度、速度、震动和电机温度。模型没有记录它们，不代表这些量不存在，只代表当前问题暂时不需要它们。

离散数学研究由一个个可区分对象组成的结构，以及这些对象之间的规则。这里的“离散”不是“零散”，而是指状态之间能够被区分、列举或计数。

电梯位于第 3 层或第 4 层，网络中的两台设备连接或不连接，一段密码包含 8 个字符，一个计算机网络中存在 12 条连接——这些都是离散状态。它们不要求所有可能状态都很少，但要求每个状态具有清楚的边界。

“能够计数”不等于“数目一定有限”。整数 $0,1,2,3,\ldots$ 永远写不完，但我们知道怎样依次列出它们。这样的集合叫作可数。相比之下，在 0 和 1 之间总能继续找到更多实数，不能用相同方式逐个列完。现在只需记住这个直觉；严格的无限集合会在后续内容中再处理。

从连续现象得到离散状态

现实世界常常同时包含连续量和离散量。理想化温度可以在一个区间中连续变化，而温控器的显示屏可能只显示到整数；电梯的实际高度连续变化，而乘客看到的是楼层编号。

判断时不要只看“它是不是一个数字”。楼层编号和温度读数都写成数字，但含义不同：

连续模型允许在两个不同值之间继续取中间值。例如，在 $20.1$ 与 $20.2$ 之间还有 $20.15$。离散模型则先规定可用状态，例如温控器只保存 20 或 21。

离散化（discretization）就是用有限或可数的状态表示更细腻的输入。最简单的方法之一是阈值分类。

假设 $x$ 表示传感器读数，$t$ 表示我们选定的阈值。记号 $q_t(x)$ 的意思是：“使用阈值 $t$ 处理输入 $x$ 后得到的结果。”结果只有 0 和 1 两种。下面的分段公式只是把两条普通语言规则写在一起：

• 若 $x<t$，输出 0。

• 若 $x\ge t$，输出 1。符号 $\ge$ 表示“大于或等于”。

这个模型保留了“是否达到阈值”，却丢失了类别内部的精确差异。$2.1$ 和 $9.7$ 可能都变成 1。离散模型并不等于现实本身；它是为了回答某类问题而保留的信息。

逐步计算一个例子。取阈值 $t=2$，输入依次为 $1.2,1.7,2.1,2.4$：

因此四个输入变成位串 0011。“位”就是只能取 0 或 1 的位置。这个例子还暴露了一个边界：输入恰好等于 2 时，因为规则使用 $x\ge t$，所以应输出 1。

改变实验中的采样点数量时，你改变了观察时机；移动阈值时，你改变了状态边界。两者都可能改变最终位串。更高的采样密度不保证模型一定更有用，因为用途、噪声和存储成本也属于设计问题。

这里出现了两个不同动作，不要把它们混在一起：

• 采样决定在什么位置或时刻读取连续信号。

• 量化决定每次读数被归入哪个离散状态。阈值分类就是一种非常简单的量化。

如果采样太少，波形在两个采样点之间的快速变化可能完全消失。如果状态太少，不同读数又会被压成相同结果。实验让你同时观察这两种信息损失。

模型由问题决定

同一个对象可以有多种正确模型。研究交通流量时，汽车可以是一个个离散对象；研究刹车距离时，速度和路面摩擦系数通常建模为连续量；研究道路连通性时，整辆汽车甚至可以被忽略，只留下路口和道路。

这说明“离散还是连续”不是对象永久携带的标签，而是对象、问题和精度要求共同决定的选择。一个模型只要能够可靠回答目标问题，就可能是有用的；加入无关细节反而会增加理解和计算成本。

选择模型时，可以依次问：

• 我需要回答什么问题？

• 哪些对象必须彼此区分？

• 每个对象有哪些可能状态？

• 哪些细节可以安全忽略？

• 被忽略的细节会在哪些边界情况下造成错误？

所有允许状态合在一起，叫作状态空间（state space）。我们先用大括号列出允许值。下一节会正式把这种对象称为集合，并系统学习相关符号。

例如，六层电梯的楼层状态写成

字母 $F$ 只是给这组楼层状态取的名字，竖线记号 $|F|$ 表示其中状态的数量，所以 $|F|=6$。这个数量也叫作基数，下一节会再次使用。

若还保存方向 $D=\{\text{上},\text{下},\text{停止}\}$ 和门状态 $O=\{\text{开},\text{关}\}$，一次完整记录可以按“楼层、方向、门”的固定顺序写成 $(f,d,o)$。例如 $(3,\text{上},\text{关})$ 表示位于第 3 层、方向向上、门关闭。括号中的顺序不能交换，否则字段含义会改变。

现在只做普通乘法：每个楼层有 3 个方向选择，每个“楼层—方向”组合又有 2 个门状态，因此最多有

种组合。稍后可以再用规则排除“门开着并且正在上行”一类不可能状态。

这个乘法得到的是上界，不保证每种组合在现实中都允许。状态变量告诉我们记录什么，约束告诉我们哪些组合不能发生。区分这两件事，是以后学习逻辑、关系和图模型的重要基础。

分拣实验中的答案依赖明确的理想化假设。例如，数字温度计显示的是离散数字，但它试图表示的物理温度通常先建模为连续量。看到一个数值不意味着它天然属于某一种模型；要先说明对象和问题。

完成分拣后，尝试给每张卡片补上一句话：“为了回答什么问题，我才这样分类？”如果问题改变，分类也可能改变。例如，研究秒表屏幕上的显示字符时，显示状态是离散的；研究真实经过时间时，常使用连续模型。

通向下一节

本节已经多次把允许状态写在大括号中，例如 $\{1,2,3,4,5,6\}$。下一节会给这种“把对象收集在一起”的结构一个正式名称——集合，并回答三个自然问题：怎样判断对象是否属于集合？怎样比较两个集合？一个集合能够产生多少种子集？