《离散数学》总复习.ppt

n1.主范式、集合、布尔格主范式、集合、布尔格(有补分配格有补分配格)运算运算n2.命题符号化命题符号化+命题命题/ /谓词逻辑推理谓词逻辑推理n3.前束范式前束范式n4.元素与集合、集合与集合的关系元素与集合、集合与集合的关系(判断判断,证明证明)n5.排列组合、容斥原理、递推方程排列组合、容斥原理、递推方程n6.关系合成、函数复合、置换乘法关系合成、函数复合、置换乘法n7.等价关系等价关系(等价类、商集、划分、自然映射等价类、商集、划分、自然映射)n8.偏序集偏序集(偏序关系、覆盖、哈斯图偏序关系、覆盖、哈斯图)、格、格n9.同构同构=同态同态双射双射n10.代数系统及其性质代数系统及其性质(判断判断)n11.域域=整环整环除环除环n0.重要概念重要概念:幂集幂集,笛卡积笛卡积,闭包闭包,积代数积代数,循环群循环群;0.重要概念重要概念:生成子图生成子图,自补图自补图,自对偶图自对偶图,割集割集n12.握手定理握手定理n13.邻接矩阵邻接矩阵n14.最短路径最短路径(标号法标号法)与与关键路径关键路径(最长路径最长路径)n15.图的类型图的类型(二部二部,欧拉欧拉,哈密顿哈密顿,平面平面,树树)判别判别n16.平面图欧拉公式：平面图欧拉公式：n m+r=2n17.树的重要性质：树的重要性质：m=n- -1n18.最小生成树最小生成树(避圈法避圈法)、基本回路、基本回路/ /割集系统割集系统n19.Huffman算法算法(最优二元树最优二元树/ /最佳前缀码最佳前缀码)n20.二二/多项式定理与组合恒等式多项式定理与组合恒等式n21.分治算法的常用递推公式分治算法的常用递推公式第第1章章 命题逻辑命题逻辑1.1 命题符号化及联结词（联结词是基础）命题符号化及联结词（联结词是基础）1.2 命题公式及分类命题公式及分类1.3 等值演算等值演算1.4 联结词全功能集联结词全功能集1.5 对偶与范式（主范式演算是重点）对偶与范式（主范式演算是重点）1.6 推理理论（重点）推理理论（重点）联结词与复合命题联结词与复合命题(小结小结)n联结词优先级: ( ), , , , n同级按从左到右的顺序进行 p q p pq pq pq pq 0 0 1 0 0 1 1 0 1 1 0 1 1 0 1 0 0 0 1 0 0 1 1 0 1 1 1 1基本复合命题的真值基本复合命题的真值1.3 命题逻辑等值演算命题逻辑等值演算等值式等值式定义定义：( (AB1) ( (AB)（重点）（重点）基本等值式基本等值式( (重点重点) ) 双重否定律双重否定律 : AA等幂律等幂律： A AA, A AA交换律交换律: A BB A, A BB A结合律结合律: (A B) CA (B C) (A B) CA (B C)分配律分配律: A (B C)(A B) (A C) A (B C) (A B) (A C)德德摩根律摩根律: (A B)AB (A B)AB基本等值式基本等值式（续）吸收律吸收律: A (A B)A, A (A B)A零律零律: A 11, A 00 同一律同一律: A 0A, A 1A排中律排中律: AA1矛盾律矛盾律: AA0蕴涵等值式蕴涵等值式: ABA B等价等值式等价等值式: AB(AB) (BA)假言易位假言易位: ABBA等价否定等值式等价否定等值式: ABAB归谬论归谬论: (AB) (AB) A1.4复合联结词（重要的非重点）复合联结词（重要的非重点）与非式与非式: p q(p q)；或非式或非式: p q(p q)习题习题1.14，1.10(4)(5)异或：异或：p q p q (pq)pq pqnAp1 p2 pn,偶数个命题变项赋值为偶数个命题变项赋值为1 (A(A0),奇数个命题变项赋值为奇数个命题变项赋值为1 (A(A1);nBq1q2qn,偶数个命题变项赋值为偶数个命题变项赋值为0 (A(A1),奇数个命题变项赋值为奇数个命题变项赋值为0 (A(A0).n习题习题1.221.5 主范式（重点）主范式（重点）n成真赋值成真赋值i对应主析取范式的极小项对应主析取范式的极小项mi；n成假赋值成假赋值j对应主合取范式的极大项对应主合取范式的极大项Mj。n命题公式有几个成真赋值，主析取范式就是几命题公式有几个成真赋值，主析取范式就是几个极小项相或个极小项相或( )；n命题公式有几个成假赋值，主合取范式就是几命题公式有几个成假赋值，主合取范式就是几个极大项相与个极大项相与( )。例。例1.31，1.32n分配律分配律Bj Bj (pi pi) (Bj pi) (Bj pi)nBj Bj (pi pi) (Bj pi) (Bj pi)n习题习题1.12(1), 1.13(1)。五。五71.6 命题逻辑推理（重点）命题逻辑推理（重点）“推理正确推理正确”定义定义：( (AB1) ( (AB)（重点）（重点）A (A B) 附加律附加律 (A B) A 化简律化简律(AB) A B 假言推理假言推理(AB)B A 拒取式拒取式(A B)B A 析取三段论析取三段论(AB) (BC) (AC) 假言三段论假言三段论(AB) (BC) (AC) 等价三段论等价三段论(AB) (CD) (A C) (B D) 构造性二难构造性二难(AB) ( AB) (AA) B 构造性二难构造性二难(特殊形式特殊形式)(AB) (CD) ( BD) ( AC) 破坏性二难破坏性二难习题习题1.18, 1.21, 1.17(2)。六。六1注意事项注意事项1：命题：命题只有能确定真假(但不能可真可假)的陈述句陈述句才是命题命题. 不管是正确的观点, 还是错误的观点, 都是命题. 猜想猜想和预言预言是命题, 如哥德巴赫猜想.感叹句,祈使句,疑问句都不是命题. 陈述句中的悖悖论论以及判断结果不惟一确定的也不是命题.有些简单命题貌似复合命题,要注意区分. 题1(15) 注意事项注意事项2：蕴涵联结词蕴涵联结词“”pq 的逻辑关系: p为q的充分条件，q为p的必要条件.“如果p,则q” 的多种表述方式：(1)若p,就q. (2)只要p,就q. (3) p仅当q. (4)只有q 才p. (5)除非q, 才p. (6)除非q, 否则非p. pq为假当且仅当为假当且仅当 p 为真为真 q 为假，即为假，即当p为假时，pq为真(不管q为真, 还是为假);当q为真时，pq为真(不管p为真, 还是为假).习题习题1.5(6)(7)了解概念、掌握方法n真值表、命题公式类型真值表、命题公式类型n所有等值的含所有等值的含n个命题变项的公式对应同一个命题变项的公式对应同一个个n元真值函数元真值函数F:0,1n0,1；哑元n最小联结词组最小联结词组n对偶式与对偶原理对偶式与对偶原理n简单析取式、简单合取式简单析取式、简单合取式n析取范式与合取范式析取范式与合取范式n附加前提证明法、附加前提证明法、反证法反证法第第2章章 一阶逻辑一阶逻辑2.1一阶逻辑基本概念（量词是关键）一阶逻辑基本概念（量词是关键）2.2一阶逻辑公式、解释及分类一阶逻辑公式、解释及分类2.3一阶逻辑等值式、前束范式（重点）一阶逻辑等值式、前束范式（重点）2.4一阶逻辑推理理论（重点）一阶逻辑推理理论（重点）一阶逻辑与命题逻辑关系一阶逻辑与命题逻辑关系n一阶逻辑将命题一阶逻辑将命题(公式公式)拆分为个体词、谓词、拆分为个体词、谓词、量词量词( 、 )。谓词是核心，没有谓词，不。谓词是核心，没有谓词，不构成命题；量词是关键。构成命题；量词是关键。n个体词（元素）个体词（元素）分为分为个体常项个体常项和和个体变项个体变项.个体域（集合）个体域（集合）: 个体变项的取值范围个体变项的取值范围. 全总个体域全总个体域: 宇宙间一切事物组成宇宙间一切事物组成n一阶逻辑一阶逻辑命题逻辑命题逻辑+量词量词n xF(x) x F(x), xF(x) x F(x);n xF(x) x F(x), xF(x) x F(x) 2.3 一阶逻辑等值式一阶逻辑等值式基本等值式基本等值式（重点）（重点） :命题逻辑中命题逻辑中16组基本等值式的代换实例组基本等值式的代换实例消去量词等值式消去量词等值式 设设D=a1,a2,an xA(x)A(a1) A(a2) A(an) xA(x)A(a1) A(a2) A(an)量词辖域收缩与扩张等值式量词辖域收缩与扩张等值式x(A(x)B)xA(x)Bx(A(x)B)xA(x)B x(A(x)B)xA(x)Bx(BA(x)BxA(x)量词分配等值式量词分配等值式 x(A(x) B(x)xA(x)xB(x) x(A(x) B(x)xA(x)xB(x)x(A(x)B)xA(x)Bx(A(x)B)xA(x)B x(A(x)B)xA(x)Bx(BA(x)BxA(x)注意事项注意事项1：前束范式：前束范式（重点）（重点）n设设A为一个一阶逻辑公式为一个一阶逻辑公式, 若若A具有如下形式具有如下形式Q1x1Q2x2QkxkB, 则称则称A为为前束范式前束范式, 其中其中Qi (1 i k)为为 或或 ，B为不含量词的公式为不含量词的公式.n1） 对对 无分配律，无分配律， 对对 无分配律无分配律n xA(x)xB(x)x y(A(x) B(y)n x y(A(x) B(y)xA(x)xB(x)n2）变量冲突，有一个要换名）变量冲突，有一个要换名.n3） x(A(x)B)xA(x)B x(A(x)B)xA(x)Bn习题习题2.21, 2.15(1), 2.14(1)。四。四102.4 一阶逻辑推理理论（重点）一阶逻辑推理理论（重点）n重要的推理定律重要的推理定律第一组第一组 命题逻辑推理定律代换实例命题逻辑推理定律代换实例第二组第二组 由基本等值式生成（由基本等值式生成（置换规则）置换规则） 第三组第三组 xA(x)xB(x)x(A(x) B(x) x(A(x) B(x)xA(x)xB(x)(12) 全称量词消去规则（简记为UI规则或UI）(13) 全称量词引入规则（简记为UG规则或UG）(14) 存在量词引入规则（简记为EG规则或EG）(15) 存在量词消去规则（简记为EI规则或EI）注注:必须先消去存在量词,后消去全称量词. 七1第三版第三版:习题习题2.22, 2.16, 2.19, 2.17(1), 2.23；例；例2.18注意事项2：一阶逻辑中命题符号化一阶逻辑中命题符号化无特别要求，用全总个体域无特别要求，用全总个体域量词顺序一般不要随便颠倒量词顺序一般不要随便颠倒 x yA(x,y) y xA(x,y)全称量词全称量词 一般对应一般对应“”存在量词存在量词 一般对应一般对应“ ”习题习题2.3(2)(5)(6)了解有限个体域有限个体域,无限个体域无限个体域;谓词常项谓词常项,谓词变项谓词变项,一元谓一元谓词词,多元谓词多元谓词(n元谓词元谓词,n 2),0元谓词元谓词,原子公式原子公式;项项字母表字母表包含：包含：1)个体常项个体常项,2)个体变项个体变项,3)函数符号函数符号,4)谓词符号谓词符号,5)量词符号量词符号( , ),6)联结词符号联结词符号( , , , , ),7)括号与逗号括号与逗号. 指导变元指导变元，辖域辖域，约束出现约束出现，自由出现自由出现闭式闭式: 不含自由出现的个体变项的公式不含自由出现的个体变项的公式.解释解释I包含：包含：(a)非空个体域非空个体域DI,(b)DI中一些特定元素中一些特定元素集集,(c)DI上特定函数集上特定函数集,(d)DI上特定谓词集上特定谓词集.n闭式在任何解释下都是命题，闭式在任何解释下都是命题，n不是闭式的公式在某些解释下也可能是命题不是闭式的公式在某些解释下也可能是命题.公式类型公式类型. 换名规则与代替规则换名规则与代替规则第第3章章 集合的基本概念和运算集合的基本概念和运算n3.1 集合的基本概念集合的基本概念n3.2 集合的基本运算（重点）集合的基本运算（重点）n3.3 集合中元素的计数（容斥原理是重点）集合中元素的计数（容斥原理是重点）3.1 集合的基本概念集合的基本概念n元素x与集合A的关系：属于属于x A，不属于不属于x An集合A与集合B的关系：习题习题3.2, 3.8, 3.12, 3.16包含包含(子集子集)A B, 不包含不包含A B 相等相等A = B, 不相等不相等A B 真包含真包含A B, 不真包含不真包含A Bn重要概念：重要概念：集合A的幂集的幂集P(A) = x | x A 。如如果果 |A| = n，则，则 |P(A)| = 2n. 习题习题3.14(4), 3.18n习题习题3.3, 3.9, 3.113.2 集合的基本运算（重点）集合的基本运算（重点）集合运算符集合运算符 ， ， ， 分别对应分别对应 联结词联结词, ， ， A B = A B = A (A B) A B = (A B) (B A)= (A B) (A B)A B A A BA B A B=B A B=A A B=A B= A B=A习题习题3.17, 3.16；例；例3.17，3.18。四。四3，4；六；六4集合运算的集合运算的文氏图表示文氏图表示习题习题3.4, 3.15(2)集合运算的算律集合运算的算律（重点）（重点） 交换交换A B=B AA B=B AA B=B A结合结合(A B) C=A (B C)(A B) C=A (B C)(A B) C=A (B C)幂等幂等A A=AA A=A 与与 与与 分配分配A (B C)=(A B) (A C)A (B C)=(A B) (A C)A (B C)=(A B) (A C)吸收吸收A (A B)=AA (A B)=A吸收律的前提：吸收律的前提： 、 可交换可交换集合运算的算律集合运算的算律（续） D.M 律律A (B C)=(A B) (A C)A (B C)=(A B) (A C) (B C)= BC (B C)= BC双重否定双重否定A=AE补元律补元律AA=AA=E零律零律A=A E=E同一律同一律A=AA E=A否定否定=E E=3.3 集合中元素的计数集合中元素的计数|.|)1(.|.|21111121mmmkjikjimimjijiimAAAAAAAAAAAA 容斥原理及其推论（重点）容斥原理及其推论（重点）习题习题3.6, 3.18, 3.19。五。五10注意1）0 是自然数是自然数.2）对于任何集合）对于任何集合 A 和元素和元素 x (可以是集合可以是集合)， x A和和x A两者成立其一，且仅成立其一两者成立其一，且仅成立其一.3） 和和 是不同层次的问题是不同层次的问题.4）空集）空集是任何集合的子集是任何集合的子集.5）在给定问题中，全集）在给定问题中，全集E包含任何集合，即包含任何集合，即 A(A E )了解概念、掌握方法了解概念、掌握方法n1）集合的表示法：）集合的表示法：列元素法列元素法A= a, b, c, d n谓词表示法谓词表示法B= x | P(x) . 习题习题3.10(4)n2）文氏图与文氏图法）文氏图与文氏图法.习题习题3.6n3）集合）集合A的基数的基数cardA=|A|=nn4）证明）证明 X Yq命题演算法命题演算法q包含传递法包含传递法q等价条件法等价条件法q反证法反证法q并交运算法并交运算法n5）证明）证明 X=Yq命题演算法命题演算法q等式代入法等式代入法q反证法反证法q运算法运算法第第4章章 二元关系与函数二元关系与函数n4.1 集合的笛卡儿积与二元关系集合的笛卡儿积与二元关系n4.2 关系的运算（重点）关系的运算（重点）n4.3 关系的性质（基础）关系的性质（基础）n4.4 关系的闭包关系的闭包n4.5 等价关系和偏序关系（重点）等价关系和偏序关系（重点）n4.6 函数的定义和性质函数的定义和性质n4.7 函数的复合和反函数函数的复合和反函数4.1 集合的笛卡儿积和二元关系集合的笛卡儿积和二元关系n1）重要概念：集合集合A与与B 的的笛卡儿积笛卡儿积A B= | x A y B .若若|A|=m, |B|=n, 则则 |A B|=mnn分配律分配律A (B C)=(A B) (A C) n (B C) A=(B A) (C A) n A (B C)=(A B) (A C) n (B C) A=(B A) (C A) nA=B= n(A C=B D) (A,B,C,D非空非空)(A=B) (C=D)n2）从）从A到到B的二元关系的二元关系R A B. AB的子集有的子集有2mn 个，个，所以所以 A到到B有有2mn个不同的二元关系个不同的二元关系.n注：笛卡儿积注：笛卡儿积不适合交换律不适合交换律和和结合律结合律.n如如R, 可记作可记作 xRy.A上重要关系上重要关系n从从A到到A的二元关系的二元关系叫做叫做 A上的二元关系上的二元关系.n空关系空关系是是 A 上的关系上的关系n全域关系全域关系EA=|xAyA=AA恒等关系恒等关系IA=|xAn小于等于关系小于等于关系 LA=| x,yAxy, A Rn整除关系整除关系DA=| x,yAx整除整除y, A Zn包含关系包含关系R =| x,yAx y, A是集合族是集合族.n类似的还可以定义大于等于关系类似的还可以定义大于等于关系, 小于关系小于关系, 大大于关系于关系, 真包含关系等等真包含关系等等.4.2 关系的运算关系的运算n逆逆R 1 = | Rn合成合成R S = | y( S R)n(1) (F G) H=F (G H)n(2) (F G) 1= G 1 F 1.n幂运算幂运算(1) R0= | xA =IAn (2) Rn+1 = Rn Rn习题习题4.13。五。五14.3 关系的性质（基础，重中之重）关系的性质（基础，重中之重）n(1)若若 xA, R, 则称则称R在在A上是上是自反自反的的.n(2)若若 xA, R,称称R在在A上是上是反自反反自反的的. n(3)若若 x y(x,yARR), 则称则称R为为A上上对称对称的关系的关系.n(4)若若 x,yA,RRx=y, 则称则称R为为A上的上的反对称反对称关系关系.n(5)若若 x,y,zA,RR R, 则称则称R是是A上的上的传递传递关系关系.n习题习题4.4关系性质判别关系性质判别自反自反反自反反自反对称对称反对称反对称传递传递表达表达式式IA RRIA= R=R 1 RR 1 IA R R R关系关系矩阵矩阵主对主对角线角线元素元素全是全是1主对角主对角线元素线元素全是全是0矩阵是对称矩阵是对称矩阵矩阵若若rij1, 且且ij, 则则rji0对对M2中中1所在位置所在位置,M中相应中相应位置都是位置都是1关系关系图图每个每个顶点顶点都有都有环环每个顶每个顶点都没点都没有环有环如果两个顶如果两个顶点之间有边点之间有边, 是一对方向是一对方向相反的边相反的边(无单边无单边)如果两点如果两点之间有边之间有边, 是一条有是一条有向边向边(无双无双向边向边)如果顶点如果顶点 xi 连通到连通到xk , 则从则从 xi到到 xk 有有边边 恒等关系恒等关系IA既是等价关系既是等价关系, 又是篇序关系。又是篇序关系。运算与性质的关系（了解）运算与性质的关系（了解）自反自反性性反自反反自反性性对称对称性性反对称反对称性性传递性传递性R1 1 R1R2 R1R2 R1 R2 R1 R2 4.5 等价关系和偏序关系（重点）等价关系和偏序关系（重点）n(1) 等价关系、等价类、商集、划分、等价关系、等价类、商集、划分、自然映射自然映射n等价关系等价关系: 同时满足自反、对称和传递的关系同时满足自反、对称和传递的关系.n若若等价关系等价关系R, 称称 x 等价于等价于y, 记做记做 xy.nx(xA)关于集合关于集合A上等价关系上等价关系R 的的等价类等价类 xR = y | yAxRy .n以集合以集合A上的等价关系上的等价关系R的所有等价类为元素的所有等价类为元素的集合称为的集合称为A关于关于R的的商集商集, 记做记做A/R.n商集商集 A/R 就是就是 A 的一个划分的一个划分;n等价关系与商集、划分一一对应等价关系与商集、划分一一对应.n习题习题4.5，4.15，4.24。五。五2；六；六14(2) 偏序关系偏序关系,覆盖覆盖,偏序集与哈斯图偏序集与哈斯图n偏序关系偏序关系：同时满足自反、反对称和传递的关：同时满足自反、反对称和传递的关系系, 记作记作 . 如果如果偏序关系偏序关系 , 则记作则记作 x y.nx y且不存在且不存在 z A 使得使得 x z y, 则称则称 y 覆覆盖盖x.n集合集合A和和A上的偏序关系上的偏序关系 一起叫做一起叫做偏序集偏序集, 记记作作 . 习题习题4.6，4.16。五。五3n哈斯图哈斯图：简化关系图。特点（注意）：每个结：简化关系图。特点（注意）：每个结点没有环，位置低的元素的顺序在前，具有覆点没有环，位置低的元素的顺序在前，具有覆盖关系的两个结点之间才连边盖关系的两个结点之间才连边.n特定元素：区分最小特定元素：区分最小(大大)元与极小元与极小(大大)元；元； n下界、上界、下确界、上确界下界、上界、下确界、上确界注意事项注意事项：特定元素：特定元素n对于有穷集，极小元和极大元必存在，可能存在多个对于有穷集，极小元和极大元必存在，可能存在多个. n 最小元和最大元不一定存在，如果存在一定惟一最小元和最大元不一定存在，如果存在一定惟一.n 最小元一定是极小元最小元一定是极小元; 最大元一定是极大元最大元一定是极大元. 反之不对反之不对.n 孤立结点既是极小元，也是极大元孤立结点既是极小元，也是极大元.n下界、上界、下确界、上确界不一定存在下界、上界、下确界、上确界不一定存在.n下界、上界存在不一定惟一下界、上界存在不一定惟一.n下确界、上确界如果存在，则惟一下确界、上确界如果存在，则惟一.n集合的最小元就是它的下确界，最大元就是它的上确集合的最小元就是它的下确界，最大元就是它的上确界；反之不对界；反之不对.4.6 函数函数n xdomF 都存在都存在唯一唯一的的yranF 使使 xFy 成成立立, 则称二元关系则称二元关系F 为为函数函数. 对于函数对于函数F, 如果如果有有 xFy, 则记作则记作 y=F(x), 并称并称 y 为为 F 在在 x 的的值值.n所有从所有从 A 到到 B 的函数的集合记作的函数的集合记作 BA, 读作读作“B上上A”，符号化表示为，符号化表示为 BA = f | f：AB n函数函数f：AB，domF=A，| f |=|A|，ranF B.n计数：计数：|A|=m, |B|=n, 且且m, n0, |BA|=nm.nB=. A, 则则 A= .n恒等函数恒等函数IA(x)=xn习题习题4.22了解n有序对有序对，有序有序n元组元组 .n关系矩阵、关系图关系矩阵、关系图; 关系的关系的定义域定义域、值域值域和和域域.习题习题4.2关系关系F 在集合在集合A上的上的限制限制F A = | xFy x A F. A在在F下的下的像像FA = ran(F A) ranF.习题习题4.3R的自反闭包的自反闭包r(R)=RR0, 对称闭包对称闭包s(R)=RR 1, 传递闭传递闭包包t(R)=RR2R3。习题。习题4.14nMr = M + E，Ms = M + M，Mt = M + M2 + M3 + n(不不)可比。可比。全序全序(线序线序)关系关系：所有元素可比；良序集：所有元素可比；良序集n单射单射, 满射满射, 双射；双射；常函数、单调函数；特征函数常函数、单调函数；特征函数.ng(a) = a是从是从 A 到商集到商集 A/R 的的自然映射自然映射.习题习题4.10,4.18n函数复合与反函数函数复合与反函数n良序集良序集：任意非空子集都有最小元素的全序集任意非空子集都有最小元素的全序集第第5章章 代数系统的一般性质代数系统的一般性质n5.1 二元运算及其性质（基础）二元运算及其性质（基础）n5.2 代数系统及其子代数和积代数代数系统及其子代数和积代数n（重要概念积代数）（重要概念积代数）n5.3 代数系统的同态与同构（重点）代数系统的同态与同构（重点）5.1 一、二元运算一、二元运算, 代数系统代数系统, 封闭性封闭性n函数函数 f：SSS 称为集合称为集合S 上的二元运算上的二元运算, 也称也称 S 对对 f 封闭封闭; 即即 x, yS, f(x, y)S.n函数函数 f：SS 称为集合称为集合S 上的一元运算上的一元运算; 即即 xS, f(x)S.n函数的性质：运算结果唯一性运算结果唯一性.n非空集合非空集合 S 和和 S 上上 k 个一元或二元运算个一元或二元运算 f1, f2, , fk 组成的系统称为一个组成的系统称为一个代数系统代数系统, 简简称称代数代数，记做，记做 V=.n习题习题5.8，5.7二元运算可能的性质二元运算可能的性质n x, y, zS(1)交换律交换律： x y = y x. n(2)结合律结合律：(x y) z = x (y z). n(3)幂等律幂等律： x x = x.n(4)消去律消去律：若：若 x y = x z, 且且x不是零元不是零元, 则则 y = z ;若若 y x = z x, 且且 x 不是零元不是零元，则，则 y = z.无零因子无零因子：( x y = x = y = ) 消去律消去律. n(1) 运算对运算对 运算满足运算满足分配律分配律：z (x y) = (z x) (z y).n(2) 和和 运算满足运算满足吸收律吸收律(前提前提 和和 都可交都可交换换) ： x (x y) = x；x (x y) = x.一些二元运算的性质一些二元运算的性质集合集合运算运算交换律交换律结合律结合律 幂等律幂等律消去律消去律Z, Q, R, C普通加法普通加法+有有有有无无有有普通乘法普通乘法 有有有有无无有有Mn(R)矩阵加法矩阵加法+有有有有无无有有矩阵乘法矩阵乘法 无无有有无无无无P(B)0, 1并并 (或或)有有有有有有无无交交 (与与)有有有有有有无无对称差对称差 ( ,) 有有有有无无有有AA函数复合函数复合 无无有有无无无无Zn模乘模乘 有有有有无无无无Z+lcm, gcd有有有有有有无无0, 1与非与非 ,或非或非 有有无无无无无无一些二元运算的性质一些二元运算的性质 集合集合 运算运算分配律分配律吸收律吸收律Z,Q, R, CMn(R)普通加法普通加法 + 与乘法与乘法 矩阵加法矩阵加法 + 与乘法与乘法 对对 + 可分配可分配无无+ 对对 不分配不分配 P(B)0, 1并并 与交与交 (或或 和与和与 ) 对对 可分配可分配有有 对对 可分配可分配交交 与对称差与对称差 (与与 和排斥或和排斥或 ) 对对 可分配可分配无无 对对 不分配不分配Zn模加 与与模乘模乘 对对 可分配可分配无 对对 不分配不分配全集全集E并并 与笛卡儿积与笛卡儿积 对对 可分配可分配无无交交 与笛卡儿积与笛卡儿积 对对 可分配可分配Z+lcm与与gcd有有有有二元运算可能的特异元素二元运算可能的特异元素n xS,(e x=x) (x e=x),称称e为为单位元单位元(幺幺元元)(惟一性惟一性). xS,( x =) (x =),称称是是零元零元(惟一性惟一性). 注注:只有左或右单位元只有左或右单位元(零零元元),不称为有单位元不称为有单位元(零元零元).n(y x=e) (x y=e), 称称y为为x的的逆元逆元, 并称并称x是是可逆可逆元素元素. 注注:逆元的存在以幺元的存在为前逆元的存在以幺元的存在为前提提.ne- -1=e. 对于可结合的二元运算对于可结合的二元运算, 可逆元素可逆元素x只只有惟一的逆元有惟一的逆元, 记作记作x 1. n习题习题5.14，5.15，5.3，5.12，5.2一些二元运算的特异元素一些二元运算的特异元素集合集合运算运算幺元幺元e零元零元逆元逆元x- -1(e- -1=e)Z,Q,R,C普通加法普通加法+ 0无无 x普通乘法普通乘法 101/ /x(x0)Mn(R) 矩阵加法矩阵加法+ 0阵阵无无 x矩阵乘法矩阵乘法 单位阵单位阵In0阵阵x 1(逆阵逆阵, x可逆可逆)P(B)0, 1并并 (或或)(0)B(1)- -1=(0- -1=0)交交 (与与)B(1)(0)B- -1=B(1- -1=1) ( )(0)无无xAA函数复合函数复合 IA无无双射逆元双射逆元=反函数反函数Zn模乘模乘 10 x, n互质互质, x有逆元有逆元模加 0无无n x(0- -1=0)Z+lcm1无无1- -1=1gcd无无1无无0, 1等价等价1无无x由运算表判别算律的一般方法由运算表判别算律的一般方法n交换律：运算表关于主对角线对称交换律：运算表关于主对角线对称n幂等律：主对角线元素排列与表头顺序一致幂等律：主对角线元素排列与表头顺序一致n消去律：所在的行与列中没有重复元素消去律：所在的行与列中没有重复元素n单位元单位元: 所在行与列的元素排列都与表头一致所在行与列的元素排列都与表头一致n零元：元素的行与列都由该元素自身构成零元：元素的行与列都由该元素自身构成nA 的可逆元：的可逆元：a 所在的行中某列所在的行中某列 (比如第比如第 j 列列) 元素为元素为 e，且第，且第 j 行行 i 列的元素也是列的元素也是 e，那么，那么 a 与第与第 j 个元素互逆个元素互逆n结合律：除了单位元、零元之外，要对所有结合律：除了单位元、零元之外，要对所有3个元素的组合验证表示结合律的等式是否成立个元素的组合验证表示结合律的等式是否成立n习题习题5.1，5.95.2 代数系统及其子代数和积代数代数系统及其子代数和积代数n重要概念：重要概念：和和是代数系统，是代数系统，积代数积代数有有： =. 题题5.10 (1) 若若 o 和和 运算是可交换的，那么运算是可交换的，那么 运算也是可交换运算也是可交换的的 (2) 若若 o 和和 运算是可结合的，那么运算是可结合的，那么 运算也是可结合运算也是可结合的的 (3) 若若 o 和和 运算是幂等的，那么运算是幂等的，那么 运算也是幂等的运算也是幂等的 (4) 若若 o 和和 运算分别具有单位元运算分别具有单位元 e1 和和 e2，那么，那么 运算运算 也具有单位元也具有单位元 (5) 若若 o 和和 运算分别具有零元运算分别具有零元 1 和和 2，那么，那么 运算运算 也具有零元也具有零元 (6) 若若 x 关于关于 o 的逆元为的逆元为 x 1, y 关于关于 的逆元为的逆元为 y 1，那，那 么么关于关于 运算也具有逆元运算也具有逆元5.3 代数系统的同态与同构代数系统的同态与同构(重点重点)nV1=和和V2=是代数系统是代数系统, f: S1S2, x, yS1, f(x y)=f(x) f(y), 则称则称f为为V1到到V2的的同态同态(映射映射).n如果同态如果同态f是满射，则称为是满射，则称为满同态满同态，这时称，这时称V2是是V1的的同态像同态像，记作，记作V1 V2；n如果同态如果同态f是双射，则称为是双射，则称为同构同构，记作，记作V1 V2.n习题习题5.6，5.5。六。六13，15满同态保持运算的算律及特异元素满同态保持运算的算律及特异元素V1 =和和V2=是代数系统是代数系统，f： V1V2是满同态，那么是满同态，那么 (1)若若o运算是可交换的（可结合、幂等的），则运算是可交换的（可结合、幂等的），则o运算运算也是可交换的（可结合、幂等的）也是可交换的（可结合、幂等的）.(2) 若若o运算对运算对 运算是可分配的，则运算是可分配的，则o运算对运算对 运算运算也是可分配的；若也是可分配的；若o 和和 运算是可吸收的，则运算是可吸收的，则 o和和 运算也是可吸收的。运算也是可吸收的。(3) 若若e为为o 运算的单位元，则运算的单位元，则 f(e)为为o运算的单位元运算的单位元.(4) 若若 为为o 运算的零元，则运算的零元，则 f( ) 为为o运算的零元运算的零元.(5) 设设 u V1，若，若 u 1 是是 u 关于关于o运算的逆元，则运算的逆元，则 f(u 1) 是是 f(u)关于关于o运算的逆元。运算的逆元。注意事项注意事项n1）集合集合S 上的二元运算就是上的二元运算就是SSS的二元函的二元函数数. 集合集合S 上的一元运算就是上的一元运算就是SS的一元函数的一元函数.n2）e- -1=e. 当当 |S| 2，单位元与零元是不同的，单位元与零元是不同的，零元无逆元；当零元无逆元；当 |S| = 1 时，这个元素既是单位时，这个元素既是单位元也是零元元也是零元.n3）子代数）子代数B 和原代数和原代数S 含有相同的代数常数含有相同的代数常数n4）同态映射保持运算的算律及特异元素）同态映射保持运算的算律及特异元素仅在仅在满同态时成立，如果不是满同态，那么相关性满同态时成立，如果不是满同态，那么相关性质在同态像中成立质在同态像中成立. n同态映射不一定能保持消去律成立同态映射不一定能保持消去律成立.了解n运算表n代数系统的代数系统的载体载体，成分，代数常数，成分，代数常数n同类型与同种代数系统同类型与同种代数系统n子代数和原代数是同种的代数系统子代数和原代数是同种的代数系统n最大的子代数最大的子代数 就是就是V 本身本身. 代数常数代数常数(对运对运算封闭算封闭)构成构成最小的子代数最小的子代数. 最大和最小子代最大和最小子代数称为数称为平凡的子代数平凡的子代数. 真子代数真子代数. 习题习题5.4n零同态零同态、单单(自自)同态同态、 (满满)自同态自同态和和自同构自同构.第第6章章 几个典型的代数系统几个典型的代数系统n6.1 半群与群半群与群n6.2 环与域（环与域（“域域”是重点）是重点）n6.3 格与布尔代数（格与布尔代数（“布尔代数布尔代数”是重点）是重点）6.1 (半半)群群|S|2封闭性结合律含幺所有元有逆元交换律=az消去律含零代数系统半群交换半群独异点群Abel群循环群重要概念：循环群，重要概念：循环群，n元置换群。元置换群。(半半)群群实例实例(1),交换半群交换半群,不含幺不含幺; ,交换半群交换半群,含幺含幺半群半群,非群非群; ,都是都是交换群交换群; ,都是交换半都是交换半群群,含幺半群含幺半群,非群非群; ,都是都是交换群。交换群。+是普通加法是普通加法,*是普通乘法是普通乘法. (2)是交换群是交换群; 是含幺半是含幺半群群,非交换。非交换。+和和 分别表示矩阵加法和乘法分别表示矩阵加法和乘法.(3),为交换半群为交换半群,含幺半含幺半群群,非群非群; 为交换群。并为交换群。并 ,交交 ,对称差对称差.(4)为交换群为交换群; 为交换半群为交换半群,含幺半含幺半群群,非群非群; (n为素数为素数)为交换群。模加为交换群。模加,模乘模乘(5)为含幺半群为含幺半群,非交换非交换, 为函数复合为函数复合.n元对称群及其子群元对称群及其子群n元置换群元置换群为为(非交换非交换)群群.注：注： Q*, R*, C*, Zn*不含不含0；Zn=0,1, , n 1.习题习题6.2，6.4，6.8掌握重要概念，了解性质掌握重要概念，了解性质设设G为群，为群，aG，令，令H=ak | kZ，则，则H是是G的子群，的子群，称为由称为由a生成的子群，记作生成的子群，记作.设设G是群，若存在是群，若存在aG使得使得G=ak | kZ，则称，则称G是是循循环群环群，记作，记作G=，称，称a为为G的的生成元生成元. 习题习题6.5，6.9(1)若若G=是无限循环群，则是无限循环群，则G只有只有a和和a 1两个生成元两个生成元. (2)若若G=是是n阶循环群，则阶循环群，则ar是是G的生成元当且仅当的生成元当且仅当r是小于等于是小于等于n且与且与n互质的正整数互质的正整数.(1) 设设G=是循环群，则是循环群，则G的子群仍是循环群的子群仍是循环群.(2) 若若G=是无限循环群，则是无限