离散数学及其应用课件：典型代数系统简介

典型代数系统简介9.1半群与群9.2环与域9.3格与布尔代数9.4代数系统应用简介

9.1半群与群

9.1.1半群与独异点半群与独异点都是具有一个二元运算的代数系统。定义9.1设V=<S,◦>是代数系统,◦为二元运算,如果◦是可结合的,则称V为半群。半群V中的二元运算◦可交换,则V是可交换半群。

例9.1(1)<Z+,+>,<N,+>,<Z,+>,<Q,+>,<R,+>都是半群,其中+表示普通加法。

(2)<Mn(R),×>是半群,其中×表示矩阵乘法。

(3)<Z+,+>,<N,+>,<Z,+>,<Q,+>,<R,+>都是可交换半群。

(4)<Mn(R),×>不是可交换半群,因为矩阵乘法不满足交换律。

定义9.2设V=<S,◦>是半群,若e∈S是关于◦运算的幺元(单位元),则称V是幺半群,也称作独异点或单位半群。有时也将独异点V记作V=<S,◦,e>。若◦是可交换的,则称为可交换幺半群或可交换独异点。

例9.2(1)<Z+,+>,<N,+>,<Z,+>,<Q,+>,<R,+>中除了<Z+,+>外都是独异点,其中加法的幺元是0。

(2)<Mn(R),×>是独异点,矩阵乘法的幺元是n阶单位矩阵E。

例9.3Z是整数集,对于下列二元运算*,哪些代数系统<Z,*>是独异点?

(1)a*b=ab+1;

(2)a*b=b。

9.1.2群和子群

1.群的定义与性质

群是具有一个二元运算的代数系统。

定义9.3设V=<S,◦>是独异点,e∈S是关于◦运算的幺元,如果∀a∈S,a-1∈S,即S中每一个元素都有逆元,则称V是群,通常记作G。

例9.4已知:Nk是由自然数前k个数组成的集合,即Nk

={0,1,2,…,k-1};

k是模k的乘法运算,如

62=(2×2)mod6=4,3

65=(3×5)mod6=3;试证<N7-{0},

7>是群。

证明(1)证明运算

7的封闭性。

定义9.4

(1)若群G是有穷集,则称G是有限群,否则称为无限群。群G的基数称为群G的阶,有限群G的阶记作|G|。

(2)只含单位元的群称为平凡群。

(3)若群G

中的二元运算是可交换的,则称G

为交换群或阿贝尔(Abel)群。

例9.5<Z,+>和<R,+>是无限群,<Zn,+>是有限群,也是n阶群。Klein四元群是4阶群。<{0},+>是平凡群。它们都是交换群,n阶(n≥2)实可逆矩阵集合关于矩阵乘法构成的群是非交换群。

定理9.1代数系统<G,◦>是群的充要条件为:

(1)对G中任意元素a,b,c,有(a◦b)◦c=a◦(b◦c);

(2)对G中任意元素a,b,方程a◦x=b和y◦a=b都有解。

证明留给读者来完成。

定理9.2若代数系统<G,◦>是群,则对◦满足消去律。

证明设a◦b=a◦c或b◦a=c◦a,则在等式两边左“乘”或右“乘”a的逆元a-1,即得b=c。

2.子群的定义与判定

定义9.7设G是群,H是G的非空子集:

(1)如果H关于G中的运算构成群,则称H是G的子群,记作H≤G。

(2)若H是G的子群,且H⊂G,则称H是G的真子群,记作H<G。

定理9.6假设G为群,H是G的非空子集,则H是G的子群当且仅当下面的条件成立:

(1)∀a,b∈H必有ab∈H;

(2)∀a∈H有a-1∈H。

证明必要性是显然的。为证明充分性,只需证明e∈H。因为H非空,必存在a∈H。由条件(2)知a-1∈H,再根据条件(1)有aa-1∈H,即e∈H。

定理9.7假设G为群,H是G的非空子集,H是G的子群当且仅当∀a,b∈H有ab-1∈H。

证明根据定理9.6必要性显然可得出,这里只证充分性。

因为H非空,必存在a∈H。根据已知条件得aa-1∈H,即e∈H。任取a∈H,由e,a∈HH得ea-1∈H,即a-1∈H。任取a,b∈H,知b-1∈H.再利用给定条件得a(b-1)-1∈,即ab∈H。

综合上述,可知H是G的子群。

9.2环与域

9.2.1环的概念定义9.9-设<R,+,·>是代数系统,R为集合,+和·为二元运算,如果:(1)<R,+>为交换群;(2)<R,·>为半群;(3)运算·对于运算+是可分配的,则称<R,+,·>是环。

定义9.10令<R,+,·>是环,若环中乘法·适合交换律,则称R是交换环。若环中乘法·存在单位元,则称R是含幺环。

注意

(1)在环中通常省略乘法运算·;

(2)为了区别含幺环中加法幺元和乘法幺元,通常把加法幺元记作0,乘法幺元记作1。可以证明加法幺元0恰好是乘法的零元。

(3)环中关于加法的逆元称为负元,记为-x;关于乘法的逆元称为逆元,记为x-1。

定义9.11在环<R,+,·>中,如果存在a,b∈R,a≠0,b≠0,但ab=0,则称a为R中的左零因子,b为R中的右零因子。如果环中的一个元素x既是左零因子又是右零因子,则称x为环中的一个零因子。如果环R中既不含左零因子,也不含右零因子,即∀a,b∈R,ab=0⇒a=0或b=0,则称R为无零因子环。若环<R,+,·>是交换、含幺和无零因子的,称R为整环。

定理9.9-设<R,+,·>是环,0是加法的幺元,对任意的a,b,c∈R都有:

(1)a0=0a=0;

(2)a(-b)=(-a)b=-ab;

(3)(-a)(-b)=ab;

(4)a(b-c)=ab-ac;

(5)(b-c)a=ba-ca。

证明这里仅证明(1)、(3)、(5),其他留给读者练习。

9.2.2域的概念

定义9.12设环<R,+,·>整环,且R至少含有2个元素,若∀a∈R(a≠0)有a-1∈R,则称R是域。

由定义可见,一个代数系统<R,+,·>是一个域,需要满足以下条件:

(1)R对于运算+构成交换群;

(2)R中全体非零元素组成的集合R*=R-{0}对运算·也构成交换群;

(3)运算·对运算+是可分配的。

例9.11设S为下列集合,+和·为普通加法和乘法。

(1)S=Z;

(2)S={x|x=2n∧n∈Z};

(3)S={x|x=2n+1∧n∈Z};

(4)S={x|x∈Z∧x≥0}=N;

(5)S={x|x=a+b3,a,b∈Q}。

问S和+,·能否构成整环?能否构成域?为什么?

解

(1)因为乘法可交换,1是幺元,且不含零因子,所以是整环。但除了±1之外,任何整数都没有乘法的逆元,所以不是域。

(2)不是整环,也不是域。因为乘法幺元是1,而1∉S。

(3)不是整环,也不是域。因为<S,+>不是群,S当然就不是环,+的幺元是0,而0∉S。

(4)<S,+>不是群,因为除0以外任何正整数x的加法逆元是-x,而-x∉S,S当然就不是环,更不是整环和域。

9.3格与布尔代数

9.3.1格的概念与性质1.格的定义类似于环和域,格是另外一种具有两个二元运算的特殊代数系统。关于它的定义有两种形式,一种是从代数系统角度的定义,另一种是从偏序集的角度进行定义。下面给出两种格的定义。

定义9.13设L是非空集合,*和·是L上的两个二元运算,如果*和·满足交换律、结合律和吸收律,则称<L,*,·>构成格,也称为代数格。

定义9.14设<A,≼>是偏序集,如果"a,b∈A,{a,b}都有最小上界和最大下界,则称<A,≼>构成格,也称为偏序格。

2.格的性质

定理9.10设<L,≼>是格,则运算∨和∧满足交换律、结合律、幂等律和吸收律,即:

(1)交换律:"a,b∈L有a∨b=b∨a,a∧b=b∧a;

(2)结合律:"a,b,c∈L有(a∨b)∨c=a∨(b∨c),(a∧b)∧c=a∧(b∧c);

(3)幂等律:"a∈L有a∨a=a,a∧a=a;

(4)吸收律:"a,b∈L有a∨(a∧b)=a,a∧(a∨b)=a。

例9.14求图9－1所示的有界格中元素的补元,并判断哪些是有补格。图9-1偏序集的哈斯图

9.3.2布尔代数的概念与性质

定义9.20如果一个格是有补分配格,则称它为布尔格或布尔代数。布尔代数通常记为<B,∨,∧,',0,1>,其中“¢”为求补运算。

定义9.21设<B,*,·>是一个格代数系统,*和·是B上的两个二元运算,如果*和·满足交换律、分配律、同一律和互补律,则称<B,*,·>为布尔代数。

例9.15设B为任意集合,证明<P(B),∪,∩,~,⌀,B>构成布尔代数,称为集合代数。

证明(1)P(B)关于∪和∩构成格,因为∪和∩运算满足交换律、结合律和吸收律。

(2)由于∪和∩互相可分配,因此P(B)是分配格。

(3)全下界是空集Æ,全上界是B。

(4)根据绝对补的定义,取全集为B,"a∈P(B),a和~a是互为补元的。

因此,<P(B),∪,∩,~,⌀,B>是布尔代数。

布尔代数是数字电路的基础,广泛应用于逻辑电路的设计。下面以两个独立开关组成的开关电路为例,介绍布尔代数在逻辑电路设计中的应用。一个开关电路有两种状态:接

通和断开,分别用1和0表示。并联用逻辑加表示,串联用逻辑乘表示,反相用逻辑补表示。这样构成了如下代数系统:<{0,1},+,·,>,其运算如表9-1所示。容易验证,这个代数系统满足有补分配格的要求,所以是布尔代数,称为开关代数。

9.4代数系统应用简介

代数系统顾名思义就是用代数的方法来构造数学模型,是数学中最重要的基础理论之一。它是描述机器可计算的函数、研究算法计算的复杂性、刻画抽象数据结构、构建程序设计语言的语义学基础、实现逻辑电路设计和编码理论等的重要工具,对程序理论、编译程序理论、数据安全、形式语言、文本编辑理论、自动机理论、逻辑电路理论、语义学研究及数据结构等计算机分支学科都有重大的理论和现实意义。

9.4.1加密算法中的代数系统

在计算机网络通信中,为了避免信息的泄露,通常要对传输的信息进行加密。根据加密密钥和解密密钥是否相同,把数据加密技术分为对称加密和非对称加密。凯撒密码作为一种最古老的对称加密体制,其基本思想是:通过把字母移动一定的位数来实现加密和解密。明文中的所有字母都在字母表上向后(向前)按照一个固定数目进行偏移后被替换成密文。凯撒密码很容易被破解,在实际应用中无法保证通信安全。为了使密码具有更高的安全性,出现了单字母替换密码。其基本思想是:明文中的每个字母可以替换成字母表中的任意字母,用密码表记录字母的替换结果。

RSA是目前最著名的非对称加密算法。其基本思想是:任取两个大素数p、q,使得n=p×q,任取一个数e,1≤e≤(p-1)×(q-1),使得gcd(e,(p-1)×(q-1))=1(gcd(x,y)为x,y的最大公约数)。计算出私有密钥d,使得ed=1mod(p-1)×(q-1))。对于

任意消息m,密文c=memodn,恢复明文m=cdmodn。RSA算法中,运算都是在集合Zn={0,1,2,…,n-1|n=p×q,gcd(e,(p-1)×(q-1))=1}中进行的,容易验证,Zn在普通乘法和模运算下构成了群。

9.4.2群论在信息编码中的应用

1.纠错码概述

我们知道,在计算机和数据通信中,经常需要将二进制数字信号进行传递,这种传递的距离近则数米、数毫米,远则超过数千公里。在传递过程中,由于存在着各种干扰,可能会使二进制信号产生失真现象,即在传递过程中二进制信号0可能会变成1,1可能会变成0。

图9-2是一个二进制信号传递的简单模型,它有一个发送端和一个接收端,二进制信号串X=x1x2…xn从发送端发出经传输介质而至接收端。由于存在着干扰对传输介质的影响,因而接收端收到的二进制信号串X'=x'1x'2…x'n中的x'i可能不一定就与xi相等,从而产生了二进制信号的传递错误。图9-2数据通信中信号干扰图示

第二个途径就是采用纠错码(ErrorCorrectingCode)的方法提高抗干扰能力。这种纠错码的方法是采用一定的编码,使得二进制数码在传递过程中一旦出错,在接收端的纠错码装置就能立刻发现错误,并将其纠正。由于这种方法简单易行,因而目前在计算机和数据通信系统中被广泛采用。采用这种方法后,二进制信号传递模型就可以变为图9-3所示的模型了。该模型按功能分为信源、编码器、信道、译码器、信宿等部分。图9-3通信系统模型

2.纠错码实例

由0和1组成的串称为字(Word),一些字的集合称为码(Code)。码中的字称为码字(CodeWord)。不在码中的字称为废码(InvalidCode)。码中的每个二进制信号0或1称为码元(CodeLetter)。

3.编码检错、纠错能力的分析

定义9.22Sn的任一非空子集C,如果是<C,◦>群,即C是Sn的子群,则称码C是群码(GroupCode)。

定义9.23设X=x1x2…xn

和Y=y1y2…yn是Sn中的两个元素,称H(X,Y)=∑ni=1xi⊕2yi为X与Y的汉明距离(HammingDistance)。

从定义可以看出,X和Y的汉明距离是X和Y中对应位码元不同的个数。设S3中两个码字为000和011,这