TIP

《离散数学及其应用》笔记

# 0 引

# 0.1 为什么要学习计算机?

我们学习计算机是为了什么?是能用一门语言写出来一个让用户满意的 APP?是创造一个 AI 模型?是利用某些框架帮助我们模拟计算?还是为了生计?

于我而言,以上都是,却也可以说全不是

# 0.1.1 以实用性为出发点

计算机对于人类社会的发展有着巨大的推动作用,其以其极高的计算能力为我们解决了无数的难题,现在的计算机可以

  • 迅速计算出很复杂的算数式,并将结果显示出来
  • 将影像播放在屏幕上
  • 将服务器上的 HTML 文档下载到本地,用浏览器显示出来
  • 为用户推送更加适合的广告
  • 等等

简单地说,计算机可以更快、更便捷地带给我们需要的东西,学习计算机,是为了更好地利用它来协助我们,当然,协助到什么程度,要看学到什么层次了

学习计算机,首先是能够使用自己需要的软件,帮助我们完成需要做的事,之后我们在使用过程中不断地思考计算机的运作机理,可以帮助我们解决一些运行 bug 等问题,再之后我们可以通过自己的方式进行创作,可能是熟练地使用某个软件进行一些高级操作、可能是学习一门编程语言写一些脚本协助我们工作……

然而我们当前阶段对于计算机的教育(非计算机专业)大多只是刻板的教书式,很多都是教教用些基本软件(MS Office?),然而计算机真正的操作却是越来越黑(黑匣子)了,这对于开发人员来说是一种成功,因为对于用户更加友好了,但是对于用户本身来说,离计算机却是越来越远了

# 0.1.2 就个人兴趣而言

如果说以前的话,大概也就是一年多以前,计算机对我而言仅仅是一个黑匣子,我能看到的,仅仅是屏幕上的,我能输入的,也仅仅是手动敲一敲(那时候敲得也很慢)、鼠标点一点而已。能让我感兴趣的,大概只有电脑中的,另一个世界——游戏,而这也成为了当今大多数人的现状,虽说用着计算机,却是一点也不懂计算机(当然我那时候不如大多数人)

最初的兴趣,源于一次巧合,有幸组装了一台台式机,认识了曾经在课程中略有耳闻的各种硬件——内存条、显卡、硬盘等等,这算是与底层硬件的一次偶遇

大概半个月后,也算是一次巧合,使我产生了学习 Python 的萌芽,嗯,算是与应用层的一次偶遇

两次偶遇使我对计算机有了新的认识,并产生了浓厚的兴趣,一发不可收,进而逐渐地开始接触计算机科学知识

那么……

# 0.2 什么是计算机科学?

虽然说如今的计算机能够实现的功能五花八门,但是其本质从未改变过,那就是计算,那么问题来了,计算机是如何利用计算来实现现在各种各样的功能的呢?

在计算机诞生之前,就有了自动计算的相关理论,也正是这些理论催生了计算机的诞生,虽然说那个时候计算机还只是一种理想中的模型,但是其理论基础却是建立的相当完善,其中最基础的理论已经成为了一门学科,那便是离散数学

# 0.2.1 离散数学是什么

在最近一年多有了解过一些计算机基础知识,比如有草草学过数据结构、组原、计网,也有正在学的操作系统,但是从没有这样一门学科让我能够觉得,计算机就是它,它就是计算机,而离散数学就是这样的一门学科,它从最基础的逻辑运算开始介绍,对我们真实世界的事物进行建模,形成一门理论进行推演解释

事实上,我们的计算机也正需要这样的完备的、严谨的理论支持,它可不允许有二义性的自然语言出现

# 0.2.2 我们为什么会造出计算机

由于计算机科学的理论基础存在,我们造出的计算机注定是现在的逻辑进行运作,而不是别的样子,基础科学决定了上层模型的形态

# 0.2.3 计算机科学会过时吗

在开始学习计算机之前我曾经担心过,量子计算机已经出现了,现在的计算机技术将来还会适用吗?现在的计算机技术是否会过时?

技术的更迭是不可避免的,说不过时是不可能的,但是令人兴奋的是,技术的更迭代表了人类社会的不断发展,但是有一点我们却是需要牢记的,我们是不断推陈出新的,新的技术是以旧的技术为基础发展而来的

当然,计算机技术依赖于计算机科学,而计算机科学本身是诞生于计算机之前的,它并不依赖于计算机的形态,计算机科学并无所谓过时与不过时,就离散数学这种基础学科而言,在任何一种计算机实现形式中,它都是基础,只不过在不同的事物上需要建立不同的模型

# 0.2.4 计算机科学带给我们的

计算机科学本身是一门逻辑性非常强的学科,就算没有学过专业知识,稍微了解一点编程的人也能体会到其中的严谨性,写错了一个字母可能连编译都通过不了的……

此外,我们通过计算机科学了解了如何将一个真实世界的事物表现为一个严密的数学模型,并利用计算机进行求解

当然,计算机科学还有很多迷人的地方,比如在计网、组原中我们学到了某种功能的分层实现、模块化的思想等等

# 0.3 对计算机科学发展的期许……

当今时代计算机技术在迅速发展,也许计算机本身就在促进着计算机的发展吧,但无论计算机将来发展到什么程度,其本质都不会改变,我认为,我所坚持的,是对计算机科学的一种期许,大概只是因为——热爱

# 1 基础:逻辑和证明

# 1.1 命题逻辑

# 1.1.1 命题

陈述句,非真即假

# 1.1.2 逻辑运算符

  • 否定 (非) ¬p\lnot p
  • 合取 (与) pqp \land q
  • 析取 (或) pqp \lor q
    • 异或 pqp \oplus q ,与“或”不同的是,两种同时满足的情况为假,也就是二者只能选其一
  • 条件语句 (蕴含) pqp \to q

    只有 ppqq 假的情况下才为假,就像一种允诺,而 pp 发生后没有依诺履行 qq ,则其为假

    • 注意逆命题、否命题(注意,不是命题的否定)、逆否命题
  • 双条件语句 (双重蕴含) pqp \leftrightarrow q

    (pq)(qp)(p \to q) \land (q \to p) ,缩写 iffiff (if and only if),只有两者真值相同的时候为真

# 1.2 命题等价式

  • 重言式(永真式):真值永远为真
  • 矛盾式:真值永远为假

# 1.2.1 逻辑等价式

在所有情况下具有相同真值的两个复合命题等价

其定义为:

如果 pqp \leftrightarrow q 是永真式,则复合命题 ppqq 是逻辑等价的,记作 pqp \equiv q

  • 德·摩根律
    • ¬(pq)¬p¬q\lnot (p \lor q) \equiv \lnot p \land \lnot q
    • ¬(pq)¬p¬q\lnot (p \land q) \equiv \lnot p \lor \lnot q

      可扩展到 nn

      • ¬(j=1npj)j=1n¬pj\lnot (\bigvee\limits_{j=1}^n p_j) \equiv \bigwedge\limits_{j=1}^n \lnot p_j
      • ¬(j=1npj)j=1n¬pj\lnot (\bigwedge\limits_{j=1}^n p_j) \equiv \bigvee\limits_{j=1}^n \lnot p_j
  • pq¬pqp \to q \equiv \lnot p \lor q
  • 分配律
    • p(qr)(pq)(pr)p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)
    • p(qr)(pq)(pr)p \land (q \lor r) \equiv (p \land q) \lor (p \land r)
  • 吸收律
    • p(pq)pp \lor (p \land q) \equiv p
    • p(pq)pp \land (p \lor q) \equiv p
  • and so on... 按需查书好了

# 1.3 谓词和量词

# 1.3.1 谓词

我们知道,x>3x > 3 不是一个语句,因为它含一个变量,我们无法判断它的真假,但是我们对 xx 进行赋值,我们就可以立即判断它的真假

我们将“ >3>3 ”抽取出来,这便是一个谓词

既然只要对变量赋值就可以判断真假,那么我们何不直接令其成为一个函数?这样的函数就是命题函数,也称为谓词

比如 P(x)P(x)x>3x > 3

注意,命题函数不是命题,这个已经反复强调过了,因为它并不能判断真假

# 1.3.2 量词

除了对命题函数进行赋值使之成为命题之外,我们使用量词也可以使之成为命题

比如

量词后跟其域,再之后是命题函数,如 x(x2x)\forall x(x^2 \geq x) ,量词优先级比逻辑运算符高

  • 全称量词 (任意) \forall

    xP(x)\forall x P(x)

    • 其等价于 j=1nP(xj))\bigwedge\limits_{j=1}^n P(x_j))
    • x<0(x2>0)x(x<0x2>0)\forall x < 0 (x^2 > 0) \equiv \forall x (x < 0 \to x^2 > 0)
    • 只要找到一个不满足就可知其为假
  • 存在量词 (存在) \exist

    • 其等价于 j=1nP(xj))\bigvee\limits_{j=1}^n P(x_j))
    • z>0(z2=2)z(z>0z2=2)\exist z > 0 (z^2 = 2) \equiv \exist z(z > 0 \land z^2 = 2)
  • 逻辑等价式

    • 分配律
      • x(P(x)Q(x))xP(x)xQ(x)\forall x(P(x) \land Q(x)) \equiv \forall x P(x) \land \forall x Q(x)
      • x(P(x)Q(x))xP(x)xQ(x)\exist x(P(x) \lor Q(x)) \equiv \exist x P(x) \lor \exist x Q(x)
    • 德·摩根律
      • ¬xP(x)x¬P(x)\lnot \exist x P(x) \equiv \forall x \lnot P(x)
      • ¬xP(x)x¬P(x)\lnot \forall x P(x) \equiv \exist x \lnot P(x)

        否定时,论域是不变的

        >>¬P(x)Q(x)>¬x(P(x)Q(x))>x(¬P(x)¬Q(x))>x(P(x)¬Q(x))>P(x)¬Q(x)>> > \begin{aligned} > & \lnot \exist P(x) Q(x) \\ > \equiv & \lnot \exist x (P(x) \land Q(x)) \\ > \equiv & \forall x (\lnot P(x) \lor \lnot Q(x)) \\ > \equiv & \forall x (P(x) \to \lnot Q(x)) \\ > \equiv & \forall P(x) \lnot Q(x) \\ > \end{aligned} >

        另外一个很容易证明,此处不作赘述

# 1.3.3 嵌套量词

一个量词出现在另一个量词的作用域内,如 xy(x+y=0)\forall x \exist y (x + y = 0)

除非都是全称量词或者全是存在量词,否则顺序不可交换

但是我们可以将量词提前,如 x((F(x)P(x))yM(x,y))xy((F(x)P(x))M(x,y))\forall x ((F(x) \land P(x)) \to \exist y M(x, y)) \equiv \forall x \exist y ((F(x) \land P(x)) \to M(x, y))

  • 例,用量词表示极限定义(limxaf(x)=L\lim\limits_{x \to a} f(x) = L)“对每个实数 ε>0\varepsilon > 0 ,存在一个实数 δ>0\delta > 0 ,使得对任意的 xx ,只要 0<xa<δ0 < |x-a| < \delta,就有 f(x)L<ε|f(x) - L| < \varepsilon
    • ε>0δ>0x(0<xa<δf(x)L<ε)\forall \varepsilon > 0 \exist \delta > 0 \forall x (0 < |x-a| < \delta \to |f(x) - L| < \varepsilon)
    • εδx(0<xa<δf(x)L<ε)\forall \varepsilon \exist \delta \forall x (0 < |x-a| < \delta \to |f(x) - L| < \varepsilon)

否定的话,逐层使用德·摩根律就好

# 1.4 推理规则

我们已经可以知道某个命题是真假,但是我们如何通过一个或者多个命题推断出新的命题的真假呢?

# 1.4.1 命题逻辑的有效论证

当我们有条件 p1p2p3pnp_1\ p_2\ p_3\ \cdots\ p_n 的时候,如何推理出结论 qq 为真?

很明显,我们让在所有前提的发生的时候,结论永远为真即可,也就是 (j=1npj)q(\bigwedge\limits_{j=1}^n p_j) \to q 是永真式的情况下,该论证形式是有效的

# 1.4.2 命题逻辑的推理规则

如何判定一个式子是永真式?某些式子我们可以记住,但是真实情况下有很多式子并没有对应的用来套用,那难道我们要去用真值表吗?

本节先介绍我们需要记住的一些式子,下节介绍如何根据已有式子推出更加复杂的式子

名称 永真式 逻辑解释
假言推理 (p(pq))q(p \land (p \to q)) \to q 已知在发生前提 pp 时必发生结果 qq ,并且前提 pp 发生了,所以结果 qq 一定会发生
取拒式 (¬q(pq))¬p(\lnot q \land (p \to q)) \to \lnot p 已知在发生前提 pp 时必发生结果 qq ,但是结果 qq 并没有发生,所以前提 pp 一定没发生
假言三段论 ((pq)(qr))(pr)((p \to q) \land (q \to r)) \to (p \to r) 已知发生前提 pp 时必发生 qq,且发生 qq 时必发生 rr ,故发生 pp 时必发生 rr
析取三段论 ((pq)¬p)q((p \lor q) \land \lnot p) \to q 已知 ppqq 至少发生了一个,并且 pp 没发生,那么 qq 必然发生
附加律 p(pq)p \to (p \lor q) 已知 pp 发生了,那么当然 ppqq 之中至少发生一件是对的了
化简律 (pq)p(p \land q) \to p 已知 ppqq 都发生了,那么 pp 当然发生了
合取律 ((p)(q))(pq)((p) \land (q)) \to (p \land q) 已知 pp 发生了, qq 也发生了, 所以说 ppqq 都发生了自然是对的
消解律 ((pq)(¬pr))(qr)((p \lor q) \land (\lnot p \lor r)) \to (q \lor r) 不太好表述啊……

# 1.4.3 使用推理规则建立论证

比如我们想从 ¬pq\lnot p \land qrpr \to p¬rs\lnot r \to ssts \to t 推出结论 tt ,要如何做到呢?

  1. ¬pq\lnot p \land q ,前提引入
  2. ¬p\lnot p , 化简律,用 (1)
  3. rpr \to p , 前提引入
  4. ¬r\lnot r , 取拒式,用 (2)(3)
  5. ¬rs\lnot r \to s ,前提引入
  6. ss , 假言推理,用 (4)(5)
  7. sts \to t ,前提引入
  8. tt ,假言推理,用 (6)(7)

# 1.4.4 量化命题的推理规则

名称 推理规则
全称实例 xP(x)P(c)\forall x P(x) \to P(c)
全称引入 P(c)xP(x)P(c) \to \forall x P(x) ,其中 cc 为任意值才能得出该结论
存在实力 xP(x)P(c)\exist x P(x) \to P(c)
存在引入 P(c)xP(x)P(c) \to \exist x P(x)

# 1.5 证明

如何得知一个语句的真实性?

# 1.5.1 直接证明法

如何证明条件语句 pqp \to q ?首先假设 pp ,通过推理得到 qq ,那么 pqp \to q 为真

# 1.5.2 反证法

基于条件语句逆反命题等价于自身的性质,即要证 pqp \to q 先证 ¬q¬p\lnot q \to \lnot p

  • 空证明 证明 pp 为假即可知 pqp \to q 为真
  • 平凡证明 证明 qq 为真即可知 pqp \to q 为真

# 1.5.3 归谬证明法

我们要证 pp 为真,可以通过找一个矛盾式 qq 使得 ¬pq\lnot p \to q 为真,因为 qq 为假,则 ¬p\lnot p 为假,即 pp 为真

由于 r¬rr \land \lnot r 是显然的矛盾式,所以经常使用其作为上式中的 qq

# 1.5.4 等价证明法

要证 pqp \leftrightarrow q 可证 (pq)(qp)(p \to q) \land (q \to p)

一般地,要证 p1p2p3pnp_1 \leftrightarrow p_2 \leftrightarrow p_3 \leftrightarrow \cdots \leftrightarrow p_n 可证 (p1p2)(p2p3)(pnp1)(p_1 \to p_2) \land (p_2 \to p_3) \land \cdots \land (p_n \to p_1) ,只需要形成这样一个全串起来的环就行,不需要任何两个之间都证一遍

# 1.5.5 穷举证明法和分情形证明法

均基于 [(p1p2p3pn)q][(p1q)(p2q)(pnq)][(p_1 \lor p_2 \lor p_3 \lor \cdots \lor p_n) \to q] \leftrightarrow [(p_1 \to q) \land (p_2 \to q) \land \cdots \land (p_n \to q)] 是重言式,将 pp 分为 p1p2pnp_1 \lor p_2 \lor \cdots \lor p_n ,即将其论域分为多个子论域,当然,这些个子论域包含了所有的情况

  • 穷举论证法 将有穷的情况一一列出,并分别证明
  • 分情形证明法 当整个论域不方便一起证明时,可将论域分割成一个个比较方便证明的子论域,一一证明

另外,值得注意的一点是,我们可以通过不失一般性对证明过程进行简化,比如在一个可以互换 xxyy 的式子中,如果我们已经证明过 xx ,那么我们可以知道 yy 也是一样的

# 1.5.6 存在性证明

  • 构造性的 通过找到这样一个实例来说明这样的实例是存在的
  • 非构造性的 并不是真正的找出这样的实例,而是通过证明得出这样的实例真的存在

# 1.5.7 唯一性证明

  1. 存在 xx 具有该性质
  2. 任何其他不是 xx 的都没有这个性质

# 1.5.8 寻找反例

通过寻找反例来证明一个语句是假的

# 1.5.9 证明策略实践

当数学家相信猜想可能是真的时,他们会尝试寻找证明。如果他们找不到证明,他们就会寻找反例。当他们寻找不到反例时,他们又会转回来再次试图证明猜想。

——《离散数学及其应用》 1.8.7 证明策略实践

# 2 基本结构:集合、函数、序列、求和与矩阵

# 2.1 集合

空集 \varnothing

# 2.1.1 集合的表示方法

  • 花名册方法 如 V={1,2,3,4,5}V = \{1, 2, 3, 4, 5\}
  • 集合构造器 如 O={xRx=p/q,pN+,qN+}O = \{x \in R | x = p / q, p \in N^+, q \in N^+\}

# 2.1.2 子集

ABA \subseteq B 当且仅当 x(xAxB)\forall x (x \in A \to x \in B)

  • 每个非空集合 SS 都至少有两个子集,空集和集合 SS 本身
  • 证明两个集合 AABB 相等,就证明 ABA \subseteq BBAB \subseteq A

# 2.1.3 集合的大小

集合 SS 的基数 S|S| ,为集合中的元素数

# 2.1.4 幂集

集合 SS 中所有子集的集合,记作 P(S)P(S)

如果一个集合有 nn 个元素,那么它的幂集就有 2n2^n 个元素

# 2.1.5 笛卡尔积

  • 有序 nn 元组:区别于集合,是一种有序的结构,表示为 (a1,a2,,an)(a_1, a_2, \cdots , a_n)
  • 序偶: 有序二元组

笛卡尔积:所有序偶 (a,b)(a, b) 的集合,其中 aAa \in AbBb \in B ,即

A×B={(a,b)aAbB} A \times B = \{ (a, b) | a \in A \land b \in B\}

笛卡尔积可以用来表示两个集合之间的关系,比如集合 AA 为一所大学所有学生的集合,集合 BB 为该大学开设的所有课程的集合,则两学校的笛卡尔积可以表示该校学生的选课的所有情况

  • A×BB×AA \times B \not = B \times A
  • A2=A×AA^2 = A \times A
  • 笛卡尔积 A×BA \times B 的一个子集称为集合 AABB 之间的一个关系,沿用上例,可以理解为某些学生选了某些课

# 2.1.6 真值集和量词

  • 论域 DD 下,谓词 PP 的真值集为 {xDP(x)}\{ x \in D | P(x) \}
  • 全称 xS(P(x))\forall x \in S (P(x))
  • 存在 xS(P(x))\exist x \in S (P(x))

# 2.2 集合运算

# 2.2.1 基本运算

  • AB={xxAxB}A \cup B = \{ x | x \in A \lor x \in B \}

    i=1n=A1A2An\bigcup \limits_{i = 1}^n = A_1 \cup A_2 \cup \cdots \cup A_n

  • AB={xxAxB}A \cup B = \{ x | x \in A \land x \in B \}
    • AB=A+BAB|A \cup B| = |A| + |B| - |A \cap B|

      i=1n=A1A2An\bigcap \limits_{i = 1}^n = A_1 \cap A_2 \cap \cdots \cap A_n

  • AB={xxAxB}A - B = \{ x | x \in A \land x \notin B \}
    • AB=ABA - B = A \cap \overline{B}
  • AB={xUxA}A \cup B = \{ x \in U | x \notin A \}
    • A=UA\overline{A} = U - A

# 2.2.2 集合恒等式

  • 分配律
    • A(BC)=(AB)(AC)A \cup (B \cap C) = (A \cap B) \cup (A \cap C)
    • A(BC)=(AB)(AC)A \cap (B \cup C) = (A \cup B) \cap (A \cup C)
  • 德·摩根律
    • AB=AB\overline{A \cap B} = \overline{A} \cup \overline{B}
    • AB=AB\overline{A \cup B} = \overline{A} \cap \overline{B}

如何证明恒等式?

  • 直接证明法 证明 ABA \subseteq B 并且 BAB \subseteq A “即可”
  • 集合构造器 始终使用集合构造器表示集合,辅之以逻辑运算,得到要的式子
  • 成员表 类似于真值表,列出各个元素是否属于该集合

# 2.2.3 集合的计算机表示

可用位串来表示 UU 的子集 AA,如果元素 aiAa_i \in A ,则第 ii 位为 1 ,否则为 0 ,这样可以很方便地实现交并补操作(按位与、或、非)

# 2.3 函数

# 2.3.1 定义

如果对每一个元素 aAa \in A 都有且仅有一个序偶 (a,b)(a, b) ,则它就定义了 AABB 的一个函数 ff

  • 定义域 原像 aa 的集合
  • 值域 像 bb 的集合
  • 陪域 BB
  • 值域只是陪域的一部分(子集)
  • 如果改变函数的定义域或陪域,那么将得到一个不同的函数,如果改变元素的映射关系,也会得到一个不同的函数

# 2.3.2 一对一、映上、一一对应

  • 一对一函数(单射函数)

    不允许多个原像对应同一个像

  • 映上函数(满射函数)

    值域等于陪域

  • 一一对应函数(双射函数)

    既是一对一的,又是映上的

# 2.3.3 反函数

一一对应才有反函数,故一一对应关系又称为可逆的

  • 定义函数的合成 $f \circ g $ ,(fg)(a)=f(g(a))(f \circ g)(a) = f(g(a))
  • f1f=ιAf^{-1} \circ f = \iota_Aff1=ιBf \circ f^{-1} = \iota_B(f1)1=f(f^{-1})^{-1} = f

    ι(x)=x\iota(x) = x

# 2.3.4 函数的图

A×BA \times B 中各个序偶集合,可以画出来帮助理解

# 2.3.5 一些重要的函数

  • 向下取整 x\lfloor x \rfloor
  • 向上取整 x\lceil x \rceil
  • 阶乘函数 n!n!

# 2.4 序列与求和

序列的项的显式公式称为闭公式

常用序列

  • 几何级数
  • 算数级数

# 2.5 集合的基数

# 2.5.1 定义

有限集的基数很简单,就是元素的个数,那么无限集呢?

对于无限集,我们可以定义他们之间的相对大小,但并不能定义他们之间的大小

如果存在一个从 AABB 之间的一个一一对应函数,那么他们有相同的基数,即 A=B|A| = |B|

相似地,如果存在从 AABB 之间的一个一对一函数,那么 AB|A| \leq |B|

# 2.5.2 可数集

一个集合或者是有限集或者与自然数集具有相同的基数,这个集合就称为可数的

如果一个无限集 SS 是可数的,我们用符号 0\alef_0 表示集合 SS 的基数 S|S|

  • 无限集是可数的当且仅当可以把集合中的元素排列成序列(下标是正整数
  • 我们可以得出几个结论:
    • 有理数集是可数的
    • 无理数集是不可数的
  • 如果 AABB 是可数集合,则 ABA \cup B 也是可数集合

# 2.5.3 不可计算函数的存在性

如果存在某种编程语言写的计算机程序能计算一个函数的值,那么这个函数称为是可计算的

  • 首先,任何编程语言写的计算机程序的集合是可数的
  • 其次,存在不可数无限多个不同的从一个特定的可数无限集到自身的函数
  • 所以,能写出来的函数是不足以满足所有的问题的,即存在不可计算的函数

# 2.6 矩阵

这里注意下 010-1 矩阵即可,其他的在线代就学过了

  • 010-1 矩阵的并 \lor ,即逐项逻辑与
  • 010-1 矩阵的交 \land ,即逐项逻辑并
  • 010-1 矩阵的布尔积 \odot ,与矩阵乘法类似,各项的乘号换成 \land (逻辑乘),各结果的加号换成 \lor (逻辑和)
  • 010-1 矩阵的布尔幂 A[r]A^{[r]} ,就是布尔积 rr

# 3 计数

# 3.1 计数的基础

  • 乘积法则
  • 求和法则
  • 减法法则 两个集合的容斥原理
  • 除法法则

# 3.2 鸽巢原理

如果 k+1k + 1 个或更多的物体放入 kk 个盒子,那么至少有一个盒子包含了 22 个或更多的物体

如果广义化,可以得到广义鸽巢原理如下:

如果 NN 个物体放入 kk 个盒子,那么至少有一个盒子包含了至少 N/k\lceil N/k \rceil 个物体

由广义鸽巢定理,我们可以得到以下定理

每个由 n2+1n^2 + 1 个不同实数构成的序列都包含一个长为 n+1n + 1 的严格递增子序列或严格递减子序列

# 3.3 排列与组合

  • 排列 AnmA_n^m
  • 组合 CnmC_n^m

# 3.4 二项式系数和恒等式

# 3.4.1 二项式定理

(x+y)n=j=0nCnjxnjyj (x + y)^n = \sum_{j = 0}^n C_n^j x^{n-j} y^j

x=1,y=1x = 1, y = 1 可得推论

j=0nCnk=2n \sum_{j = 0}^n C_n^k = 2^n

类似的,还可得到一些其它推论,不作赘述

# 3.4.2 帕斯卡恒等式

Cn+1k=Cnk1+Cnk C_{n + 1}^k = C_n^{k - 1} + C_n^k

# 3.5 排列与组合的推广

  • 有重复的排列

    具有 nn 个对象的集合运行重复的 rr 排列数是 nrn^r

  • 有重复的组合

    nn 个元素的集合中允许重复的 rr 组合有 Cn+r1rC_{n + r - 1}^r

  • 等等等等,具体问题具体分析即可,对问题的探索过程可以参考书上内容(我才不会说是因为我懒得打了呢)

# 3.6 生成排列与组合

既然我们已经排列与组合都有多少种了,可是我们如何去求解分别是哪些种呢?有没有专门的算法进行求解呢?

# 3.6.1 生成排列

首先将原有元素从 11nn 进行排列,作为原始的字典顺序,之后按照该顺序进行生成后续顺序

# 3.6.2 生成组合

使用位串对元素进行标记,计算位串的顺序,据此生成组合

# 4 高级计数技术

我们上章讨论了一些简单的计数问题,但是还有很多计数问题使用上章的方法是不容易求解的,本章会对这些内容进行讨论

# 4.1 递推关系的应用

# 4.1.1 用递推关系构造模型

如著名的

  • 兔子和斐波那契数问题
  • 汉诺塔问题
  • 不含 2 个连续 0 的 n 位二进制位串数问题
  • 编码字的枚举问题

# 4.1.2 动态规划问题

比如最大参与讲座总数问题

# 4.2 求解线性递推关系

形如

an=c1an1+c2an2++ckank+F(n)a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k} + F(n)

的递推关系,,我们称其为线性的,当 F(n)=0F(n) = 0 时,我们称其为齐次的,类似于微分方程的研究,我们先考虑线性齐次递推关系

# 4.2.1 求解常系数线性齐次递推关系

我们需要寻找形如 an=rna_n = r^n 的解,我们可以将其代入递推关系中,可以知道我们需要求解

rkc1rk1c2rk2ck1rck=0r^k - c_1 r^{k-1} - c_2 r^{k-2} - \cdots - c_{k-1} r - c_k = 0

我们称其为该递推关系的特征方程

下面就是求解出其根啦,比如我们考虑二阶的情况

  • 有两个不相等的实根 r1,r2r_1, r_2 ,那么 an=α1r1n+α2r2na_n = \alpha_1 r_1^n + \alpha_2 r_2^n
  • 两个相等的实根 r1r_1 ,那么 an=α1r1n+α2nr1na_n = \alpha_1 r_1^n + \alpha_2 n r_1^n

    至于 α1,α2\alpha_1, \alpha_2 我们很容易通过初值列方程求解

在二阶的结论很容易推广到高阶,不作赘述

# 4.2.2 常系数线性非齐次的递推关系

还是和微分方程求解那里很类似,求解其相伴的线性齐次递推关系的一个解,然后加上该递推关系的一个特解就好啦

# 4.3 分治算法和递推关系

分治算法是将一个大问题分解成多个小问题进行解决,我们可以很容易地得到其递推关系式 f(n)=af(n/b)+g(n)f(n) = af(n/b) + g(n)

比较经典的分治问题有

  • 二分搜索
  • 找一个序列的最大和最小
  • 整数的快速乘法 对二进制数进行分块,那么两个 2n2n 位整数的乘法可以用 3 个 nn 位整数的乘法加上加法、减法以及一位来实现
  • 快速矩阵乘法 类似于上面的算法

我们还可以得到分治问题的时间复杂度算法,这里就不列出了

# 4.4 生成函数

我们将序列的项作为幂级数(形式幂级数,只用其一些性质,并不是真的将其表示为函数)的系数,这样幂级数的一些结论(某个幂级数的和函数、逐项微分等性质)就可以用来研究一些计数问题,我们主要关注的是幂级数里某一项或几项的阶数以及其系数

# 4.5 容斥

前面其实我们已经了解过一些容斥原理在其他问题上的表现了,比如说两个有穷集的并集的元素数明显是

AB=A+BAB |A \cup B| = |A| + |B| - |A \cap B|

再看看三个有穷集,不难得出 ABC=A+B+CABACBC+ABC|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|

这样,我们很容易推广到 nn 个有穷集的情况

A1A2An=1inAi1i<jnAiAj+1i<j<knAiAjAk+(1)n+1A1A2An|A_1 \cup A_2 \cup \cdots \cup A_n| = \sum\limits_{1 \leq i \leq n} |A_i| - \sum\limits_{1 \leq i < j \leq n} |A_i \cap A_j| + \sum\limits_{1 \leq i < j < k \leq n} |A_i \cap A_j \cap A_k| - \cdots + (-1)^{n+1} |A_1 \cap A_2 \cap \cdots \cap A_n|

# 4.6 容斥原理的应用

容斥原理的另一种形式,用于求解在一个集合中的元素胡,使得这些元素不具有 nn 个性质 P1,P2,,PnP_1, P_2, \cdots , P_n 中的任何一条性质

该形式往往有着更多的应用,比如

  • 找出不超过一个给定正整数的素数的个数 可以先找合数,然后根据容斥原理反推质数
  • 映上函数的个数
  • 计数排列 nn 个物体并使得没有一个物体在他的初始位置上的方式数

# 5 关系

# 5.1 关系及其性质

AABB 是集合,一个从 AABB 的二元关系是 A×BA \times B 的子集

(a,b)R(a, b) \in R 也记作 aRbaRb

# 5.1.1 集合的关系

集合 AA 到他自身的关系更令人感兴趣

  • nn 元素集合上有 2n22^{n^2}个不同的关系

# 5.1.2 集合的性质

  • 自反 若对每个元素 aAa \in A(a,a)R(a, a) \in R ,那么定义在集合 AA 上的关系 RR 称为是自反的
  • 对称 对于任意 a,bAa, b \in A ,若只要 (a,b)R(a, b) \in R 就有 (b,a)R(b, a) \in R ,则称定义在集合 AA 上的关系 RR 为对称的
  • 反对称 对于任意 a,bAa, b \in A ,若 (a,b)R(a, b) \in R(b,a)R(b, a) \in R ,一定有 a=ba = b ,则称定义在集合 AA 上的关系 RR 为反对称的
  • 传递 若对于任意 a,b,cAa, b, c \in A(a,b)R(a, b) \in R 并且 (b,c)R(b, c) \in R(a,c)R(a, c) \in R ,那么定义在集合 AA 上的关系 RR 称为传递的

# 5.1.3 关系的组合

  • R1R2R_1 \cup R_2
  • R1R2R_1 \cap R_2
  • R1R2R_1 \oplus R_2
  • R1R2R_1 - R_2
  • R2R1R_2 - R_1
  • R1R2R_1 \circ R_2 关系的合成,可将自身的合成表示为 nn 次幂的形式

# 5.2 n 元关系及其应用

# 5.2.1 数据库和关系

关系数据模型

  • 由记录组成
  • 记录是由域构成的 nn 元组

# 5.2.2 n 元关系的运算

  • 选择 返回满足条件的 nn 元关系
  • 投影 返回 nn 元组中的 mm 个分量
  • 连接 将两个表合成一个表

# 5.3 关系的表示

除了前面提到的用列举有序对和表的方式来表示关系,下面我们介绍两种新的表示关系的方式

# 5.3.1 用矩阵表示关系

使用 010-1 矩阵即可,如果 aRbaRb 那么 MR(a,b)=1M_R(a, b) = 1

很容易想到关系的性质在矩阵表示情况下的表现

  • 自反 MRM_R 主对角线上的所有元素都为 1
  • 对称 MRM_R 是对称矩阵,即 MR=(MR)TM_R = (M_R)^T
  • 反对称 对称位置上相反

至于运算

  • MR1R2=MR1MR2M_{R_1 \cup R_2} = M_{R_1} \lor M_{R_2}
  • MR1R2=MR1MR2M_{R_1 \cap R_2} = M_{R_1} \land M_{R_2}
  • MSR=MRMSM_{S \circ R} = M_R \odot M_S
  • MRn=MR[n]M_{R^n} = M_R^{[n]}

# 5.3.2 用图表示关系

使用有向图来表示

性质的表现

  • 自反 每个顶点都有环
  • 对称 对有向图不同顶点之间的每一条边都存在一条方向相反的边
  • 反对称 在两个不同的顶点之间不存在两条方向相反的边

# 5.4 关系的闭包

如果存在包含 RR 的具有性质 PP 的最小传递关系 SS ,并且 SS 是所有包含 RR 且具有性质 PP 的关系的子集,那么 SS 叫做 RR 的关于性质 PP 的闭包

# 5.4.1 自反闭包

RδR \cup \delta ,其中 δ\deltaAA 上的对角关系

# 5.4.2 对称闭包

RR1R \cup R^{-1}

# 5.4.3 传递闭包

传递闭包的推导比较复杂,先从有向图的路径说起

  • 有向图的路径

    不难理解,路径就是若干条有向边首尾相连而成,如果在关系里看就是若干个关系的合成

    不难得到下面的定理

    RR 是集合 AA 上的关系,从 aabb 存在一条长为 1 的路径,当且仅当 (a,b)R(a, b) \in R

  • 连通性关系

    连通性关系 RR^* 使得原本关系 RR 上任何两个元素之间都有一条长度至少为 1 的路径

    易知 R=n=1RnR^* = \bigcup\limits_{n=1}^\infty R^n

  • 传递闭包

    关系 RR 的传递闭包等于连通性关系 RR^*

    确定两个顶点之间是否存在一条路径,不需要检测任意长的路径,只需要检测到 nn 条边的情况就行了,也就是说 R=n=1nRnR^* = \bigcup\limits_{n=1}^n R^n

  • 如何计算

    • 普通矩阵运算 按照上面的描述,依次从 RR 算到 RnR^n 并取并,需要 O(n4)O(n^4)
    • 沃舍尔算法 依次加点,只需要 O(n3)O(n^3)

# 5.5 等价关系

如果一个集合上的关系是自反的对称的传递的,那么称其为等价关系

# 5.5.1 等价类

RR 是定义在集合 AA 上的等价关系,与 AA 中的一个元素 aa 有关系的所有元素的集合叫作 aa 的等价类,记为 [a]R[a]_R 当只考虑一个关系时,可直接记为 [a][a]

# 5.5.2 集合的划分

很明显,集合上所有元素等价类的并集就是集合本身,而两个等价类或者相等或者不相交,故可使用等价类对集合进行划分

# 5.6 偏序

如果一个集合上的关系是自反的反对称的传递的,那么称其为偏序关系

# 5.6.1 概念

在一个偏序集中,记号 aba \preccurlyeq b 表示 (a,b)R(a, b) \in R

  • 偏序集 (S,)(S, \preccurlyeq) 中的元素 aabb 是可比的,如果 aba \preccurlyeq bbab \preccurlyeq a
  • 如果偏序集中每对元素都可比,那么该偏序集称为全序集
  • 如果偏序集是全序集且其每个非空子集都有一个最小元素,就称它为良序集

# 5.6.2 字典顺序

类似于字符串的比较,或者说字符串就是据此比较的

# 5.6.3 哈塞图

因为偏序关系的图上有着很多一定存在的边,所以我们可以将其去掉,只留下我们所关心的部分,用来表征偏序关系就行了

  • 因为自反,所以每个顶点都有环,可以将环去掉
  • 因为传递,所以会有若干个因为传递性而出现的边,可以将它们去掉
  • 排列每条边使得它的起点在终点下面,移走有向边上所有的箭头

# 5.6.4 极大元与极小元

  • 一个偏序集的极大元不小于这个偏序集的任何其他元素,极小元相反
  • 一个偏序集的最大元大于这个偏序集的任何其他元素,最大元相反
  • 如果 uuSS 中的元素,使得对所有的元素 aAa \in A ,有 aua \preccurlyeq u ,那么 uu 称为 AA 的一个上界,下界相反
  • 如果 xx 是一个上界并且它小于 AA 的任何其他的上界,那么称 xxAA最小上界,最大下界相反

这些可以类比于连续数学中的概念理解,注意离散数学要考虑其所在的集合

# 5.6.5 格

如果一个偏序集的每对元素都有最小上界和最大下界,就称这个偏序集为

应用:

  • 信息流的格模型

# 5.6.6 拓扑排序

如果只要 aRbaRb 就有 aba \preccurlyeq b ,则称一个全序 \preccurlyeq 与偏序 RR相容

从一个偏序构造一个相容的全序称为拓扑排序

应用:

  • 处理任务的前驱后继关系

实现:

  • 不断从偏序集中选取极小元,直至偏序集为空

# 6 图

# 6.1 图和图模型

  • 简单图 边无向 不允许多重边 不允许环
  • 多重图 边无向 允许多重边 不允许环
  • 伪图 边无向 允许多重边 允许环
  • 简单有向图 边有向 不允许多重边 不允许环
  • 有向多重图 边有向 允许多重边 允许环
  • 混合图 边有向无向混合 允许多重边 允许环

# 6.1.1 图模型

  • 社交网络
    • 交往和朋友关系图
    • 影响图 有向
    • 合作图
  • 通信网络
    • 呼叫图
  • 信息网络
    • 网络图
    • 引用图
  • 软件设计应用
    • 模块依赖图
    • 优先图与并发处理
  • 路线图
    • 航线图
    • 道路网
  • 生态网
    • 生态学中的栖息地重叠图
    • 蛋白质相互作用图
  • 比赛模型
    • 循环赛
    • 单淘汰赛

# 6.2 图的术语和几种特殊的图

# 6.2.1 基本术语

  • 顶点 vv 的所有相邻顶点的集合记作 N(v)N(v)
  • AAVV 的子集,那么 N(A)=vAN(v)N(A) = \bigcup \limits_{v \in A} N(v)
  • 无向图中,顶点的度是与该顶点相关联的边的数目,环双倍,记作 deg(v)deg(v)
    • 度为 0 的顶点称为孤立的
    • 度为 1 的顶点称为悬挂的
  • 握手定理:无向图顶点的度之和是边数的 2 倍
    • 无向图有偶数个度为奇数的顶点
  • 顶点的入度记作 deg(v)deg^-(v) ,定点的出度记作 deg+(v)deg^+(v) ,环对于入度出度贡献均为 1
  • 因为每条边都有一个起点和一个终点,所以在带有向边的图中,所有顶点的入度之和与所有顶点的出度之和相等且等于图中的边数

# 6.2.2 一些特殊的简单图

  • 完全图 KnK_n
  • 圈图 CnC_n
  • 轮图 WnW_n
  • nn 立方体图 QnQ_n

# 6.2.3 二分图

将简单图的顶点分成两个集合,集合内任意两顶点没有边,那么就是一个二部划分

可以用上色的方法判断一个简单图是不是二分图,用两种颜色上色,且相邻顶点颜色不同,如果满足就是一个二分图

  • 完全二分图 Km,nK_{m, n}

# 6.2.4 二分图和匹配

任务分配问题,将员工和任务各作一个集合,然后看两个集合的二分图

# 6.2.5 特殊类型图的一些应用

  • 局域网
    • 星型拓扑 完全二分图
    • 环形拓扑 圈图
    • 混合形式 轮图
  • 并行计算的互连网络
    • 任意两个处理器都有连接
    • 线性阵列
    • 栅格网络(二维阵列)
    • 超立方体 对应前面的 nn 立方体图

# 6.2.6 从旧图构造新图

  • 删除或增加图中的边
  • 边的收缩 去掉边后,将边的两端点连接成一个端点
  • 从图中删除顶点
  • 图的并集

# 6.3 图的表示和图的同构

# 6.3.1 图的表示

  • 邻接表
  • 邻接矩阵
  • 关联矩阵 矩阵的一个轴是各顶点,一个轴是各边,如果某个边连接了某个顶点,那么该位置为 1

# 6.3.2 图的同构

可根据图形不变量来判断,同构的两个图图形不变量一定相同,但图形不变量相同的两个图并不一定同构

常用的图形不变量

  • 顶点数
  • 边数
  • 对应顶点的度
  • 长度为 kk 的简单回路的存在性,其中 kk 是大于 2 的正整数

# 6.4 连通性

# 6.4.1 通路

边的序列,类似于关系里面的路径

  • 回路: 起点和终点相同的通路
  • 简单通(回)路: 若一条通路(回路)不重复地包含相同的边,就称它为简单的

# 6.4.2 无向图的连通性

若无向图中每一对不同的顶点之间都有通路,则称该图为连通的

  • 连通分支: 即极大连通子图

# 6.4.3 图是如何连通的

  • 割点: 去掉该点之后产生更多连通分支

  • 点割集: 去掉该集合内的点,会产生更多连通分支

    • 除了完全图之外,每个连通图都有一个点割集,点割集最小的顶点数记为 κ(G)\kappa (G) ,叫做点连通度
    • 完全图记 κ(G)=n1\kappa (G) = n - 1
  • 割边: 去掉该边之后产生更多连通分支

  • 边割集: 去掉该集合内的边,会产生更多连通分支

    • 边连通度 λ(G)\lambda(G)
  • 点连通度、边连通度的不等式 κ(G)λ(G)minvVdeg(v)\kappa (G) \leq \lambda (G) \leq \min \limits_{v \in V} deg(v)

# 6.4.4 有向图的连通性

  • 强连通图: 有向图中任意顶点 aabb ,都有从 aabb 和从 bbaa 的通路
  • 弱连通图: 有向图的基本无向图是连通的即可

# 6.4.5 计算顶点之间的通路数

类似于 5.4.3 关系的运算,用邻接矩阵 AA 表示图,从 viv_ivjv_j 长度为 rr 的不同通路的数目等于 ArA^r 的第 (i,j)(i, j) 项,其中 rr 是正整数

# 6.5 欧拉通路与哈密顿通路

# 6.5.1 欧拉通路与欧拉回路

  • 欧拉回路 包含图 GG 中每一条边的简单回路

  • 欧拉通路 包含图 GG 中每一条边的简单通路

  • 充要条件

    • 欧拉回路 每一个顶点必有偶数度
    • 欧拉通路 恰有 2 个度为奇数的顶点

欧拉回路的主要应用问题:

  • 中国邮递员问题

# 6.5.2 哈密顿通路与哈密顿回路

  • 哈密顿回路 包含图 GG 中每一个顶点的简单回路
  • 哈密顿通路 包含图 GG 中每一个顶点的简单通路

哈密顿回路很难找到存在的充要条件,但是有一些充分条件可以判断哈密顿回路不存在

  • 带有度为 1 的顶点的图没有哈密顿回路
  • 若图中有度为 2 的顶点,则关联这个顶点的两条边属于任意一条哈密顿回路
  • 狄拉克定理 如果 GG 是有 nn 个顶点的简单图,其中 n3n \geq 3 ,并且 GG 中每个顶点的度都至少为 n/2n/2 ,则 GG 有哈密顿回路
  • 欧尔定理 如果 GG 是有 nn 个顶点的简单图,其中 n3n \geq 3 ,并且对于 GG 中每一对不相邻的顶点 uuvv 来说,都有 deg(u)+deg(v)ndeg(u) + deg(v) \geq n ,则 GG 有哈密顿回路(很明显,这一条可以推出上一条)

另外

  • n3n \geq 3 时, KnK_n 有哈密顿回路

哈密顿回路的主要应用问题:

  • 旅行商问题
  • 格雷码

# 6.6 最短通路问题

本节主要研究加权图,通路的长度是指经过各边的权值之和

# 6.6.1 最短通路算法

Dijkstra 算法,也就是数据结构中学的有权图的单源最短路径算法,就是不断收录新的顶点,并对有关联的未收录的顶点进行更新,这样保证了最短路径一定只通过已收录的点

# 6.6.2 旅行商问题

比较简单粗暴的方法是,检查所有的哈密顿回路……但这复杂度太高了,一般情况下,只用近似算法,得到近似与精确值的解

# 6.7 平面图

若可以在平面中画出一个图而边没有任何交叉,则这个图是平面图

平面图的一些应用:

  • 电子电路设计
  • 公路网的设计

# 6.7.1 欧拉公式

GG 是带 ee 条边和 vv 个顶点的连通平面简单图,设 rrGG 的平面图表示中的面数(面是被边分割出来的那些,包括那个无界面),则 r=ev+2r = e - v + 2

  • 推论 1: 若 GGee 条边和 vv 个顶点的连通平面简单图,其中 v3v \geq 3 ,则 e3v6e \leq 3v - 6
  • 推论 2: 若 GG 是连通平面简单图,则 GG 中有度数不超过 5 的顶点
  • 推论 3: 若连通平面简单图有 ee 条边和 vv 个顶点, v3v \geq 3 并且没有长度为 3 的回路,则 e2v4e \leq 2v - 4

# 6.7.2 库拉图斯基定理

首先,K3,3K_{3, 3}K5K_5 都是非平面图,那么包含他们的图一定也都是非平面图

同胚的定义: 在某个边上打个点(去掉某条边,增加一个顶点和两条边),这样的操作称为初等细分,初等细分前后的图称为是同胚的

库拉图斯基定理: 一个图是非平面图当且仅当它包含一个同胚K3,3K_{3, 3}K5K_5子图

# 6.8 图着色

参考地图的着色问题,将其建模为图,相邻图块的顶点之间加边

  • 简单图的着色是对该图的每个顶点都指定一种颜色,使得没有两个相邻的顶点颜色相同

  • 图的着色数是着色这个图所需要的最少颜色数,图 GG 的着色数记作 χ(x)\chi(x)

  • 四色定理 : 平面图的着色数不超过 4

# 6.8.1 简单图的着色数

  • KnK_n 的着色数是 nn
  • Km,nK_{m, n} 的着色数是 2
  • CnC_n 的着色数
    • nn 是奇数且 n>1n > 1,着色数为 3
    • nn 是偶数,着色数为 2

# 6.8.2 图着色的应用

  • 安排期末考试 安排考试使得没有同学同时考两门
  • 频率分配 将频道分配给各个电视台,避免两家电视台在相同频道播出
  • 变址寄存器 编译器将频繁使用的变量暂存大变址寄存器中,那么最少需要几个变址寄存器呢?

# 7 树

# 7.1 树的概述

  • 定义:树是没有简单回路连通无向图
    • 如果不连通,就是森林啦
    • 一个无向图是树当且仅当在它的每对顶点之间存在唯一简单通路

# 7.1.1 有根树

有根树是指定一个顶点作为根并且每条边的方向都离开根的树

  • mm 叉树 若有根树的每个内点都有不超过 mm 个孩子,则称它为 mm 叉树

  • mm 叉树 每个内点都有恰好 mm 个孩子

  • 有序根树 每个内点的孩子都排序的有根树,比如有序二叉树(通常只称二叉树)

# 7.1.2 树作为模型

  • 饱和碳氢化合物
  • 组织机构
  • 计算机文件系统
  • 树形连接并行处理系统

# 7.1.3 树的性质

  • 带有 nn 个顶点的树含有 n1n-1 条边

  • 带有 ii 个内点的满 mm 叉树含有 n=mi+1n = mi + 1 个顶点, l=(m1)i+1l = (m-1)i + 1 个树叶

  • 平衡的 mm 叉树

    高度为 hhmm 叉树的所有树叶都在 hh 层或 h1h-1 层,则这棵树是平衡的

  • 在高度为 hhmm 叉树中至多有 mhm^h 个树叶

  • 若一棵高度为 hhmm 叉树带有 ll 个树叶,则 hlogmlh \geq \lceil \log_m l \rceil ,若这棵 mm 叉树是满的和平衡的,则 h=logmlh = \lceil \log_m l \rceil

# 7.2 树的应用

# 7.2.1 二叉搜索树

平衡二叉搜索树有着更好的查找性能

# 7.2.2 决策树

  • 基于二元比较的排序算法至少需要 logn!\lceil \log n! \rceil 次比较
  • 基于二元比较的排序算法排序 nn 个元素所用的平均比较次数是 Ω(nlogn)\Omega(n \log n)

# 7.2.3 前缀码

  • 前缀码 要使用不等长位串来编码字母,需要保证一个字母的位串永远不出现在另一个字母的位串的开头部分,拥有该性质的编码称为前缀码,可通过二叉树来表示
  • 哈夫曼编码 根据字母在字符串中的出现频率,对字母进行有效编码,尽可能地压缩数据量

# 7.2.4 博弈树

  • 取石子游戏
  • 井字游戏

有些著名游戏的博弈树非常大,所以设计了一些有用的方法以确定好的策略

  • αβ\alpha - \beta 剪枝,剪掉不能影响祖先顶点的值的那部分博弈树
  • 使用求值函数(估计)

# 7.3 树的遍历

# 7.3.1 遍历算法

有序根树都可以遍历

  • 前序遍历
  • 中序遍历
  • 后序遍历

# 7.3.2 中缀、前缀和后缀记法

前缀还是中缀后缀是指使用哪种方式对表达式树(表达式树是唯一的)进行遍历

  • 中缀表达式 即我们平时用的表达式,容易记,但是不使用括号会有二义性
  • 后缀(逆波兰记法)和前缀(波兰记法)表达式 不会有二义性

# 7.4 生成树

简单图 GG ,的生成树是包含 GG 的每个顶点的 GG 的子图

  • 简单图是连通的当且仅当它有生成树

  • 应用

    • IP 组播

# 7.4.1 生成树的构造

  • 从简单回路删除边
  • 深度优先搜索(回溯)
    • 应用
      • 图着色
      • nn 皇后问题
      • 子集之和
    • 有向图中的应用
      • 网络爬虫
  • 广度优先搜索

# 7.4.2 最小生成树

  • 普林算法 让一棵小树长大
  • 克鲁斯达尔算法 让森林合并成大树

# 8 布尔代数

基本布尔代数运算

  • 补 (记作 ˉ\bar{\quad}) 对应于逻辑非 ¬\lnot
  • 布尔和 (记作 OROR++) 对应于逻辑或 \lor
  • 布尔积 (记作 ANDAND\cdot ,可省略) 对应于逻辑与 \land

# 8.1 布尔函数

# 8.1.1 布尔表达式和布尔函数

有多少个不同的 nn 元布尔函数?

因为有 2n2^n 个不同的 nn 元组,然后对这 nn 元组进行赋 0011 ,故共有 22n2^{2^n} 个不同的 nn 元布尔函数

# 8.1.2 布尔代数恒等式

类似于逻辑恒等式

# 8.1.3 对偶性

将恒等式中的 1100 对换、++\cdot 对换,得到的仍然是恒等式,且称其为原恒等式的对偶

# 8.2 布尔函数的表示

# 8.2.1 积之和展开式

任何布尔函数都可以表示成小项(各个布尔变元或者其补之积)之和

所以,集合 {,+,ˉ}\{\cdot, +, \bar{\quad} \} 是函数完备的

# 8.2.2 函数完备性

  • 三元素函数完备集合

    已经知道集合 {,+,ˉ}\{\cdot, +, \bar{\quad} \} 是函数完备的,下面尝试寻找更小的函数完备集合

  • 二元素函数完备集合

    我们可以使用恒等式 x+y=xˉyˉx + y = \overline{\bar{x} \bar{y}} 替换掉所有的布尔和,或者使用恒等式 xy=xˉ+yˉxy = \overline{\bar{x} + \bar{y}} 替换掉所有的布尔积,就可以找到只包含两个元素的函数完备集合

  • 单元素函数完备集合

    定义运算符 |NANDNAND) 以及运算符 \downarrowNORNOR),很容易证明集合 {}\{ | \}{}\{ \downarrow \} 都是函数完备的

# 8.3 逻辑门电路

# 8.3.1 基本元件

  • 反相器
  • 或门
  • 与门

# 8.3.2 门的组合

使用门的组合来表示任意布尔函数

# 8.3.3 加法器

  • 半加法器 接受两个输入(xxyy)得到两个输出(和位 ss 与进位 cc),因为不考虑之前加法所产生的进位,所以称为半加法器
  • 全加法器 接收三个输入 (xxyy 和进位 cic_i)得到两个输出(和位 ss 与新的进位 ci+1c_{i+1}

# 8.4 电路的极小化

积之和虽然可以方便地将问题转化为布尔函数,但是这样的布尔函数计算次数相对较多,相应地,就需要更多的逻辑门元件,为了使得元件数量降低,布尔函数的化简也是极为重要的

# 8.4.1 卡诺图

变元数量超过 4 个时,就很难操作了,而且不适合机械化

# 8.4.2 奎因-莫克拉斯基方法

适合机械化,可以用于含有任意多个变元的布尔函数

# References

  1. 《离散数学及其应用》 Kenneth H. Rosen