《离散数学ch7 代数系统》由会员分享，可在线阅读，更多相关《离散数学ch7 代数系统（21页珍藏版）》请在金锄头文库上搜索。
1、 欢迎进入离 散 数 学 第 七章 代 数系统近世代数 第七章 代数系统7.1 代数系统的引入前言7.2 运算及其性质结束第七章第七章 代数系统代数系统 人们研究和考察现实世界中的各种现象或 过程往往要借助于所谓的数学模型。 例如:在微 积分中,物体的速度可用导数,面积、体积可用定 积分计算。针对某个具体问题选用适宜的数学结 构去进行较为确切的描述， 这就是所谓数学模 型。 可见数学结构在数学模型中占有极为重要 的地位， 我们现在下面讨论的数学结构是由集 合上定义若干运算而组成的系统称为代数 系统。 在计算机科学中，研究机器可计算性语言 、算法计算的复杂性、刻划抽象的数据结构等 等，都需要这现
2、代代数系统知识。 7.1 7.1 代数系统的引入代数系统的引入 代数系统是由一个集合（此集合称为代数的载 体）和定义在集合上的运算构成。注：载体一般是非空集合，定义在载体上的n元运算是一个从An到B的 映射。 例：）取整 X，求绝对值 |X|，是一元运算）+,X是二元运算,）if x运算封闭否，呢？解：2r，2sA， 2r x 2s=2r+sA （ ）运算封闭2，4A，2+4A，运算不封闭2，4A，2/4A， 运算不封闭2、结合律证：a，b，cA，a*（b*c）=a*c=c( a*b）*c=b*c=ca*（b*c）=（a*b）*c *满足结合律已知，若x，y，zA，有x*（y*z ）=（x*y
3、）*z，称*满足结合律。 例：，若a，bA，有a*b=b证明：*满足结合律 7.2 7.2 运算及其性质运算及其性质3、交换律已知，若x，yA，有 x*y=y*x，称*满足交换律。例：设,*定义如下：a*b=a+b-ab ，问*满足交换律否？证：a，bA，a*b=a+b-ab=b+a-ba=b*a*满足交换律。7.2 7.2 运算及其性质运算及其性质设，若x，y，zA有:x*(yz)=（x*y）（x*z） ; (yz)*x=(y*x)(z*x)称运算*在上可分配 例：设A=，二元运算*，定义如左:* 问分配律成立否？ 证明：x(y*z)=(xy)*(xz)证：当x=：x(y*z)= ; (xy
4、)*(xz)=当x=：x(y*z)=y*z ; (xy)*(xz)=y*z 注: 若找不到规律,对该例则应用8个式子进行验证。 、运算*对运算不可分配证：*（）=*=（*）（*）= 7.2.1 7.2.1 运算及其性质运算及其性质 4.分配律例:N为自然数集,x,yN，x*y=maxx，y,xy=minx，y证明：x，yN，x*（xy）=maxx，minx，y=x xy =x*满足吸收律 x x ，若x，y，zA有:x*(x z)=x 称运算*满足吸收律; x (x * y) =x； 运算 满足吸收律试证：*，满足吸收律已知A，*，若xA，x*x=x 则称* 满足等幂律 例：已知集合s,（s）
5、,则,满足吸收律，等幂律 7.2 7.2 运算及其性质运算及其性质6.等幂律7.2 7.2 运算及其性质运算及其性质二、么元（单位元）和零元 1、定义 : 设*是s上二元运算，er，eI，r，e， s ， 有.若xs，有el*x=x，称el为运算*的左么元若xs，有x*er=x，称er为运算*的右么元 .若xs，有l*x=l ，称l为运算*的左零元若xs，有x*r=r，称r为运算*的右零元 . 若xs，有e*x=x，x*e=x称e为运算*的么元若xs，有*x=x* = ，称为运算*的零元 例：代数A=a，b，c， 。 用下表定 义：。 a b c a a b b b a b c c a b a
6、则b是左么元，无右么元,a是右零元，b是右零元，无左零元;二、么元（单位元）和零元运算。既不满足结合律，也不满足交换律 。 例:a）I，x， I为整数集则么元为1，零元为0二、么元（单位元）和零元b）（s）,对运算，是么元， s是零元，对运算，s是么元 ，是零元。 c）N，+有么元0，无零元。2、性质 、Th1: 设*是s上的二元运算，满足结合律，具有左么元el，右么元er，则el=er=e 证明： er = el* er = el二、么元（单位元）和零元推论：二元运算的么元若存在则唯一证明：反证法：设有二个么元e，e ； 则e=e*e=e、Th2: 设*是s上的二元运算， 具有左零元ol ，
7、右零元or， 则ol=or=o推论：二元运算的零元若存在则唯一三、 逆元1、逆元定义设*是s上的二元运算，e是运算*的么元7.2 7.2 运算及其性质运算及其性质、若x*y=e那对于运算*，x是y的左逆元，y是x的右逆元、若x*y=e，y*x=e，则称x是y的逆元，y的逆元通常记为y-1，存在逆元(左逆无，右逆元）的元素称为可逆的（左可逆的，右可逆的）例：a)、代数 N，+中仅有么元0，有逆元0，R，*中，除零元0外所有元素均有逆元 b)、A=a，b，c，*由下表定义： * a b ca a a bb a b cc a c cb是么元,a的右逆元为c，无左逆元， b的逆元为b，c的右逆元为空，左逆元为a 三、 逆元d）A=0，1，2，k-1，k模k乘法k定义如下：x ky= x y x y kx y-n k x yk, n0, 1， 则有些元素存在逆元，有些元素无逆元当且仅当x与k互质时，x有逆元 三、 逆元Th3: 对于可结合运算 ，如果元素X有 左逆 元， 右逆元r，则l=r=x推论：逆元若存在，则唯一 证：=（xr）=（x）逆元存在为r若存在X的另一个逆元r ; 则:r r =r(xr)=(rx)r=r r三、 逆元 2、逆元的性质四、同态和同构一、同态1、定义：满同态：单一同态：二、同构1、定义：五、同余关系六、积代数七、商代数谢 谢 使 用
