第九章代数系统.ppt

1、第九章 代数系统,杨圣洪 4/ysh007 离散数学通0701_04,一“代数系统”前言 小学的“+”四则运算可知，两个整数相加、相减、相乘仍是整数，相除不一定是整数。 今天我们将学习与“+”类似的运算，姑且称为“广义的加减乘除”。 当将变量的取值范围，限制A=1,2的幂集,即为P(A)=,2,1,1,2，可在P(A)定义广义“加”与“乘”, xP(A), yP(A) x+y =xy, xy=xy +=, +1=1=1 +2=2=2 +1,2=1,2=1,2 1+=1=1, 1+1=11=1 1+2=12=1,2 1+1,2=11,2=1,2 =, 1=

2、1= 2=2= 1,2= 1,2= 1=1=, 1 1=1 1=1 12=12= 1 1,2=1 1,2=,一“代数系统”前言 由“+”四则运算，知道两个整数相加、相减、相乘仍是整数，相除不一定是整数。 今天我们将学习与“+”类似的运算，姑且称为“广义的加减乘除”。 当将变量的取值范围0,1，则可定义广义“加”与“乘”, xBoolean, yBoolean x+y =xy, xy=xy 0+0=00=0, 0+1=01=1 1+0=10=1, 1+1=11=1 00=00=0, 01=01=0 10=10=0, 11=11=1,一“代数系统”前言 我们很小就学习的“+”四则运算，知道两个整数

3、相加、相减、相乘仍是整数，相除不一定是整数。 今天我们将学习与“+”类似的运算，姑且称为“广义的加减乘除”。 当将变量的取值范围n阶方阵A(n,n),A中每个元素的值为实数，则定义广义“加”、“减”、“乘”。 对应元素加减乘 x+y =(x(i,j)+y(i,j), x-y =(x(i,j)-y(i,j), xy=(x(i,j) y(i,j), 普通矩阵乘 xy =(x(i,j)y(i,j),二“代数系统”前言 我们很小就学习的“+”四则运算，知道两个整数相加、相减、相乘仍是整数，相除不一定是整数。 今天我们将学习与“+”类似的运算，姑且称为“广义的加减乘除”。 从以上实例可知，尽管参与运算的

4、对象不尽一致，有集合、布尔变量、矩阵、整数，它们都有相同的性质： (1)参与运算的对象同一个集合的2个对象，如2个整数、2个子集、2个布尔变量、2个矩阵。 这种运算符称为双目运算符。 还有单目运算符，p (2)运算后的结果仍属于同一个集合，仍为整数、子集、布尔量、矩阵，这称为该运算是封闭的。 并不是所有的运算都封闭。如23不是整数,二、运算的定义 xP(A), yP(A) x+y =xy, xy=xy xBoolean, yBoolean x+y =xy, xy=xy x+y =(x(i,j)+y(i,j), x-y =(x(i,j)-y(i,j), xy=(x(i,j) y(i,j), 很幸

5、运！这些运算都可利用所在领域的运算符来定义，不幸的是，还有很多运算，无法用其领域的运算符来表示，这时我们只能给出其运算的结果，如真值表一样。,二运算的定义 xP(A), yP(A) x+y =xy, xy=xy xBoolean, yBoolean x+y =xy, xy=xy x+y =(x(i,j)+y(i,j), x-y =(x(i,j)-y(i,j), xy=(x(i,j) y(i,j), 不能用其领域的运算符来定义，只能给出其运算的结果，如xy=(xy) mod 5 x,y0,1,2,3,4,二运算的定义 xP(A), yP(A) x+y =xy, xy=xy xBoolean, y

6、Boolean x+y =xy, xy=xy x+y =(x(i,j)+y(i,j), x-y =(x(i,j)-y(i,j), xy=(x(i,j) y(i,j), 很幸运！这些运算都可利用，它们所在领域的运算符来定义，不幸的是，还有很多运算，无法用其他领域的运算符来表示，这时我们只能给出其运算的结果，如真值表一样。,二运算的定义 xP(A), yP(A) x+y =xy, xy=xy xBoolean, yBoolean x+y =xy, xy=xy x+y =(x(i,j)+y(i,j), x-y =(x(i,j)-y(i,j), xy=(x(i,j) y(i,j), 很幸运！这些运算都

7、可利用，它们所在领域的运算符来定义，还有很多运算，只能给出其运算的结果，如xy=(xy) mod 5 x,y0,1,2,3,4,三、运算的性质 1、交换律 设是集合S上的二元运算，若x,yS都有xy=y x， 则称在S上是可交换的， 或者说运算在S上满足交换律。 如： xP(A), yP(A) x+y =xy, xy=xy xBoolean, yBoolean x+y =xy, xy=xy x+y =(x(i,j)+y(i,j), x-y =(x(i,j)-y(i,j), xy=(x(i,j) y(i,j) 整数上的加、减、乘满足交换律！ 若运算表是对称的，则满足交换律。,三、运算的性质 1、

8、交换律 设是集合S上的二元运算，若x,yS都有xy=y x， 则称在S上是可交换的， 或者说运算在S上满足交换律。 若运算表是对称的，则满足交换律。xy=(xy) mod 5 x,y0,1,2,3,4,三、运算的性质 2、结合律 设是集合S上的二元运算，若x,y,zS都有(xy)z=x(yz)， 则称在S上是可结合的,或者说运算在S上满足结合律。 如：x,y,zP(A) (x+y)+z=(xy)z=x(yz)=x+(y+z) (xy)z=(xy)z=x(yz)=x(yz) 当运算满足结合律时，常将决定运算次序的园括号去掉，如(x+y)+z=x+y+z。 普通的加、乘、集合的并、交、逻辑的与、逻

9、辑或、矩阵的加、乘满足结合律。,三、运算的性质 2、结合律 设是集合S上的二元运算，若x,y,zS都有(xy)z=x(yz)， 则称在S上是可结合的,或者说运算在S上满足结合律。 如：x,y,zP(A) (x+y)+z=(xy)z=x(yz)=x+(y+z) (xy)z=(xy)z=x(yz)=x(yz) 当运算满足结合律时，常将决定运算次序的园括号去掉，如(x+y)+z=x+y+z。 普通的加、乘、集合的并、交、逻辑的与、逻辑或、矩阵的加、乘满足结合律。,三、运算的性质 3、幂等律 设是集合S上的二元运算，若xS都有xx=x， 则称在S上是幂等的,或者说运算在S上满足幂等律。 如：xP(A)

10、 x+x=(xx)=x , xx=(xx)=x 逻辑的与、逻辑或满足结合律。 有些运算不满足幂等律，但是集合S中的某些元素满足！ 如普通加法不满足幂等，但0满足0+0=0, 普通乘法不满足幂等，但1满足11=1。 普通矩阵的乘法不幂等，但单位矩阵满足！,三、运算的性质 4、分配律 设与*是集合S上的二种运算，若x,y,zS都有 x*(yz)=(x*y)(x*z)， (yz)*x=(y*x)(z*x) 则称*对是可分配的。 如： x,y,zP(A), 对可分配， x(yz)=(xy)(xz) 对也可分配， x (yz)=(xy)(x z) 逻辑的与、逻辑或满足结合律。 有些运算不满足幂等律，但是

11、集合S中的某些元素满足！ 如普通加法不满足幂等，但0满足0+0=0, 普通乘法不满足幂等，但1满足11=1。 普通矩阵的乘法不幂等，但单位矩阵满足！,三、运算的性质 5、吸收律 设与*是集合S上的二种可交换的二元运算，若x,yS都有 x*(xy)=x ， x(x*y)=x则称*与是满足吸收律。 如： x,y,zP(A), x(xy)=x， x (xy)=x 又如： x,y,z命题变元 x (xy)=x， x (x y)=x 小结： 交换律、结合律、幂等律、分配律、吸收律是普通的加与乘、集合的并与交、命题变元的与或等运算的规律的总结、推广！,四、集合S中满足某运算的特殊元素 1、单位元 设是集合

12、S上的二元运算，如果集合S中的某元素eL，对xS都有 eLx=x 则称之为左单位元。 设是集合S上的二元运算，如果集合S中的某元素eR，对xS都有 xeR=x 则称之为右单位元。 如果S中某个元素既是左单位元，又是右单位元，则为单位元。 如：A= A=A 0+x=x+0=x 1*x=x*1=x,四、集合S中满足某运算的特殊元素 1、单位元 对xS都有 eLx=x 则称之为左单位元。 对xS都有 xeR=x 则称之为右单位元。 定理:设是S上的二元运算,若存在左单位元eL与右单位元eR,则eL=eR=e且唯一 证明： xS都有eLx=x eLeR=eR xS都有 xeR=x eLeR=eL 由以

13、上二式可知eR=eL，即两个单位元的值相等，不妨将其值记为e ，则e既是左单位元，又是右单位元，故由单位元定义可知,e是单位元。 如： A= A=A 0+x=x+0=x 1*x=x*1=x,四、集合S中满足某运算的特殊元素 2、零元 对xS都有 Lx= L 则称之为左零元。 对xS都有 x R = R 则称之为右零元。 若既是左零元，又是右零元则为零元。 如实数中乘法中的0：0*x=0=x*0. 交集运算中空集： A=A 与运算中的逻辑假0：0 x=0=x0. 定理：设是S上的二元运算,若存在左零元L与右零元R,则L=R=。且唯一！ 证明： xS都有Lx= L L R=L xS都有 xR=RL

14、R=R 由以上二式可知R=L，即两个零元的值相等，不妨将其值记为 ，则既是左零元，又是右零元，故是零元,四、集合S中满足某运算的特殊元素 2、零元 对xS都有 Lx= L 则称之为左零元。 对xS都有 x R = R 则称之为右零元。 若既是左零元，又是右零元则为零元。 定理：设是S上的二元运算,若存在左零元L与右零元R,则L=R=。且唯一。 证明：假设有二个零元 1与2， 根据零元的定义可知x 1=1 , 取x=2，则有21=1 .(1) 根据零元的定义可知 2x =2 , 取x=1，则有2*1=2 .(2) 由于(1)(2)可知， 1=2 ，故唯一。,四、集合S中满足某运算的特殊元素 1、

15、单位元 对xS都有 eLx=x 则称之为左单位元。 对xS都有 xeR=x 则称之为右单位元。 2、零元 对xS都有 Lx= L 则称之为左零元。 对xS都有 x R = R 则称之为右零元。 定理：设是S上的二元运算,若存在零元与单位元e,且集合S中至少有2个元素，则e 。 证明：假设=e ， 由单位元定义可知，xS都有xe=x， 由假设可知=e ， 故x=x . (1) 。 由零元的定义可知，xS都有x=.(2) 由(1)(2)可知x=，又由假设可知=e ，故x= =e 故S中只有1个元素！矛盾！假设错！,四、集合S中满足某运算的特殊元素 1、单位元 对xS都有 eLx=x 则称之为左单位

16、元。 对xS都有 xeR=x 则称之为右单位元。 2、零元 对xS都有 Lx= L 则称之为左零元。 对xS都有 x R = R 则称之为右零元。 3、逆元 并不是所有元素有逆元！ 某xS若有yLS,使得yLx=e，左逆元。 某xS若有yRS,使得xyR=e，右逆元。 则y既是x的左逆元又是右逆元，则为x的逆元。 如若xR-0,存在yR，使得xy=1,乘法单位元 若xR，存在yR，使得x+y=0 ，加法单位元 若xR(n,n)且|a|0，则存在yR，使得x*y=e ，单位矩阵，逆矩阵。,四、集合S中满足某运算的特殊元素 3、逆元 并不是所有元素有逆元！ 某xS若有yLS,使得yLx=e，左逆元

17、。 某xS若有yRS,使得xyR=e，右逆元。 则y既是x的左逆元又是右逆元，则为x的逆元。 定理：设运算满足结合律且存在单位元，某元素x，若存在左逆元yL与右逆元yR,则yL=yR并且唯一。 证明：yL=yLe=yL(xyR)=(yLx)yR=eyR=yR。 唯一性：若x有两个逆元y1、y2。 y1=y1e=y1(xy2)=(y1x)y2=ey2=y2.,五、代数系统 设一元名二元运算f1,f2,fk定义在非空集合S上，则它们统称为代数系统，记为 如自然集N中的加法,是代数系统 整数集Z中的加法与乘法代数系统 是代数系统。 六、代数系统同构与同态 我们研究广义的加法与乘法即代数系统的基本手段

18、是，将这些系统与普通的加法与乘法进行类比，如果与普通的加法与乘法系统类似，则将加法或乘法的规律迁移到该系统。 如果判断类似呢？同构或同态检测！,六、代数系统同构与同态 我们研究广义的加法与乘法即代数系统的基本手段是，将这些系统与普通的加法与乘法进行类比，如果与普通的加法与乘法系统类似，则将加法或乘法的规律迁移到该系统。 如果判断类似呢？同构或同态检测！ 定义1：设有两个代数系统,，若能在集合A与B之间构造映射f，满足如下要求： (1)yB均xA，使得y=f(x) (1)满射(2)1-1 (2)当x1,x2A, x1x2有f(x1),f(x2)B, f(x1)f(x2) (3) x1,x2A有f(x1x2)=f(x1) *f(x2