数字电路课件

1、第三篇 代数系统1代数系统简介人们研究和考察现实世界中的各种现象或过程，往往要借助于一些数学工具。这些现象或过程，就是我们的研究对象。描述时，需要建立适当的模型。从物理学角度考虑，就是建立该模型的运动方程（这通常由微分方程表述，反映的是研究对象的运动规律）。从数学角度考虑，需要建立合适的数学描述语言，或适当的数学结构，可以较为准确地描述研究对象。 2代数系统简介合适的数学结构相当重要。在微积分中，可以用导数描述质点运动的速度，可以用定积分来计算面积、体积等；在代数学中，可以用正整数集合上的加法运算来描述工厂产品的累计数，用集合之间的“交”、“并”运算来描述人和人之间的关系等。 3代数系统简介我

2、们要研究的是一类特殊的数学结构由集合上定义若干个运算而组成的系统。称为代数系统。4代数系统简介代数系统的一般形式是：（A, f1, f2, , fn）。其中A是一个非空集合，f1, f2, , fn是定义在A上的运算（close）。fi可以是一元运算（unitary operation）、二元运算（binary operation）、三元运算等，即n-元运算（n-nary operation）。5代数系统简介我们将要讨论的数学结构包括：群（group，涉及到对称性，symmetry）、环（ring）和域（field）、格（lattice，涉及到布尔代数，Boolean algebra）。实际上

3、，我们已学过一些代数结构，如:, 等。N: set of natural number, R: set of real number, -: negation.6代数系统代数系统的运算（运算表）和性质 代数系统之间的关系：同态和同构典型的代数系统：广群，半群，含幺半群（独异点），群，环与域布尔代数7框架8引言代数系统-由集合上定义若干运算而组成的系统：原子命题+5个联结词二元关系+关系的并、交、补、差+关系复合、关系的逆、关系的闭包代数结构的主要研究对象就是各种典型的抽象代数系统这些代数系统中的运算又具有某些性质，从而确定了这些代数系统的数学结构。9第五章 代数结构代数系统的引入运算及其性质具

4、有一个二元运算的代数系统半群群同态与同构-两个同型代数系统之间的联系具有两个二元运算的代数系统环域10要求：1.掌握代数系统的基本概念和运算性质。2.掌握代数系统之间的同构关系和同态关系，并能够证明两个代数系统是否同构或同态。3.掌握广群、半群、独异点、群等基本的代数系统的概念 第五章 代数结构115-1 代数结构(系统)的概念 所谓代数结构(系统)，无非是有一个运算对象的集合，和若干个运算，构成的系统。12 所谓代数结构(系统)，无非是有一个运算对象的集合，和若干个运算，构成的系统。一. n元运算 如何定义运算,先看几个我们熟悉的例子：整数集合I上取相反数运算“-”、集合的补运算“” 和N上

5、的“+、” 0。1。2。-1。-2。.。0。-1。-2。1。2.P(E)P(E)a 。b 。a,b 。 。a。b。a,b。0.。1。2。3。.。II可见运算“-”、“”、“+” “”就是个映射。N2N+。0.。1。2。3。.。N2N5-1 代数结构(系统)的概念131.定义：设X是个集合，f:XnY是个映射，则称f 是X上的n元运算。(Xn =XX.X -n个X的笛卡尔积)，如果YX，则称运算f 在X上是封闭的。 f:XY 是个一元运算。前面的-、是一元运算。 f:X2Y 是个二元运算。+是二元运算。思考题：下面说法是否正确？ 减法是N上封闭的二元运算。 除法是整数 I上的二元运算。 除法是实

6、数 R上的二元运算。这里我们主要讨论二元运算。n个5-1 代数结构(系统)的概念通常用、 、 、+、等表示抽象的二元运算。 如果用“”表示二元运算f 时，通常将 f()=z 写成 xy=z 。142.二元运算的运算表 有时用一个表来表示二元运算的运算规律。 例如令E=a,b P(E)上的运算表如图所示。 aaaaabbbbba,ba,ba,b上 表 头 元 素左表头元素运算 从运算表除了可以看清运算的规律外，可以很容易地看出运算的性质。5-1 代数结构(系统)的概念15S R A LS S R A LR R A L SA A L S RL L S R A 再如令X=S,R,A,L其中 S表示开

7、始时的位置； R表示“向右转”； A表示“向后转”； L表示“向左转”； “”表示转动的复合运算；其运算表如图所示。5-1 代数结构(系统)的概念16二.代数系统的概念1.代数系统的定义：X是非空集合，X上的m个运算f1,f2,fm, 构成代数系统U,记作U= ( m1) 注意：这m个运算f1,f2,fm的元数可能各不相同, 比如f1是一元运算，f2是二元运算,fm是k元运算。 例如 ，2.有限代数系统： U= 是个代数系统，如果X是个有限集合，则称U是个有限代数系统。 例如上边的X=S,R,A,L，是个有限代数系统。3. 同类型代数系统：给定两个代数系统U= ，V= 如对应的运算fi和 gi

8、的元数相同(i=1,2,3,m),则称U与V是同类型代数系统。 例如 5-1 代数结构(系统)的概念175-2 运算及其性质一般的二元运算的一些性质：封闭性交换律结合律分配律吸收律等幂律特异元素：单位元（幺元）零元逆元185-2 运算及其性质一般的二元运算的一些性质：封闭性交换律结合律分配律吸收律等幂律19封闭性定义 5-2.1 设*是定义在A上的二元运算，若x，yA，有x*yA，称*在A上是封闭的。 例如在N上加法+和乘法封闭，而减法不封闭。 从运算表可以很容易看出运算是否封闭。20封闭性P178 例题1：设A=xx=2n，nN， 问乘法运算是否封闭？对加法运算呢？解：对于任意的2r，2s

9、A，r,s N，因为2r2s = 2r+s A所以乘法运算是封闭的。因为2，22 A，但2+22=6A，所以对于加法运算是不封闭的。21交换律定义 5-2.2 设*是定义在A上的二元运算，若x，yA，有x*y=y*x，称*满足交换律。（ *是可交换的）大家都知道：加法、乘法、交、并、对称差是可交换的。22交换律从运算表看交换性：是个以主对角线为对称的表。aaaaabbbbba,ba,ba,bS R A LS S R A LR R A L SA A L S RL L S R A23交换律P179例题2：设Q是有理数集，是Q上的二元运算，对于任意的a,b Q，a b=a+b-ab ，问是否可交换？

10、解：因为a b=a+b-ab =b+a-ba= b a所以是可交换的。24结合律定义 5-2.3 设*是定义在A上的二元运算，若 x，y，zA，有x*（y*z）=（x*y）*z，则称*满足结合律（*是可结合的）可结合的：数值的加法、乘法，集合的交、并、对称差，关系的复合、函数的复合，命题的合取、析取。是可结合的运算的，元素x的运算，通常可以写成乘幂的形式。如下： xx=x2 x2x=xx2=x3 xmxn=xm+n (xm)n=xmn思考题：对于加法 +： 13 =( ) 对于乘法： 13 =( )25结合律P179例题3：设A是一个非空集合，*是A上的二元运算，对于任意的a,b A，有a*b

11、=b，证明*是可结合运算。证明：因为对于任意的a,b,cA (a *b)*c= b*c=c ；a*(b*c)= a*c=c所以(a *b)*c= a *(b*c)即*是可结合运算。26分配律定义 5-2.4 设*， 是定义在A上的两个二元运算，若 x，y，zA有:x*(yz)= (x*y)(x*z)(yz)*x= (y*x)(z*x) 则称运算*对于运算是可分配的。 例如 乘法对加法可分配。 集合的与互相可分配。 命题的与互相可分配。27分配律P179例题4：设集合A=,，在A上定义两个二元运算*和， 如下表所示。运算对于*可分配吗？运算*对于呢？ * 解：容易验证运算对于*是可分配的。即x(

12、y*z)=(xy)*(xz)验证如下：当x=：x(y*z)= ; (xy)*(xz)=*= 当x=：x(y*z)=y*z ; (xy)*(xz)=y*z但是运算*对于是不可分配的，因为*()= *= 而(*)(*)=28吸收律定义 5-2.5 设*， 是定义在A上的两个可交换的二元运算，若 x，yA有: x*(xy)=x；x(x*y)=x，称运算*和运算满足吸收律。 例如 集合的与满足吸收律。 命题的与满足吸收律。 29吸收律P180例题5：设集合N为自然数全体，在N上定义两个二元运算，如果对于任意的x,y N ,有x*y=max(x,y);x y=min(x,y)，验证*和的吸收律。解：对于

13、任意的a,bNa*(ab)=max(a,min(a,b)=aa(a*b)=min(a,max(a,b)=a因此*和满足吸收律。30等幂律定义 5-2.6 设*是定义在A上的二元运算，若xA有:x*x=x，称运算*满足等幂律（*是等幂的）。从运算表看幂等元、幂等性：看主对角线的元素与上表头(或左表头)元素相同。请看的运算表，有幂等性。aaaaabbbbba,ba,ba,b31等幂律P180例题6：设(S)是集合S的幂集，在(S)上定义的两个运算，集合的“并”运算和集合的“交”运算，验证和是等幂的。解：对于任意的A(S),有AA=A,AA=A，因此运算和都满足等幂律。325-2 运算及其性质特异元

14、素：单位元（幺元）零元逆元33单位元（幺元）定义 5-2.7 设*是定义在A上的二元运算若有一个元素elA,对于任意的xA有:el*x=x，称el为A中关于运算*的左单位元(左幺元)；若有一个元素erA,对于任意的xA有:x*er=x，称er为A中关于运算*的右单位元(右幺元)；若A中的一个元素e，关于*运算既是左单位元(左幺元)又是右单位元(右幺元), 即xA有: e*x=x*e=x。则称e为A中关于运算*的单位元(幺元)。34单位元（幺元）例7：设集合S=,，在S上定义两个二元运算*和， 如下表所示。指出左幺元或右幺元。 * 解： 和都是S中关于运算*的左幺元，而是S中关于运算的右幺元。3

15、5关于幺元有下述的唯一性定理定理5-2.1（幺元唯一性定理）设*是定义在集合A上的一个二元运算，且在A中具有关于运算*的左幺元el和右幺元er，则el=er=e，且在A中的幺元是唯一的。证明： 因为el和er分别是A中关于运算*的左幺元和右幺元，所以el = el* er（ er 为右幺元）；el* er =er （ el 为左幺元)，所以el=er,将这个幺元记作e。设另有一幺元e1 A,则e1=el*e = e。36零元定义 5-2.8 设*是定义在A上的二元运算若有一个元素lA,对于任意的xA有: l*x=l，称l为A中关于运算*的左零元；若有一个元素rA,对于任意的xA有:x*r=r，

16、称r为A中关于运算*的右零元；若A中的一个元素，关于*运算既是左零元又是右零元, 即xA有: *x=x*=。则称为A中关于运算*的零元。37零元例8：设集合S=浅色,深色，定义在S上的一个二元运算*如下表所示，试指出零元和幺元。浅色 深色浅色 浅色 深色深色 深色 深色*解： 深色是S中关于运算*的零元，而浅色是S中关于运算*的幺元。38关于零元有下述的唯一性定理定理5-2.2 （零元唯一性定理）设*是定义在集合A上的一个二元运算，且在A中具有关于运算*的左零元l和右零元r，则l=r=，且在A中的零元是唯一的。证明类似于定理5-2.1 的证明。39关于幺元与零元的定理定理5-2.3设是一个代数

17、系统，且集合A中的元素个数大于1。如果该代数系统中存在幺元e和零元，则e.证明：用反证法。设=e，那么对于任意的xA,必有x=e*x=*x=e于是,A中所有的元素都是相同的，这与A中含有多个元素相矛盾。这个定理说明：幺元与零元是不同的,除非集合S只有一个元素。在这种情况下,这个唯一的元素既是幺元也是零元。40逆元定义 5-2.8 设代数系统,*是定义在A上的一个二元运算，且e是A中关于运算*的单位元(幺元)。如果对于A中的一个元素a存在着A中的某个元素b，使得b*a=e，那么称b为a的左逆元；如果a*b=e成立，那么称b为a的右逆元；如果一个元素b，它既是a的左逆元又是a的右逆元，即 b*a=

18、 a*b=e，那么就称b是a的一个逆元。很明显，如果b是a的逆元，那么a也是b的逆元，简称a与b互逆。一个元素x的逆元记为x-1.41逆元注：一般地,一个元素的左逆元不一定等于该元素的右逆元。而且，一个元素可以有左逆元而没有右逆元。甚至一个元素的左(右)逆元还可以不是唯一的。42逆元例9：设集合S=,，定义在S上的一个二元运算*， 如下表所示。指出代数系统中各个元素的左、右逆元情况。 * 解： 是幺元。有两个左逆元和；右逆元是的左逆元和右逆元都是，故和 互为逆元；的左逆元是都 而右逆元是；的左逆元为和 ，右逆元为和的右逆元为 ，但没有左逆元。43关于逆元有下述的唯一性定理定理5-2.4（逆元唯

19、一性定理）设是一个代数系统，*是定义在A上的一个二元运算，A中存在幺元e，且每个元素都有左逆元。如果*是可结合的运算，那么，这个代数系统中的任何一个元素的左逆元必定也是该元素的右逆元，且每个元素的逆元是唯一的。44和是代数系统, , 是二元运算：1.封闭性：x,yA, 有 xyA。2.可交换性：x,yA, 有 xy=y x。3.幂等性： xA, 有 xx=x。4. 有幺元： eA, xA，有 ex=xe=x.5.有零元: A,xA，有x=x=.6.可结合性：x,y,zA, 有 (xy)z =x(yz)。7.有逆元： xA, 有x-1A，使得 x-1x=xx-1=e8.分配律： 对可分配：x,y,zA，有 x(yz)=(xy)(xz) 或 (xy)z =(xz)(yz) 9.吸收律：x,yA，有 x(xy)=x 和 x(xy)=x 对这些性质要求会判断、会证明。 小结45小结是一个代数系统，*是A上的一个二元运算,那么该运算的有些性质可以从运算表中直接看出。（1）运算*具