[TOC]

离散数学期末复习

第一章 集合论

最大公约数：gcd(a, b) greatest

最小公倍数：lcm(a, b) least

常用证明方法：

  • 公理、定理、引理、推论
  • 充分必要条件
  • 反证法
  • 数学归纳法

常用集合：

  • Q——有理数集合{0, 1, 2, 3, 4, 5…n, …}
  • C——复数集合
  • R——实数集合
  • N——自然数集合
  • Z——整数集合

集合的表示方法

  • 枚举法 eg. A={a, b, c, d, e}

  • 隐式法（叙述法） eg. P = {x|P(x)}

  • 归纳法

    image-20230614194924045 image-20230614194932604

  • 递归指定集合 eg. a~0~ = 1, a~i+1~ = a~i~ * 2, S = {a~k~ | k≥0}

  • 文氏图解法

计算和证明题

集合的三大特征：互异性、确定性、无序性

外延性原理：A=B当且仅当A与B具有相同的元素，否则A≠B

B⊆\subseteqA   ⟺  \iff 对任意x，如x∈\inB，则x∈\inA

A⊆\subseteqB, B⊆\subseteqA   ⟺  \iff A = B

B⊂\subA   ⟺  \iff 对任意x，如x∈\inB，则x∈\inA，并且，∃\exist y∈\inA，但是y∉\notinB

image-20230614200559430

空集是绝对唯一的，空集是一切集合的子集。对唯一性的证明通常采用反证法——假设“不唯一，得出矛盾，从而说明结论正确”

基数：集合A中元素的数目

n元集有2^n^个子集：Cn0+Cn1+...+Cnn=(1+1)n=2nC_n^0 + C_n^1 + ... + C_n^n = (1+1)^n = 2^n

幂集（集族）：A的所有不同子集构成的集合，记为P(A)或2^A^

image-20230614201242720

对称差集：A⨁B=x∣(x∈A)且(x∉B)或(x∈B)或(x∉A)A\bigoplus{B} = {x|(x\in A)且(x \notin B)或(x \in B)或(x \notin A)}

image-20230614201556204

分配律：

  • A⋂(B⋃C)=(A⋂B)⋃(A⋂C)A \bigcap(B\bigcup{C}) = (A\bigcap{B}) \bigcup (A \bigcap C)
  • A⋃(B⋂C)=(A⋃B)⋂(A⋃B)A\bigcup(B\bigcap C) = (A\bigcup B)\bigcap(A\bigcup{B})

A−B=A⋂B‾A - B = A \bigcap{\overline{B}}

等势：A，B两集合间存在1-1对应关系，则称A与B是等势的，记为A~B

  • 若A = B，则A~B
  • 若A~B，则A = B

可数集合：与自然数集合等势的集合，记为ℵ0\aleph_0（读作阿列夫零）

image-20230614205023900 image-20230614205037638 image-20230614205103780

不可数集合：与开区间(0, 1)等势的集合，记作ℵ\aleph

image-20230614205126624 image-20230614205143061 image-20230614205213719

第二章 计数基础

  • 加法原理和乘法原理
  • 排列和组合
  • 容斥原理与鸽笼原理

容斥原理：A⋃B=∣A∣+∣B∣−∣A⋂B∣A\bigcup{B} = |A| + |B| - |A\bigcap{B}|

鸽笼原理：若有n+1个鸽子住进n个鸽笼，则有一个鸽笼至少住进2只鸽子

​ 鸽笼原理提供了存在性证明

第三章 命题逻辑

数理逻辑

命题：T or F，有确切真值（一切没有判断内容的句子都不能作为命题）

举个栗子：

  • 太阳是圆的 T
  • 1+1=10 T/F
  • 这个语句是假的 非命题
  • x+y>0 非命题
  • 把门关上 非命题
  • 如果周末天气晴朗，则我们将到郊外旅游 T/F

命题分类：原子命题、复合命题

联结词

联结词是句子与句子之间的联结，而非单纯的名词、形容词、数词等联结；连接词是两个句子真值间的联结，而非句子的具体含义的联结，两个句子间可以无任何的内在联系

析取——⋁\bigvee

合取——⋀\bigwedge

蕴含——→

​ 数理逻辑中，可以允许前提和结论间无必然因果联系

image-20230615162344193

命题联结词优先级：否定→合取→析取→蕴含→等价

命题公式

命题变元：一个任意的没有赋予具体内容的原子命题

  • 永真公式（重言式）
  • 永假公式（矛盾式）
  • 可满足公式——不是永假（永真式一定是可满足式，可满足式不一定是永真式，可满足式的否定不一定是不可满足式）

基本等价公式：

  • 分配律：
    • G⋁(H⋀S)=(G⋁H)⋀(G⋁S)G\bigvee(H\bigwedge S) = (G\bigvee H)\bigwedge (G\bigvee S)
    • G⋀(H⋁S)=(G⋀H)⋁(G⋀S)G\bigwedge (H\bigvee S) = (G\bigwedge H)\bigvee (G\bigwedge S)
  • 德·摩根律：
    • ¬(G⋁H)=¬G⋀¬H\lnot(G\bigvee H) = \lnot G \bigwedge \lnot H
    • ¬(G⋀H)=¬G⋁¬H\lnot(G\bigwedge H) = \lnot G \bigvee \lnot H
  • 蕴涵：G→H=¬G⋁HG\rightarrow H = \lnot G \bigvee H
  • 假言易位：G→H=¬G→¬HG\rightarrow H = \lnot G \rightarrow \lnot H
  • 归谬论：(G→H)⋀(G→¬H)=¬G(G \rightarrow H) \bigwedge (G\rightarrow \lnot H) = \lnot G

公式的标准型——范式

析取范式和合取范式：

  • 命题变元和命题变元的否定称为文字
  • 有限个文字的析取称为析取式(也称为子句）
  • 有限个文字的合取称为合取式(也称为短语）
  • P与¬\lnot P称为互补对
  • 有限个短语的析取式称为析取范式（合取再析取为析取范式）
  • 有限个子句的合取式称为合取范式（析取再合取为合取范式）

一个命题变元或者其否定既可以是简单的子句，也可以是简单的短语。P与¬\lnot P是文字、子句、短语

一个不含最外层括号的短语（子句）也可以是析取范式（合取范式）

image-20230618192708135 image-20230618193121384

对于n个命题变元，可构成2^n^个极小项和2^n^个极大项

  • 极大项 + ⋁\bigvee 1为P，0为¬\lnotP

  • 极小项 * ⋀\bigwedge 0为P，1为¬\lnotP

  • 所有极小项的析取为永真公式，所有极大项的合取为永假公式

  • 极大项的否定是极小项，极小项的否定是极大项

  • 主析取范式：每一个短语都是极小项

  • 主合取范式：每一个子句都是极大项

求主析取范式和主合取范式

  • 公式转换
  • 真值表
image-20230618193945648 image-20230618194008965 image-20230618194014638 image-20230618194022085 image-20230618194028425

第四章 谓词逻辑

个体词、个体域、n元谓词≠命题

量词∀\forall ∃\exists，记为(∀x)F(x),(∃x)F(x)(\forall x)F(x), (\exists x)F(x)

谓词逻辑符号化的两条规则：

  • 全称量词(∀x)(\forall x)，刻划其个体域的特性谓词作为蕴涵式的前提加入
  • 存在量词(∃x)(\exists x)，刻划其个体域的特性谓词作为合取式的项加入

一元谓词描述一个个体的某种特性，n元谓词描述n个个体间的关系

谓词符号P， 函数符号f，变量符号abc，变量符号xyz

原子公式、合式公式

约束变元的改名/代入规则：

  • 量词中出现的变元及该量词辖域中此变量都用新的个体变元替换
  • 新变元有别于改名辖域中的其他变量

改名规则与代入规则的不同点：

  • 实行的对象不同：改名规则是对约束变元施行，代入规则是对自由变元施行
  • 施行的范围不同：改名规则可以只对公式的一个子公式施行，代入规则必须对整个公式施行
  • 施行后的结果不同：改名后公式含义不变（约束变元只改名为另一个个体变元），代入后可以用另一个个体变元或个体变量代入
image-20230616013328183 image-20230616013308348

闭式：G中无自由出现的个体变元

有效公式、矛盾公式、可满足公式：

  • 有效公式的否定为矛盾公式
  • 矛盾公式的否定为有效公式
  • 有效公式一定为可满足公式

Skolem标准型：消去G中所有的量词

​ 操作：第一个存在——变为常量a，任意——不变，后面的所有存在——用已消去的任意的函数表示

image-20230616153926328

推理规则

  • US——全称特指 Universal Specify
    • (∀x)G(x)⇒G(y)(\forall x)G(x) \Rightarrow G(y)
    • (∀x)G(x)⇒G(c)(\forall x)G(x)\Rightarrow G(c)
  • ES——存在特指 Existential Specify
    • (∃x)G(x)⇒G(c)(\exists x)G(x) \Rightarrow G(c)
  • UG——全称推广 Universal Generalize
    • G(y)⇒(∀x)G(x)G(y) \Rightarrow (\forall x)G(x)，G(y)对x是自由的
  • EG——存在推广 Existential Generalize
    • G(c)⇒(∃x)G(x)G(c) \Rightarrow (\exists x)G(x)
    • G(y)⇒(∃x)G(x)G(y) \Rightarrow (\exists x)G(x)，G(y)对x是自由的
  • P——前提引入
  • T——一个或几个前提蕴涵得到的其他命题公式
    • I——T规则通过蕴涵式推出其他命题公式
    • E——T规则通过等价式推出其他命题公式
  • CP——结论是以条件（或析取形式）给出

谓词演算的综合推理方法

  • 消去量词：US ES
  • 要求结论定量：UG EG
  • 对无量词的公式可以引用命题演算中的基本等价公式和基本蕴涵公式
  • 对有量词的公式可以引用谓词中的基本等价公式和基本蕴涵公式

要注意的点：

image-20230616155421405 image-20230616155835864 image-20230616160129249 image-20230616160139088 image-20230616160303124

再举个栗子：

image-20230616171531443 image-20230616171539560 image-20230616171549009

第五章 证明技术

证明P⇒QP\Rightarrow Q，只需证明P→QP\rightarrow Q为永真公式

基本证明方法

  • 直接证明
  • 间接证明 P→Q等价于¬Q→¬PP \rightarrow Q等价于 \lnot Q \rightarrow \lnot P

第六章 二元关系

序偶：<x, y>，N重有序组

笛卡尔乘积

A×B=<x,y>∣(x∈A)⋀(y∈B)A×B = {<x,y>|(x\in A)\bigwedge (y\in B)} ——仍然是集合，两个元素分别取自A、B

  • 笛卡尔积不满足交换律和结合律
  • 对有限集A，B，有∣A×B∣=∣B×A∣=∣A∣×∣B∣|A×B| = |B×A| = |A|×|B|
  • 笛卡尔积对并交满足分配律
    • A×(B⋃C)=(A×B)⋃(A×C)A×(B\bigcup C) = (A×B)\bigcup (A×C)
    • (B⋃C)×A=(B×A)⋃(C×A)(B\bigcup C)×A = (B\times A)\bigcup (C\times A)
    • A×(B⋂C)=(A×B)⋂(A×C)A×(B\bigcap C) = (A×B)\bigcap (A×C)
    • (B⋂C)×A=(B×A)⋂(C×A)(B\bigcap C)×A = (B\times A)\bigcap (C\times A)
  • (A×B)⊆(C×D)⇔A⊆C,B⊆D(A\times B)\subseteq (C\times D)\Leftrightarrow A \subseteq C, B\subseteq D
  • 集合A~1~，A~1~，…，A~n~都是有限集时，A1×A2×...×An=∣A1∣×∣A2∣×...×∣An∣A_1 \times A_2\times ... \times A_n = |A_1|\times |A_2|\times ...\times |A_n|
  • A和B都是有限集时，A×B共有2^|A|·|B|^个不同的子集，即从A到B的不同关系共有2^|A|·|B|^个

​ image-20230616223833176

关系的表示

  • 集合表示法（枚举法和叙述法） R3={<a,c>},R4={<a,b>,<a,c>}R_3 = \{<a,c>\}, R_4=\{<a,b>, <a, c>\}

  • 关系图法

    image-20230616233937027
image-20230616234001256
  • 关系矩阵（邻接矩阵、布尔矩阵）：A对应矩阵元素的行下标，B对应元素序号对应矩阵元素的列下标
image-20230616234448831 image-20230616234458386

​ 布尔矩阵的运算：

image-20230616234749522 image-20230616234806986 image-20230616235742783 image-20230616235802168

关系的复合运算

ABC三个集合，R是从A到B的关系（R:A→B），S是从B到C的关系（S:B→C），则R与S的复合关系（合成关系）RoS是从A到C的关系：

  • R和S是可复合的⇔\LeftrightarrowR的后域和S的前域完全相同
  • RoS的前域是R的前域A，后域是S的后域C
  • RoS = ∅\empty ⇔\Leftrightarrow对任意的x∈\inA和z∈\inC，不存在y∈\inB，使得xRy和ySz同时成立
  • ∅\emptyoR = Ro∅\empty = ∅\empty
image-20230617000750995 image-20230617001020334
  • ABCD任意四个集合，R、S和T分别是A到B，B到C，C到D的二元关系，则：
    • (RoS)oT=R0(SoT)(RoS)oT = R0(SoT)
    • IAoR=RoIB=RI_AoR = RoI_B = R，其中I~A~和I~B~分别是A和B上的恒等关系
  • ABCD任意四个集合，R是从A到B的关系，S~1~、S~2~是从B到C的关系，T是从C到D的关系，则：
    • Ro(S1⋃S2)=(RoS1)⋃(RoS2)Ro(S_1\bigcup S_2) = (RoS_1)\bigcup (RoS_2)
    • Ro(S1⋂S2)⊆(RoS1)⋂(RoS2)Ro(S_1\bigcap S_2)\subseteq(RoS_1)\bigcap(RoS_2)
    • (S1⋃S2)oT=(S1oT)⋃(S2oT)(S_1\bigcup S_2)oT = (S_1oT)\bigcup(S_2oT)
    • (S1⋂S2)oT⊆(S1oT)⋂(S2oT)(S_1\bigcap S_2)oT\subseteq (S_1oT)\bigcap(S_2oT)
    • （展开：并等于，交包含）

关系的逆运算

R−1={<b,a>∣<a,b>∈R}R^{-1} = \{<b,a>|<a,b>\in R\}称为RR的逆关系，运算“-1”称为逆运算，(R−1)−1=R(R^{-1})^{-1} = R

关系是一种集合，逆关系也是一种集合

R−1R^{-1}的前域与后域正好是RR的后域和前域，domR = ranR^-1^，domR^-1^ = ranR

  • ∣R∣=∣R−1∣|R| = |R^{-1}|

  • (RoS)−1=S−1oR−1(RoS)^{-1} = S^{-1}oR^{-1}

  • 分配性：

    • (R⋃S)−1=R−1⋃S−1(R\bigcup S)^{-1} = R^{-1}\bigcup S^{-1}
    • (R⋂S)−1=R−1⋂S−1(R\bigcap S)^{-1} = R^{-1}\bigcap S^{-1}
    • (R−S)−1=R−1−S−1(R-S)^{-1} = R^{-1}-S^{-1}

  • 可换性：

    • (R‾)−1=R−1‾(\overline{R})^{-1} = \overline{R^{-1}}
    • (A×B)−1=(B×A)(A\times B)^{-1} = (B\times A)

  • 单调性：S⊆R⇔S−1⊆R−1S\subseteq R \Leftrightarrow S^{-1} \subseteq R^{-1}

关系的幂运算

R是集合A上的关系，则R的n次幂记为RnR^n，定义如下：

  • R0=IA={<a,a>∣a∈A}R^0 = I_A = \{<a,a>|a\in A\}
  • R1=RR^1 = R
  • Rn+1=RnoR=RoRnR^{n+1} = R^noR = RoR^n

显然RmoRn=Rm+nR^moR^n = R^{m+n}，(Rm)n=Rmn(R^m)^n = R^{mn}

幂集RnR^n的基数∣Rn∣|R^n|并非随着n的增加而增加，而是呈递减趋势

A是有限集合，且∣A∣=n|A|=n，R是A上的二元关系，则⋃i=1∞Ri=⋃i=1nRi\bigcup ^{\infty}_{i=1}R^i = \bigcup ^n_{i=1}R^i

关系性质的定义

  • 自反性和反自反性
    • 自反性：∀x∈A,<x.x>∈R⇔(∀x)(x∈A→<x,x>∈R)=1\forall x\in A, <x.x>\in R\quad \Leftrightarrow\quad (\forall x)(x\in A \rightarrow <x,x>\in R)=1
    • 反自反性：∀x∈A,<x,x>∉R⇔(∀x)(x∈A→<x,x>∉R)=1\forall x\in A,<x,x>\notin R\quad \Leftrightarrow \quad (\forall x)(x\in A \rightarrow <x,x>\notin R)=1
    • 自反：关系图每个结点都有自环，关系矩阵主对角线上全为1
    • 反自反：关系图每个结点都无自环，关系矩阵主对角线上全为0
  • 对称性和反对称性（可同时具有）
    • 对称性：<x,y>∈R,则<y,x>∈R⇔(∀x)(∀y)(x∈A⋀y∈A⋀<x,y>∈R→<y,x>∈R)=1<x,y>\in R,则<y,x>\in R \quad \Leftrightarrow \quad (\forall x)(\forall y)(x\in A \bigwedge y\in A \bigwedge <x,y>\in R {\rightarrow} <y,x>\in R) = 1
    • 反对称性：<x,y>∈R且<y,x>∈R,则x=y⇔(∀x)(∀y)(x∈A⋀y∈A⋀<x,y>∈R⋀<y,x>∈R→x=y)=1<x,y>\in R且<y,x>\in R,则x=y \quad \Leftrightarrow \quad (\forall x)(\forall y)(x\in A \bigwedge y\in A \bigwedge <x,y>\in R\bigwedge <y,x>\in R {\rightarrow} x=y) = 1
    • 存在既不是对称也不是反对称的关系，也存在既是对称也是反对称的关系
    • 关系R是对称的 ⇔\Leftrightarrow 关系图中任何一对结点间要么有方向相反的两条边，要么无任何边 ⇔\Leftrightarrow 关系矩阵是对称矩阵
    • 关系R是反对称的 ⇔\Leftrightarrow 关系图中任何一对结点间，至多有一条边 ⇔\Leftrightarrow 关系矩阵是反对称矩阵
  • 传递性（∉\notin也可以传递）
    • <x,y>∈R且<y,z>∈R，则<x,z>∈R⇔(∀x)(∀y)(∀z)(x∈A∧y∈A∧z∈A∧<x,y>∈R∧<y,z>∈R→<x,z>∈R)=1<x,y>\in R且<y,z>\in R，则<x,z>\in R\quad \Leftrightarrow \quad (\forall x)(\forall y)(\forall z)(x∈A∧y∈A∧z∈A∧<x,y>∈R∧<y,z>∈R→<x,z>∈R)=1
    • 当且仅当x,y,z∈A,有<x,y>∈R且<y,z>∈R,但<x,z>∉R时，R在A上不是传递的当且仅当x,y,z\in A,有<x,y>\in R且<y,z>\in R,但<x,z>\notin R时，R在A上不是传递的
image-20230617144909957

关系的闭包运算

闭包：A上的另一个关系R’满足：

  • R’是自反的（对称的、或传递的）
  • 对任何自反的（对称的、或传递的）关系R’’，若R⊆R′′R\subseteq R''，就有R′⊆R′′R'\subseteq R''，则称为R的自反闭包（或对称闭包、传递闭包）——关系闭包是增加最少的元素，使其具备所需性质的扩充
  • 自反闭包、对称闭包、传递闭包分别记为r(R)、s(R)、t(R)r(R)、s(R)、t(R)

关系图求关系R闭包的方法

  • 在没有自环的结点处加上自环，可得r®的关系图
  • 将每条单向边全部改成双向边，可得s®的关系图
  • 从每个结点出发，找到其终点，如果该结点到其终点没有边相连，就加上此边，可得t®的关系图

特殊关系

  • 等价关系
  • 拟序关系
  • 偏序关系
  • 全序关系
  • 良序关系

等价关系

  • R是等价关系 ⇔\Leftrightarrow R具备自反性、对称性、传递性
  • R不是等价关系 ⇔\Leftrightarrow R不具备自反性或对称性或传递性

举个栗子：

image-20230617152812572 image-20230617152822064 image-20230617152831487

再举个例子：

image-20230617153716919 image-20230617153707404

以n位模的同余关系，记xRyxRy为x=y(modn)x=y(mod\quad n )，称为同余式。resn(x)res_n(x)表示x除以n的余数

集合的划分：非重叠划分，块/类

等价类：R是非空集合A上的等价关系，对任意x∈Ax\in A，称集合[x]R={y∣y∈A⋀<x,y>∈R}[x]_R = \{y|y\in A\bigwedge <x,y>\in R\}为关于R的等价类，其中xx称为[x]R[x]_R的生成元（或叫代表元、典型元）

  • 等价类产生的前提：A上的关系R必须是等价关系
  • A中任意一个元素一定对应一个由它生成的等价类
  • R具有自反性意味着∀x∈A,[x]R≠∅\forall x \in A, [x]_R\neq \empty
  • R具有对称性意味着对∀x,y∈A，若有y∈[x]R，则一定有x∈[y]R\forall x,y\in A，若有y\in [x]_R，则一定有x\in [y]_R
image-20230617163206054

若R是非空集合A上的等价关系：

  • 对∀x∈A，[x]R∉∅对\forall x\in A，[x]_R\notin \empty
  • 对∀x,y∈A对\forall x,y\in A
    • 若y∈[x]R，则有[x]R=[y]R若y\in [x]_R，则有[x]_R =[y]_R
    • 若y∉[x]R，则有[x]R⋂[y]R=∅若y\notin [x]_R，则有[x]_R \bigcap [y]_R = \empty
  • ⋃x∈A[x]R=A\bigcup _{x\in A}[x]_R = A

商集：R是非空集合A上的等价关系，由R确定的一切等价类的集合，称为集合A上关于R的商集，记为A/R

​ 即：A/R={[xR]∣(x∈A)}A/R = \{[x_R]|(x\in A)\}

image-20230617164022709 image-20230617164103444 image-20230617164558444

次序关系——拟序关系

R是非空集合A上的关系，如果R是反自反和传递的，则称R是A上的拟序关系，记为"<"，"<a,b>∈<<a,b>\in <“记为”a<ba<b"。序偶<A,<>称为拟序集

拟序“<”的逆关系“<^-1^"也是拟序，用“>”表示，读作大于

设R是集合A上的拟序关系，则R是反对称的

次序关系——偏序关系

R是非空集合A上的关系，如果R是自反的、反对称的和传递的，则称R是A上的偏序关系，记为“≤”，并将“<a,b>∈≤<a,b>\in \leq”记为a≤b，序偶<A,≤>称为偏序集

偏序“≤”的逆关系“<^-1^"也是偏序，用“≥”表示，读作大于等于

（“≤”-I~A~）为A上的拟序关系，（“＜”⋃\bigcupI~A~）为A上的偏序关系

哈斯图

  • 因自反性：圆圈代表A中元素，省掉关系图中的环
  • 因反对称性：∀x,y∈A，若x<y，将x画在y的下方，可省掉关系图中所有边的箭头\forall x,y\in A，若x<y，将x画在y的下方，可省掉关系图中所有边的箭头
  • 因传递性：∀x,y∈A(x≠y)，若x≤y，且x与y之间不存在z∈A，使得x≤z≤y，则x与y之间用一条线相连，否则无线相连\forall x,y \in A(x\neq y)，若x\leq y，且x与y之间不存在z\in A，使得x\leq z\leq y，则x与y之间用一条线相连，否则无线相连
image-20230617213044956 image-20230617213055382

特殊元素

设<A,≤><A,≤>是偏序集，B是A的任何一个子集，若存在元素b∈Bb\in B，使得对∀x∈B\forall x\in B：

  • 最大元：B中最大的元素
  • 最小元：B中最小的元素
  • 极大元：B中没有比b大的元素
  • 极小元：B中没有比b小的元素
  • 最大元最小元极大元极小元都在B中找

举个栗子：同一层次是无法比较大小 的，所以可能存在两个极大元/极小元

image-20230617214929375
  • 最小上界（上确界）：所有A的子集中最小的上界，记为a′=SupBa' = SupB
  • 最大下界（下确界）：所有A的子集中最大的下界，记为a′=lnfBa' = lnfB

需要注意：

  • 子集B的上下界和上下确界必须在集合A中寻找
  • 子集B的上下界不一定存在，若存在可以不唯一
  • 子集B的上下确界不一定存在，若存在一定唯一
  • 子集B有上（下）确界，则必有上（下）界，反之不然

举个栗子：

image-20230617215419351 image-20230617215924154

  • 若b是B的最大元，则b一定是B的极大元、上界和上确界；反之不然

  • 若b是B的最小元，则b一定是B的极小元、下界和下确界；反之不然

  • 若B存在最大元，则B的最大元是惟一的；

  • 若B存在最小元，则B的最小元是惟一的；

  • b是B的最大元 $\Leftrightarrow $ b是B的惟一极大元；

  • b是B的最小元 $\Leftrightarrow $ b是B的惟一极小元；

  • 若B存在上确界，则B的上确界是惟一的；

  • 若B存在下确界，则B的下确界是惟一的。

举个栗子：

image-20230617222511744 image-20230617222518325

全序关系

∀x,y∈A\forall x,y\in A，总有x≤y或y≤xx\leq y或y\leq x则称关系“≤\leq”为全序关系或线序关系，称<A,≤><A,≤>为全序集或线序集或链

全序关系是偏序关系，反之不然

良序关系

<A,≤><A,≤>是一偏序集，若A的任何一个非空子集都有最小元素，则称“≤”为良序关系

  • R是良序关系 ⇔\Leftrightarrow R是偏序关系和A的任何非空子集都有最小元
  • 良序关系一定是偏序关系，反之不然
  • 良序关系一定是全序关系，反之不然
  • 有限全序集一定是良序集

第八章 函数

f:A→Bf:A→B（必须是一对一或多对一的关系），定义域A，记为domf=Adomf = A；值域B，记为ranfranf

  • <x,y>∈f⇔y=f(x)<x,y>\in f\quad \Leftrightarrow \quad y = f(x)
  • <x,y>∈f⋀<x,z>∈f⇒y=z<x,y>\in f \bigwedge<x,z>\in f \quad \Rightarrow \quad y = z
  • ∣f∣=∣A∣|f| = |A|
  • f(x)f(x)表示一个变值，ff表示一个集合，因此f≠f(x)f\neq f(x)

注意，ff中要有A中所有元素及其象 eg.A={1,2,3,4},B={a,b,c,d},f4={<2,b>,<3,b>,<4,c>}A = \{1,2,3,4\}, B=\{a,b,c,d\}, f_4=\{<2,b>,<3,b>,<4,c>\}，f4f_4不是函数，因为没有第一个元素和其象

函数和关系的差别：

  • 个数：A到B的不同的关系有2^|A|×|B|^个，从A到B不同的函数有|B|^|A|^
  • 集合元素的第一个元素：关系中序偶的第一个元素可以相同，函数中序偶的第一元素一定互不相同
  • 集合基数：关系的基数为从0到|A|×|B|，每个函数的基数都为|A|个（|f| = |A|）

函数类型：

  • 单射：不同x对应不同y
  • 满射：值域ranf=Branf = B（B中所有元素都作函数的结果）
  • 双射：f是满射且是单射
  • A=B，f为A上的函数；A上的函数f是双射时，f为一个变换

结论：AB为有限集合，f为从A到B的函数，则：

  • f是单射的必要条件：∣A∣≤∣B∣|A|\leq|B|
  • f是满射的必要条件：∣B∣≤∣A∣|B|\leq|A|
  • f是双射的必要条件：∣A∣=∣B∣|A|=|B|
  • f是单射当且仅当f是满射
image-20230617233505917 image-20230617233514313 image-20230617233529706 image-20230618001720981 image-20230618002422227 image-20230618002429403 image-20230618002451923

传递性：f和g分别是A到B和B到C的函数，则：

  • fg是满射，则fog是从A到C满射
  • fg是单射，则fog是从A到C单射
  • fg是双射，则fog是从A到C双射
  • fog是从A到C的满射，则g是从B到C的满射
  • fog是从A到C的单射，则f是从A到B的单射
  • fog是从A到C的双射，则g是从B到C的满射，f是从A到B的单射

函数的逆运算

逆函数$$f^{-1}$$存在当且仅当ff是双射

f−1={x∈A⋀y∈B⋀<x,y>∈f}f^{-1} = \{x\in A\bigwedge y\in B\bigwedge <x,y>\in f\}

设ff是A到B的双射函数，则：

  • f−1of=IB={<b,b>∣b∈B}f^{-1}of = I_B = \{<b,b>|b\in B\}
  • fof−1=IA={<a,a>∣a∈A}fof^{-1} = I_A = \{<a,a>|a\in A\}
  • IAof=foIB=fI_Aof = foI_B = f
  • ff的逆函数f−1f^{-1}是B到A的双射

置换函数

A={a1,a2,...,an}A = \{a_1,a_2,...,a_n\}是有限集合，从A到A的双射函数称为A上的置换或排列，记为P:A→AP:A\rightarrow A，n称为置换的阶

第九章 图

基本概念

一个图是一个序偶G=<V,E>G=<V,E>

  • V——结点集，是有限非空集合，viv_i称为结点
  • E——边集，是有限集合，E中每个元素都有V中的结点与之对应
  • <u,v><u,v>——有向边，(u,v)(u,v)——无向边
  • 邻接矩阵

零图——仅有孤立结点组成的图（一个结点处有环时，自己是自己的邻接点）

平凡图——仅含一个结点的零图

（n，m）图——含有n个结点，m条边的图

平行边——同始点同终点 重数——平行边的个数

多重图/线图——有/无平行边的图 简单图——无环的线图

赋权图——<V,E,g><V,E,g>（一般考虑的赋权图指三重组）或<V,E,f,g><V,E,f,g>，ff是从V到非负实数集合的函数，gg是从E到非负实数集合的函数

子图：结点和边都是原图的子集

真子图：

生成子图：结点不变，边是原图的子集

导出子图：边不变，点是原图的子集，与删除的点相邻的边也要删

完全图——任意两个节点间都有边相连（不说有向则默认无向），记为KnK_n

补图——完全图 - 简单图，记为G‾\overline{G}（G与其补图的结点集是相同的，边集是相对完全图的边集为全集的补集），KnK_n的补图是n个几点的零图（不要漏掉孤立结点）

结点的度数——出度deg+(v)deg^+(v)、入度deg−(v)deg^-(v)，度deg(v)=deg+(v)+deg−(v)deg(v) = deg^+(v) + deg^-(v)

​ 度数为1的结点称为悬挂结点，以悬挂结点为端点的边称为悬挂边

握手原理：图中结点度数的总和等于边数的二倍

​ 图中度数为奇数的结点个数为偶数 奇/偶度数结点

​ 度数序列

图的同构的必要条件（经常用反证法）：

  • 结点数目相同
  • 边数相同
  • 度数相同的结点数相同

通路、回路与连通性

给定图G=<V,E>G=<V,E>中结点和边相继交错出现的序列Γ=v0e1v1e2v2...ekvk\Gamma=v_0e_1v_1e_2v_2...e_kv_k：

  • 若Γ\Gamma中eie_i的两端点是vi−1v_{i-1}和viv_i（i=1,2,...ki=1,2,...k），则称Γ\Gamma为始点v0v_0到终点vkv_k的通路。通路中边的数目kk称为此通路的长度。v0=vkv_0=v_k时，此通路称为回路
  • 简单通/回路（迹/闭迹）：通/回路中所有边互不相同
  • 基本通/回路（初级通路/路径和初级回路/圈）：通/回路中所有结点互不相同
  • 一般而言，某条通路可能是回路，基本通路指它不是基本回路的情况

A=(aij)n×nA=(a_{ij})_{n×n}为G的邻接矩阵，Am=(aij(m))n×nA^m=(a_{ij}^{(m)})_{n×n}（这里是矩阵乘法）：

  • 邻接矩阵中的aij(m)a_{ij}^{(m)}为结点viv_i到结点vjv_j长度为m的通/回路数目，aii(m)a_{ii}^{(m)}为结点viv_i到自身长度为k的回路数目
image-20230618100617825 image-20230618100736112 image-20230618100626712 image-20230618100641191 image-20230618100653581 image-20230618100800128

结点间可达/不可达 短程线——结点间长度最短的通路 结点间距离——短程线的长度，记为d(vi,vj)d(v_i,v_j)，不可达时为∞\infty

在一个具有n个结点的图中：

  • 如果从结点viv_i到vjv_j（i≠ji≠j）存在一条通路，则从viv_i到vjv_j存在一条长度不大于n-1的通路
  • 如果存在经过结点viv_i回路，则存在一条经过viv_i的长度不大于n的回路
  • 如果存在经过结点viv_i回路，则存在一条经过viv_i的长度不大于n的基本回路

Bn=(bij(n))n×n=A+A2+A3+...+AnB^n = (b_{ij}^{(n)})_{n\times n} = A+A^2+A^3+...+A^n（AA是邻接矩阵）

bij(n)=aij(1)+aij(2)+aij(3)+...+aij(n)b_{ij}^{(n)} = a_{ij}^{(1)}+a_{ij}^{(2)}+a_{ij}^{(3)}+...+a_{ij}^{(n)}

​ 若bij(n)>0b_{ij}^{(n)}>0，则viv_i到vjv_j可达，否则不可达

可达性矩阵，BnB^n的非零元素变为1

无向图的连通性：

​ 连通图（非连通图/分离图）：无向图G中任何两个结点都是可达的（不可达的）

​ 无向完全图KnK_n（n≥1）都是连通图，多于一个结点的零图都是非连通图

​ 非平凡无向线图G是连通图当且仅当它的可达性矩阵P的所有元素均为1

​ 可达关系R是自反、对称、传递的

​ R的每个等价类导出的子图都称为G的一个连通分支，用p(G)p(G)表示G中的连通分支个数，无向图G是连 通图当且仅当p(G)=1p(G)=1

有向图的连通性：

​ 弱连通图：略去方向——A′=A⋁ATA'=A\bigvee A^T所有元素均为1

​ 单向连通图：任一对结点间，至少一个结点到另一个结点可到——P′=P⋁PTP'=P\bigvee P^T除主对角元外其余元素均为1

​ 强连通图：任何一对结点间相互可达——可达性矩阵PP所有元素均为1

​ 继承性：强连通/单向连通/弱连通——eg.强连通分支（均有极大性特点，增加边/点就不是强连通） 强分图

​ 在有向图G=<V,E>G=<V,E>中，

  • 每一个结点位于且仅位于一个强连通分支
  • 每一个结点至少位于一个单向连通分支
  • 每一条边至多在一个强连通分支中，至少在一个单向连通分支中，在且仅在一个弱连通分支

无向赋权图的最短通路

迪杰斯特拉算法：给定结点间的最短通路

image-20230618112433935 image-20230618112442780

Floyd算法：任意两节点间的最短通路

image-20230618114439558 image-20230618114449134 image-20230618114457174 image-20230618114506190

第十章 树

树没有环和平行边，一定是简单图。没有度数为0的结点

无向树

设无向图G=<V,E>,∣V∣=n,∣E∣=mG=<V,E>,|V|=n,|E|=m：

  • G连通而不含回路（G是树）
  • G中无回路，且m=n−1m=n-1
  • G中无回路，但在G任二结点间增加一条新边，就得到唯一一条基本回路
  • G是连通的，但删除G中任一条边后，不连通（n≥2n\geq 2）
  • G中每一对结点间有唯一一条基本通路（n≥2n\geq 2）

在结点给定的无向图中：树是边数最多的无回路树，树是边数最少的连通图

​ 在无向图G=(n,m)G=(n,m)中，若m<n−1m<n-1，则G是不连通的；若m>n−1m>n-1，G必含回路

任意非平凡树T=(n,m)T=(n,m)至少有两片叶

image-20230618124739161

生成树：图G=<V,E>G=<V,E>的某个生成子图（结点数相同）是树，称为G的生成树，记为TGT_G

​ TGT_G的边为树枝，G中不在TGT_G中的边为弦，所有弦的集合称为生成树的补

​ 图G存在生成树TG=<VT,ET>T_G=<V_T,E_T>的充分必要条件是G是连通的

求生成树——破圈法和避圈法：

  • 破圈法：每次删除回路中的一条边，其删除的边的综述为m−n+1m-n+1
  • 避圈法：每次选取G中一条与已选取的边不构成回路的边，选取的边的总数为n−1n-1
  • 生成树不是唯一的
image-20230618130138211 image-20230618130145178

广度优先搜索算法

image-20230618130341194

标记后驱，直至搜索到所有点

最小生成树：具有最小权的生成树（不唯一）

Kruskal算法：

image-20230618131805737 image-20230618131828065

Prim算法：

image-20230618131841969 image-20230618131850935

根树

有向树：略去所有有向边的方向得到的无向图是一棵树

根树/外向树：一棵非平凡的有向树，恰有一个结点的入度为0，其余所有结点的入度均为1

  • 内点：入度为1，出度大于0
  • 分支点：内点和根
  • 层数：根到任一结点的通路长度

家族关系：祖先、后代、父亲、儿子、兄弟

有序树：规定了每一层上结点的次序

根树T中：

  • k元树：每个分支点至多有k个儿子
  • k元完全树：每个分支点恰有k个儿子
  • k元有序树
  • k元有序完全树

k元完全树中，叶数为t，分支点为i，则有(k−1)×i=t−1(k-1)\times i = t-1

根树的遍历：① 转化为二元树 ② 二元树的遍历

二元树的遍历：

  • 先根次序遍历：根→左子树→右子树
  • 中根次序遍历：左子树→根→右子树
  • 后根次序遍历：左子树→右子树→根
image-20230618144654131

根树转化为二元树：弟弟变右儿子

  • 根开始，保留每个父亲同其最左边儿子的联系，撤销与其他儿子的连线
  • 兄弟间用从左向右的有向边连接
  • 确定左右儿子：直接位于给定结点下面的结点，作为左儿子，对于同一水平线上与给定结点右邻的结点作为右儿子
image-20230618150507291

有序森林业转换成二元树：

  • 每一棵树表示成二元树
  • 除第一棵二元树，依次将剩下的每棵二元树作为左边二元树的根的右子树，直到所有的二元树都连成一棵二元树为止
image-20230618150822398

最优树与哈夫曼算法

image-20230618151008649

eg. {1, 01, 001, 000}是前缀码，{1, 11, 001, 0011}不是前缀码

二元树产生二元前缀码：

  • 二元树TT，假设有tt片树叶。vv是TT的任意一个分支点。
  • viv_i中的符号串前缀均在viv_i所在的通路上，因而所得集合为二元（0和1组成）前缀码
  • 若TT存在带一个儿子的分支点，则由T产生的前缀码不唯一，但若TT若为完全二元树，则TT产生的前缀码就是唯一的
image-20230618151656055

最优树：W(T)=∑i=1twi×L(wi)W(T)=\sum^t_{i=1}w_i \times L(w_i)最小的树（同一层权值和 × 层数）

哈夫曼算法：

image-20230618152424581 image-20230618152858875 image-20230618153036632 image-20230618153045901 image-20230618153936074

波兰符号法与逆波兰符号法（）

中缀符号法：中缀次序遍历算法访问T，得到正常算式

波兰符号法（前缀符号法）：运算符在参加运算的两数之前

逆波兰符号法（后缀符号法）：运算符在参加运算的两数之后

image-20230618154114693 image-20230618154318661 image-20230618154326650

决策树

博弈树

第十一章 特殊图

  • 欧拉图
  • 哈密顿图
  • 偶图
  • 平面图

欧拉图

欧拉通路（回路）：G是无孤立结点的图，经过图中每边依次且仅一次的通路（回路）

​ 欧拉通/回路是经过图中所有边的通/回路中长度最短的通/回路，即为通过图中所有边的简单通/回路

欧拉图：具有欧拉回路的图（不能是通路）

平凡图为欧拉图，以上定义既适合无向图，又适合有向图

欧拉图的判定（无向图对图中各结点度数计算，有向图对图中各结点出度与入度计算）：

  • 无向图G=<V,E>G = <V, E>具有一条欧拉通路，当且仅当G是连通的，且仅有零个或两个奇度数结点
  • 无向图G=<V,E>G = <V, E>具有一条欧拉回路，当且仅当G是连通的，并且所有结点的度数均为偶数
  • 有向图G具有一条欧拉通路，当且仅当G是连通的，且除了两个结点以外，其余结点的入度等于出度，而这两个例外的结点中，一个结点的入度比出度大1，另一个结点的出度比入度大1
  • 有向图G具有一条欧拉回路，当且仅当G是连通的，且所有结点的入度等于出度

设G=<V,E>,e∈EG=<V,E>, e\in E，若p(G−e)>p(G)p(G-e)>p(G)，称ee为GG的桥或割边——所有的悬挂边都是桥

Fleury算法

image-20230618160520189 image-20230618162848271

哈密顿图

哈密顿通路（回路）：经过图中每个结点一次且仅一次的通路（回路）

​ 哈密顿通/回路是经过图中所有结点的通/回路中长度最短的通/回路，即为通过图中所有结点的基本通/回路

哈密顿图：存在哈密顿回路的图

平凡图为哈密顿图，以上定义既适合无向图，又适合有向图

哈密顿图的判定：

设无向图G=<V,E>G=<V,E>是哈密顿图，V1V_1是VV的任意非空子集，则p(G−V1)≤∣V1∣p(G-V_1)\leq|V_1|，其中p(G−V1)p(G-V_1)是从GG中删除V1V_1后所得图的连通分支数。推论有：

  • 对VV的任意非空子集V1V_1有，p(G−V1)≤∣V1∣+1p(G-V_1)\leq|V_1|+1——常用逆否命题：若存在V的某个非空子集V1使得p(G−V1)>∣V1∣+1p(G-V_1)>|V_1|+1，则G不是哈密顿图
  • （充分条件）设G=<V,E>G=<V,E>是具有n个结点的简单无向图，若对任意两个不相邻的结点u,v∈Vu,v\in V，均有deg(u)+deg(v)≥n−1deg(u)+deg(v)\geq n-1，则GG中存在哈密顿通路
  • 设G=<V,E>G=<V,E>是具有n个结点的简单无向图，若对任意两个不相邻的结点u,v∈Vu,v\in V，均有deg(u)+deg(v)≥ndeg(u)+deg(v)\geq n，则GG中存在哈密顿回路
  • 设G=<V,E>G=<V,E>是有n(n≥2)n(n\geq 2)个结点的一些简单有向图。若忽略GG中边的方向所得的无向图中含生成子图KnK_n，则有向图中存在哈密顿通路
image-20230618165310911

举个栗子：

image-20230618164927778 image-20230618164949633 image-20230618165121311

最邻近算法

最邻近算法不是好的算法

image-20230618165410263 image-20230618165557856

抄近路算法

image-20230618165658607 image-20230618170703993 image-20230618170729423

设赋权完全图Kn(n≥3)K_n(n≥3)满足三角不等式，d0d_0是KnK_n中最短哈密顿回路的长度，HH是用抄近路算法求出的KnK_n中的哈密顿回路，则W(H)＜2d0W(H)＜2d_0

偶图

无向图G=<V,E>G=<V,E>的结点集VV能够划分成两个子集V1V_1，V2V_2，满足V1⋂V2=∅V1\bigcap V_2 = \empty，V1⋃V2=VV_1\bigcup V_2 = V，使得GG中任意一条边的两个端点，一个属于V1V_1，另一个属于V2V_2，则称GG为偶图（二分图）。V1V_1和V2V_2称为互补结点子集，偶图通常记为G=<V1,E,V2>G=<V_1,E,V_2>

偶图没有自回路，平凡图和零图可看成特殊的偶图

完全偶图（完全二分图）：偶图GG中，V1V_1和V2V_2的每个结点都有且仅有一条边相关联，记为Ki,jK_{i,j}，i=∣V1∣,j=∣V2∣i=|V_1|,j=|V_2|

image-20230618171538586

偶图的判定

无向图G=<V,E>G=<V,E>为偶图的充分必要条件是GG的所有回路的长度均为偶数。一般用逆否命题：无向图G=<V,E>G=<V,E>不是偶图的充分必要条件是GG的所有回路的长度均为奇数

匹配：在偶图G=<V1,E,V2>G=<V_1,E,V_2>中，若存在EE的子集E′={(v1,v1′),...(vq,vq′)}E'=\{(v_1,v_1'),...(v_q,v_q')\}，其中v1′,...vq′v_1',...v_q'是V2V_2中的q个不同的结点，则称GG的子图G′G'为从V1V_1到V2V_2的一个完全匹配，简称匹配

​ 必要条件：在偶图G=<V1,E,V2>G = <V_1, E, V_2>中，若存在V1V_1到V2V_2的单射ff，使得对任意v∈V1v∈V_1，都有(v,f(v))∈E(v, f(v))∈E，则存在V1V_1到V2V_2的匹配。由单射的性质知，不是所有的偶图都有匹配，存在匹配的必要条件是∣V1∣≤∣V2∣|V_1| ≤ |V_2|

霍尔定理

偶图G=<V1,E,V2>G = <V_1, E, V_2>中存在从V1V_1到V2V_2的匹配的充分必要条件是V1V_1中任意kk个结点至少与V2V_2中的kk个结点相邻，k=1,2,…,∣V1∣k = 1, 2, …, |V_1|（通常又称为相异性条件）

image-20230618184957090

tt条件：G=<V_1,E,V_2>是一个偶图，若满足条件则存在匹配（只需计算是一个偶图，若满足条件则存在匹配（只需计算V1V_1中结点的最小度数和V2V_2中结点的最大度数）：

  • V1V_1中每个结点至少关联tt条边
  • V2V_2中每个结点至多关联tt条边

平面图

交叉点、交叉边

平面图：除公共结点外没有其他交叉点

平面图的判定：

  • 观察法

欧拉公式：

  • 面：边包围，内部不含图的结点和边
  • 边界：包围该面的诸边构成的回路
  • 次数：面rr的边界长度，记为D(r)D(r)
  • 有限面/无线面：区域面积有限/无限
  • 平面图有且仅有一个无限面

对于平面图的不同平面表示，面的数目相同，但各面的边界和次数会不同

平面图中所有面的次数之和等于边数的二倍

欧拉公式：设G=<V,E>G=<V,E>是连通平面图，若它有nn个节点、mm条边和rr个面，则有n−m+r=2n-m+r = 2

​ 推论：若GG是一个简单连通平面图，若m>1m>1，则有m≤3n−6m\leq 3n-6（逆否命题常用来判定是否为非平面图）

image-20230618190100291

​ 推论：若GG是一个(n,m)(n,m)简单连通平面图，若每个面的次数至少为k(k≥3)k(k\geq 3)，则有：m≤kk−2(n−2)m\leq \frac{k}{k-2}(n-2)（常用逆否命题判定是否为非平面图）

库拉托夫斯基定理

一个图是平面图的充分必要条件是它的任何子图都不可能收缩为K5K_5或K3,3K_{3,3}

K5K_5或K3,3K_{3,3}称为库拉托夫斯基图（完全图和完全偶图）