离散数学知识点.doc

说明：定义：红色表示。定理性质：橙色表示。公式：蓝色表示。算法: 绿色表示页码：灰色表示数理逻辑：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. 无向树与根树：无向树，生成树，最小生成树，Kruskal，根树，m叉树，最优二叉树，Huffman算法6. 平面图:平面图，面，欧拉公式，Kuratoski定理数理逻辑：命题：具有确定真值的陈述句。 否定词符号：设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】合式公式:(1) 命题常元和变元符号是合式公式；(2) 若A是合式公式，则(A)是合式公式，称为A的否定式； (3) 若A，B是合式公式，则 (AB)， (AB)， (AB)，(AB)是合式公式；(4) 所有合式公式都是有限次使用(1)，(2)，(3)、(4)得到的符号串。子公式: 如果是合式公式A的一部分，且本身也是一个合式公式，则称为公式A的子公式。【定义1.6】赋值（指派，解释）： 设是命题变元集合，则称函数v： 1，0是一个真值赋值。【定义1.8】真值表：公式A在其所有可能的赋值下所取真值的表，称为A的真值表。【定义1.9】重言式（永真式）:任意赋值v， v A矛盾式（永假式）:任意赋值v， 有v A【定义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, A A排中律 AA 矛盾律 AA 蕴涵等值式 ABAB等价等值式 AB(AB)(BA)假言易位 ABBA等价否定等值式ABAB归谬论 (AB)(AB) A置换规则： 设是公式A的子公式, Y。将A中的（可以是全部或部分X）用Y来置换，所得到的公式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】主析取范式：给定的命题公式的主析取范式是一个与之等价的公式，后者由极小项的析取组成。主合取范式：给定的命题公式的主合取范式是一个与之等价的公式，后者由极大项的合取组成。【定义2.5】公式的真值表中真值为F的指派所对应的极大项的合取，即为此公式的主合取范式。真值函数： 称F:0,1n 0,1 为n元真值函数.【定义2.6】联结词的完备集：设C是联结词的集合，若对于任意一个合式公式均存在一个与之等价的公式，而后者只含有C中的联结词，则称C是联结词的完备集。【定义2.7】， ， , ， ， ， ， ，是联结词的完备集。【定理2.6】c异或PQ ： (P Q)条件否定PQ： (P Q)与非PQ： (P Q)或非PQ： (P Q)【定义2.8】,都是联结词的完备集【定理2.7】重言蕴含式：当且仅当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). (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(1il)是某个Aj, 或者可由序列中前面的公式应用推理规则得到, 并且Cl =B。【定义3.3】CP规则(演绎定理)：若G R|- S，则 G |- RS, 其中G为命题公式的集合。个体词：用于表示命题中主语部分的符号或符号串。个体常元 表示确指个体。个体变元 表示不确指个体。个体域: 个体变元的取值范围，常用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是公式，则(AB)，(AB)，AB)，(AB)是公式；(4) 若A是公式，x是变元，则xA，$xA是公式； (5) 仅仅有限次使用得到的符号串才是合式公式。 【定义4.4】设公式 a的一个子公式为 x A或$ x A。则称： 指导变元：x是或$的指导变元。辖域：A是相应量词的辖域。约束出现：辖域中x的一切出现，以及( x)中的x称为x在a中的约束出现。自由出现：变元的非约束出现。约束变元：约束出现的变元。自由变元：自由出现的变元。 【定义4.5】封闭的：一个公式A是封闭的，若其中不含自由变元。【定义4.6】变元换名：（1） 换名的范围是量词的指导变元,及其相应辖域中的变元，其余部分不变。 （2） 换名时最好选用辖域中未出现的变元名。变元代入：代入对自由变元进行。不能改变约束关系。解释： 谓词语言的一个解释 I= (D, j )包括： (1) 非空集合D，称之为论域； (2) 对应于每一个个体常元a， j(a)D； (3) 对应于每一个n元函数符号f都有一个函数 j(f):Dn D； (4) 对应于每一个n元谓词符号A都有一个n元关系j(A) Dn。【定义4.7】赋值：解释I中的赋值v为每一个个体变元x指定一个值v(x ） D，即设 V为所个体变元的集合，则赋值v是函数 v:V D.可满足的：给定公式A，若在某一解释中至少有一种赋值使A取值为1，则称A为可满足的。否则称A是不可满足的。等值式A B：若AB是有效的【定义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)（5）多个量词的使用 x y A(x,y) y x A(x,y) $ x $ y A(x,y) $ y $ x A(x,y)置换规则：设F(A)是含A的公式, 那么, 若AB, 则F(A)F(B).换名规则：设A为一公式，将A中某量词辖域中个体变项的所有约束出现及相应的指导变元换成该量词辖域中未曾出现过的个体变项符号，其余部分不变，设所得公式为A，则AA.前束范式：如果谓词公式A有如下形状：Q1x1QnxnM，其中 Qixi或者是xi，或者是$xi，i=1，n，M是不含量词的公式， Q1x1Qnxn称为首标，M称为母式。【定义5.2】前束范式存在定理：对于任意谓词公式，都存在与它逻辑等价的前束范式。【定理5.1】前束范式的算法：步1. 对约束出现的变元进行必要的换名，使得约束出现的变元互不相同且不与任何自由变元同名。步2. 将所有的否定号深入到量词后面。步3. 将量词符号移至公式最外层。逻辑蕴含式A C：当且仅当AC是有效的。几类逻辑蕴涵式第一组 命题逻辑推理定理的代换实例 如, xF(x)$yG(y) xF(x) 第二组 基本等值式生成的推理定理 如, xF(x) xF(x), xF(x) xF(x) xF(x)$xF(x), $xF(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)：xAxAy或xAxAcx,y个体变项，c个体常项+规则(UG)：AxxAxx个体变项$- 规则(ES)：xAxAcx个体变项, c个体常项$+ 规则(EG)：AyxAx或BAyBxAxx,y个体变项，c个体常项AcxAx或BAcBxAx先用ES，再用US自然推理系统N L ：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 ( xA xB )【定义6.1】A = B A B B A【定义6.2】A B A B A B 【定义6.3】A B $x ( xA xB ) 空集 ：不含有任何元素的集合【定义6.4】空集是任何集合的子集。【定理6.1】幂集P(A) = x | x A 【定义6.5】如果 |A|=n，则 |P(A)|=2n全集 E：包含了所有元素的集合【定义6.6】并AB = x | xA xB交AB = x | xA xB 差（相对补）A-B = x | xA xB【定义6.7】对称差AB = (A-B)(B-A) 【定义6.8】补（绝对补）A = E-A = x|xA【定义6.9】广义并A = x | $z ( zA xz )【定义6.10】广义交A = x | z ( zA xz )【定义6.11】集合恒等式1.只涉及一个运算的算律：交换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)=(A-B)(A-C)A-(BC)=(A-B)(A-C)(BC)=BC(BC)=BC双重否定A=A4涉及全集和空集的算律：E补元律AA=AA=E零律A=AE=E同一律A=AAE=A否定=EE=序偶（有序对 ）： 由两个元素 x 和 y，按照一定的顺序组成的二元组，记作.【定义7.1】笛卡儿积:设A,B为集合，A与B的笛卡儿积记作AB定义为AB = | xAyB.【定义7.2】笛卡尔积性质：A=或B=时, AB=“ ”不满足结合律A(BC) = (AB)(AC)关系：（两个定义）(1) 序偶的一个集合, 确定了一个二元关系R。R 中任一序偶 ,可记作 R 或 xRy【定义7.3】(2) 笛卡尔积的子集： R AB 【定义7.4】空关系:全域关系：AB 恒等关系 IA = | xA【定义7.5】关系矩阵：若A=x1, x2, , xm，B=y1, y2, , yn，R是从A到B的关系，R的关系矩阵是布尔矩阵MR = rij mn, 其中rij = 1 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-1 = | R 【定义7.7】互逆 (R-1)-1 = R(R S) -1 = R -1 S -1(R S) -1 = R -1 S -1(A B) -1 = BA(R - S) -1 = R -1 - S -1 复合关系 RS = | $ y (R S) 【定义7.8】(Ro S)o P=Ro (So P) Rm = RoRo oR 设R X Y,S YZ,则 (Ro S) -1 = S -1 o R -1 【定理7.2】R在A上的限制RA = | xRyxA A在R下的像RA=ran(RA) 【定义7.9】自反的：若 xA，都有R, 则称 R 是自反的反自反的：若 xA，都有 R, 则称 R 是反自反的.【定义7.11】对称的：对任意x,yA,满足, 若 R,则R反对称的：对任意x,yA,满足，若 R且R,则x=y【定义7.12】传递的：对任意的x,y,zA, 满足:若R且R, 则R,则称R是传递的【定义7.13】自反闭包（对称、传递） ：设R是A上的二元关系,如果有另一个关系R满足: R是自反（对称、传递）的; RR; 对于任何自反的关系R”,若RR, 则有RR.则称关系R为R的自反闭包. 记为 r(R)（对称闭包 s(R) 和传递闭包 t(R)）。【定义7.14】设R为A上的关系, 则有(1) r(R)=RIA(2) s(R)=RR-1(3) t(R)=RR2R3（若|A|=n， 则 t(R)=RR2 Rn ）等价关系：设 R 为集合 A 上的一个二元关系。若 R 是自反的, 对称的, 传递的, 则称 R 为 A 上的等价关系【定义7.15】等价类 ：设R为集合A上的等价关系, 对aA, 定义:aR = x|xA 且 R称之为元素a关于R的等价类。【定义7.16】给定A上的等价关系R,对于a,bA有当且仅当aR=bR【定理17.4】商集：设R是A上的等价关系，定义 A/R=aR|aA称之为A关于R的商集.【定义7.17】划分：设A为非空集合, 若A的子集族( P(A)满足: (1) (2) xy(x,yxyxy=) (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,yA满足: xy或 yx则称 为全序关系. 为全序集.【定义7.21】覆盖：设为偏序集,若x,yA, xy,xy且没有其它元素z满足xz,zy,则称y覆盖x. 记covA= |x,yA且y覆盖x【定义7.23】哈斯图：作图规则 用小元圈o代表元素; 若xy且xy,则将代表y的小元圈画在代表x的小元圈之上; 若covA, 则在x,y之间用直线连接。你极小元/极大元：设为偏序集, B A (1) 对bB，若B中不存在x满足: bx且 xb则称b为B的极小元. (2) 对bB，若B中不存在x满足: bx且 bx则称b为B的极大元.最小元/最大元：设为偏序集,BA,若有某个bB (1) 对于B中每一个元素x都有bx，则称b为B的最小元.(2) 对于B中每一个元素x都有xb，则称b为B的最大元.【定义7.24】下界/上界：设为偏序集, B A (1) 若有aA,且对xB 满足 ax，则称a为B的下界。进一步: 设a为B的下界,若B的所有下界y均有ya,则称a为B的下确界 ，记为glb B。 (2) 若有aA,且对xB 满足 xa，则称a为B的上界。进一步: 设a为B的上界,若B的所有上界y均有ay,则称a为B的上确界 ，记为lub B。【定义7.25】函数：设X,Y为两个集合,fXY, 若对xX,$!(唯一的)yY,满足: f,则称f为函数.记为:f:XY定义域: domf=X 值域: ranf (有时记为f(X)=f(x)|xX【定义8.1】函数相等：设f和g都是从A到B的函数, 若对任意xA,有f(x)=g(x),则称f和g相等.记为f=g【定义8.2】函数的个数：设f:AB,|A|=m, |B|=n.记 BA=f|f: AB, 则| BA |= nm满射(到上映射)：设 f: X Y, 若 ranf = Y, 则称 f 为满射的.入射（单射）(一对一映射)：设f: XY, 对 x1, x2 X, 满足:若 x1 x2, 则 f(x1) f(x2),称 f 为入射的.双射 (一一对应映射)：设f:XY, 若f既是满射的, 又是入射的. 则称f是双射的.【定义8.6】常函数:设 f:AB, 如果存在cB使得对所有的 xA都有 f(x)=c, 则称 f:AB是常函数.恒等函数:称 A上的恒等关系IA为A上的恒等函数, 对所有的xA都有IA(x)=x.单调递增:设, 为偏序集，f:AB，如果对任意的x1, x2A, x1x2, 就有 f(x1) f(x2), 则称 f 为单调递增的；严格单调递增:如果对任意的x1, x2A, x1x2, 就有f(x1) f(x2), 则称 f 为严格单调递增的. 类似的也可以定义单调递减和严格单调递减的函数特征函数：设A为集合, 对于任意的AA, A的特征函数cA :A0,1定义为cA(a)=1, aA;cA(a)=0, aA-A自然映射：设R是A上的等价关系, 令g:AA/R；g(a)=a, aA称 g 是从 A 到商集 A/R 的自然映射【定义8.7】复合函数：设 f:XY,g:YZ, 定义: fo g = |xX且zZ且可找到yY使y=f(x),z=g(y)称fo 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:XY是一个双射函数，那么f -1是YX的双射函数. 称f -1为f的反函数.互逆 (f -1 )-1=f设 f:AB是双射的, 则 f -1f = 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康托定理(1) N R； (2) 对任意集合A都有AP(A).【定义8.7】有限集(有穷集)/无限集 (无穷集) ：设A为一个集合. 若存在某个自然数n, 使得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是不可数的.基数的常识： 对于有穷集合A, 基数是其元素个数n，|A| = n; 没有最大的基数。将已知的基数按从小到大的顺序排列就得到： 0, 1, 2, , n, , 0, , 代数结构运算：对于集合 A，f 是从An到 A 的函数，称 f 为集合A上的一个n元运算。 【定义9.1】 交换律：已知，若x，yA，有x*y=y*x，称*在A上是可交换的。【定义9.3】结合律：已知，若x，y，zA，有x*（y*z）=（x*y）*z，称*在A上是可结合的。【定义9.4】幂等律：已知A，*，若xA，x*x=x 则称满足幂等律 。【定义9.5】分配律：设，若x，y，zA有: x*(yz)=（x*y）（x*z） ; (yz)*x=(y*x)(z*x)称运算*对是可分配的。【定义9.6】吸收律：设*,D是定义在集合A上的两个可交换二元运算，若对x,y A,都有:x*(xD y) = x ； xD(x* y) = x则称运算*和D满足吸收律.【定义9.7】单位元（幺元）: 设*是A上二元运算， el, er,eA左幺元：若xA，有el*x=x，称el为运算*的左幺元；右幺元：若xA，有x*er=x，称er为运算*的右幺元；若e既是左幺元又是右幺元，称e为运算*的幺元【定义9.8】设*是A上的二元运算，具有左幺元el，右幺元er，则el=er=e 【定理9.1】零元: 设*是A上二元运算， ql, qr, qA左零元：若xA，有ql*x=ql ，称ql为运算*的左零元； 右零元：若xA，有x*qr=qr，称qr为运算*的右零元；若q既是左零元又是右零元，称q为运算*的零元。 【定义9.9】设*是A上的二元运算，具有左零元q l ，右零元qr， 则q l= q r= q【定理9.2】逆元：设*是A上的二元运算，e是运算*的幺元，若x*y=e那对于运算*，x是y的左逆元，y是x的右逆元 存在逆元(左逆无，右逆元）的元素称为可逆的（左可逆的，右可逆的）【定义9.10】对于可结合运算 ，如果元素x有 左逆元，右逆元r，则l=r=x【定理9.4】消去律：已知，若x，y，zA，有 (1) 若 x*y = x*z且 x q,则y=z；(左消去律) (2) 若 y*x = z*x且 x q,则y=z；（右消去律）那么称*满足消去律。【定义9.11】代数系统：设A为非空集合，W为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=是同类型的代数系统，和*为二元运算，在集合AB上如下定义二元运算， ,AB，有= 称V=为V1与V2的积代数，记作V1V2. 这时也称V1和V2为V的因子代数. 【定义9.15】设V1=和V2=是同类型的代数系统，V1V2=是它们的积代数. (1) 如果 和 *运算是可交换（可结合、幂等）的，那幺运算也是可交换（可结合、幂等）的(2) 如果 e1 和 e2（q1和q2）分别为 和 *运算的单位元（零元），那幺（）也是运算的单位元（零元）(3) 如果 x 和 y 分别为和 *运算的可逆元素，那幺也是运算的可逆元素，其逆元就是 【定理9.5】同态:设V1=和V2=是同类型的代数系统，f:AB，对x, yA 有f(xy) = f(x)*f(y), 则称 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，a-1G，则称V是群(Group). 通常将群记作G. 【定义10.1】群的阶数：设是一个群有限群：如果G是有限集，那么称为有限群阶数：|G| 为该有限群的阶数； 无限群：如果G是无限集，则称为无限群。平凡群：阶数为1（即只含单位元）的群称为平凡群【定义10.2】群的性质：设是一个群。（1）非平凡群中不可能有零元.（2）对于a,b G, 必存在唯一的x G,使得a* x =b.（3）对于a,b,c G若: a*b = a*c或b*a = c*a则必有b=c (消去律)。（4）运算表中的每一行或每一列都是一个置换。（5）除幺元e外,不可能有任何别的幂等元。元素的幂：设G是群，aG，nZ，则a 的 n次幂【定义10.3】元素的阶：设G是群，aG，使得等式 ak=e 成立的最小正整数k 称为元素a 的阶，记作|a|=k，称 a 为 k 阶元。若不存在这样的正整数 k，则称 a 为无限阶元。【定义10.4】幂运算性质：(1) aG，(a-1)-1=a(2) a,bG，(ab)-1=b-1a-1(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 )|a-1| = |a| 【定理10.3】子群：设G 是群，H 是G 的非空子集， 如果H关于G中的运算构成群，则称H是G 的子群, 记作HG。真子群：若H是G 的子群，且HG，则称H是G的真子群，记作HG.平凡子群：对任何群G都存在子群. G和e都是G 的子群，称为G 的平凡子群. 【定义10.5】子群判定定理一：设G为群，H是G的非空子集，则H是G的子群当且仅当(1) a,bH有abH；(2) aH有a-1H。【定理10.4】子群判定定理二：设G为群，H是G的非空子集. H是G的子群当且仅当a,bH有ab-1H.【定理10.5】子群判定定理三：设G为群，H是G的非空有穷子集，则H是G的子群当且仅当a,bH有abH. 【定理10.6】生成子群：设G为群，aG，令H=ak| kZ，则H是G的子群，称为由 a 生成的子群，记作.陪集：设是群的一个子群,a G则:左陪集：aH := aH，由a所确定的H在G中的左陪集.右陪集：Ha:=Ha陪集是左陪集与右陪集的统称.【定义10.6】陪集性质：设H是群G的子群，则 He = H aG 有aHa a,bG有：aHb ab-1H Ha=Hb 在G上定义二元关系R： a,bG, R ab-1H则 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使得G = .阿贝尔群（交换群）：若群G中的运算是可交换的，则称G为交换群或阿贝尔群。循环群：设G是群，若存在aG使得G=ak| kZ 则称G是循环群，记作G=，称 a 为G 的生成元.n 阶循环群: 设G=是循环群，若a是n 阶元，则 G = a0=e, a1, a2, , an-1 无限循环群: 若a 是无限阶元，则 G = a0=e, a1, a2, 【定义10.7】循环群的生成元:设G=是循环群(1) 若G是无限循环群，则G只有两个生成元，即a和a-1.(2)若G是n阶循环群，则G含有f(n)个生成元. 对于任何小于n且与 n 互质的数r0,1,n-1, ar是G的生成元.【定理10.11】循环群的子群：(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(b-c) = ab-ac， (b-c)a = ba-ca(4) a1,a2,.,an,b1,b2,.,bmR (n,m2)i=1naij=1mbj=i=1nj=1maibj【定理10.14】设是环交换环：若环中乘法 适合交换律，则称R是交换环；含幺环：若环中乘法 存在单位元，则称R是含幺环；无零因子环：若a,bR，ab=0 a=0b=0，则称R是无零因子环。整环：设是一个代数系统,若满足:(1) 是阿贝尔群；(2) 是可交换独异点，且无零因子，即对a,bR, a0,b0 则a b0；(3) 运算对+是可分配的， 则称是整环域 ：设是一个代数系统,若满足:(1) 是阿贝尔群；(2)