离散数学（全套ppt课件）.ppt

离散数学,第一章 集合论初步,1 集合论基础,1.1 关于集合的概念,集合：一些不同的确定的对象的全体。元素：构成集合的对象。 如：（1）全班同学 （2）计算机内存的全部单元 集合用大写字母表示，如A,B,C；元素用小写字母表示，如a,x,y。,集合A元素的个数称为A的基数，记为|A|。,Note:,1集合中的元素是确定的。,2 集合中的每个元素均不相同。,如：a,b,c,d 和a,b,b,c,d 是相同的。,3集合中元素具体不作限制,如: a,b,a,b,相关概念：,有限集无限集空集 （元素个数为零）全集（包含所有研究问题的对象全体的集合，用E表示）,集合的表示方法：,（1）枚举法,即全部列出来。 A=1,2,3,20,（2）描述法,A=x|p(x)，p表示某性质， 如：A=x|x+50,xR,1.2 集合间的关系,如果集合A与集合B的元素相同，则称两个集合相等，记为A=B。,（否则，称为不相等，记为A B。）,定义1、,Note:对于相等关系和包含关系，可用文氏图（venn diagram) 表示:,例2、A=1,2,3,3，B=1,2,3，则A=B。,例3、设P=x|(x+1)2 4, Q=x|x2+16 5x，求P,Q间的关系。,1.3 集合代数,用代数的方法讨论集合，建立集合的一些运算。,定义3 并集：由集合A、B所有元素合并组成的集合，记为AB。 即A B=x|xA或xB,定义4 交集：由集合A、B所有的公共元素所组成的集合。AB=x|xA且xB,定义5 分离：AB= ,定义6 差集：属于集合A而不属于B的元素所组合成的集合。 A-B=x|xA且x B,例：A=a,b,c,d,e,，B=d,e,f,g,h，则 A-B=a,b,c,定义7、补集：A=E-A,定义8、对称差（或称布尔和）： A+B=(A-B)(B-A) = AB-AB,例: (上例中）A+B=a,b,c,f,g,h至此，定义了五种运算：并，交，差，对称差，（二元）和补（一元）。,1.4 集合代数的基本公式,1 交换律 AB=BA; AB=BA.,2 结合律 A(BC)=(AB)C A(BC)=(AB)C,3 分配律 A(BC)=(AB) (AC) A(BC)=(AB) (AC),4 同一律 A=A AE=A,5 零一律 AE=E A=,7 等幂律 AA=A AA=A,8 吸收律 A(AB)=A A(AB)=A,6 补余律 AA=E AA=,9 狄-莫根定律(De Morgens Law) (AB)=AB (AB)=AB,例：设M=x|f1(x)=0,N=x|f2(x)=0,则方程f1(x)*f2(x)=0的解为( )。,(1)MN (2)M (3)MN (4)N,答案: (3),例：设A=,B=,则B-A是( ),(1) (2) (3), (4) ,答案: (3),1.5 有限集的基数,定理1 A、B为有限集，则,定理2 A、B、C为有限集，则,例：P44例4.4,2 幂集，n重有序组及笛卡尔乘积,2.1 幂集,定义： 由集合A的所有子集（包括空集及A本身）所组成的集合叫A的幂集，记作2A 或(A)。,例：A=1,2,3,则(A)=，1，2，3，1，2，1，3，2，3，A。,定理：若集合A为有n个元素所组成的有限集，则(A)为有限，且由2n 个元素组成。,2.2 n重有序组,定义: 两个客体a,b按一定次序排列，组成一个有序序列，叫做有序偶，记作(a,b)。,Note: (a,b)一般不与(b,a)相等，如在坐标中，可用一个有序偶来表示一个点，有(1,3) (3,1)。,定义: 有序偶(a,b)和(c,d)，如果有a=c,b=d,则说(a,b)和(c,d)相等。,定义: n个(n1)客体a1 ,an 按一定次序排列，构成一个有序序列，叫做n重有序组，记以(a1 ,an ),2.3 笛卡尔乘积,定义: 集合A,B的笛卡尔乘积定义为： AB=(a,b)|a A,b B,例：平面直角坐标系中的所有点可用一笛卡尔乘积表示：R R=(x,y)|xR,yR,定义7：集合A1 ,A2 ,An 的笛卡尔乘积定义为：A 1 A 2 An=(x1 ,xn )|x1A1 ,xn An,例：设A=1,2,B=a,b,A=,，则： AB=(1,a),(1,b),(2,a),(2,b) ABC=(1,a,),(1,a, ),(1,b,),(1,b,), (2,a,),(2,a,),(2,b,),(2,b,),例：设A=1,2 ,则 A 2= (1,1),(1,2),(2,1),(2,2),3 无限集,定义1. 集合A与B的元素间如果存在一一对应的 关系，则称A与B是等势的。记以A B。,对于有限集：AB A、B元素个数相等。 如 1，2 3，4 ,对于无限集：AB 存在A B的一一 映射f 。,3.1 无限集的性质,例1.自然数集N=0，1，2，3与其子集 S=1，3，5，均为无限集。, NS,例2. 设A=（ 0, 1 ）, B=（ 0, 2 ）。构造一个从 A到B的一一映射函数，以说明A B。,解：令 f (x) = 2x（ x（0，1），则 f (x) 为一一映射函数，且Df =（0，1）， Cf =（0，2）。 A B 。,定理1. 一集合为无限集，则它必含有与其等势 的真子集。,推论：一集合为无限集它含有与其等势的真子集。,定义2. 一集合若存在与其等势的子集，则该集合称为无限集，否则称为有限集。,定义3. 凡与自然数集N等势的集合叫可列集。,定理2. 一无限集必包含一可列集。,定理3. 可列集的无限子集仍为一可列集。,定理4. 整数集I为可列集。,证：即要证明IN。为此建立一一对应关系如下：,定理5. 有理数集Q为可列集。,3.2 无限集的基数,有限集：集合A的基数|A|表示元素的个数。,令|N|= 0（Aleph） 。则由可列集的定义知，所有可列集的基数均为 0 。,对于无限集，若AB，则|A|= |B|，认为A、B“大小”相等。故N是“最小”的无限集。,定理1. 实数集R是不可列的。,由以上可得到关于无限集的大小： （1）无限集也有大小，最小的无限集为可列集，其次是实数集，等等。 （2）无限集的“大小”也是无限的，即对任意集合，总存在比其基数更大的集合。,德国数学家康托尔（Cantor）证明，|(A)|A|。此外，他还认为：,结论 1. 两个可列集之并仍为可列集。,2. 可列个可列集之并仍为可列集。,第二章 关系与映射,1 关系的基本概念,1.1 关系及其定义,例1：讨论旅馆的“某旅客住在某房间”关系，记为R,设有3各房间，一个房间可住2人。 旅客与房间之间关系示意图如下：,从图上可看出；a与1存在关系R，记为aR1;同理有bR1, cR2, dR2, eR3, fR3.,Note:,1满足R的关系pRq可看成是一个有序偶: (p, q), 如aR1可写成（a, 1）. 2满足R的所有关系可看成是一个有序偶的集合，即 R=(a,1), (b,1), (c,2), (d,2), (e,3), (f,3) 关系是一些有序偶的集合。 3令A=a, b, c, d, e, f, B=1, 2, 3.则:AB=(a,1), (b,1),(c,1), (d,1), (e,1), (f,1),定义1：从集合A到集合B的一个关系R是 AB的一个子集。,定义2：当A=B时，则A到B的关系称为集合A上的关系。 例2：给定集合A=0, 1, 2, 3, 4, 令R=(0,1), (0,2), (0,3), (0,4), (1,2), (1,3), (1,4), (2,3), (2,4), (3,4) 则R为集合A上的“小于”关系，即（x, y）R表示xy.,例3：给定集合B=2,3,4,8,求集合B上的“整除”关系。解：R=(2,2), (3,3), (4,4), (8,8), (2,4), (2,8), (4,8)定义3: 空关系: 若集合X到集合Y不存在某种关系R，则称此种关系为空关系。定义4: 全关系: 若X的每个元素到Y的每个元素均具有某种关系，则称此关系为全关系。 X到Y的全关系即为 XY.,定义5: n元关系: 由集合X1,X2,，Xn所确定的n元关系是X1X2Xn的一个子集。,1.2 关系的图形表示和矩阵表示,一个从X到Y的关系R可用图形或矩阵表示。,1.2.1 图形表示 先用结点把X和Y的元素表示出来,若xi R yj (xi X, yj Y), 则用一带箭头的线段把xi和yj连接起来。,例4: X=x1,x2,x3, Y=y1,y2,y3,R为X到Y的一个关系，R=(x1,y1), (x1,y2), (x2,y2), (x2,y3), (x3,y3), (x3,y1)。则其图形表示如下,Note: 集合X上的关系亦可用关系图表示.,例5: S=a, b, c,令R1=(a, b), (b, c), (c, a), R2=(a, a), (a, b), (a, c),则,R1的关系图,R2的关系图,注:上述关系可理解为程序调用关系，如R2表示a递归调用, a调用b, a调用c.,a,c,b,a,b,c,设X元素个数为m, Y元素个数为n, 则X到Y的关系的表示矩阵:,若(xi ,yi) R,如例4中，,1 1 0,0 1 1,1 0 1,1.2.2 矩阵表示,MR=(aij)mn=,MR=,例4: X=x1,x2,x3, Y=y1,y2,y3,R为X到Y的一个关系，R=(x1,y1), (x1,y2), (x2,y2), (x2,y3), (x3,y3), (x3,y1)。,0 1 0,0 0 1,1 0 0,MR1=,1 1 1,0 0 0,0 0 0,MR2=,例5中，,例5: S=a, b, c,令R1=(a, b), (b, c), (c, a), R2=(a, a), (a, b), (a, c),2 关系的运算,2.1 关系的交、并、补、差 由于关系是一些有序偶的组成的集合，故有关集合的运算关系仍适用。,例1:X=a, b, c, Y=1, 2; X到Y的关系R=(a, 1), (c, 2), S=(a, 2), (b, 1), (c, 2),(a, 2), (b, 1), (b, 2), (c, 1),则 RS=(c, 2),(注：E=XY),2.2 复合关系2.2.1 复合关系的定义定义1: 设R是一X到Y的关系，S是一Y到Z的关系，则R与S的复合关系ROS可定义为: ROS=(x, z)| x X, z Z, 且存在y Y, 使 (x, y) R, 且(y, z) S,例2: 给定集合A=1, 2, 3, 4, 5及A上的二个二元关系R=(1, 2), (3, 4), (2, 2),S=(4, 2), (2, 5), (3, 1),(1, 5), (3, 2), (2, 5),(4, 2), (3, 2),(4, 5),=(1, 2), (2, 2),则ROS=,SOR=,SOS=,ROR,2.2.2 复合关系的图形与矩阵表示例3: 设X=x1, x2, x3, Y=y1, y2, y3, Z=z1, z2, z3,从X到Y的关系R=(x1, y1), (x1, y2), (x2, y2) ,从Y到Z的关系S=(y1, z2), (y2, z3), (y3, z3) 则ROS=(x1, z2), (x1, z3), (x2, z3)用关系图表示如下：,ROS的矩阵MRS=MRMS (其中” ”运算为布尔矩阵乘法，即,定理1: 设R, S, T分别表示从X到Y, Y到Z，Z到U的关系，则有 (ROS) OT=RO (SOT),则MRS=MRMS =,2.3 逆关系 定义：R为X到Y的关系，则Y到X的关系:R-1:=(y, x)| (x, y) R 称为R的逆关系。,例:设X=1, 2, 3. Y=a, b, c R为从X到Y的关系， R=(1, a), (2, b), (3, c),定理2:设R, S分别为从X到Y, Y到Z的关系，则,(a, 1), (b, 2), (c, 3),则 R-1 =,3. 关系的某些性质,例1: 实数集R上的”关系是自反的。例2: 实数集R上的”关系是反自反的。,Note: 自反=不是反自反. 反自反=不是自反.,自反的。,反自反的。,两条即说明,存在既不是自反,又不是反自反的关系.例3: X=1, 2, 3, 4上的关系R R=(1, 1), (1, 2), (3, 4), (2, 2)则R既不是自反的，也不是反自反的。定义3: 集合X上的关系R，如果有(x, y) R, 必有(y, x) R,则称R是对称的。,反对称的。,例4：集合X=1, 2, 3, 4上的关系 R1=(1, 2), (2, 1) R2=(1, 2), (2, 4), (3, 2) R3=(1, 2), (2, 1), (3, 4), (4, 2)则: R1是对称的，R2是反对称的，R3既不是对称的，也不是反对称的。,定义3: 集合X上的关系R，如果有(x, y) R且(y, z) R, 必有(x, z) R, 则称R是传递的。,Note: 从关系图及关系矩阵来判断关系的性质,例6 (P22. 例2.20),例7 整数集I上定义一个关系R,试验证R具有哪几种性质。,4 关系的闭包运算,定义1 设 R 是集合X上的一个关系，则R的自反闭包是一个满足下列条件的关系 R:,（1） R是自反的；,思考：若R是自反（对称、传递）的，则其自反（对称、传递）闭包是？,“”关系；,对称闭包是,“”关系；,例1 整数集I 上的“”关系的自反闭包是,传递闭包是,本身.,定理1 设R是集合X上的关系，则,例2 设有程序集P=p1, p2, p3, p4及其上的“调用”关系：R=(p1, p2), (p1, p3), (p2, p4), (p3, p4)。Q=(p1, p1), (p2, p2), (p3, p3), (p4, p4),定理2 设R是集合X上的关系，则,解：由关系图 R=(a, a), (a, b), (a, c),定理3 设R是集合X上的关系，则,定理4 设R是有限集合X上的关系，并设X有n个元素，则有,解：(1),例3 设S=a, b, c, d, 给定S上的一个关系 R=(a, b), (b, c), (c, d), (d, a)求r (R), s (R), t (R).,Q=(a, a), (b, b), (c, c), (d, d), r (R)=RQ=(a, b), (b, c), (c, d), (d, a), (a, a), (b, b), (c, c), (d, d),解： （2）,例3 设S=a, b, c, d, 给定S上的一个关系 R=(a, b), (b, c), (c, d), (d, a)求r (R), s (R), t (R).,解： （3）,例3 设S=a, b, c, d, 给定S上的一个关系 R=(a, b), (b, c), (c, d), (d, a)求r (R), s (R), t (R).,R2=ROR=(a, c), (b, d), (c, a), (d, b) R3=R2 OR=(a, d), (b, a), (c, b), (d, c) R4=R3 O R=(a, a), (b, b), (c, c), (d, d)t (R)=RR2R3R4=(a, a), (b, b), (c, c), (d, d), (a, b), (a, c), (a, d), (b, c), (b, d), (c, d), (d, c), (d, b), (d, a), (c, b), (c, a), (b, a),5 次序关系,定义1 集合X上的关系R如果是自反的、反对称的、传递的，则称R是X上的偏序关系，称X为R的偏序集，记为(X,R).,Note: 用“”表示偏序 （不作特殊说明）,例2 整数集I上的“”(不是偏序关系的符号) 是偏序关系。,例3 集合X=2, 3, 6, 8上的整除关系 R=(2, 2), (3, 3), (6, 6), (8, 8), (2, 6), (2, 8), (3, 6) 是偏序的.,定义2 集合X上的关系R如果是反自反的、传递的，则称R在X上是拟序的，或称R是X上的拟序关系。,Note: 拟序关系一般用“”表示.,定理1 集合X上的关系R是拟序的，则其必反对称.,定理2 设R是X上的关系，则 （1） 若R是一个拟序关系，则r (R)是一个偏序关系. （2） 若R是一个偏序关系，则R-Q是一个拟序关系.,定义3 “”是集合X上的偏序，若 x, y X，都有xy或y x.则称“”是X上的线性次序关系。,例6 集合X=a, b, c上的关系 R=(a, b), (b, c), (a, c), (a, a), (b, b), (c, c) 则 R首先是一个偏序关系； R是一个线性次序关系。,(a, b两元素之间不存在“ ”关系.),不是线性次序的.,例7 集合A=a, b, (A)=, a, b, a, b,(A)上的“ ”关系，,定义4 “”为集合X上的偏序关系，且Y X,（2） yY，且不存在yY， 有y y且 yy，则称y是Y的极大元素；若有yy，则称y是Y的极小元素。,（1） yY，使 yY， 均有yy，则称y是Y 的最大元素；若有yy，则称y是Y的最小元素。,Note:最大(小)元素、极大(小)元素只在Y中讨论.上(下)界、上(下)确界在X中讨论. 上、下界可能不唯一.,（4）若 xX是Y的上(或下)界 ，且对每一个Y 的上(或下)界 x，均有xx(或xx)，则称x是Y的上确界（或下确界）。,（3） xX，使 yY， 均有yx，则称x是Y 的上界；若有xy，则称x是Y 的下界。, B=a, b, b, c, b, c, ，则B的,例8 集合A=a, b, c，(A)= , a , b , c , a, b, a, c, b, c, a, b, c上的“ ”关系是一个偏序关系,(4) 极小元:,(1)最大元 :,没有,(2) 最小元:,(3)极大元:,(5) 上界:,a, b, c,(6) 下界 :,(7)上确界:,a,b, c,(8)下确界 :,a,b, b,c,若B=a, c, 则它的,(4) 极小元:,(1)最大元 :,没有,(2) 最小元:,(3)极大元:,(5) 上界:,(6) 下界 :,(7)上确界:,a,c,(8)下确界 :,a, c,没有,a, c,a, c, a, b, c,定理3 “”是X上的一个偏序关系，且Y X,（1） 最大(小)元 = 极大(小)元（2） 最大(小)元 = 上(下)确界（3） x是上(下)确界,且x Y = x是最大(小)元,方法：X上的偏序关系” ” 若x y且不存在zX使xz, z y,则将结点x画在y的下面；且用一线相连. 若x, y不存在关系，则放在同一水平线上，不用线相连.,哈斯图分析偏序关系,例9 X=2, 3, 6, 12, 24, 36上的整除关系,由哈斯图可看出，子集Y=2, 3, 6的,最大元：,最小元：,6,无,极大元：,6,极小元：,2,3,上界：,6,12,24,36,上确界：,6,下界：,无,下确界：,无,作业：P34 2.7(1)、(2) 2.8 (3) 补充：设A= , a , b , a, b上的关系“ ”. （1）画出哈斯图； （2）求子集B1= , a 和B2= a , b的最大元、最小元、极大元、极小元、上界、下界、上确界、下确界,6 相容关系,定义1 集合X上的关系R，如果它是自反的、对称的，则称此关系为相容关系.一般用“”表示相容关系.,例1 X=2166,243,375,648,455,关系R为元素间有相同的数字 如(2166, 243) 则R是相容关系, 相容关系的关系图由于边均是双向边，且各点均有环出现，故可简化. (具体方法：去掉环 双向有向边单向无向边),如例1中,x1,x2,x3,x4,x5,关系矩阵为对称矩阵且主对角元为1.(故可简化为下三角.),X=2166,243,375,648,455,关系R为元素间有相同的数字,Note:,X=2166,243,375,648,455,关系R为元素间有相同的数字,例2 例1中,定义2 “”为集合X上的相容关系且A X，如果 x、yA，均有xy，且 zXA，使 xA均有xz，则称A是X的极大相容性分块。,极大相容性分块在关系图中找“最大完全多边形”. 最大完全多边形：任何两顶点之间均有边相连，且不能再行扩充.,x1, x2, x4为X的一个极大相容性分块.,例3：X=1,2,3,4,5上的相容关系R的关系图如下:,则R的极大相容分块为,2,3,4,5和1,3,4,例4 X=x1, x2, x3, x4, x5, R1和R2为X上的相容关系，其简化图如图a, b所示，求R1和R2的极大相容性分块.,解 R1：x1, x2, x5, x2, x3, x4, x5 R2：x1, x2, x4, x2, x3, x4, x3, x4, x5例5 （P30. 例2.44）,定义3 X上的相容关系“”由它的所有极大相容性分块所构成的集合成为X的完全覆盖.,例6 例3中的完全覆盖是,定理1 X上的每个相容关系，唯一的定义一个完全覆盖.,2，3，4，5，1，3，4, 7 等价关系,定义1 集合X上的关系R，如果它是自反的、对称的、传递的，则称此关系为等价关系.,例1 信息管理专业学生集上的“同姓关系”. 全校学生集合上的“同班同学”关系. 所有三角形组成集合上的“相似”关系. 52张扑克牌中的同花关系,例2 整数集I上的关系R： R=(x, y)| x-y可被3整除 讨论R是否为等价关系。,例3 整数集I上的关系R: R=(x, y)| (x-y)能被m整除, m为正整数称此关系为以m为模的同余关系. x R y, 记作 xy (mod m),定义2 S 是一个集合，A1, A2, , Am是它的子集。若它们满足:（1）所有Ai均是分离的, 即AiAj= (i j),则集合A=A1, , Am称为S的一个划分.而Ai称为块.,定义3 R为集合X上的等价关系， x X，称集合xR= y| yX, 且xRy 为x对于R的等价类.,Note：关于等价类的几个性质 xxR 若yxR,则yR=xR, 若y xR, 则yR与xR分离,定理1 集合X上的等价关系所构成的类产生X的一个划分.,例4 (例2)中以3为模的同余关系 R=(x, y)| x, y I且x-y都被3整除 为整数集I上的等价关系. 求R所构成的等价类 及商集 I/R.,此划分称为X关于R的商集,记以X/R,0R=,-6,-3,0,3,6,1R=,-5,-2,1,4,7,2R=,-4,-1,2,5,8,0R, 1R, 2R为R所构成的等价类.I/R=0R, 1R, 2R,例5 X=0,1,2,3,5,6,8, R为X上的以3为模的同余关系.,其关系图如下：,由关系图求等价类,由关系图求等价类即为在图中找分离的完全图.故R有三个等价类 0R=0,3,6; 1R=1; 2R=0,3,6,例6 设S=1,2,3,4,5的一个划分C=1，2，3，4，5.求由划分C所确定的S上的一个等价关系. 解：R1=C1C1=(1,1) R2=C2C2=(2,2), (2,3), (3,2), (3,3) R3=C3C3=(4,4), (4,5), (5,4), (5,5), 8 映射,一、映射的概念,一般定义：有集合X和Y，存在对应关系f : XY，使X的任一元素x能与Y中唯一的元素y对应，则该关系称为从X到Y的映射（或函数）。x称为原像， y称为像。,另一定义：有集合X和Y，f 为 XY的关系，若 x X，存在且唯一存在yY，使(x,y) f，则称f为从X到Y的映射（或函数）。,二、映射的分类,1、以原像是否唯一划分,2、以每个像是否均有原像划分,三、几种特殊的映射,1、一一映射：一对一的满设,2、变换：若X=Y， f 为 XY的一一映射，则称f 为X上的变换。,3、恒等变换：称f 为X上的变换，且 f(x)=x ( x X) 。,第三章 关系与映射 （复习）,关系,第三章 无限集,定义1. 集合A与B的元素间如果存在一一对应的 关系，则称A与B是等势的。记以A B。,对于有限集：AB A、B元素个数相等。 如 1，2 3，4 ,对于无限集：AB 存在A B的一一 映射f 。,3.1 无限集的性质,例1.自然数集N=0，1，2，3与其子集 S=1，3，5，均为无限集。, NS,例2. 设A=（ 0, 1 ）, B=（ 0, 2 ）。构造一个从 A到B的一一映射函数，以说明A B。,解：令 f (x) = 2x（ x（0，1），则 f (x) 为一一映射函数，且Df =（0，1）， Cf =（0，2）。 A B 。,定理1. 一集合为无限集，则它必含有与其等势 的真子集。,推论：一集合为无限集它含有与其等势的真子集。,定义2. 一集合若存在与其等势的子集，则该集合称为无限集，否则称为有限集。,定义3. 凡与自然数集N等势的集合叫可列集。,定理2. 一无限集必包含一可列集。,定理3. 可列集的无限子集仍为一可列集。,定理4. 整数集I为可列集。,证：即要证明IN。为此建立一一对应关系如下：,定理5. 有理数集Q为可列集。,3.2 无限集的基数,有限集：集合A的基数|A|表示元素的个数。,令|N|= 0（Aleph） 。则由可列集的定义知，所有可列集的基数均为 0 。,对于无限集，若AB，则|A|= |B|，认为A、B“大小”相等。故N是“最小”的无限集。,定理1. 实数集R是不可列的。,由以上可得到关于无限集的大小： （1）无限集也有大小，最小的无限集为可列集，其次是实数集，等等。 （2）无限集的“大小”也是无限的，即对任意集合，总存在比其基数更大的集合。,德国数学家康托尔（Cantor）证明，|(A)|A|。此外，他还认为：,结论 1. 两个可列集之并仍为可列集。,2. 可列个可列集之并仍为可列集。,2. 可列个可列集之并仍为可列集。,第四章 代数系统,代数系统(或代数结构)，主要研究各种抽象的运算系统。 这些抽象的代数系统主要有群、环、域和格等。,1 代数系统的基本概念,1.1 代数系统的一般概念,定义1：满足下面三个条件的系统称为代数系统： 系统有一非空集合S； 系统有一些建立在S上的运算； 运算在S上封闭。, 封闭： x, y S , x y S, 则称运算“ ”在S 上的封闭。,Note 运算具有广泛性和抽象性， 如、逻辑运算、求余等； 运算可以有一个、两个、多个；可以是一元、二元、多元；,例1：整数集I，运算为普通加法“”，则（I，）为代数系统。,例2：(A)上的集合运算“ ”、“ ”，构成一个 代数系统： （(A) ， ， ）。,例3：自然数集N及其上的运算“”、“”运算不构成代数系统（ “” 在N上不封闭。）,例4： 集合X：由字母构成的所有字符串（包括空串） 运算：字符串的连接“ ”。 则（ X ， ）为一代数系统。,定义2：相同个数的运算符，且各相对应的运算符有相同的元数，这样的代数系统称为有相同的类型。,如：例1，例4具有相同的类型，而例1，例2的类型不同。,定义3：设（S， ）和（S ，）是两个代数系统，若,则称(S, *)是（S， ）的子系统（或子代数）,例5：偶数集E，则（E,）是（I，）的子系统。,1.2 代数系统常见的一些性质,1. 结合律,并不是所有的代数系统的都满足结合律，如（I，）,2. 交换律,如（I ，），但方阵集合M上的矩阵乘法运算（M，）不满足交换律。,3. 分配律,4. 单位元,例6： （R ，） 关于“”的单位元：,0,1,关于“”的单位元：,5. 零元素,例7： （I，）,关于“”的零元:,无；,0。,关于“”的零元:,6. 逆元素,1.3 同构与同态,1.3.1 同构,这两个代数系统：,(1) 同一类型的；,(1) 结合律,同构映射使代数系统保持6条性质：,（2） 交换律,（3）单位元存在性,（4） 逆元素,（5） 零元素存在性,(6) 分配律,定理9. 代数系统间的同构关系是等价关系。,由此定理可知：,1.3.2 同态,注：,定义10. 满同态：g为满射，g(X)=Y。,还有自同态，自同构的定义。,例14. 代数系统（I，）与（I，）,例15. 证明代数系统（N ，）和（N ，）同态。,分析,同构，同态，满同态在性质传递上的区别,同构：保持，双向,2 半群与单元半群,例1. 代数系统(I , +)是一个半群， 而且可换； 而(I , -)不是半群。,例2. 代数系统(R , max)为半群，且为可换。,2.1 半群,返回,同理可定义有集合M生成的半群，M称为生成集。,例4 代数系统（I+，+） 是循环半群，生成元为1。,例5 例3中的代数系统 是循环半群，生成集为a,b。(p=ab, q=aa),定理2 循环半群一定是可换半群。,证：设（S, )是一循环半群，生成元为a，,定理3 由一个半群的任一元素a的所有的幂组成的集合M为一个由a生成的循环子半群。,证：设（S, )是一循环半群，M=a,a2,a3,故为子半群。,又（M，o)显然为由a生成的循环半群，故得证。,2.2 单元半群,定义4 若半群(M，o)存在单位元，则称 (M，o)为 单元半群 。,例6. (I , +)和(I , )都是半群，且都有单位元（分别为0和1），故均是单元半群，且可换！,例7. X*：字母串集合，“o” 表示字母串的连接，则(X*, o) 是一个单元半群，单位元为空串。 但不可换！,(I+ , +),不是单元半群,例8. R为以m为模的同余关系,令,定义 Zm 上的两个运算m 和 m ：,则 (Zm , m)和 (Zm , m)均是单元半群，单位元分别为0R和1R,定理4 一个有可数个元素的单元半群的运算组合表每行（列）内容均不全同。,证：设（M, )是一单元半群，M=e, a, b, c,d, ,则各行的第一个元素两两不同，各列的第一个元素也不同。,例9. (A , *) 是代数系统，“*”运算如下表,(A , *) 的单位元是a，且可验证“*”满足结合律，故是单元半群，各行（列）不同。,定义5 (M, o)是一个单元半群， (M , o)是其子系统，若 e M ，则(M , o)也是单元半群，称为(M, o)的子单元半群。,同理：循环单元半群的定义,例10. 一个可换单元半群的所有等幂元构成一个子单元半群。,证明：设(M, o)是一个单元半群， M为其所有等幂元构成的集合。（1）首先证(M , o)是代数系统，即证封闭：（2）再证e M（3）由定义（10）得证。,3 群论,3.1 群的定义和性质,3.2 变换群,3.3 有限群,3.4 循环群,3.5 子群,3.1 群的定义和性质,定义1 一代数系统(G， o)，若其满足： （1）结合律 （2）存在单位元 e,则代数系统(G， o)称为群。,3.1.1 群的定义,例1. (I , +)是群。,例2. (I , )是单元半群，但不是群。,定义2 若群满足交换律，则称为可换群（或阿贝尔群）。,定义3 一个群(G， o)，如果它的子代数(H， o)也是群，则称为(G， o)的子群。,定义4 相关概念：有限群、无限群、群的阶。,例3、G=2m3n | m，nI，：普通乘法，证明（G，）是群 。,3.1.2 群的性质,群(G， o)， a,b,cG，有,(1) 群满足消去律，即,(3) 群中只有单位元是等幂元素。,由性质(4)、(5)可得群的另一个定义。,定义6,3.1.3 群的同构,证 结合律，单位元，逆元性质均保持。,定义7,定理1,3.1 群的定义和性质,3.2 变换群,3.3 有限群,3.4 循环群,3.5 子群,3.2 变换群,定义9. 集合S上的若干个变换与复合运算若构成群，则 称为变换群。,定义10.,例5. S=1,2,3, 求S的对称群。,例6 群(S , )的运算表为,3.1 群的定义和性质,3.2 变换群,3.3 有限群,3.4 循环群,3.5 子群,3.3 有限群,3.3.1 有限群的另一定义,3.3.2 有限群的群表,群的运算组合表称为群表。, 可换群的群表为对称阵。,解：,3.1 群的定义和性质,3.2 变换群,3.3 有限群,3.4 循环群,3.5 子群,3.4 循环群,例9. 判断群(A , )是否为循环群,其中A=a,b,c,d , 运算表为：,3.1 群的定义和性质,3.2 变换群,3.3 有限群,3.4 循环群,3.5 子群,3.5 子群,3.5.1 子群的充要条件,3.5.2 子群的陪集,（1）右陪集关系,考虑整数加群（I,+）上的模3同余关系R，它将I分成3个等价类：,0R=，-6, -3, 0, 3, 6，,1R=，-5, -2, 1, 4, 7，,2R=，-4, -1, 2, 5, 8，,令H=3*i| iI ，则易证（H,+） 是（I,+）的子群,进一步，任意 (a,b) R 则必有a-b H，即a b-1 H,3.5.2 子群的陪集,定义：群(G, )及其子群 (H, )，R是G上的一个关系，若,则此关系称为G上的右陪集关系。记为,定理：右陪集关系是一个等价关系。,3.5.2 子群的陪集,定义：群(G, )的子群 (H, )所确定的右陪集关系对G所划分的等价类，称为(H, )的右陪集。 包含元素a的右陪集记为Ha.,（2）右陪集,3.5.2 子群的陪集,（3）左陪集关系与左陪集,定义：群(G, )及其子群 (H, )，R是G上的一个关系，若,则此关系称为G上的左陪集关系。,定理：左陪集关系是一个等价关系。,3.5.2 子群的陪集,（3）左陪集关系与左陪集,定义：群(G, )的子群 (H, )所确定的左陪集关系对G所划分的等价类，称为(H, )的左陪集。 包含元素a的左陪集记为aH.,可以推导：,3.5.2 子群的陪集,定理. 群G的子群H与其每个右陪集等势。,（4）拉格朗日定理,定理. （拉格朗日定理） 有限群的阶一定被它的子群的阶所等分。,定义. G内H的指数： H右陪集的个数，记为k，则,3.5.2 子群的陪集,例. S=1,2,3, S上的变换共有6个,1 2 3,1 2 3,1 2 3,1 3 2,1 2 3,2 1 3,1 2 3,2 3 1,1 2 3,3 1 2,1 2 3,3 2 1,（P1，P4，P5, )为（S3, )的子群，求其所有右陪集。,3.5.2 子群的陪集,例. 设（A, *）是群， （M, *）是其子群，其中A=a,b,c,d，M =a,b, *运算表如下，求（M, *）所有的右陪集和左陪集。,3.5.3 正规子群,定理：可换群的每个子群均为正规子群。,5 格与布尔代数,5.1 格,解： S是偏序集，其哈斯图为,对偶定理：在格中任一定理，其对偶式亦是定理。,5.2 格的基本定律,(1) 幂等律,5.3 分配格，有界格与有补格,定义6. 如果一个格既有上界，又有下界，则称其为有界格。,且其上界记为1 ，下界为0 。,5.4 布尔代数,布尔代数的性质：（1）等幂律（2）吸收律（3）交换律（4）结合律（5）零一律（6）同一律,除此之外，还有：,例12. 二值布尔代数（开关代数）,第五章 图论,图论可应用于多个领域，如信息论，控制论，运筹学，运输网络，集合论等（如用关系图来描述一个关系）。,问题1、哥尼斯堡桥问题,问题：一个散步者能否从任一块陆地出发，走过七座桥，且每座桥只走过一次，最后回到出发点？,1 图论基本概念,1-1 图的实例,问题2、旅游问题。,1-2 图的基本概念,定义1、 一个图G由两部分组成，记为，其中，V=v1，vn是非空结点集，E=l1，l2，lm为边的集合。其中li=(vk，vj)。,例1、哥尼斯堡桥问题的图可记为G=，其中，V=A,B,C,D，E=l1,l2,l3,l4,l5,l6,l7。,例2、设有四个城市c1,c2,c3,c4；其中c1与c2间，c1与c4