《glj-chapter1 引言和预备知识》由会员分享，可在线阅读，更多相关《glj-chapter1 引言和预备知识（91页珍藏版）》请在金锄头文库上搜索。
1、近世代数近世代数离散数学系列课程之一离散数学系列课程之一郭龙江郭龙江黑龙江大学计算机科学技术学院黑龙江大学计算机科学技术学院2012年年4月月教材教材离散数学离散数学耿素云耿素云, 屈婉玲屈婉玲, 张立昂张立昂. 高等教育出版社高等教育出版社(修订版修订版) 2008年年3月第月第1版版 普通高等教育普通高等教育“十五十五”国家级规划教材国家级规划教材参考书参考书 离散数学离散数学 学习指导与习题解析学习指导与习题解析耿素云耿素云, 屈婉玲屈婉玲, 张立昂张立昂 高等教育出版社高等教育出版社 普通高等教育普通高等教育“十五十五”国家级规划教材配套参考国家级规划教材配套参考书书内容介绍内容介绍n
2、第三部分第三部分 代数结构代数结构n第一章第一章 引言和预备知识引言和预备知识 n第二章第二章 代数系统代数系统n第三章第三章 半群和群半群和群n第四章第四章 环和域环和域n第五章第五章 格和布尔代数格和布尔代数进度安排进度安排n课程每周课程每周2次次,一次一次2节课。节课。n进行进行9周周(第第9周周-第第17周周)n课程将于课程将于6月底结束月底结束.n考试时间：考试时间：2012/7/4 13:30-15:30答疑答疑n时间：周四晚时间：周四晚7:00n地点：实验楼地点：实验楼327室室nEmail：nljguo_第一章第一章 引言和预备知识引言和预备知识 主要内容主要内容一、引言一、引
3、言 近世代数的研究对象近世代数的研究对象 近世代数的发展和应用领域近世代数的发展和应用领域二、预备知识二、预备知识 集合、映射的基本知识集合、映射的基本知识 关系的基本知识关系的基本知识 偏序关系和偏序集及相关知识偏序关系和偏序集及相关知识 整数的性质整数的性质1.1 引言引言一、近世代数的研究对象一、近世代数的研究对象n代代数数Algebra是是数数学学的的其其中中一一门门分分支支，当当中可大致分为中可大致分为经典代数学经典代数学和和抽象代数学抽象代数学两部分两部分n经经典典代代数数（classical algebra）包包括括：初初等等代代数数，高高等等代代数数和和线线性性代代数数。它它的
4、的研研究究对对象象主主要是代数方程和线性方程组。要是代数方程和线性方程组。n抽抽 象象 代代 数数 又又 称称 为为 近近 世世 代代 数数 （ modern algebra）。它它的的研研究究对对象象是是抽抽象象的的公公理理化化代数系统代数系统。概念：代数系统概念：代数系统n代数系统：是由一个非空集合代数系统：是由一个非空集合S和定义在这个集合上的一种运算和定义在这个集合上的一种运算或若干运算所构成的一个系统。或若干运算所构成的一个系统。n定义在非空集合定义在非空集合S上的上的运算运算，其，其运算结果一定还在运算结果一定还在S中，这是运中，这是运算的封闭性。算的封闭性。 例子：例子：代数系统
5、的例子代数系统的例子n例例1：整数集合和普通的加法：整数集合和普通的加法“+”构成一个代数系统构成一个代数系统,记作记作. n例例2：自然数集合：自然数集合N和普通的加法和普通的加法“-”不构成一个代数系统不构成一个代数系统.为什么呢？为什么呢？n取自然数集合取自然数集合N中的中的2个数个数5和和8，5-8=-3 N，不不满足封足封闭性。性。 二、二、近世代数应用领域近世代数应用领域 n在计算机科学中：软件规范、编译系统、在计算机科学中：软件规范、编译系统、编码理论、密码学编码理论、密码学(群群, 环环)、数据仓库、数据仓库(格格)、网络安全、形式语言、数字逻辑等课、网络安全、形式语言、数字逻
6、辑等课程中都用到了近世代数。程中都用到了近世代数。n在近代物理、近代化学、计算机科学、在近代物理、近代化学、计算机科学、数字通信和系统工程等领域都有应用。数字通信和系统工程等领域都有应用。一些有趣的例子n现实世界用计算机软件来表达，就需要更复杂的数学模型。n世代数为我们提供了有力的数学工具。n洗扑克牌、华容道n抽象成数学模型是置换群。12345678910111213141516171819200 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 190 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 190 1
7、 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 190 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 17 16 18 190 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 190 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19* 1 2 * * 5 6 * * * * * * * * * * * * * 13 14 * * 17 18 * * * * * * * * * * * * * n网页可以抽象成图，对网页结构的分类实际是找不同的
8、图的结构n具有n个顶点的简单图有多少个不同的图形？n可用置换群求解n密码加密n明文：You are a good studentn密文：Dtz fwj f ltti xyzijsy 1.2 预备知识预备知识一、集合与映射一、集合与映射 1、集合的记号 n一些对象的整体就构成集合，这些对象称为元素一些对象的整体就构成集合，这些对象称为元素(element)或成员或成员(member) 。n常用的数集合常用的数集合nN：自然数自然数(natural numbers)集合集合 N=0,1,2,3,nZ：整数整数(integers)集合集合 Z=0, 1, 2, nQ：有理数有理数(rational
9、numbers)集合集合nR：实数实数(real numbers)集合集合nC：复数复数(complex numbers)集合集合2、包含排斥原理（principle of inclusion/exclusion例子例子n例1: 在1到10000之间既不是某个整数的平方,也不是某个整数的立方的数有多少? 例子例子n 例2: 6个人开6辆车去试车，要求试车时不能开自己的车，问有多少种分法?（这是错排问题：n个有序元素应有n！种不同的排列，若一排列使得所有元素都不在原来位置，则称这个排列为错排。） n3、映射的定义 n定义：设A，B为两个非空集合，若存在一个A到B的对应关系f，n若对任意的xA都存
10、在唯一的yB与之对应，n则称f为A到B的一个映射或函数，记为f :AB。x称为原像，y称为x的像。 例子例子n记：记：Mn(R)=全体全体n阶实方阵阶实方阵n规定规定Mn(R)到到R的对应关系为的对应关系为f：n由于每个矩阵的行列式是唯一确定的。所以这由于每个矩阵的行列式是唯一确定的。所以这是一个是一个Mn(R)到到R的映射。的映射。 n注意：在映射定义中，要注意单值性，即对任意的xA都存在唯一的确定yB与之对应。因此要检验一个对应关系f是否是映射需要检验下列条件： 例子例子n规定Q到Z的对应关系为: nf是是Q到到Z的映射吗？的映射吗？n4、映射的分类定义 设函数f :AB(1)若ranfB
11、,则称f是满射的(或到上的)；这里ranf表示f的值域。(2) 若对于任何的x1, x2 A, x1x2 ,都有 f (x1)f(x2 )，则称f是单射的(或一一的)；(3)若f既是满射的，又是单射的，则称f是双射的(或一一到上的) n定义: 函数的象 n5、映射的复合n定义：定义： f :AB; g :BC, f o g : AC 且对且对 n函数复合不满足交换律(p146 例子 8.8)；n函数复合满足结合律(p143 推论1)； 二、二、二元关系二元关系 n1、笛卡儿积n定义：AB=|xAyB. nA=1, 2 B=3, 4nAB=, , , n特别地，A= 笛卡儿积性质(1)n非交换:
12、 AB BA n (除非 A=B A= B=) n反例: A=1, B=2. nAB= BA=笛卡儿积性质(2)n非结合: (AB)C A(BC) n反例: A=B=C=1. n(AB)C=,1,nA(BC)=1,. n (除非 A= B= C=)笛卡儿积性质(3)n分配律: 1.A (B C) = (A B) (A C)2.A (B C) = (A B) (A C)3.(B C) A = (B A) (C A)4.(B C) A = (B A) (C A) 笛卡儿积性质n其他: AB= A= B=等 n2、二元关系n定义（A到B的二元关系）:是AB的任意子集.nR是A到B的二元关系 RAB
13、RP(AB) , P(AB)表示AB的幂集.n例子：A=1, 2 B=3, 4nAB=, , , nR= , RAB n若|A|=m,|B|=n, 则|AB|=mn, 故|P(AB)|=2mnnA到B不同的二元关系共有2mn个。 解：解： ， 例例6、。上的包含关系，求特殊关系 n设A是任意集合, 则可以定义A上的: n空关系: n恒等关系: IA = | xA n全域关系: UA = AA = | xA yA 三、三、等价关系和等价类等价关系和等价类 n1、等价关系(equivalence relation)n定义 设R为非空集合A上的关系,如果R是自反的、对称的和传递的,则称R为A上的等价
14、关系.对任何x，yA,如果R,则记作xRy. 定义 关系矩阵的特点 关系图的特点 自反性 ，都有 主对角线元素全为1图中每个顶点都有环反自反性 ，都有 主对角线元素全为0图中每个顶点都无环定义 关系矩阵的特点 关系图的特点 对称性 对称矩阵 若两顶点间有 边，必是一对方向相反的边 反对称性 若两顶点间有边， 必是一条有向边 若则 ，若则 ，且若则 ，且定义 关系矩阵的特点 关系图的特点 传递性 若，则且若顶点则有边，到有边，到必有边到等价关系的例子n例: A1,2,8,R|x,yAxy(mod 3),其中x=y(mod 3)的含义就是x-y可以被3整除(x mod 3 = y mod 3).
15、R为A上的等价关系 R=, , , , , , n2、等价类n定义 设R是非空集合A上的等价关系,对任意的xA, 令 xR=y| yA R. 称xR为x关于R的等价类,简称x等价类,简记为xR. 等价类的例子n例: A1,2,8, (P123 例7.16)R|x,yAxy(mod 3),其中x=y(mod 3)的含义就是x-y可以被3整除. R为A上的等价关系 1=4=7=1, 4, 72=5=8=2, 5, 83=6=3, 6等价关系的性质n性质 设R是非空集合A上的等价关系,对任意的x,yA,下面的结论成立.(1)x,且xA；(2)若xRy,则x=y；(3)若x y,则xy； (4)n3、
16、商集定义 设R为非空集合A上的等价关系,以R的所有等价类为元素的集合叫做A在R下的商集,记作AR.A/R=xR |xA商集的例子n例: A1,2,8, R|x,yAxy(mod 3),其中x=y(mod 3)的含义就是x-y可以被3整除. R为A上的等价关系 1=4=7=1, 4, 7; 2=5=8=2, 5, 83=6=3, 6A/R=1, 2, 3=1,4,7,2,5,8,3,6商集的例子n例 在整数集合z上模n的等价关系,其等价类是0,2n, n,0,n,2n, 1,2n1,n十1,1,n1,2n1,2,2n2,n2,2,n2,2n十2,n1,2nn1, nn 1,n1,nn1,Z/R=
17、0, 1, 2, ,n-1= nz+i|z Z | i=0, 1, 2, ,n-1四、偏序和全序关系四、偏序和全序关系 n1、偏序集 n定义 设R为非空集合A上的关系,如果R是自反的、反对称的和传递的,则称R为A上的偏序关系.简称偏序,记作 . n反对称反对称 x y (x, y A R R x=y) 则称则称R为为A上的上的反对称反对称的关系。的关系。偏序集的例子n n n2、全序集 n定义 设为偏序集,若x, yA, xy或者yx成立,则称x与y是可比的.n对任意的x, yA, x和y都可比, 则称为A上的全序关系.为全序集. 全序集的例子n1,2,3,4,5上的小于等于关系是全序关系n整
18、除关系不是全序关系. n3、哈斯图 n定义 设为偏序集,对于任意的x,yA,如果xy或者yx成立,则称x与y是可比的. 如果xy(即xyxy)(读作x小于y),且不存在zA使得xzy,则称y覆盖x.n哈斯图的画法：如果xy，则将x画在y的下方。如果y覆盖x，就用一条线段连接x和y。n4、偏序集中的特殊元n定义 设为偏序集,BA.(1)若yB,使得x(xB yx), y是B的最小元(2)若yB,使得x(xB xy), y是B的最大元(3)若yB,使得x(xB xy x=y), y是B的极小元. (4)若yB,使得x(xB yx x=y) , y是B的极大元.n例例 设偏序集如下图所示，求A的极小
19、元，最小元，极大元，最大元。 极小元：极小元：a, b, c, g a, b, c, g 极大元：极大元：a, f, h a, f, h 没没有最大元和最小元。有最大元和最小元。 n定义 设为偏序集,BA.(1)y是B的上界:若yA,使得x(xBxy)(2)y是B的下界:若yA,使得x(xByx)(3)B的最小上界或上确界:令Cy|y为B的上界, 则称C的最小元为上确界(4)B的最大下界或下确界:令Dy|y为B的下界, 则称D的最大元为下确界nA=1, 2, , 12nB=2, 3, 6nB的上界是6，12nB的最小上界6nB的下界是1nB的最大下界是1五、数论初步五、数论初步n1、带余除法定
20、理n定理定理1. 设a, b为给定的整数，a0, 则一定存在唯一的一对整数q与r，满足b=q.a+r，0rb) rn+1即为所求。即为所求。 n辗转相除法（Euclid法）的原理例子例子nd=(6731, 2809)6731 = 2809 * 2 + 11132809 = 1113 * 2 + 5831113 = 583 * 1 + 530583 = 530 * 1 + 53530 = 53 * 10 + 0 故d = 53例子例子d = (735000, 421160, 238948)d = (735000, 421160, 238948)d1 = (735000, 238948) = 4d
21、1 = (735000, 238948) = 4d = (d1, 421160) = 4 d = (d1, 421160) = 4 (4 | 421160)(4 | 421160) n 最小公倍数的求解方法 nI、先将待求的先将待求的 分解成素分解成素因数之积，相同的素因数写成因数之积，相同的素因数写成 形式。形式。 设所有出现的素因数为设所有出现的素因数为 则则 ，其中，其中 取取 形如中最大的形如中最大的 . . 例子例子(24, 36)=1224, 36=24*36/12=72 II.最大公约数和最小公倍数的性质最大公约数和最小公倍数的性质最大公约数和最小公倍数的性质最大公约数和最小公倍数的性质最大公约数和最小公倍数的性质最大公约数和最小公倍数的性质n4、欧拉函数 P91, 例子6.6n(12)=4
