离散数学知识点

来源：世旅网

说明：定义：红色表示。定理性质：橙色表示。

公式：蓝色表示。算法: 绿色表示页码：灰色表示

数理逻辑：

1. 命题公式：命题，联结词(，，，，)，合式公式，子公式 2. 公式的真值：赋值，求值函数，真值表，等值式，重言式，矛盾式

3. 范式：析取范式，极小项，主析取范式，合取范式，极大项，主合取范式 4. 联结词的完备集：真值函数，异或，条件否定，与非，或非，联结词完备集 5. 推理理论：重言蕴含式，有效结论，P规则，T规则， CP规则，推理 6. 谓词与量词:谓词，个体词，论域，全称量词，存在量词

7. 项与公式:项，原子公式，合式公式，自由变元，约束变元，辖域，换名，代入 8. 公式语义:解释，赋值，有效的，可满足的，不可满足的 9. 前束范式:前束范式

10. 推理理论:逻辑蕴含式，有效结论，-规则（US），+规则（UG）， -规则(ES)，+

规则(EG), 推理集合论：

1. 集合: 集合, 外延性原理, ,  , , 空集, 全集, 幂集, 文氏图, 交, 并, 差, 补, 对称

差

2. 关系: 序偶, 笛卡尔积, 关系, domR, ranR, 关系图, 空关系, 全域关系, 恒等关系 3. 关系性质与闭包:自反的, 反自反的, 对称的, 反对称的, 传递的,自反闭包 r(R),对称

闭包 s(R), 传递闭包 t(R)

4. 等价关系: 等价关系, 等价类, 商集, 划分

5. 偏序关系:偏序, 哈斯图, 全序(线序), 极大元/极小元, 最大元/最小元, 上界/下界 6. 函数: 函数, 常函数, 恒等函数, 满射,入射,双射，反函数, 复合函数 7. 集合基数:基数, 等势, 有限集/无限集, 可数集, 不可数集代数结构：

1. 运算及其性质：运算，封闭的,可交换的,可结合的,可分配的,吸收律, 幂等的，幺元,零

元,逆元

2. 代数系统：代数系统，子代数，积代数，同态，同构。

3. 群与子群：半群,子半群,元素的幂，独异点，群，群的阶数，子群,平凡子群，陪集，

拉格朗日（Lagrange）定理

4. 阿贝尔群和循环群：阿贝尔群(交换群)，循环群,生成元 5. 环与域：环，交换环，含幺环，整环，域

6. 格与布尔代数：格，对偶原理，子格，分配格，有界格，有补格，布尔代数，有限

布尔代数的表示定理图论：

1. 图的基本概念：无向图、有向图、关联与相邻、简单图、完全图、正则图、子图、

补图，握手定理，图的同构 2. 图的连通性:通路，回路，简单通路，简单回路（迹）初级通路（路径），初级回路（圈），

点连通，连通图，点割集，割点，边割集，割边，点连通度，边连通度，弱连通图，

3. 4. 5. 6.

单向连通图，强连通图，二部图（二分图）图的矩阵表示：关联矩阵，邻接矩阵，可达矩阵

欧拉图与哈密顿图：欧拉通路、欧拉回路、欧拉图、半欧拉图，哈密顿通路、哈密顿回路、哈密顿图、半哈密顿图

无向树与根树：无向树，生成树，最小生成树，Kruskal，根树，m叉树，最优二叉树，Huffman算法

平面图:平面图，面，欧拉公式，Kuratoski定理

数理逻辑：

命题：具有确定真值的陈述句。

否定词符号：设p是一个命题，p称为p的否定式。p是真的当且仅当p是假的。p是真的当且仅当p是假的。【定义1.1】

合取词符号：设p，q是两个命题，命题 “p并且q”称为p，q的合取，记以pq，读作p且q。pq是真的当且仅当p和q都是真的。【定义1.2】

析取词符号：设p，q是两个命题，命题 “p或者q”称为p，q的析取，记以pq，读作p或q。pq是真的当且仅当p，q中至少有一个是真的。【定义1.3】

蕴含词符号 ：设p，q是两个命题，命题 “如果p，则q”称为p蕴含q，记以pq。pq是假的当且仅当p是真的而q是假的。【定义1.4】

等价词符号 ：设p，q是两个命题，命题 “p当且仅当q”称为p等价q，记以pq。pq是真的当且仅当p，q或者都是真的，或者都是假的。【定义1.5】合式公式:

(1) 命题常元和变元符号是合式公式；

(2) 若A是合式公式，则(A)是合式公式，称为A的否定式；

(3) 若A，B是合式公式，则 (AB)， (AB)， (AB)，(AB)是合式公式； (4) 所有合式公式都是有限次使用(1)，(2)，(3)、(4)得到的符号串。

子公式: 如果Ｘ是合式公式A的一部分，且Ｘ本身也是一个合式公式，则称Ｘ为公式A的子公式。【定义1.6】

赋值（指派，解释）：设是命题变元集合，则称函数v：  {1，0}是一个真值赋值。【定义1.8】

真值表：公式A在其所有可能的赋值下所取真值的表，称为A的真值表。【定义1.9】重言式（永真式）:任意赋值v， v

A【定义1.10】

矛盾式（永假式）:任意赋值v，有v 基本等值式

双重否定律 AA

幂等律 AAA, AAA 交换律 ABBA, ABBA

结合律 (AB)CA(BC), (AB)CA(BC)

分配律 A(BC)(AB)(AC), A(BC)(AB)(AC) 德摩根律 (AB)AB ,(AB)AB 吸收律 A(AB)A, A(AB)A

零律 A  , A 同一律 AA, A A 排中律 AA 

等值式：若等价式AB是重言式，则称A与B等值，记作AB。【定义2.1】

    矛盾律 AA  蕴涵等值式 ABAB

等价等值式 AB(AB)(BA) 假言易位 ABBA 等价否定等值式ABAB 归谬论 (AB)(AB) A

置换规则：设Ｘ是公式A的子公式, Ｘ Y。将A中的Ｘ（可以是全部或部分X）用Y来置换，所得到的公式B，则 AB。

文字: 设A（命题变元集）, 则A和  A都称为命题符号A的文字，其中前者称为正文字，后者称为负文字。【定义2.2】

析取范式：形如A1  A2  … An (n1) 的公式称为析取范式，其中Ai(i=1,…,n)是由文字组成的合取范式。

合取范式：形为A1 A2  …An (n 1) 的公式称为合取范式，其中A1,…,An都是由文字组成的析取式。【定义2.3】

极小项：文字的合取式称为极小项，其中公式中每个命题符号的文字都在该合取式中出现一次。极大项：文字的析取式称为极大项，其中公式中每个命题符号的文字都在该合取式中出现一次。【定义2.4】

主析取范式：给定的命题公式的主析取范式是一个与之等价的公式，后者由极小项的析取组成。主合取范式：给定的命题公式的主合取范式是一个与之等价的公式，后者由极大项的合取组成。【定义2.5】

公式的真值表中真值为F的指派所对应的极大项的合取，即为此公式的主合取范式。真值函数：称F:{0,1}n {0,1} 为n元真值函数.【定义2.6】

联结词的完备集：设C是联结词的集合，若对于任意一个合式公式均存在一个与之等价的公式，而后者只含有C中的联结词，则称C是联结词的完备集。【定义2.7】

{，，，，}，{ ，， } , {， }， {， }，{ ，}是联结词的完备集。【定理2.6】异或PQ ：

  (P  Q)   (P  Q)

  (P  Q)【定义2.8】

c 条件否定PQ：   (P  Q)

与非PQ：或非PQ：

{},{↓}都是联结词的完备集【定理2.7】

重言蕴含式：当且仅当PQ是一个重言式时，称P重言蕴含Q，记为PQ。有效结论：设A、C是两个命题公式，若A  C，称C是A的有效结论。【定义3.1】推理定律——重言蕴涵式

1. A  (AB) 2. (AB)  A

附加律化简律假言推理拒取式析取三段论假言三段论等价三段论构造性二难

构造性二难(特殊形式)

3. (AB)A  B 4. (AB)B  A 5. (AB)B  A

6. (AB)(BC)  (AC) 7. (AB)(BC)  (AC) (AB)(AB)  B

8. (AB)(CD)(AC)  (BD)

9. (AB)(CD)( BD)  (AC) 破坏性二难

形式系统: 一个形式系统 I 由下面四个部分组成： (1) 非空的字母表，记作 A(I).

(2) A(I) 中符号构造的合式公式集，记作 E(I). (3) E(I) 中一些特殊的公式组成的公理集，记作 AX(I). (4) 推理规则集，记作 R(I).

记 I=, 其中是 I 的形式语言系统, 是 I 的形式演算系统.

自然推理系统: 无公理, 即AX(I)=

公理推理系统: 推出的结论是系统中的重言式, 称作定理【定义3.2】 P规则：在推导过程中,可以随时添加前提。

T规则：在推导过程中,可以引入公式S，它是由其前题的一个或多个公式借助重言、蕴含而得到的。

推理（证明）：从前提A1, A2,, Ak到结论B的推理是一个公式序列C1, C2,, Cl. 其中Ci(1il)是某个Aj, 或者可由序列中前面的公式应用推理规则得到, 并且Cl =B。【定义3.3】 CP规则(演绎定理)：若 {R}|- S，则  |- RS, 其中为命题公式的集合。个体词：用于表示命题中主语部分的符号或符号串。个体常元表示确指个体。个体变元表示不确指个体。

个体域: 个体变元的取值范围，常用D表示。量词：限定个体数量特性的词。全称量词：对所有的存在量词：有些

谓词语言：用符号串表示个体、谓词、量词和命题

个体变元符号： x，y，z，… 个体常元符号： a，b，c，… 函数符号：f，g，… 谓词符号：P，Q，R，… 命题常元符号：  ，量词符号： ，

连接词符号：  , , , ,  辅助符号：） , （

【定义4.1】

项: (1)个体常元和变元是项；

(2) 若f是n元函数符号，t1, …, tn是项，则f(t1, …, tn)是项； (3) 仅仅有限次使用(1)，(2)产生的符号串是项。【定义4.2】

原子公式: 若P是一个元谓词符号，t1,…,tn是项, 则P(t1,…,tn)是原子公式。【定义4.3】合式公式： (1) 原子公式是公式；

(2) 若A是合式公式，则( A)是合式公式；

(3) 若A，B是公式，则(AB)，(AB)，AB)，(AB)是公式； (4) 若A是公式，x是变元，则xA，xA是公式；

(5) 仅仅有限次使用１～４得到的符号串才是合式公式。【定义4.4】

设公式 的一个子公式为 x A或 x A。则称：指导变元：x是或的指导变元。辖域：A是相应量词的辖域。

约束出现：辖域中x的一切出现，以及( x)中的x称为x在中的约束出现。

 自由出现：变元的非约束出现。约束变元：约束出现的变元。

自由变元：自由出现的变元。【定义4.5】

封闭的：一个公式A是封闭的，若其中不含自由变元。【定义4.6】

变元换名：（1）换名的范围是量词的指导变元,及其相应辖域中的变元，其余部分不变。（2）换名时最好选用辖域中未出现的变元名。变元代入：代入对自由变元进行。不能改变约束关系。解释：谓词语言的一个解释 I= (D,  )包括： (1) 非空集合D，称之为论域；

(2) 对应于每一个个体常元a， (a)D；

(3) 对应于每一个n元函数符号f都有一个函数 (f):Dn  D；

(4) 对应于每一个n元谓词符号A都有一个n元关系(A)  Dn。【定义4.7】

赋值：解释I中的赋值v为每一个个体变元x指定一个值v(x ） D，即设 V为所个体变元的集合，则赋值v是函数 v:V  D.

可满足的：给定公式A，若在某一解释中至少有一种赋值使A取值为1，则称A为可满足的。否则称A是不可满足的。

等值式A  B：若AB是有效的【定义5.1】几类等值式

（1）命题公式的推广

e.g. P(x)  Q(x)   P(x)  Q(x) （2）否定深入

  x P(x)   x( P(x))   xP(x)   x ( P(x)) （3）量词作用域的扩张与收缩

设B中不含x的自由出现，则

 x(A(x) B)   x A(x)  B  x(A(x) B)   x A(x)  B  x(A(x)B)   x A(x)  B  x(B A(x))  B  x A(x)  x(A(x) B)   x A(x)  B  x(A(x) B)   x A(x)  B  x(A(x)B)   x A(x)  B  x(B A(x))  B x A(x) （4）量词分配等值式

 x(A(x)  B(x))   x A(x)   x B(x)

 x(A(x)  B(x))   x A(x)   x B(x)  x  y A(x,y)   y  x A(x,y)  x  y A(x,y)   y  x A(x,y)

（5）多个量词的使用

置换规则：设(A)是含A的公式, 那么, 若AB, 则(A)(B).

换名规则：设A为一公式，将A中某量词辖域中个体变项的所有约束出现及相应的指导变元换成该量词辖域中未曾出现过的个体变项符号，其余部分不变，设所得公式为A，则AA. 前束范式：如果谓词公式A有如下形状：Q1x1…QnxnM，其中 Qixi或者是xi，或者是xi，i=1，…，n，M是不含量词的公式， Q1x1…Qnxn称为首标，M称为母式。【定义5.2】

前束范式存在定理：对于任意谓词公式，都存在与它逻辑等价的前束范式。【定理5.1】前束范式的算法：

步1. 对约束出现的变元进行必要的换名，使得约束出现的变元互不相同且不与任何自由变元同名。

步2. 将所有的否定号深入到量词后面。

步3. 将量词符号移至公式最外层。逻辑蕴含式A  C：当且仅当AC是有效的。几类逻辑蕴涵式

第一组命题逻辑推理定理的代换实例

如, xF(x)yG(y)  xF(x)

如, xF(x) xF(x), xF(x) xF(x) 第二组基本等值式生成的推理定理

xF(x)xF(x), xF(x)  xF(x)

第三组其它常用推理定律

(1) xA(x)xB(x)  x(A(x)B(x)) (2) x(A(x)B(x))xA(x)xB(x) (3) x(A(x)B(x))  xA(x)xB(x) (4)  x(A(x)B(x))  xA(x)xB(x)

∀𝑥𝐴(𝑥)∴𝐴(𝑦𝐴(𝑥)∴∀𝑥𝐴(𝑥)

∀𝑥𝐴(𝑥)∴𝐴(𝑐)

推理规则

- 规则(US)：+规则(UG)：

或)

x,y个体变项，c个体常项 x个体变项

x个体变项, c个体常项 x,y个体变项，c个体常项

- 规则(ES)：+ 规则(EG)：

∴∃𝑥𝐴(𝑥)∴𝐴(𝑐)𝐴(𝑦)∴∃𝑥𝐴(𝑥𝐴(𝑐)

或)

𝐵→𝐴(𝑦)∴𝐵→∃𝑥𝐴(𝑥)𝐵→𝐴(𝑐)

∴∃𝑥𝐴(𝑥

或)

∴𝐵→∃𝑥𝐴(𝑥)

先用ES，再用US

自然推理系统N ：

1. 字母表. 同一阶语言L 的字母表 2. 合式公式. 同L的合式公式 3. 推理规则: (1) 前提引入规则 (2) 结论引入规则 (3) 置换规则 (4) 假言推理规则 (5) 附加规则 (6) 化简规则 (7) 拒取式

(8) 假言三段论规则 (9) 析取三段论规则

(10) 构造性二难推理规则 (11) 合取引入规则 (12)  -规则 (13)  +规则 (14)  -规则

(15)  +规则【定义5.3】

集合论：

A  B  x ( xA  xB )【定义6.1】 A = B  A  B  B  A 【定义6.2】 A  B  A  B  A  B 【定义6.3】 A ⊈ B  x ( xA  xB )

空集 ：不含有任何元素的集合【定义6.4】空集是任何集合的子集。【定理6.1】幂集P(A) = { x | x  A }【定义6.5】如果 |A|=n，则 |P(A)|=2

全集 E：包含了所有元素的集合【定义6.6】并AB = {x | xA  xB} 交AB = {x | xA  xB}

差（相对补）AB = {x | xA  xB}【定义6.7】对称差AB = (AB)(BA) 【定义6.8】补（绝对补）A = EA = {x|xA}【定义6.9】广义并A = { x | z ( zA  xz )}【定义6.10】广义交A = { x | z ( zA  xz )}【定义6.11】集合恒等式

1.只涉及一个运算的算律：

 交换结合幂等 AB=BA (AB)C=A(BC) AA=A n

 AB=BA (AB)C=A(BC) AA=A  AB=BA (AB)C=A(BC) 2．涉及两个不同运算的算律： 与 分配 A(BC)=(AB)(AC) A(BC)=(AB)(AC) 与 A(BC)=(AB)(AC) 吸收 A(AB)=A A(AB)=A 3．涉及补运算的算律：   D.M律 A(BC)=(AB)(AC) A(BC)=(AB)(AC) (BC)=BC (BC)=BC A=A 双重否定 4．涉及全集和空集的算律：  补元律零律同一律否定 AA= A= A=A =E E AA=E AE=E AE=A E= 序偶（有序对）：由两个元素 x 和 y，按照一定的顺序组成的二元组，记作.【定义7.1】笛卡儿积:设A,B为集合，A与B的笛卡儿积记作AB定义为AB = {| xAyB}.【定义7.2】

笛卡尔积性质：A=或B=时, AB=

“ ”不满足结合律 A(BC) = (AB)(AC)

关系：（两个定义）

(1) 序偶的一个集合, 确定了一个二元关系R。R 中任一序偶 ,可记作 R 或 xRy【定义7.3】

(2) 笛卡尔积的子集： R  AB 【定义7.4】空关系: 全域关系：A×B

恒等关系 IA = {| x∈A} 【定义7.5】

关系矩阵：若A={x1, x2, …, xm}，B={y1, y2, …, yn}，R是从A到B的关系，R的关系矩阵是布尔矩阵MR = [ rij ] mn, 其中rij = 1 < xi, yj> R.

关系图：若A= {x1, x2, …, xm}，R是从A上的关系，R的关系图是GR=, 其中A为结点集，

R为边集. 如果属于关系R，在图中就有一条从 xi 到 xj 的有向边.

前域(定义域) dom(R) = {x|y.R} 值域 ran(R) ={y|x.R} 域fld(R) = domR  ranR

【定义7.6】

逆关系R = { | R } 【定义7.7】互逆 (R)= R (R  S) = R  S (R S)= R  S (A B) = BA (R - S) = R - S

复合关系 RS = { |  y (R  S) }【定义7.8】 (R S) P=R (S P) R = RR … R

设R X Y,S YZ,则 (R S) = S R【定理7.2】 R在A上的限制R↾A = { | xRy∧x∈A }

1 1

A在R下的像R[A]=ran(R↾A) 【定义7.9】

自反的：若 x∈A，都有R, 则称 R 是自反的

反自反的：若 x∈A，都有  R, 则称 R 是反自反的.【定义7.11】对称的：对任意x,yA,满足, 若 R,则R

反对称的：对任意x,yA,满足，若 R且R,则x=y【定义7.12】

传递的：对任意的x,y,zA, 满足:若R且R, 则R,则称R是传递的【定义7.13】自反闭包（对称、传递）：

设R是A上的二元关系,如果有另一个关系R'满足:

① R'是自反（对称、传递）的; ② R'R;

③ 对于任何自反的关系R”,若R\"R, 则有R\"R'.

则称关系R'为R的自反闭包. 记为 r(R)（对称闭包 s(R) 和传递闭包 t(R)）。【定义7.14】设R为A上的关系, 则有 (1) r(R)=R∪IA (2) s(R)=R∪R

(3) t(R)=R∪R∪R∪…（若|A|=n，则 t(R)=R∪R∪… ∪R）

等价关系：设 R 为集合 A 上的一个二元关系。若 R 是自反的, 对称的, 传递的, 则称 R 为 A 上的等价关系【定义7.15】

等价类：设R为集合A上的等价关系, 对aA, 定义:[a]R = {x|xA 且 R}称之为元素a关于R的等价类。【定义7.16】

给定A上的等价关系R,对于a,bA有当且仅当[a]R=[b]R【定理17.4】

商集：设R是A上的等价关系，定义 A/R={[a]R|aA}称之为A关于R的商集.【定义7.17】划分：设A为非空集合, 若A的子集族π(π  P(A))满足:

(1)  π

(2) xy(x,yπ∧x≠yx∩y=) (3) ∪π = A

则称π是A的一个划分, 称π中的元素为A的划分块.【定义7.18】

给定集合 A 上的等价关系 R, 则商集 A/R 是 A 的一个划分.

集合A的一个划分π诱导出A上的一个等价关系R. R定义为R= {| x,y A 且x,y在π的同一分块中}

设R1和R2为非空集合A上的一个等价关系,则 R1 = R2当且仅当A/R1 = A/R2.

偏序：设A是一个集合. 如果 A 上的二元关系 R 是自反的,反对称的和传递的, 则称R是A上的一个偏序关系. 记R为“”, 且称序偶为偏序集。【定义7.19】【定义7.22】

全序（线序）：设为偏序集, 若对任意的x,yA满足: xy或 yx则称  为全序关系. 为全序集.【定义7.21】

覆盖：设为偏序集,若x,yA, xy,xy且没有其它元素z满足xz,zy,则称y覆盖x. 记covA={ |x,yA且y覆盖x}【定义7.23】哈斯图：作图规则

① 用小元圈代表元素;

② 若xy且xy,则将代表y的小元圈画在代表x的小元圈之上; ③ 若covA, 则在x,y之间用直线连接。你

极小元/极大元：设为偏序集, B A

(1) 对bB，若B中不存在x满足: bx且 xb则称b为B的极小元.

(2) 对bB，若B中不存在x满足: bx且 bx则称b为B的极大元. 最小元/最大元：设为偏序集,BA,若有某个bB (1) 对于B中每一个元素x都有bx，则称b为B的最小元.

(2) 对于B中每一个元素x都有xb，则称b为B的最大元.【定义7.24】下界/上界：设为偏序集, B A

(1) 若有aA,且对xB 满足 ax，则称a为B的下界。

进一步: 设a为B的下界,若B的所有下界y均有ya,则称a为B的下确界，记为glb B。 (2) 若有aA,且对xB 满足 xa，则称a为B的上界。

进一步: 设a为B的上界,若B的所有上界y均有ay,则称a为B的上确界，记为lub B。【定义7.25】

函数：设X,Y为两个集合,fXY, 若对xX,!(唯一的)yY,满足: f,则称f为函数.记为:f:XY

定义域: domf=X

值域: ranf (有时记为f(X))={f(x)|xX}【定义8.1】

函数相等：设f和g都是从A到B的函数, 若对任意xA,有f(x)=g(x),则称f和g相等.记为f=g【定义8.2】

函数的个数：设f:AB,|A|=m, |B|=n.记 B={f|f: AB}, 则| B |= n 满射(到上映射)：设 f: X Y, 若 ranf = Y, 则称 f 为满射的.

入射（单射）(一对一映射)：设f: XY, 对  x1, x2 X, 满足:若 x1  x2, 则 f(x1)  f(x2),称 f 为入射的.

双射 (一一对应映射)：设f:XY, 若f既是满射的, 又是入射的. 则称f是双射的.【定义8.6】常函数:设 f:A→B, 如果存在c∈B使得对所有的 x∈A都有 f(x)=c, 则称 f:A→B是常函数. 恒等函数:称 A上的恒等关系IA为A上的恒等函数, 对所有的x∈A都有IA(x)=x.

单调递增:设, 为偏序集，f:A→B，如果对任意的x1, x2∈A, x1≺x2, 就有 f(x1)≼ f(x2), 则

称 f 为单调递增的；

严格单调递增:如果对任意的x1, x2∈A, x1≺x2, 就有f(x1) ≺f(x2), 则称 f 为严格单调递增的.

类似的也可以定义单调递减和严格单调递减的函数

a∈A';A'(a)=0, a∈AA'

自然映射：设R是A上的等价关系, 令g:A→A/R；g(a)=[a], a∈A称 g 是从 A 到商集 A/R 的自然映射

【定义8.7】

复合函数：设 f:XY,g:YZ, 定义: f g = {|xX且zZ且可找到yY使y=f(x),z=g(y)} 称f g为f与 g 的复合函数. 设f:A→B, g:B→C

(1) 如果 f:A→B, g:B→C是满射的, 则 fg:A→C也是满射的 (2) 如果 f:A→B, g:B→C是单射的, 则 fg:A→C也是单射的

(3) 如果 f:A→B, g:B→C是双射的, 则 fg:A→C也是双射的【定理8.2】

反函数（逆函数）：设f:XY是一个双射函数，那么f 是YX的双射函数. 称f 为f的反函数. 互逆 (f )=f

设 f:A→B是双射的, 则 f f = IB, f f  = IA 【定理8.5】

基数：用来衡量集合大小的一个概念. 对于有限集合集来说, 集合的基数就是其中所含元素的个数.

等势的：设A, B是集合, 如果存在着从A到B的双射函数, 就称A和B是等势的, 记作A≈B. 如果A不与B等势, 则记作A≉B. N ≈ Z ≈ Q ≈ N×N

注：通常将A的基数记为 |A|.【定义8.8】

-1

特征函数：设A为集合, 对于任意的A'A, A'的特征函数A ' :A→{0,1}定义为A'(a)=1,

任何实数区间都与实数集合R等势 {0,1}≈R 康托定理

(1) N ≉ R；

(2) 对任意集合A都有A≉P(A).【定义8.7】有限集(有穷集)/无限集 (无穷集) ：

设A为一个集合. 若存在某个自然数n, 使得A与集合{0,1,…,n-1}等势, 则称A是有限的. 若集合A不是有限的, 则称A是无限的.【定义8.11】 ：实数集R的基数记作, 即cardR = 【定义8.12】

可数集(可列集)：设A为集合，若cardA≤0，则称A为可数集或可列集。【定义8.14】与自然数集N等势的任意集合称为可数的. 其基数为0 结论：

(1) A为可数的当且仅当可排列成A={a1,a2,… ,an,…}的形式. (2) 任一无限集必含有可数子集. (3) 可数集的任何无限子集是可数的.

(4) 可数个两两不相交的可数集合的并集,仍是一个可数集. (5) NN是可数集.

(6) 有理数的全体组成的集合是可数集. (7) 全体实数构成的集合R是不可数的. 基数的常识：

① 对于有穷集合A, 基数是其元素个数n，|A| = n;

② 没有最大的基数。将已知的基数按从小到大的顺序排列就得到： 0, 1, 2, …, n, …, 0, , …

代数结构

运算：对于集合 A，f 是从An到 A 的函数，称 f 为集合A上的一个n元运算。【定义9.1】交换律：已知，若x，y∈A，有x*y=y*x，称*在A上是可交换的。【定义9.3】结合律：已知，若x，y，z∈A，有x*（y*z）=（x*y）*z，称*在A上是可结合的。【定义9.4】

幂等律：已知〈A，*〉，若x∈A，x*x=x 则称满足幂等律。【定义9.5】

分配律：设，若x，y，z∈A有: x*(y△z)=（x*y）△（x*z） ; (y△z)*x=(y*x)△(z*x)称运算*对△是可分配的。【定义9.6】

吸收律：设,是定义在集合A上的两个可交换二元运算，若对x,y A,都有:x(x y) = x ； x(x y) = x则称运算和满足吸收律.【定义9.7】单位元（幺元）:

设*是A上二元运算， el, er,eA

左幺元：若xA，有el*x=x，称el为运算*的左幺元；右幺元：若xA，有x*er=x，称er为运算*的右幺元；

若e既是左幺元又是右幺元，称e为运算*的幺元【定义9.8】

设*是A上的二元运算，具有左幺元el，右幺元er，则el=er=e 【定理9.1】零元:

设*是A上二元运算， l, r, A

左零元：若xA，有l*x=l ，称l为运算*的左零元；右零元：若xA，有x*r=r，称r为运算*的右零元；

若既是左零元又是右零元，称为运算*的零元。【定义9.9】

设*是A上的二元运算，具有左零元 l ，右零元r，则 l=  r= 【定理9.2】

逆元：设*是A上的二元运算，e是运算*的幺元，若x*y=e那对于运算*，x是y的左逆元，y是

x的右逆元存在逆元(左逆无，右逆元）的元素称为可逆的（左可逆的，右可逆的）【定义9.10】对于可结合运算ο ，如果元素x有左逆元ｌ，右逆元r，则l=r=x【定理9.4】消去律：已知，若x，y，z∈A，有 (1) 若 x*y = x*z且 x ,则y=z；(左消去律) (2) 若 y*x = z*x且 x ,则y=z；（右消去律）那么称*满足消去律。【定义9.11】

代数系统：设A为非空集合，为A上运算的集合,称为一个代数系统.【定义9.12】同类型的代数系统：如果两个代数系统中运算的个数相同，对应运算的元数相同，且代数常数的个数也相同，则称它们是同类型的代数系统.【定义9.13】

子代数：设V=是代数系统，B是S的非空子集，如果B对f1, f2, …, fk 都是封闭的，且B和S含有相同的代数常数，则称是V的子代数系统，简称子代数【定义9.14】

最大的子代数：就是V本身

最小的子代数：如果令V中所有代数常数构成的集合是B，且B对V中所有的运算都是封闭的，则B就构成了V的最小的子代数

平凡的子代数:最大和最小的子代数称为V 的平凡的子代数

真子代数：若B是S的真子集，则B构成的子代数称为V的真子代数.

因子代数：设V1=和V2=是同类型的代数系统，◦和为二元运算，在集合AB上如下定义二元运算▪， ,AB，有▪= 称V=为V1与V2的积代数，记作V1V2. 这时也称V1和V2为V的因子代数. 【定义9.15】设V1=和V2=是同类型的代数系统，V1V2=是它们的积代数.

(1) 如果◦ 和 运算是可交换（可结合、幂等）的，那幺▪运算也是可交换（可结合、幂等）的 (2) 如果 e1 和 e2（1和2）分别为◦ 和 运算的单位元（零元），那幺（<1,2>）也是▪运算的单位元（零元）

(3) 如果 x 和 y 分别为◦和 运算的可逆元素，那幺也是▪运算的可逆元素，其逆元就是【定理9.5】

同态:设V1=和V2=是同类型的代数系统，f:AB，对x, yA 有f(x∘y) = f(x)f(y), 则称 f 是V1到V2的同态映射，简称同态 (1) f 如果是单射，则称为单同态。

(2) 如果是满射，则称为满同态，这时称V2是V1的同态像，记作V1V2。 (3) 如果是双射，则称为同构，也称代数系统V1同构于V2，记作V1V2 。 (4) 如果V1=V2，则称作自同态。【定义9.16】

半群：设V=是代数系统，∘为二元运算，如果∘运算是可结合的，则称V为半群。独异点：设V=是半群，若e∈S是关于∘运算的单位元，则称V是含幺半群，也叫做独异点。有时也将独异点V 记作 V=.