离散数学知识点

1、-. z. . . . . 资料. . .说明：定义：红色表示。定理性质：橙色表示。公式：蓝色表示。算法:绿色表示页码：灰色表示数理逻辑：命题公式：命题，联结词(，)，合式公式，子公式公式的真值：赋值，求值函数，真值表，等值式，重言式，矛盾式*式：析取*式，极小项，主析取*式，合取*式，极大项，主合取*式联结词的完备集：真值函数，异或，条件否认，与非，或非，联结词完备集推理理论：重言蕴含式，有效结论，P规则，T规则， CP规则，推理谓词与量词:谓词，个体词，论域，全称量词，存在量词项与公式:项，原子公式，合式公式，自由变元，约束变元，辖域，换名，代入公式语义:解释，赋值，有效的，可满足的，不可

2、满足的前束*式:前束*式推理理论:逻辑蕴含式，有效结论，-规则US，+规则UG，-规则(ES)，+规则(EG), 推理集合论：集合: 集合, 外延性原理, , , , 空集, 全集, 幂集, 文氏图, 交, 并, 差, 补, 对称差关系: 序偶, 笛卡尔积, 关系, domR, ranR, 关系图, 空关系, 全域关系, 恒等关系关系性质与闭包:自反的, 反自反的,对称的, 反对称的, 传递的,自反闭包 r(R),对称闭包 s(R), 传递闭包 t(R)等价关系: 等价关系, 等价类, 商集, 划分偏序关系:偏序, 哈斯图, 全序(线序), 极大元/极小元, 最大元/最小元, 上界/下界函数:

3、 函数, 常函数, 恒等函数, 满射,入射,双射，反函数, 复合函数集合基数:基数, 等势, 有限集/无限集, 可数集, 不可数集代数构造：运算及其性质：运算，封闭的,可交换的,可结合的,可分配的,吸收律, 幂等的，幺元,零元,逆元代数系统：代数系统，子代数，积代数，同态，同构。群与子群：半群,子半群,元素的幂，独异点，群，群的阶数，子群,平凡子群，陪集，拉格朗日Lagrange定理阿贝尔群和循环群：阿贝尔群(交换群)，循环群,生成元环与域：环，交换环，含幺环，整环，域格与布尔代数：格，对偶原理，子格，分配格，有界格，有补格，布尔代数，有限布尔代数的表示定理图论：图的根本概念：无向图、有向图、

4、关联与相邻、简单图、完全图、正则图、子图、补图，握手定理，图的同构图的连通性:通路，回路，简单通路，简单回路迹初级通路路径，初级回路圈，点连通，连通图，点割集，割点，边割集，割边，点连通度，边连通度，弱连通图，单向连通图，强连通图，二部图二分图图的矩阵表示：关联矩阵，邻接矩阵，可达矩阵欧拉图与哈密顿图：欧拉通路、欧拉回路、欧拉图、半欧拉图，哈密顿通路、哈密顿回路、哈密顿图、半哈密顿图无向树与根树：无向树，生成树，最小生成树，Kruskal，根树，m叉树，最优二叉树，Huffman算法平面图:平面图，面，欧拉公式，Kuratoski定理数理逻辑：命题：具有确定真值的陈述句。否认词符号：设p是一个

5、命题，p称为p的否认式。p是真的当且仅当p是假的。p是真的当且仅当p是假的。【定义1.1】合取词符号：设p，q是两个命题，命题p并且q称为p，q的合取，记以pq，读作p且q。pq是真的当且仅当p和q都是真的。【定义1.2】析取词符号：设p，q是两个命题，命题p或者q称为p，q的析取，记以pq，读作p或q。pq是真的当且仅当p，q中至少有一个是真的。【定义1.3】蕴含词符号：设p，q是两个命题，命题如果p，则q称为p蕴含q，记以pq。pq是假的当且仅当p是真的而q是假的。【定义1.4】等价词符号：设p，q是两个命题，命题p当且仅当q称为p等价q，记以pq。pq是真的当且仅当p，q或者都是真的，或

6、者都是假的。【定义1.5】合式公式:命题常元和变元符号是合式公式；假设A是合式公式，则(A)是合式公式，称为A的否认式；假设A，B是合式公式，则 (AB)， (AB)， (AB)，(AB)是合式公式；所有合式公式都是有限次使用(1)，(2)，(3)、(4)得到的符号串。子公式: 如果是合式公式A的一局部，且本身也是一个合式公式，则称为公式A的子公式。【定义1.6】赋值指派，解释：设是命题变元集合，则称函数v： 1，0是一个真值赋值。【定义1.8】真值表：公式A在其所有可能的赋值下所取真值的表，称为A的真值表。【定义1.9】重言式永真式:任意赋值v， v A矛盾式永假式:任意赋值v，有v A【定

7、义1.10】等值式：假设等价式AB是重言式，则称A与B等值，记作AB。【定义2.1】根本等值式双重否认律AA幂等律AAA, AAA交换律ABBA, ABBA结合律(AB)CA(BC), (AB)CA(BC)分配律A(BC)(AB)(AC),A(BC)(AB)(AC)德摩根律(AB)AB,(AB)AB吸收律A(AB)A, A(AB)A零律 A, A同一律 AA, AA排中律 AA 矛盾律 AA蕴涵等值式 ABAB等价等值式 AB(AB)(BA)假言易位 ABBA等价否认等值式ABAB归谬论 (AB)(AB) A置换规则：设是公式A的子公式, Y。将A中的可以是全部或局部*用Y来置换，所得到的公式

8、B，则 AB。文字: 设A命题变元集, 则A和 A都称为命题符号A的文字，其中前者称为正文字，后者称为负文字。【定义2.2】析取*式：形如A1 A2 An(n1) 的公式称为析取*式，其中Ai(i=1,n)是由文字组成的合取*式。合取*式：形为A1 A2 An(n 1) 的公式称为合取*式，其中A1,An都是由文字组成的析取式。【定义2.3】极小项：文字的合取式称为极小项，其中公式中每个命题符号的文字都在该合取式中出现一次。极大项：文字的析取式称为极大项，其中公式中每个命题符号的文字都在该合取式中出现一次。【定义2.4】主析取*式：给定的命题公式的主析取*式是一个与之等价的公式，后者由极小项的

9、析取组成。主合取*式：给定的命题公式的主合取*式是一个与之等价的公式，后者由极大项的合取组成。【定义2.5】公式的真值表中真值为F的指派所对应的极大项的合取，即为此公式的主合取*式。真值函数：称F:0,1n 0,1 为n元真值函数.【定义2.6】联结词的完备集：设C是联结词的集合，假设对于任意一个合式公式均存在一个与之等价的公式，而后者只含有C中的联结词，则称C是联结词的完备集。【定义2.7】， , ， ，是联结词的完备集。【定理2.6】c异或PQ： (P Q)c条件否认PQ： (P Q)与非PQ： (P Q)或非PQ： (P Q)【定义2.8】,都是联结词的完备集【定理2.7】重言蕴含式：当

10、且仅当PQ是一个重言式时，称P重言蕴含Q，记为PQ。有效结论：设A、C是两个命题公式，假设A C，称C是A的有效结论。【定义3.1】推理定律重言蕴涵式1. A (AB)附加律2. (AB) A化简律3. (AB)A B假言推理4. (AB)B A拒取式5. (AB)B A析取三段论6. (AB)(BC) (AC)假言三段论7. (AB)(BC) (AC)等价三段论8. (AB)(CD)(AC) (BD)构造性二难(AB)(AB) B构造性二难(特殊形式)9. (AB)(CD)( BD) (AC)破坏性二难形式系统: 一个形式系统I 由下面四个局部组成： (1) 非空的字母表，记作A(I). (

11、2) A(I) 中符号构造的合式公式集，记作E(I). (3) E(I) 中一些特殊的公式组成的公理集，记作A*(I). (4) 推理规则集，记作R(I).记I=, 其中是I 的形式语言系统, 是I 的形式演算系统.自然推理系统: 无公理, 即A*(I)=公理推理系统: 推出的结论是系统中的重言式, 称作定理【定义3.2】P规则：在推导过程中,可以随时添加前提。T规则：在推导过程中,可以引入公式S，它是由其前题的一个或多个公式借助重言、蕴含而得到的。推理证明：从前提A1, A2, Ak到结论B的推理是一个公式序列C1, C2, Cl. 其中Ci(1il)是*个Aj, 或者可由序列中前面的公式应

12、用推理规则得到, 并且Cl =B。【定义3.3】CP规则(演绎定理)：假设R|- S，则 |- RS, 其中为命题公式的集合。个体词：用于表示命题中主语局部的符号或符号串。个体常元表示确指个体。个体变元表示不确指个体。个体域: 个体变元的取值*围，常用D表示。量词：限定个体数量特性的词。全称量词：对所有的存在量词：有些谓词语言：用符号串表示个体、谓词、量词和命题个体变元符号： *，y，z，个体常元符号： a，b，c，函数符号：f，g，谓词符号：P，Q，R，命题常元符号：，量词符号：，连接词符号： , , , , 辅助符号： , 【定义4.1】项: (1)个体常元和变元是项；(2) 假设f是n元

13、函数符号，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是公式，则(AB)，(AB)，AB)，(AB)是公式；(4) 假设A是公式，*是变元，则*A，*A是公式；(5) 仅仅有限次使用得到的符号串才是合式公式。【定义4.4】设公式的一个子公式为 * A或 * A。则称：指导变元：*是或的指导变元。辖域：A是相应量词的辖域。约束

14、出现：辖域中*的一切出现，以及( *)中的*称为*在中的约束出现。自由出现：变元的非约束出现。约束变元：约束出现的变元。自由变元：自由出现的变元。【定义4.5】封闭的：一个公式A是封闭的，假设其中不含自由变元。【定义4.6】变元换名：1换名的*围是量词的指导变元,及其相应辖域中的变元，其余局部不变。2换名时最好选用辖域中未出现的变元名。变元代入：代入对自由变元进展。不能改变约束关系。解释：谓词语言的一个解释 I= (D, )包括： (1) 非空集合D，称之为论域； (2) 对应于每一个个体常元a，(a)D； (3) 对应于每一个n元函数符号f都有一个函数(f):Dn D； (4) 对应于每一个

15、n元谓词符号A都有一个n元关系(A) Dn。【定义4.7】赋值：解释I中的赋值v为每一个个体变元*指定一个值v(* D，即设 V为所个体变元的集合，则赋值v是函数 v:V D.可满足的：给定公式A，假设在*一解释中至少有一种赋值使A取值为1，则称A为可满足的。否则称A是不可满足的。等值式A B：假设AB是有效的【定义5.1】几类等值式1命题公式的推广 e.g. P(*) Q(*) P(*) Q(*)2否认深入 * P(*) *( P(*) *P(*) * ( P(*)3量词作用域的扩*与收缩设B中不含*的自由出现，则 *(A(*) B) * A(*) B *(A(*) B) * A(*) B

16、*(A(*)B) * A(*) B *(B A(*) B * A(*) *(A(*) B) * A(*) B *(A(*) B) * A(*) B *(A(*)B) * A(*) B *(B A(*) B * A(*)4量词分配等值式 *(A(*) B(*) * A(*) * B(*) *(A(*) B(*) * A(*) * B(*)5多个量词的使用 * y A(*,y) y * A(*,y) * y A(*,y) y * A(*,y)置换规则：设(A)是含A的公式, 则, 假设AB, 则(A)(B).换名规则：设A为一公式，将A中*量词辖域中个体变项的所有约束出现及相应的指导变元换成该量词

17、辖域中未曾出现过的个体变项符号，其余局部不变，设所得公式为A，则AA.前束*式：如果谓词公式A有如下形状：Q1*1Qn*nM，其中 Qi*i或者是*i，或者是*i，i=1，n，M是不含量词的公式， Q1*1Qn*n称为首标，M称为母式。【定义5.2】前束*式存在定理：对于任意谓词公式，都存在与它逻辑等价的前束*式。【定理5.1】前束*式的算法：步1. 对约束出现的变元进展必要的换名，使得约束出现的变元互不一样且不与任何自由变元同名。步2. 将所有的否认号深入到量词后面。步3. 将量词符号移至公式最外层。逻辑蕴含式A C：当且仅当AC是有效的。几类逻辑蕴涵式第一组命题逻辑推理定理的代换实例如,

18、*F(*)yG(y) *F(*) 第二组根本等值式生成的推理定理如, *F(*) *F(*), *F(*) *F(*)*F(*)*F(*), *F(*) *F(*)第三组其它常用推理定律 (1) *A(*)*B(*) *(A(*)B(*) (2) *(A(*)B(*)*A(*)*B(*) (3) *(A(*)B(*) *A(*)*B(*) (4) *(A(*)B(*) *A(*)*B(*)推理规则- 规则(US)： QUOTE 或 QUOTE *,y个体变项，c个体常项+规则(UG)： QUOTE *个体变项- 规则(ES)： QUOTE *个体变项, c个体常项+ 规则(EG)： QUOTE

19、 或 QUOTE *,y个体变项，c个体常项 QUOTE 或 QUOTE 先用ES，再用US自然推理系统NL：1. 字母表. 同一阶语言L 的字母表2. 合式公式. 同L的合式公式3. 推理规则:(1) 前提引入规则(2) 结论引入规则(3) 置换规则(4) 假言推理规则(5) 附加规则(6) 化简规则(7) 拒取式(8) 假言三段论规则(9) 析取三段论规则(10) 构造性二难推理规则(11) 合取引入规则(12) -规则(13) +规则(14) -规则(15) +规则【定义5.3】集合论：A B * ( *A *B )【定义6.1】A = B A B B A【定义6.2】A B A B A

20、 B 【定义6.3】AB * ( *A *B ) 空集：不含有任何元素的集合【定义6.4】空集是任何集合的子集。【定理6.1】幂集P(A) = * | * A 【定义6.5】如果 |A|=n，则 |P(A)|=2n全集 E：包含了所有元素的集合【定义6.6】并AB= * | *A *B交AB = * | *A *B 差相对补AB = * | *A *B【定义6.7】对称差AB = (AB)(BA) 【定义6.8】补绝对补A = EA = *|*A【定义6.9】广义并A= * | z ( zA*z )【定义6.10】广义交A = * | z ( zA *z )【定义6.11】集合恒等式1.只涉及

21、一个运算的算律：交换AB=BAAB=BAAB=BA结合(AB)C=A(BC)(AB)C=A(BC)(AB)C=A(BC)幂等AA=AAA=A2涉及两个不同运算的算律：与与分配A(BC)=(AB)(AC)A(BC)=(AB)(AC)A(BC)=(AB)(AC)吸收A(AB)=AA(AB)=A3涉及补运算的算律：D.M律A(BC)=(AB)(AC)A(BC)=(AB)(AC)(BC)=BC(BC)=BC双重否认A=A4涉及全集和空集的算律：E补元律AA=AA=E零律A=AE=E同一律A=AAE=A否认=EE=序偶有序对：由两个元素 * 和 y，按照一定的顺序组成的二元组，记作.【定义7.1】笛卡儿

22、积:设A,B为集合，A与B的笛卡儿积记作AB定义为AB = | *AyB.【定义7.2】笛卡尔积性质：A=或B=时, AB=不满足结合律A(BC) = (AB)(AC)关系：两个定义(1) 序偶的一个集合, 确定了一个二元关系R。R 中任一序偶 ,可记作 R 或 *Ry【定义7.3】(2) 笛卡尔积的子集： R AB【定义7.4】空关系:全域关系：AB 恒等关系IA= | *A【定义7.5】关系矩阵：假设A=*1, *2, , *m，B=y1, y2, , yn，R是从A到B的关系，R的关系矩阵是布尔矩阵MR = rij mn, 其中rij= 1 R. 关系图：假设A= *1, *2, , *

23、m，R是从A上的关系，R的关系图是GR=, 其中A为结点集，R为边集. 如果属于关系R，在图中就有一条从*i 到*j 的有向边. 前域(定义域) dom(R) = *|y.R值域 ran(R)=y|*.R域fld(R) = domR ranR【定义7.6】逆关系R1= | R 【定义7.7】互逆(R1)1 = R(R S)1 = R1 S1(R S)1 = R1 S1(A B)1 = BA(R - S)1 = R1 - S1复合关系RS= | y (R S) 【定义7.8】(R S) P=R (S P) Rm = RRR 设R * Y,S YZ,则 (R S)1 = S1 R1 【定理7.2】

24、R在A上的限制RA = | *Ry*A A在R下的像RA=ran(RA) 【定义7.9】自反的：假设*A，都有R, 则称 R 是自反的反自反的：假设*A，都有 R, 则称 R 是反自反的.【定义7.11】对称的：对任意*,yA,满足, 假设 R,则R反对称的：对任意*,yA,满足，假设 R且R,则*=y【定义7.12】传递的：对任意的*,y,zA, 满足:假设R且R, 则R,则称R是传递的【定义7.13】自反闭包对称、传递：设R是A上的二元关系,如果有另一个关系R满足:R是自反对称、传递的;RR;对于任何自反的关系R,假设RR, 则有RR.则称关系R为R的自反闭包. 记为 r(R)对称闭包 s

25、(R) 和传递闭包 t(R)。【定义7.14】设R为A上的关系, 则有(1) r(R)=RIA(2) s(R)=RR1(3) t(R)=RR2R3假设|A|=n，则 t(R)=RR2Rn 等价关系：设 R 为集合 A 上的一个二元关系。假设 R 是自反的, 对称的, 传递的, 则称 R 为 A 上的等价关系【定义7.15】等价类：设R为集合A上的等价关系, 对aA, 定义:aR = *|*A 且 R称之为元素a关于R的等价类。【定义7.16】给定A上的等价关系R,对于a,bA有当且仅当aR=bR【定理17.4】商集：设R是A上的等价关系，定义 A/R=aR|aA称之为A关于R的商集.【定义7.

26、17】划分：设A为非空集合, 假设A的子集族( P(A)满足:(1) (2) *y(*,y*y*y=)(3) = A则称是A的一个划分, 称中的元素为A的划分块.【定义7.18】给定集合 A 上的等价关系 R, 则商集 A/R 是 A 的一个划分.集合A的一个划分诱导出A上的一个等价关系R. R定义为R= | *,y A 且*,y在的同一分块中设R1和R2为非空集合A上的一个等价关系,则 R1 = R2当且仅当A/R1 = A/R2.偏序：设A是一个集合. 如果 A 上的二元关系 R 是自反的,反对称的和传递的, 则称R是A上的一个偏序关系. 记R为, 且称序偶 为偏序集。【定义7.19】【定

27、义7.22】全序线序：设 为偏序集, 假设对任意的*,yA满足: *y或 y*则称为全序关系. 为全序集.【定义7.21】覆盖：设为偏序集,假设*,yA, *y,*y且没有其它元素z满足*z,zy,则称y覆盖*. 记covA= |*,yA且y覆盖*【定义7.23】哈斯图：作图规则用小元圈代表元素;假设*y且*y,则将代表y的小元圈画在代表*的小元圈之上;假设covA, 则在*,y之间用直线连接。你极小元/极大元：设为偏序集, B A (1) 对bB，假设B中不存在*满足: b*且 *b则称b为B的极小元. (2) 对bB，假设B中不存在*满足: b*且 b*则称b为B的极大元.最小元/最大元：

28、设为偏序集,BA,假设有*个bB (1) 对于B中每一个元素*都有b*，则称b为B的最小元.(2) 对于B中每一个元素*都有*b，则称b为B的最大元.【定义7.24】下界/上界：设为偏序集, B A(1) 假设有aA,且对*B 满足 a*，则称a为B的下界。进一步: 设a为B的下界,假设B的所有下界y均有ya,则称a为B的下确界，记为glb B。(2) 假设有aA,且对*B 满足 *a，则称a为B的上界。进一步: 设a为B的上界,假设B的所有上界y均有ay,则称a为B的上确界，记为lub B。【定义7.25】函数：设*,Y为两个集合,f*Y, 假设对*,!(唯一的)yY,满足: f,则称f为函

29、数.记为:f:*Y定义域: domf=*值域: ranf (有时记为f(*)=f(*)|*【定义8.1】函数相等：设f和g都是从A到B的函数, 假设对任意*A,有f(*)=g(*),则称f和g相等.记为f=g【定义8.2】函数的个数：设f:AB,|A|=m, |B|=n.记 BA=f|f: AB, 则| BA |= nm满射(到上映射)：设 f: * Y, 假设 ranf = Y, 则称 f 为满射的.入射单射(一对一映射)：设f: *Y, 对 *1, *2*, 满足:假设 *1 *2, 则 f(*1) f(*2),称 f 为入射的.双射(一一对应映射)：设f:*Y, 假设f既是满射的, 又是

30、入射的. 则称f是双射的.【定义8.6】常函数:设f:AB, 如果存在cB使得对所有的*A都有 f(*)=c, 则称f:AB是常函数.恒等函数:称 A上的恒等关系IA为A上的恒等函数, 对所有的*A都有IA(*)=*.单调递增:设, 为偏序集，f:AB，如果对任意的*1, *2A, *1*2, 就有f(*1)f(*2), 则称 f 为单调递增的；严格单调递增:如果对任意的*1, *2A, *1*2, 就有f(*1) f(*2), 则称 f 为严格单调递增的. 类似的也可以定义单调递减和严格单调递减的函数特征函数：设A为集合, 对于任意的AA, A的特征函数A :A0,1定义为A(a)=1, a

31、A;A(a)=0, aAA自然映射：设R是A上的等价关系, 令g:AA/R；g(a)=a, aA称 g 是从 A 到商集 A/R 的自然映射【定义8.7】复合函数：设 f:*Y,g:YZ, 定义: f g = |*且zZ且可找到yY使y=f(*),z=g(y)称f g为f与 g 的复合函数.设f:AB, g:BC(1) 如果 f:AB, g:BC是满射的, 则 fg:AC也是满射的(2) 如果 f:AB, g:BC是单射的, 则 fg:AC也是单射的(3) 如果 f:AB, g:BC是双射的, 则 fg:AC也是双射的【定理8.2】反函数逆函数：设f:*Y是一个双射函数，则f -1是Y*的双射

32、函数. 称f -1为f的反函数.互逆 (f -1 )-1=f设f:AB是双射的, 则f1f = IB, f f 1 = IA 【定理8.5】基数：用来衡量集合大小的一个概念. 对于有限集合集来说, 集合的基数就是其中所含元素的个数.等势的：设A, B是集合, 如果存在着从A到B的双射函数, 就称A和B是等势的, 记作AB. 如果A不与B等势, 则记作AB.注：通常将A的基数记为 |A|.【定义8.8】N Z Q NN任何实数区间都与实数集合R等势0,1NR康托定理N R；对任意集合A都有AP(A).【定义8.7】有限集(有穷集)/无限集 (无穷集)：设A为一个集合. 假设存在*个自然数n, 使

33、得A与集合0,1,n-1等势, 则称A是有限的. 假设集合A不是有限的, 则称A是无限的.【定义8.11】：实数集R的基数记作, 即cardR=【定义8.12】可数集(可列集)：设A为集合，假设cardA0，则称A为可数集或可列集。【定义8.14】与自然数集N等势的任意集合称为可数的.其基数为0结论： (1) A为可数的当且仅当可排列成A=a1,a2, ,an,的形式.(2) 任一无限集必含有可数子集.(3) 可数集的任何无限子集是可数的.(4) 可数个两两不相交的可数集合的并集,仍是一个可数集.(5) NN是可数集.(6) 有理数的全体组成的集合是可数集.(7) 全体实数构成的集合R是不可数

34、的.基数的常识：对于有穷集合A, 基数是其元素个数n，|A| = n; 没有最大的基数。将的基数按从小到大的顺序排列就得到： 0, 1, 2, , n, , 0, , 代数构造运算：对于集合 A，f 是从An到 A 的函数，称 f 为集合A上的一个n元运算。【定义9.1】交换律：，假设*，yA，有*y=y*，称*在A上是可交换的。【定义9.3】结合律：，假设*，y，zA，有*y*z=*y*z，称*在A上是可结合的。【定义9.4】幂等律：A，*，假设*A，*=* 则称满足幂等律。【定义9.5】分配律：设，假设*，y，zA有: *(yz)=*y*z ; (yz)*=(y*)(z*)称运算*对是可分

35、配的。【定义9.6】吸收律：设,是定义在集合A上的两个可交换二元运算，假设对*,y A,都有:*(*y) = * ； *(* y) = *则称运算和满足吸收律.【定义9.7】单位元幺元:设*是A上二元运算， el, er,eA左幺元：假设*A，有el*=*，称el为运算*的左幺元；右幺元：假设*A，有*er=*，称er为运算*的右幺元；假设e既是左幺元又是右幺元，称e为运算*的幺元【定义9.8】设*是A上的二元运算，具有左幺元el，右幺元er，则el=er=e 【定理9.1】零元:设*是A上二元运算，l, r, A左零元：假设*A，有l*=l，称l为运算*的左零元；右零元：假设*A，有*r=r

36、，称r为运算*的右零元；假设既是左零元又是右零元，称为运算*的零元。【定义9.9】设*是A上的二元运算，具有左零元l，右零元r，则l= r= 【定理9.2】逆元：设*是A上的二元运算，e是运算*的幺元，假设*y=e那对于运算*，*是y的左逆元，y是*的右逆元存在逆元(【定义9.10】对于可结合运算，如果元素*有左逆元，右逆元r，则l=r=*【定理9.4】消去律：，假设*，y，zA，有 (1) 假设 *y = *z且 * ,则y=z；(左消去律) (2) 假设 y* = z*且 * ,则y=z；右消去律则称*满足消去律。【定义9.11】代数系统：设A为非空集合，为A上运算的集合,称为一个代数系统

37、.【定义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=和V

38、2=是同类型的代数系统，和为二元运算，在集合AB上如下定义二元运算，,AB，有= 称V=为V1与V2的积代数，记作V1V2. 这时也称V1和V2为V的因子代数. 【定义9.15】设V1=和V2=是同类型的代数系统，V1V2=是它们的积代数. (1) 如果和运算是可交换可结合、幂等的，那幺运算也是可交换可结合、幂等的(2) 如果e1 和e21和2分别为和运算的单位元零元，那幺也是运算的单位元零元(3) 如果* 和y 分别为和运算的可逆元素，那幺也是运算的可逆元素，其逆元就是 【定理9.5】同态:设V1=和V2=是同类型的代数系统，f:AB，对*, yA 有f(*y) = f(*)f(y), 则称

39、f 是V1到V2的同态映射，简称同态(1) f 如果是单射，则称为单同态。(2) 如果是满射，则称为满同态，这时称V2是V1的同态像，记作V1V2。(3) 如果是双射，则称为同构，也称代数系统V1同构于V2，记作V1V2 。(4) 如果V1=V2，则称作自同态。【定义9.16】半群：设V=是代数系统，为二元运算，如果运算是可结合的，则称V为半群。独异点：设V=是半群，假设eS是关于运算的单位元，则称V是含幺半群，也叫做独异点。有时也将独异点V 记作 V=. 群设V=是独异点，e G关于运算的单位元，假设aG，a1G，则称V是群(Group). 通常将群记作G. 【定义10.1】群的阶数：设是一

40、个群有限群：如果G是有限集，则称为有限群阶数：|G| 为该有限群的阶数；无限群：如果G是无限集，则称为无限群。平凡群：阶数为1即只含单位元的群称为平凡群【定义10.2】群的性质：设是一个群。1非平凡群中不可能有零元.2对于a,b G, 必存在唯一的* G,使得a * =b.3对于a,b,c G假设: ab = ac或ba = ca则必有b=c (消去律)。4运算表中的每一行或每一列都是一个置换。5除幺元e外,不可能有任何别的幂等元。元素的幂设G是群，aG，nZ，则a 的 n次幂【定义10.3】元素的阶：设G是群，aG，使得等式ak=e 成立的最小正整数k 称为元素a 的阶，记作|a|=k，称a

41、 为k 阶元。假设不存在这样的正整数k，则称a 为无限阶元。【定义10.4】幂运算性质：(1) aG，(a1)1=a(2) a,bG，(ab)1=b1a1(3) aG，anam = an+m，n, mZ(4) aG，(an)m = anm，n, mZ (5) 假设G为交换群，则 (ab)n = anbn.【定理10.1】元素的阶的性质：G为群，aG且 |a| = r. 设k是整数，则(1) ak = e当且仅当r | k(r整除k)(2 )|a1| = |a|【定理10.3】子群：设G 是群，H 是G 的非空子集，如果H关于G中的运算构成群，则称H是G 的子群, 记作HG。真子群：假设H是G

42、的子群，且HG，则称H是G的真子群，记作HG.平凡子群：对任何群G都存在子群. G和e都是G 的子群，称为G 的平凡子群.【定义10.5】子群判定定理设G为群，H是G的非空子集，则H是G的子群当且仅当(1) a,bH有abH；(2) aH有a1H。【定理10.4】子群判定定理二：设G为群，H是G的非空子集. H是G的子群当且仅当a,bH有ab1H.【定理10.5】子群判定定理三：设G为群，H是G的非空有穷子集，则H是G的子群当且仅当a,bH有abH. 【定理10.6】生成子群：设G为群，aG，令H=ak| kZ，则H是G的子群，称为由a 生成的子群，记作.陪集设是群的一个子群,a G则:左陪集

43、aH := aH，由a所确定的H在G中的左陪集.右陪集Ha:=Ha陪集是左陪集与右陪集的统称.【定义10.6】陪集性质：设H是群G的子群，则He = HaG 有aHaa,bG有：aHb ab1H Ha=Hb在G上定义二元关系R：a,bG, R ab1H则R是G上的等价关系，且aR = Ha.|Ha|=|H|【定理10.7】【定理10.8】拉格朗日定理：设G是有限群，H是G的子群，则|G| = |H|G:H 其中G:H 是H在G中的不同右陪集(或左陪集) 数，称为H在G 中的指数.【定理10.10】推论：1设G是n阶群，则aG，|a|是n的因子，且an= e. 2对阶为素数的群G，必存在aG使得

44、G = .阿贝尔群交换群：假设群G中的运算是可交换的，则称G为交换群或阿贝尔群。循环群：设G是群，假设存在aG使得G=ak| kZ 则称G是循环群，记作G=，称a 为G 的生成元.n 阶循环群:设G=是循环群，假设a是n 阶元，则 G= a0=e, a1, a2, , an1 无限循环群:假设a 是无限阶元，则 G= a0=e, a1, a2, 【定义10.7】循环群的生成元:设G=是循环群(1) 假设G是无限循环群，则G只有两个生成元，即a和a1.(2)假设G是n阶循环群，则G含有(n)个生成元. 对于任何小于n且与n 互质的数r0,1,n-1, ar是G的生成元.【定理10.11】循环群的

45、子群：(1)设G=是循环群，则G的子群仍是循环群；(2) 假设G=是无限循环群，则G的子群除e以外都是无限循环群；(3) 假设G=是n阶循环群，则对n的每个正因子d，G恰好含有一个d 阶子群。【定理10.12】环：设是代数系统，+和是二元运算. 如果满足以下条件:(1) 构成交换群；(2) 构成半群；(3) 运算关于+运算适合分配律，则称是一个环. 【定义10.11】环的运算性质：设是环，则(1) aR，a0 = 0a = 0(2) a,bR，(a)b = a(b) = ab(3) a,b,cR，a(bc) = abac， (bc)a = baca(4) a1,a2,.,an,b1,b2,.,

46、bmR (n,m2) QUOTE 【定理10.14】设是环交换环：假设环中乘法 适合交换律，则称R是交换环；含幺环：假设环中乘法 存在单位元，则称R是含幺环；无零因子环：假设a,bR，ab=0 a=0b=0，则称R是无零因子环。整环：设是一个代数系统,假设满足:(1) 是阿贝尔群；(2) 是可交换独异点，且无零因子，即对a,bR, a0,b0 则a b0；(3) 运算对+是可分配的，则称是整环域：设是一个代数系统,假设满足:(1) 是阿贝尔群；(2) 是阿贝尔群；(3) 运算对+是可分配的，则称是域。【定义10.12】格：设是偏序集，如果*,yS，*,y都有最小上界和最大下界，则称S关于偏序作

47、成一个格【定义11.1】格的代数系统定义：设是代数系统, 和是二元运算, 如果和满足交换律、结合律和吸收律, 则构成格【定义11.3】对偶命题：设f 是含有格中元素以及符号 =, , ,和的命题. 令f*是将f 中的替换成,替换成,替换成,替换成所得到的命题. 称f* 为f 的对偶命题【定义11.2】格的对偶原理：设 f 是含有格中元素以及符号=,和等的命题. 假设 f 对一切格为真, 则 f 的对偶命题 f*也对一切格为真.格的性质：设是格, 则运算和适合交换律、结合律、幂等律和吸收律, 即(1) a,bL 有ab = ba, ab = ba(2) a,b,cL 有 (ab)c = a(bc

48、), (ab)c = a(bc)(3) aL 有aa = a, aa = a(4) a,bL 有a(ab) = a, a(ab) = a 【定理11.1】格的序与运算性质：设L是格, 则a,bL有a bab = aab = b 【定理11.3】格的保序性质：设L是格, a,b,c,dL，假设a b 且c d, 则ac bd, acbd【定理11.4】子格：设是格, S是L的非空子集, 假设S关于L中的运算和仍构成格, 则称S是L的子格【定义11.4】分配格：设是格, 假设a,b,cL,有a(bc) = (ab)(ac) a(bc) = (ab)(ac) 则称L为分配格.【定义11.5】分配格的

49、判别：设L是格, 则L是分配格当且仅当L不含有与钻石格或五角格同构的子格【定理11.5】全下界：设L是格,假设存在aL使得*L有 a *, 则称a为L的全下界；全上界：设L是格,假设存在bL使得*L有 * b, 则称b为L的全上界。【定义11.6】有界格：设L是格，假设L存在全下界和全上界, 则称L 为有界格，一般将有界格L记为.【定义11.7】有界格的性质：设是有界格,则aL有a0 = 0,a0 = a,a1 = a, a1=1补元：设是有界格, aL, 假设存在bL 使得ab = 0 和ab = 1成立, 则称b是a的补元【定义11.8】有界分配格的补元惟一性定理：设是有界分配格. 假设L

50、中元素 a 存在补元, 则存在惟一的补元.【定理11.6】有补格 :设是有界格,假设L中所有元素都有补元存在, 则称L为有补格.【定义11.9】布尔格布尔代数：如果一个格是有补分配格, 则称它为布尔格或布尔代数. 布尔代数标记为, 为求补运算. 【定义11.10】布尔代数的代数系统定义：设是代数系统, 和是二元运算. 假设和运算满足：(1) 交换律, 即a,bB有 ab = ba, ab = ba (2) 分配律, 即a,b,cB有a(bc) = (ab)(ac), a(bc) = (ab) (ac)(3) 同一律, 即存在0,1B, 使得aB有a 1 = a, a0 = a(4) 补元律,

51、即aB, 存在 aB 使得 a a = 0, aa = 1 则称 是一个布尔代数.【定义11.11】布尔代数的性质：设是布尔代数, 则(1) aB, (a) = a .(2) a,bB, (ab) = ab, (ab) = ab德摩根律【定理11.7】原子：设 L 是格, 0L, aL假设bL有 0 b a b = a, 则称 a 是 L 中的原子【定义11.12】有限布尔代数的表示定理：设B是有限布尔代数, A是B的全体原子构成的集合, 则B同构于A的幂集代数P(A).【定理11.8】推论1：任何有限布尔代数的基数为2n, nN.推论2：任何等势的有限布尔代数都是同构的图论无序积：AB=(*

52、,y) | *AyB无向图G = , 其中(1) V 为顶点集，元素称为顶点；(2) E为VV 的多重集，其元素称为无向边，简称边。【定义14.1】有向图D=, 只需注意E是VV 的多重子集【定义14.2】n阶图：顶点个数为n.零图：边的个数为0. n 阶零图记为Nn平凡图：1阶零图N1空图：标定图与非标定图：依据顶点和边是否命名标识。有向图的基图：有向边改为无向边后的图。顶点与边的关联关系ek=(vi , vj) 关联：ek与vi , vj关联关联次数：0(不关联)，1(vi vj )， 2(vi =vj ) 环：与同一顶点关联次数为2的边；孤立点：不与任何边关联的顶点。顶点相邻：两个顶点之

53、间有边。边相邻：两条边有公共端点。平行边：关联的端点一样的两条边有向图中方向一样。vV(G) (G为无向图) v的邻域：v的闭邻域：v 的关联集：vV(D) (D为有向图)v的后继元集：v的先驱元集：v的邻域：v多重图：含平行边的图；简单图：即不含平行边又不含环的图。【定义14.3】度度数：设G=为无向图, vV, d(v)v的度数, 简称度设D=为有向图, vV,出度d+(v)v入度d(v)v作为边的终点的次数度度数d(v)d+(v)+ d(v)最大度(G)=ma*d(v)|vV(G)最小度(G)= mind(v)|vV(G)+(D)=ma*d+(v)|vV(D)+(D)=mind+(v)|

54、vV(D)(D)=ma*d-(v)|vV(D)(D)=mind-(v)|vV(D)(D)=ma*d(v)|vV(D)(D)=mind(v)|vV(G)奇顶点度：度为奇数的顶点偶度顶点：度为偶数的顶点【定义14.4】握手定理：设G=为任意无向图，V=v1,v2,vn, |E|=m, 则设D=为任意有向图，V=v1,v2,vn, |E|=m, 则【定理14.1】【定理14.2】推论：任何图 (无向或有向) 中，奇度顶点的个数是偶数.度数列：V=v1, v2, , vn为无向图G的顶点集，称d(v1), d(v2), , d(vn)为G的度数列V=v1, v2, , vn为有向图D的顶点集度数列：d

55、(v1), d(v2), , d(vn)出度列：d+(v1), d+(v2), , d+(vn)入度列：d(v1), d(v2), , d(vn) 非负整数列d=(d1, d2, , dn)V=v1,v2,vnnG,使得d(vi)=di，则称d是可图化的。特别的，假设得到的图是简单图，则称d是可简单图化的。非负整数列d=(d1, d2, , dn)是可图化的当且仅当为偶数.【定理14.3】设G为任意n阶无向简单图，则(G) n -1.【定理14.4】图的同构：设G1=, G2=为两个无向图(两个有向图)，假设存在双射函数f :V1V2，对于vi, vjV1, (vi,vj)E1 当且仅当 (f

56、(vi), f(vj)E2 E1 当且仅当 E2 )并且, (vi,vj)与 (f(vi), f(vj)的重数一样，则称G1与G2是同构的，记作G1G2.【定义14.5】n (n1) 阶无向完全图每个顶点与其余顶点均相邻的无向简单图，记作Kn.边数n (n1)阶有向完全图每对顶点之间均有两条方向相反的有向边的有向简单图.边数n (n1) 阶竞赛图基图为Kn的有向简单图.【定义14.6】边数n 阶k正则图：=k的无向简单图。【定义14.7】边数G=, G=子图：VV 且EE ,则称G为G的子图，记为GG ，称G为G的母图;生成子图：假设GG且V=V，则称G为G的生成子图；真子图：假设VV或EE，

57、称G为G的真子图；导出子图：VVV且V的导出子图，记作GV；EEE且E的导出子图，记作GE.【定义14.8】补图：设G=为n阶无向简单图，以V为顶点集，以所有使G成为完全图Kn的添加边组成的集合为边集的图，称为G的补图，记作.假设G , 则称G是自补图【定义14.9】Gv从G中将v及关联的边去掉GV从G中删除V中所有的顶点Ge将e从G中去掉GE删除E中所有边【定义14.10】通路与回路：给定图G=无向或有向的，G中顶点与边的交替序列 = v0e1v1e2elvl称为从v0到vl的通路，其中vi1, vi 是 ei 的端点.；假设 v0=vl，为回路。中的边数称为通路的长度. 简单通路与简单回路

58、：所有边各异。初级通路(路径)与初级回路(圈)：中所有顶点各异v0=vl 除外，所有边也各异复杂通路与复杂回路：有边重复出现【定义14.11】在n 阶图G中，假设从顶点vi 到vjvivj存在通路，则从vi 到vj 存在长度小于或等于n1 的通路.【定理14.5】推论：在n 阶图G中，假设从顶点vi到vjvivj存在通路，则从vi到vj 存在长度小于或等于n1的初级通路路径在一个n 阶图G中，假设存在vi 到自身的回路，则一定存在vi 到自身长度小于或等于n 的回路.【定理14.6】推论：在一个n 阶图G中，假设存在vi 到自身的简单回路，则一定存在长度小于或等于n 的初级回路.顶点的连通性：

59、G=为无向图，假设vi 与vj 之间有通路，则称vi 与vj是连通的，记为vivj 假设u,vV，uv，则称G是连通的；【定义14.12】连通分支：V/R=V1,V2,Vk，称GV1, GV2, ,GVk为连通分支，其个数称为连通分支数，记为p(G)【定义14.13】短程线uv：，u与v之间长度最短的通路距离d(u,v)：短程线的长度【定义14.14】d(u,v)0, uv时d(u,v)=d(u,v)=d(v,u)d(u,v)+d(v,w)d(u,w)G=, VV点割集p(GV)p(G)，且对任意VV均有p(GV)=p(G)V为点割集割点v为点割集，则v为割点【定义14.15】G=, EE边割

60、集p(GE)p(G)且有极小性则E是边割集割边桥e为边割集e是割边桥【定义14.16】G为连通非完全图点连通度(G) = min |V |V 为点割集 规定(Kn) = n1;假设G非连通，(G) = 0k-连通图：假设(G)k，则称G为k-连通图【定义14.17】设G为连通图边连通度(G) = min|E|E为边割集规定：假设G非连通，则(G) = 0r 边-连通图：假设(G)r，则称G是r 边-连通图【定义14.18】, , 之间的关系：(G)(G)(G)【定理14.7】D=为有向图可达vi vj：存在从vi 到vj 有通路相互可达vi vj： vi vjvj vi【定义14.19】D=为