离散数学知识点

离散数学知识点离散数学知识点/离散数学知识点说明： 定义：红色表示。 定理性质：橙色表示。 公式：蓝色表示。 算法:绿色表示 页码：灰色表示数理逻辑：命题公式：命题，联结词(，，，，)，合式公式，子公式公式的真值：赋值，求值函数，真值表，等值式，重言式，矛盾式范式：析取范式，极小项，主析取范式，合取范式，极大项，主合取范式联结词的完备集：真值函数，异或，条件否定，与非，或非，联结词完备集推理理论：重言蕴含式，有效结论，P规则，T规则，规则，推理谓词与量词:谓词，个体词，论域，全称量词，存在量词项与公式:项，原子公式，合式公式，自由变元，约束变元，辖域，换名，代入公式语义:解释，赋值，有效的，可满足的，不可满足的前束范式:前束范式推理理论:逻辑蕴含式，有效结论，-规则（），+规则（），-规则()，+规则(),推理集合论：集合:集合,外延性原理,,,,空集,全集,幂集,文氏图,交,并,差,补,对称差关系:序偶,笛卡尔积,关系,,,关系图,空关系,全域关系,恒等关系关系性质与闭包:自反的,反自反的,对称的,反对称的,传递的,自反闭包r(R),对称闭包s(R),传递闭包t(R)等价关系:等价关系,等价类,商集,划分偏序关系:偏序,哈斯图,全序(线序),极大元/极小元,最大元/最小元,上界/下界函数:函数,常函数,恒等函数,满射,入射,双射，反函数,复合函数集合基数:基数,等势,有限集/无限集,可数集,不可数集代数结构：运算与其性质：运算，封闭的,可交换的,可结合的,可分配的,吸收律,幂等的，幺元,零元,逆元代数系统：代数系统，子代数，积代数，同态，同构。群与子群：半群,子半群,元素的幂，独异点，群，群的阶数，子群,平凡子群，陪集，拉格朗日（）定理阿贝尔群和循环群：阿贝尔群(交换群)，循环群,生成元环与域：环，交换环，含幺环，整环，域格与布尔代数：格，对偶原理，子格，分配格，有界格，有补格，布尔代数，有限布尔代数的表示定理图论：图的基本概念：无向图、有向图、关联与相邻、简单图、完全图、正则图、子图、补图，握手定理，图的同构图的连通性:通路，回路，简单通路，简单回路（迹）初级通路（路径），初级回路（圈），点连通，连通图，点割集，割点，边割集，割边，点连通度，边连通度，弱连通图，单向连通图，强连通图，二部图（二分图）图的矩阵表示：关联矩阵，邻接矩阵，可达矩阵欧拉图与哈密顿图：欧拉通路、欧拉回路、欧拉图、半欧拉图，哈密顿通路、哈密顿回路、哈密顿图、半哈密顿图无向树与根树：无向树，生成树，最小生成树，，根树，m叉树，最优二叉树，算法平面图:平面图，面，欧拉公式，定理数理逻辑：命题：具有确定真值的陈述句。否定词符号：设p是一个命题，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或者都是真的，或者都是假的。【定义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，vA矛盾式（永假式）:任意赋值v，有vA【定义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中的Ｘ（可以是全部或部分X）用Y来置换，所得到的公式B，则AB。文字:设A（命题变元集）,则A和A都称为命题符号A的文字，其中前者称为正文字，后者称为负文字。【定义2.2】析取范式：形如A1A2…(n1)的公式称为析取范式，其中(1,…)是由文字组成的合取范式。合取范式：形为A1A2…(n1)的公式称为合取范式，其中A1,…都是由文字组成的析取式。【定义2.3】极小项：文字的合取式称为极小项，其中公式中每个命题符号的文字都在该合取式中出现一次。极大项：文字的析取式称为极大项，其中公式中每个命题符号的文字都在该合取式中出现一次。【定义2.4】主析取范式：给定的命题公式的主析取范式是一个与之等价的公式，后者由极小项的析取组成。主合取范式：给定的命题公式的主合取范式是一个与之等价的公式，后者由极大项的合取组成。【定义2.5】公式的真值表中真值为F的指派所对应的极大项的合取，即为此公式的主合取范式。真值函数：称F:{0,1}n{0,1}为n元真值函数.【定义2.6】联结词的完备集：设C是联结词的集合，若对于任意一个合式公式均存在一个与之等价的公式，而后者只含有C中的联结词，则称C是联结词的完备集。【定义2.7】{，，，，}，{，，},{，}，{，}，{，}是联结词的完备集。【定理2.6】c异或PQ： (PQ)c条件否定PQ：(PQ)与非PQ： (PQ)或非PQ： (PQ)【定义2.8】{},{↓}都是联结词的完备集【定理2.7】重言蕴含式：当且仅当PQ是一个重言式时，称P重言蕴含Q，记为PQ。有效结论：设A、C是两个命题公式，若AC，称C是A的有效结论。【定义3.1】推理定律——重言蕴涵式 1.A(AB) 附加律2.(AB)A 化简律3.(AB)AB 假言推理4.(AB)BA 拒取式5.(AB)BA 析取三段论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). (2)A(I)中符号构造的合式公式集，记作E(I). (3)E(I)中一些特殊的公式组成的公理集，记作(I). (4)推理规则集，记作R(I).记<A(I)(I)(I)(I)>,其中<A(I)(I)>是I的形式语言系统,<(I)(I)>是I的形式演算系统.自然推理系统:无公理,即(I)=公理推理系统:推出的结论是系统中的重言式,称作定理【定义3.2】P规则：在推导过程中,可以随时添加前提。T规则：在推导过程中,可以引入公式S，它是由其前题的一个或多个公式借助重言、蕴含而得到的。推理（证明）：从前提A1,A2,,到结论B的推理是一个公式序列C1,C2,,.其中(1il)是某个,或者可由序列中前面的公式应用推理规则得到,并且。【定义3.3】规则(演绎定理)：若{R}S，则RS,其中为命题公式的集合。个体词：用于表示命题中主语部分的符号或符号串。个体常元表示确指个体。个体变元表示不确指个体。个体域:个体变元的取值范围，常用D表示。量词：限定个体数量特性的词。全称量词：对所有的存在量词：有些谓词语言：用符号串表示个体、谓词、量词和命题 个体变元符号：x，y，z，… 个体常元符号：a，b，c，… 函数符号：f，g，… 谓词符号：P，Q，R，… 命题常元符号：， 量词符号：， 连接词符号：,,,, 辅助符号：）,（ 【定义4.1】项:(1)个体常元和变元是项；(2)若f是n元函数符号，t1,…,是项，则f(t1,…,)是项；(3)仅仅有限次使用(1)，(2)产生的符号串是项。【定义4.2】原子公式:若P是一个元谓词符号，t1,…是项,则P(t1,…)是原子公式。【定义4.3】合式公式：(1)原子公式是公式；(2)若A是合式公式，则(A)是合式公式；(3)若A，B是公式，则(AB)，(AB)，AB)，(AB)是公式；(4)若A是公式，x是变元，则，是公式；(5)仅仅有限次使用１～４得到的符号串才是合式公式。【定义4.4】设公式的一个子公式为xA或xA。则称：指导变元：x是或的指导变元。辖域：A是相应量词的辖域。约束出现：辖域中x的一切出现，以与(x)中的x称为x在中的约束出现。自由出现：变元的非约束出现。约束变元：约束出现的变元。自由变元：自由出现的变元。【定义4.5】封闭的：一个公式A是封闭的，若其中不含自由变元。【定义4.6】变元换名：（1）换名的范围是量词的指导变元,与其相应辖域中的变元，其余部分不变。（2）换名时最好选用辖域中未出现的变元名。变元代入：代入对自由变元进行。不能改变约束关系。解释：谓词语言的一个解释(D,)包括：(1)非空集合D，称之为论域；(2)对应于每一个个体常元a，(a)D；(3)对应于每一个n元函数符号f都有一个函数(f)D；(4)对应于每一个n元谓词符号A都有一个n元关系(A)。【定义4.7】赋值：解释I中的赋值v为每一个个体变元x指定一个值v(x）D，即设V为所个体变元的集合，则赋值v是函数D.可满足的：给定公式A，若在某一解释中至少有一种赋值使A取值为1，则称A为可满足的。否则称A是不可满足的。等值式AB：若AB是有效的【定义5.1】几类等值式（1）命题公式的推广.P(x)Q(x)P(x)Q(x)（2）否定深入xP(x)x(P(x))(x)x(P(x))（3）量词作用域的扩张与收缩 设B中不含x的自由出现，则x(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(BA(x))BxA(x)x(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(BA(x))BxA(x)（4）量词分配等值式x(A(x)B(x))xA(x)xB(x) x(A(x)B(x))xA(x)xB(x)（5）多个量词的使用 xyA()yxA() xyA()yxA()置换规则：设(A)是含A的公式,那么,若AB,则(A)(B).换名规则：设A为一公式，将A中某量词辖域中个体变项的所有约束出现与相应的指导变元换成该量词辖域中未曾出现过的个体变项符号，其余部分不变，设所得公式为A，则AA.前束范式：如果谓词公式A有如下形状：Q1x1…，其中或者是，或者是，1，…，n，M是不含量词的公式，Q1x1…称为首标，M称为母式。【定义5.2】前束范式存在定理：对于任意谓词公式，都存在与它逻辑等价的前束范式。【定理5.1】前束范式的算法：步1.对约束出现的变元进行必要的换名，使得约束出现的变元互不相同且不与任何自由变元同名。步2.将所有的否定号深入到量词后面。 步3.将量词符号移至公式最外层。逻辑蕴含式AC：当且仅当AC是有效的。几类逻辑蕴涵式 第一组命题逻辑推理定理的代换实例 如,(x)(y)(x)第二组基本等值式生成的推理定理 如,(x)(x),(x)(x)(x)xF(x),xF(x)(x)第三组其它常用推理定律 (1)(x)(x)x(A(x)B(x)) (2)x(A(x)B(x))(x)(x) (3)x(A(x)B(x))(x)(x) (4)x(A(x)B(x))(x)(x)推理规则 -规则()：∀xAx∴Ay或∀ +规则()：Ax∴∀xAx -规则()：∴∃xAx∴Ac x +规则()：Ay∴∃xAx或B Ac∴∃ 先用，再用自然推理系统NL：1.字母表.同一阶语言L的字母表2.合式公式.同L的合式公式3.推理规则:(1)前提引入规则 (2)结论引入规则(3)置换规则(4)假言推理规则(5)附加规则(6)化简规则(7)拒取式(8)假言三段论规则(9)析取三段论规则(10)构造性二难推理规则(11)合取引入规则(12)-规则(13)+规则(14)-规则(15)+规则 【定义5.3】集合论：ABx(xAxB)【定义6.1】A=BABBA 【定义6.2】ABABAB 【定义6.3】A⊈Bx(xAxB)空集：不含有任何元素的集合【定义6.4】空集是任何集合的子集。【定理6.1】幂集P(A)={x|xA}【定义6.5】如果，则(A)2n全集E：包含了所有元素的集合【定义6.6】并AB={x|xAxB}交AB={x|xAxB}差（相对补）AB={x|xAxB}【定义6.7】对称差AB=(AB)(BA)【定义6.8】补（绝对补）A=EA={A}【定义6.9】广义并A={x|z(zAxz)}【定义6.10】广义交A={x|z(zAxz)}【定义6.11】集合恒等式1.只涉与一个运算的算律：交换AAAAAA结合(AB)(BC)(AB)(BC)(AB)(BC)幂等AA2．涉与两个不同运算的算律：与与分配A(BC)=(AB)(AC)A(BC)=(AB)(AC)A(BC)=(AB)(AC)吸收A(AB)A(AB)3．涉与补运算的算律：律A(BC)=(AB)(AC)A(BC)=(AB)(AC)(BC)=BC(BC)=BC双重否定4．涉与全集和空集的算律：E补元律AA零律A=A同一律AA否定序偶（有序对）：由两个元素x和y，按照一定的顺序组成的二元组，记作<>.【定义7.1】笛卡儿积:设为集合，A与B的笛卡儿积记作AB定义为AB={<>|xAyB}.【定义7.2】笛卡尔积性质：或时,A“”不满足结合律A(BC)=(AB)(AC)关系：（两个定义）(1)序偶的一个集合,确定了一个二元关系R。R中任一序偶<>,可记作<x,y>R或【定义7.3】(2)笛卡尔积的子集：RAB【定义7.4】空关系:全域关系：A×B恒等关系={<>|x∈A} 【定义7.5】关系矩阵：若{x1,x2,…,}，{y1,y2,…,}，R是从A到B的关系，R的关系矩阵是布尔矩阵=[]mn,其中=1<,>R.关系图：若{x1,x2,…,}，R是从A上的关系，R的关系图是<A,R>,其中A为结点集，R为边集.如果<>属于关系R，在图中就有一条从到的有向边.前域(定义域)(R)={y.<>R} 值域(R)={x.<>R}域(R)= 【定义7.6】逆关系R1={<y,x>|<x,y>R} 【定义7.7】互逆(R1)1=R(RS)1=R1S1(RS)1=R1S1(AB)1=BA(R-S)1=R1-S1复合关系RS={<x,z>|y(<x,y>R<y,z>S)}【定义7.8】(RS)(SP)=RR…R设RXYZ,则(RS)1=S1R1【定理7.2】R在A上的限制R↾A={<>|∧x∈A} A在R下的像R[A](R↾A) 【定义7.9】自反的：若x∈A，都有<>R,则称R是自反的反自反的：若x∈A，都有<>R,则称R是反自反的.【定义7.11】对称的：对任意A,满足,若<>R,则<>R反对称的：对任意A,满足，若<>R且<>R,则【定义7.12】传递的：对任意的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)∪(2)s(R)∪R1(3)t(R)∪R2∪R3∪…（若，则t(R)∪R2∪…∪）等价关系：设R为集合A上的一个二元关系。若R是自反的,对称的,传递的,则称R为A上的等价关系【定义7.15】等价类：设R为集合A上的等价关系,对aA,定义:[a]R={A且<>R}称之为元素a关于R的等价类。【定义7.16】给定A上的等价关系R,对于A有<>当且仅当[a][b]R【定理17.4】商集：设R是A上的等价关系，定义{[a]A}称之为A关于R的商集.【定义7.17】划分：设A为非空集合,若A的子集族π(πP(A))满足: (1)π (2)xy(π∧x≠yx∩) (3)∪π=A则称π是A的一个划分,称π中的元素为A的划分块.【定义7.18】给定集合A上的等价关系R,则商集是A的一个划分.集合A的一个划分π诱导出A上的一个等价关系R.R定义为{<>|A且在π的同一分块中}设R1和R2为非空集合A上的一个等价关系,则R1=R2当且仅当1=2.偏序：设A是一个集合.如果A上的二元关系R是自反的,反对称的和传递的,则称R是A上的一个偏序关系.记R为“”,且称序偶<A,>为偏序集。【定义7.19】【定义7.22】全序（线序）：设<A,>为偏序集,若对任意的A满足:xy或yx则称为全序关系.<A,>为全序集.【定义7.21】覆盖：设<A,>为偏序集,若A,xy且没有其它元素z满足xy,则称y覆盖x.记{<>A且y覆盖x}【定义7.23】哈斯图：作图规则用小元圈代表元素;若xy且xy,则将代表y的小元圈画在代表x的小元圈之上;若<>,则在之间用直线连接。你极小元/极大元：设<A,>为偏序集,BA(1)对bB，若B中不存在x满足:bx且xb则称b为B的极小元.(2)对bB，若B中不存在x满足:bx且bx则称b为B的极大元.最小元/最大元：设<A,>为偏序集A,若有某个bB(1)对于B中每一个元素x都有bx，则称b为B的最小元.(2)对于B中每一个元素x都有xb，则称b为B的最大元.【定义7.24】下界/上界：设<A,>为偏序集,BA (1)若有aA,且对xB满足ax，则称a为B的下界。进一步:设a为B的下界,若B的所有下界y均有ya,则称a为B的下确界，记为B。 (2)若有aA,且对xB满足xa，则称a为B的上界。进一步:设a为B的上界,若B的所有上界y均有ay,则称a为B的上确界，记为B。【定义7.25】函数：设为两个集合XY,若对xX,!(唯一的)yY,满足:<>f,则称f为函数.记为Y定义域:值域:(有时记为f(X))={f(x)X}【定义8.1】函数相等：设f和g都是从A到B的函数,若对任意xA,有f(x)(x),则称f和g相等.记为【定义8.2】函数的个数：设,.记{:AB},则|满射(到上映射)：设f:XY,若=Y,则称f为满射的.入射（单射）(一对一映射)：设f:XY,对x1,x2X,满足:若x1x2,则f(x1)f(x2),称f为入射的.双射(一一对应映射)：设Y,若f既是满射的,又是入射的.则称f是双射的.【定义8.6】常函数:设→B,如果存在c∈B使得对所有的x∈A都有f(x),则称→B是常函数.恒等函数:称A上的恒等关系为A上的恒等函数,对所有的x∈A都有(x).单调递增:设<A,≼>,<B,≼>为偏序集，→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'的特征函数A'→{0,1}定义为A'(a)=1,a∈A';A'(a)=0,a∈AA'自然映射：设R是A上的等价关系,令→；g(a)=[a],a∈A称g是从A到商集的自然映射 【定义8.7】复合函数：设Z,定义:fg={<>X且zZ且可找到yY使(x)(y)}称fg为f与g的复合函数.设→B,→C

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

(3)如果→B,→C是双射的,则f→C也是双射的

【定理8.2】反函数（逆函数）：设Y是一个双射函数，那么f-1是YX的双射函数.称f-1为f的反函数.互逆(f-1)-1设→B是双射的,则f1f=,ff1=【定理8.5】基数：用来衡量集合大小的一个概念.对于有限集合集来说,集合的基数就是其中所含元素的个数.等势的：设A,B是集合,如果存在着从A到B的双射函数,就称A和B是等势的,记作A≈B.如果A不与B等势,则记作A≉B. 注：通常将A的基数记为.【定义8.8】N≈Z≈Q≈N×N任何实数区间都与实数集合R等势{0,1}N≈R康托定理N≉R；对任意集合A都有A≉P(A).【定义8.7】有限集(有穷集)/无限集(无穷集)：设A为一个集合.若存在某个自然数n,使得A与集合{0,1,…1}等势,则称A是有限的.若集合A不是有限的,则称A是无限的.【定义8.11】：实数集R的基数记作,即=【定义8.12】可数集(可列集)：设A为集合，若≤0，则称A为可数集或可列集。【定义8.14】与自然数集N等势的任意集合称为可数的.其基数为0结论： (1)A为可数的当且仅当可排列成{a12,…,…}的形式.(2)任一无限集必含有可数子集.(3)可数集的任何无限子集是可数的.(4)可数个两两不相交的可数集合的并集,仍是一个可数集.(5)NN是可数集.(6)有理数的全体组成的集合是可数集.(7)全体实数构成的集合R是不可数的.基数的常识：对于有穷集合A,基数是其元素个数n，=n;没有最大的基数。将已知的基数按从小到大的顺序排列就得到：0,1,2,…,n,…,0,,…代数结构运算：对于集合A，f是从到A的函数，称f为集合A上的一个n元运算。【定义9.1】交换律：已知<A，*>，若x，y∈A，有x**x，称*在A上是可交换的。【定义9.3】结合律：已知<A，*>，若x，y，z∈A，有x*（y*z）=（x*y）*z，称*在A上是可结合的。【定义9.4】幂等律：已知〈A，*〉，若x∈A，x*则称满足幂等律。【定义9.5】分配律：设<A，*，△>，若x，y，z∈A有:x*(y△z)=（x*y）△（x*z）;(y△z)*(y*x)△(z*x)称运算*对△是可分配的。【定义9.6】吸收律：设,是定义在集合A上的两个可交换二元运算，若对A,都有(xy)=x；x(xy)=x则称运算和满足吸收律.【定义9.7】单位元（幺元）:设*是A上二元运算，,A 左幺元：若xA，有*，称为运算*的左幺元； 右幺元：若xA，有x*，称为运算*的右幺元；若e既是左幺元又是右幺元，称e为运算*的幺元【定义9.8】设*是A上的二元运算，具有左幺元，右幺元，则【定理9.1】零元:设*是A上二元运算，l,r,A 左零元：若xA，有l*l，称l为运算*的左零元； 右零元： 若xA，有x*r，称r为运算*的右零元；若既是左零元又是右零元，称为运算*的零元。【定义9.9】设*是A上的二元运算，具有左零元l，右零元r，则【定理9.2】逆元：设*是A上的二元运算，e是运算*的幺元，若x*那对于运算*，x是y的左逆元，y是x的右逆元存在逆元(左逆无，右逆元）的元素称为可逆的（左可逆的，右可逆的）【定义9.10】对于可结合运算ο，如果元素x有左逆元ｌ，右逆元r，则－１【定理9.4】消去律：已知<A，*>，若x，y，z∈A，有(1)若x*y=x*z且x,则；(左消去律)(2)若y*x=z*x且x,则；（右消去律）那么称*满足消去律。【定义9.11】代数系统：设A为非空集合，为A上运算的集合,称<A,>为一个代数系统.【定义9.12】同类型的代数系统：如果两个代数系统中运算的个数相同，对应运算的元数相同，且代数常数的个数也相同，则称它们是同类型的代数系统.【定义9.13】子代数：设<S,f1,f2,…,>是代数系统，B是S的非空子集，如果B对f1,f2,…,都是封闭的，且B和S含有相同的代数常数，则称<B,f1,f2,…,>是V的子代数系统，简称子代数【定义9.14】最大的子代数：就是V本身最小的子代数：如果令V中所有代数常数构成的集合是B，且B对V中所有的运算都是封闭的，则B就构成了V的最小的子代数平凡的子代数:最大和最小的子代数称为V的平凡的子代数真子代数：若B是S的真子集，则B构成的子代数称为V的真子代数.因子代数：设V1=<A,◦>和V2=<B,>是同类型的代数系统，◦和为二元运算，在集合AB上如下定义二元运算▪，<a11>,<a22>AB，有<a11>▪<a22>=<a1◦a2,b1b2>称<AB,▪>为V1与V2的积代数，记作V1V2.这时也称V1和V2为V的因子代数.【定义9.15】设V1=<A,◦>和V2=<B,>是同类型的代数系统，V1V2=<AB,▪>是它们的积代数.(1)如果◦和运算是可交换（可结合、幂等）的，那幺▪运算也是可交换（可结合、幂等）的(2)如果e1和e2（1和2）分别为◦和运算的单位元（零元），那幺<e12>（<1,2>）也是▪运算的单位元（零元）(3)如果x和y分别为◦和运算的可逆元素，那幺<>也是▪运算的可逆元素，其逆元就是<x11>【定理9.5】同态:设V1=<A,∘>和V2=<B,>是同类型的代数系统，B，对x,yA有f(x∘y)=f(x)f(y),则称f是V1到V2的同态映射，简称同态(1)f如果是单射，则称为单同态。(2)如果是满射，则称为满同态，这时称V2是V1的同态像，记作V1V2。(3)如果是双射，则称为同构，也称代数系统V1同构于V2，记作V1V2。(4)如果V12，则称作自同态。【定义9.16】半群：设<S,∘>是代数系统，∘为二元运算，如果∘运算是可结合的，则称V为半群。独异点：设<S,∘>是半群，若e∈S是关于∘运算的单位元，则称V是含幺半群，也叫做独异点。有时也将独异点V记作<S,∘>.群：设<G,∘>是独异点，eG关于∘运算的单位元，若aG，a1G，则称V是群().通常将群记作G.【定义10.1】群的阶数：设<G,>是一个群 有限群：如果G是有限集，那么称<G,>为有限群 阶数：为该有限群的阶数； 无限群：如果G是无限集，则称<G,>为无限群。平凡群：阶数为1（即只含单位元）的群称为平凡群【定义10.2】群的性质：设<G,>是一个群。（1）非平凡群中不可能有零元.（2）对于G,必存在唯一的xG,使得ax.（3）对于{}G若:ab=ac或ba=ca则必有(消去律)。（4）运算表中的每一行或每一列都是一个置换。（5）除幺元e外,不可能有任何别的幂等元。元素的幂：设G是群，a∈G，n∈Z，则a的n次幂【定义10.3】元素的阶：设G是群，a∈G，使得等式成立的最小正整数k称为元素a的阶，记作，称a为k阶元。若不存在这样的正整数k，则称a为无限阶元。【定义10.4】幂运算性质： (1)a∈G，(a1)1 (2)∈G，()11a1 (3)a∈G，=，n,m∈Z (4)a∈G，()m=，n,m∈Z (5)若G为交换群，则()n=.【定理10.1】元素的阶的性质：G为群，a∈G且=r.设k是整数，则(1)=e当且仅当r|k(r整除k)(2)1|=【定理10.3】子群：设G是群，H是G的非空子集，如果H关于G中的运算构成群，则称H是G的子群,记作H≤G。真子群：若H是G的子群，且HG，则称H是G的真子群，记作H<G.平凡子群：对任何群G都存在子群.G和{e}都是G的子群，称为G的平凡子群.【定义10.5】子群判定定理一：设G为群，H是G的非空子集，则H是G的子群当且仅当(1)∈H有∈H；(2)a∈H有a1∈H。【定理10.4】子群判定定理二：设G为群，H是G的非空子集.H是G的子群当且仅当∈H有1∈H.

【定理10.5】子群判定定理三：设G为群，H是G的非空有穷子集，则H是G的子群当且仅当∈H有∈H.【定理10.6】生成子群：设G为群，a∈G，令{k∈Z}，则H是G的子群，称为由a生成的子群，记作<a>.陪集：设<H,>是群<G,>的一个子群G则: 左陪集：{a}H，由a所确定的H在G中的左陪集. 右陪集：{a}陪集是左陪集与右陪集的统称.

【定义10.6】陪集性质：设H是群G的子群，则=Ha∈G有a∈∈G有：a∈1∈H在G上定义二元关系R：∈G,<>∈R1∈H则R是G上的等价关系，且[a]R=. 【定理10.7】【定理10.8】拉格朗日定理：设G是有限群，H是G的子群，则=·[]其中[]是H在G中的不同右陪集(或左陪集)数，称为H在G中的指数.【定理10.10】推论：（1）设G是n阶群，则a∈G，是n的因子，且=e.（2）对阶为素数的群G，必存在a∈G使得G=<a>.阿贝尔群（交换群）：若群G中的运算是可交换的，则称G为交换群或阿贝尔群。循环群：设G是群，若存在a∈G使得{k∈Z}则称G是循环群，记作<a>，称a为G的生成元.

n阶循环群:设<a>是循环群，若a是n阶元，则G={a0,a1,a2,…,1}无限循环群:若a是无限阶元，则G={a0,a±1,a±2,…}【定义10.7】循环群的生成元:设<a>是循环群(1)若G是无限循环群，则G只有两个生成元，即a和a1.

(2)若G是n阶循环群，则G含有(n)个生成元.对于任何小于n且与n互质的数r∈{0,1,…1},是G的生成元.【定理10.11】循环群的子群：(1)设<a>是循环群，则G的子群仍是循环群；(2)若<a>是无限循环群，则G的子群除{e}以外都是无限循环群；(3)若<a>是n阶循环群，则对n的每个正因子d，G恰好含有一个d阶子群。【定理10.12】环：设<,·>是代数系统，+和·是二元运算.如果满足以下条件:(1)<>构成交换群；(2)<R,·>构成半群；(3)·运算关于+运算适合分配律，则称<,·>是一个环.【定义10.11】环的运算性质：设<,·>是环，则(1)a∈R，a0=0a=0(2)∈R，(a)b=a(b)=(3)∈R，a(bc)=，(bc)a=(4)a1212∈R(≥2)i=1nai设<,·>是环 交换环：若环中乘法·适合交换律，则称R是交换环；含幺环：若环中乘法·存在单位元，则称R是含幺环；无零因子环：若∈R，00∨0，则称R是无零因子环。整环：设<,>是一个代数系统,若满足:(1)<>是阿贝尔群；(2)<R,>是可交换独异点，且无零因子，即对R,a00则ab0；(3)运算对+是可分配的，则称<,>是整环域：设<,>是一个代数系统,若满足:(1)<>是阿贝尔群；(2)<{0},>是阿贝尔群；(3)运算对+是可分配的，则称<,>是域。【定义10.12】格：设<S,≼>是偏序集，如果S，{}都有最小上界和最大下界，则称S关于偏序≼作成一个格【定义11.1】格的代数系统定义：设<S,∗,◦>是代数系统,∗和◦是二元运算,如果∗和◦满足交换律、结合律和吸收律,则<S,∗,◦>构成格【定义11.3】对偶命题：设f是含有格中元素以与符号=,≼,≽,∨和∧的命题.令f*是将f中的≼替换成≽,≽替换成≼,∨替换成∧,∧替换成∨所得到的命题.称f*为f的对偶命题【定义11.2】格的对偶原理：设f是含有格中元素以与符号=,≼,≽,∨和∧等的命题.若f对一切格为真,则f的对偶命题f*也对一切格为真.格的性质：设<L,≼>是格,则运算∨和∧适合交换律、结合律、幂等律和吸收律,即(1)∈L有a∨b=b∨a,a∧b=b∧a(2)∈L有(a∨b)∨c=a∨(b∨c),(a∧b)∧c=a∧(b∧c)(3)a∈L有a∨a=a,a∧a=a(4)∈L有a∨(a∧b)=a,a∧(a∨b)=a【定理11.1】格的序与运算性质：设L是格,则∈L有a≼ba∧b=aa∨b=b【定理11.3】格的保序性质：设L是格,∈L，若a≼b且c≼d,则a∧c≼b∧d,a∨c≼b∨d【定理11.4】子格：设<L,∧,∨>是格,S是L的非空子集,若S关于L中的运算∧和∨仍构成格,则称S是L的子格【定义11.4】分配格：设<L,∧,∨>是格,若∈L,有a∧(b∨c)=(a∧b)∨(a∧c)a∨(b∧c)=(a∨b)∧(a∨c)则称L为分配格.【定义11.5】分配格的判别：设L是格,则L是分配格当且仅当L不含有与钻石格或五角格同构的子格【定理11.5】全下界：设L是格,若存在a∈L使得x∈L有a≼x,则称a为L的全下界；全上界：设L是格,若存在b∈L使得x∈L有x≼b,则称b为L的全上界

。【定义11.6】有界格：设L是格，若L存在全下界和全上界,则称L为有界格，一般将有界格L记为<L,∧,∨,0,1>.【定义11.7】有界格的性质：设<L,∧,∨,0,1>是有界格,则a∈L有a∧0=0∨0=∧1=a,a∨1=1补元：设<L,∧,∨,0,1>是有界格,a∈L,若存在b∈L使得a∧b=0和a∨b=1成立,则称b是a的补元 【定义11.8】有界分配格的补元惟一性定理：设<L,∧,∨,0,1>是有界分配格.若L中元素a存在补元,则存在惟一的补元. 【定理11.6】有补格:设<L,∧,∨,0,1>是有界格,若L中所有元素都有补元存在,则称L为有补格.【定义11.9】布尔格（布尔代数）：如果一个格是有补分配格,则称它为布尔格或布尔代数.布尔代数标记为<B,∧,∨,,0,1>,为求补运算.【定义11.10】布尔代数的代数系统定义：设<B,∗,◦>是代数系统,∗和◦是二元运算.若∗和◦运算满足：(1)交换律,即∈B有a∗b=b∗a,a◦b=b◦a(2)分配律,即∈B有a∗(b◦c)=(a∗b)◦(a∗c),

a◦(b∗c)=(a◦b)∗(a◦c)(3)同一律,即存在0,1∈B,使得a∈B有a∗1=a,a◦0=a(4)补元律,即a∈B,存在a∈B使得a∗a=0,a◦a=1则称<B,∗,◦>是一个布尔代数. 【定义11.11】布尔代数的性质：设<B,∧,∨,,0,1>是布尔代数,则(1)a∈B,(a)=a.(2)∈B,(a∧b)=a∨b,(a∨b)=a∧b（德摩根律）【定理11.7】原子：设L是格,0∈L,a∈L若b∈L有0≺b≼ab=a,则称a是L中的原子【定义11.12】有限布尔代数的表示定理：设B是有限布尔代数,A是B的全体原子构成的集合,则B同构于A的幂集代数P(A). 【定理11.8】推论1：任何有限布尔代数的基数为2n,n∈N.推论2：任何等势的有限布尔代数都是同构的图论无序积：A{()|xAyB}无向图G=<>,其中(1)V为顶点集，元素称为顶点；(2)E为VV的多重集，其元素称为无向边，简称边。【定义14.1】有向图<>,只需注意E是VV的多重子集 【定义14.2】n阶图：顶点个数为n.零图：边的个数为0.n阶零图记为平凡图：1阶零图N1空图：标定图与非标定图：依据顶点和边是否命名标识。有向图的基图：有向边改为无向边后的图。顶点与边的关联关系(,) 关联：与,关联 关联次数：0(不关联)，1()，2() 环：与同一顶点关联次数为2的边； 孤立点：不与任何边关联的顶点。顶点相邻：两个顶点之间有边。边相邻：两条边有公共端点。平行边：关联的端点相同的两条边（有向图中方向相同）。vV(G)(G为无向图) v的邻域： v的闭邻域： v的关联集：vV(D)(D为有向图) v的后继元集： v的先驱元集： v的邻域： v的闭邻域：多重图：含平行边的图；简单图：即不含平行边又不含环的图。【定义14.3】度（度数）：设<>为无向图,vV,d(v)——v的度数,简称度设<>为有向图,vV, 出度(v)：v作为边的始点的次数 入度d(v)：v作为边的终点的次数度（度数）d(v)：(v)+d(v)最大度(G){d(v)∈V(G)}最小度(G)={d(v)∈V(G)}最大出度+(D){(v)∈V(D)}最小出度+(D){(v)∈V(D)}最大入度(D){(v)∈V(D)}最小入度(D){(v)∈V(D)}最大度(D){d(v)∈V(D)}最小度(D){d(v)∈V(G)}奇顶点度：度为奇数的顶点偶度顶点：度为偶数的顶点 【定义14.4】握手定理：设<>为任意无向图，{v12,…},,则 设<>为任意有向图，{v12,…},,则 【定理14.1】【定理14.2】推论：任何图(无向或有向)中，奇度顶点的个数是偶数.度数列：{v1,v2,…,}为无向图G的顶点集，称d(v1),d(v2),…,d()为G的度数列{v1,v2,…,}为有向图D的顶点集度数列：d(v1),d(v2),…,d()出度列：(v1),(v2),…,()入度列：d(v1),d(v2),…,d()可图化的：非负整数列(d1,d2,…,)，若存在以{v12,…}为顶点集的n阶无向图G,使得d()，则称d是可图化的。特别的，若得到的图是简单图，则称d是可简单图化的。非负整数列(d1,d2,…,)是可图化的当且仅当为偶数.【定理14.3】设G为任意n阶无向简单图，则(G)n-1.【定理14.4】图的同构：设G1=<V11>,G2=<V22>为两个无向图(两个有向图)，若存在双射函数f1V2，对于,V1,()E1当且仅当(f(),f())E2（<>E1当且仅当<f(),f()>E2)并且,()（<>）与(f(),f())（<f()()>）的重数相同，则称G1与G2是同构的，记作G1G2.【定义14.5】n(n1)阶无向完全图：每个顶点与其余顶点均相邻的无向简单图，记作.边数n(n1)阶有向完全图：每对顶点之间均有两条方向相反的有向边的有向简单图.边数n(n1)阶竞赛图：基图为的有向简单图.【定义14.6】边数n阶k正则图：=的无向简单图。【定义14.7】边数<>,G=<V> 子图：V’V且E’E,则称G’为G的子图，记为GG，称G为G的母图; 生成子图：若GG且V，则称G为G的生成子图； 真子图：若VV或EE，称G为G的真子图； 导出子图：V（VV且V）的导出子图，记作G[V]； E（EE且E）的导出子图，记作G[E]. 【定义14.8】补图：设<>为n阶无向简单图，以V为顶点集，以所有使G成为完全图的添加边组成的集合为边集的图，称为G的补图，记作.若G,则称G是自补图 【定义14.9】Gv：从G中将v与关联的边去掉GV：从G中删除V中所有的顶点Ge：将e从G中去掉GE：删除E中所有边【定义14.10】通路与回路：给定图<>（无向或有向的），G中顶点与边的交替序列=v0e1v1e2…称为从v0到的通路，其中1,是的端点.；若v0，为回路。中的边数称为通路的长度.简单通路与简单回路：所有边各异。初级通路(路径)与初级回路(圈)：中所有顶点各异（v0除外），所有边也各异复杂通路与复杂回路：有边重复出现 【定义14.11】在n阶图G中，若从顶点到（）存在通路，则从到存在长度小于或等于n1的通路.【定理14.5】推论：在n阶图G中，若从顶点到（）存在通路，则从到存在长度小于或等于n1的初级通路（路径）在一个n阶图G中，若存在到自身的回路，则一定存在到自身长度小于或等于n的回路.【定理14.6】推论：在一个n阶图G中，若存在到自身的简单回路，则一定存在长度小于或等于n的初级回路.顶点的连通性：<>为无向图，若与之间有通路，则称与是连通的，记为连通图：若V，uv，则称G是连通的；【定义14.12】连通分支：{V12,…}，称G[V1],G[V2],…[]为连通分支，其个数称为连通分支数，记为p(G)【定义14.13】短程线uv：，u与v之间长度最短的通路距离d()：短程线的长度 【定义14.14】d()0,u≁v时d()=d()()d()()d()<>,VV 点割集：p(GV)>p(G)，且对任意VV均有p(GV)(G)，则V为点割集 割点：{v}为点割集，则v为割点 【定义14.15】<>,EE边割集：p(GE)>p(G)且有极小性则E是边割集割边（桥）：{e}为边割集e是割边（桥）【定义14.16】G为连通非完全图 点连通度(G)={|V为点割集}。规定()=n1;若G非连通，(G)=0 连通图：若(G)k，则称G为连通图【定义14.17】设G为连通图 边连通度(G)={|E为边割集}规定：若G非连通，则(G)=0r边-连通图：若(G)r，则称G是r边-连通图 【定义14.18】,,之间的关系：(G)(G)(G)【定理14.7】<>为有向图 可达：存在从到有通路 相互可达：且 【定义14.19】<>为有向图 弱连通(连通)：基图为无向连通图 单向连通：V，或 强连通：V， 【定义14.21】有向图的连通性判别法：(1)D强连通当且仅当D中存在经过每个顶点至少一次的回路；【定理14.8】(2)D单向连通当且仅当D中存在经过每个顶点至少一次的通路。【定理14.9】二部图(二分图)(偶图)：设<>为一个无向图，若能将V分成V1和V2(V1V2，V1V2=)，使得G中的每条边的两个端点都是一个属于V1，另一个属于V2，则称G为二部图(或称二分图、偶图等)，称V1和V2为互补顶点子集，常将二部图G记为<V12>.完全二部图：若G是简单二部图，V1中每个顶点均与V2中所有的顶点相邻，则称G为完全二部图，记为，其中1|，2|.【定义14.22】二部图的判别法：无向图<>是二部图当且仅当G中无奇圈。【定理14.10】关联矩阵M(G)：无向图<>，，，令为与的关联次数，称()nm为G的，记为M(G).【定义14.23】(4)平行边的列相同关联矩阵M(D)：有向图<>，令则称()nm为D的关联矩阵，记为.【定义14.24】(4)平行边对应的列相同邻接矩阵：设D＝()是有向图，V={v1,…}，构造矩阵[]如下：(1n)称A为图D的邻接矩阵。【定义14.25】邻接矩阵的含义：设A为有向图D的邻接矩阵，{v1,v2,…,}为顶点集，则A的l次幂（l1）中元素为D中到长度为l的通路数，其中为到自身长度为l的回路数，而为D中长度为l的通路总数，为D中长度为l的回路总数.【定理14.11】可达矩阵P(D)：设<>为有向图.{v1,v2,…,},令称()nn为D的可达矩阵，记作P(D)，简记为P.【定义14.26】欧拉通路：经过图（无向图或有向图）中每条边一次且仅一次行遍所有顶点的通路.欧拉回路：经过图中每条边一次且仅一次行遍所有顶点的回路.欧拉图：具有欧拉回路的图.半欧拉图：具有欧拉通路而无欧拉回路的图【定义15.1】平凡图是欧拉图.欧拉通路是简单通路，欧拉回路是简单回路无向欧拉图的判别法：(1)无向图G是欧拉图当且仅当G连通且无奇度数顶点.【定理15.1】(2)无向图G是半欧拉图当且仅当G连通且恰有两个奇度顶点.【定理15.2】有向欧拉图的判别法：(1)有向图D是欧拉图当且仅当D是强连通的且每个顶点的入度都等于出度.【定理15.3】(2)有向图D是半欧拉图当且仅当D是单向连通的，且D中恰有两个奇度顶点，其中一个的入度比出度大1，另一个的出度比入度大1，而其余顶点的入度都等于出度.【定理15.4】算法(求欧拉回路)：(1)任取v0V(G)，令P00.(2)设=v0e1v1e2…已经行遍，按下面方法从E(G){e12,…}中选取1：(a)1与相关联；(b)除非无别的边可供行遍，否则1不应该为=G{e12,…}中的桥.(3)当(2)不能再进行时，算法停止.哈密顿通路：经过图（无向图或有向图）中所有顶点一次仅一次的通路.哈密顿回路：经过图中所有顶点一次仅一次的回路.哈密顿图：具有哈密顿回路的图.半哈密顿图：具有哈密顿通路且无哈密顿回路的图. 【定义15.2】平凡图是哈密顿图.哈密顿通路是初级通路，哈密顿回路是初级回路.哈密顿图的必要条件：设无向图<>是哈密顿图，对于任意V1V且V1，均有p(GV1)1| 【定理15.6】推论：设无向图<>是半哈密顿图，对于任意的V1V且V1均有p(GV1)11哈密顿通路的充分条件：设G是n阶无向简单图，若对于任意不相邻的顶点，均有d()()n1则G中存在哈密顿通路.【定理15.7】推论（哈密顿图的充分条件）：设G为n(n3)阶无向简单图，若对于G中任意两个不相邻的顶点，均有d()()n则G中存在哈密顿回路，从而G为哈密顿图带权图：设Ｇ＝()是图，若G的