离散数学基础学习辅导

其它代数系统

本章学习环、域、格与布尔代数。

一、基本要求

1. 知道环、子环与域的概念。

2. 了解格(偏序格、代数格及其等价性)、子格等概念。

3. 知道有界格、有余格、分配格的概念。

4. 了解布尔代数概念，掌握其性质和运算。

掌握布尔恒等式的证明和布尔表达式的化简。知道亨廷顿公理。

本章重点：格与布尔代数概念，布尔代数运算、化简和恒等式证明。

二、学习指导

1. 环与域

h环设G是非空集合，在G上定义加法＋和乘法·两种运算，如果满足：

(1) (G,+)是交换群(阿贝尔群)；

(2) (2) (G,·)是半群；

(3) (3) 乘法对加法适合左、右分配律，即对"a,b,cÎG,有

a·(b+c)=a·b+a·c (a+b)·c=a·c+b·c

则称代数系统(G,+,·)为环.

环就是定义了代数运算＋，·，其中“＋”满足交换律，“·”满足结合律，·对＋满足左右分配律。

h交换环环(G,+,·)的乘法满足交换律：a·b=b·a. 则称(G,+,·)是交换环。

交换环就两个代数运算都满足交换律。

h除环环(G,+,·)的乘法·存在单位元；非0元对·有逆元的环。

h域设(S,+,·)是代数系统，如果满足：

(1) (1) (S，＋)是交换群；

(2) (2) (S－{0}，·)是交换群；

(3) (3) 运算·对运算＋是可分配的.

则称(S,+,·)为域.。或者域就是交换除环。

域比环条件强，但是比交换环条件弱。

环与域关系图

h环的同态、同构

例8.1 证明是环，其中Z是整数集，运算定义如下：

证明 (1)，

显然有

又，即1是运算的单位元。

对，即2－a是运算的逆元。

从而得到(Z,)是交换群。

(2)，

所以运算是可结合的。那么(Z，)是半群。

(3)，

故，运算对适合分配律。

总之，()能构成环。

例8.2 试判别()和()是不是域。其中

解根据环的定义，不难验证(Z₃,＋₃，Ä₃)和(Z₄,＋₄，Ä₄)是环(即验证①(Z₃,＋₃)是交换群；②(Z₃,Ä₃)是半群；③运算Ä₃对＋₃有分配律)。

对于(Z₃,＋₃，Ä₃)和(Z₄,＋₄，Ä₄)，我们只需验证它们满足以下条件：

(1) (1) 运算Ä₃和Ä₄是否可交换；

(2) (2) 运算Ä₃和Ä₄是否具有单位元；

(3)Z₃和Z₄中的每一个非0元素分别对于Ä₃和Ä₄是否具有逆元。

（注：满足(1)和(2)，表示(Z₃,＋₃，Ä₃)和(Z₄,＋₄，Ä₄)是除环，又满足(1)表示(Z₃,＋₃，Ä₃)和(Z₄,＋₄，Ä₄)是交换除环）

为此我们构造Ä₃和Ä₄的运算表

表8－1 Ä₃的运算表 表8－2 Ä₄的运算表

Ä₃	0	1	2	Ä₄	1	2	3
0	0	0	0	0	0	0	0
1	0	1	2	1	1	2	3
2	0	2	1	2	2	0	2
				3	3	2	1

由表8－1可知，运算Ä₃是可交换的，1是Ä₃的单位元(因为"kÎZ₃，k=0,1,2，,kÄ₃1=k=1Ä₃k)。非0元素关于Ä₃存在有逆元，1^－1＝1，2^－1＝2(从表看出1Ä₃1^－1＝1Ä₃1＝1(单位元)，2Ä₃2^－1＝2Ä₃2＝1(单位元))。因此，(Z₃,＋₃，Ä₃)是域。

从表8－2可知，运算Ä₄是可交换的，1是Ä₄的单位元(因为"kÎZ₄，k=0,1,2，3，,kÄ₃1=k=1Ä₃k)。非0元素1，3，有1^－1＝1，3^－1＝3(从表看出1Ä₄1^－1＝1Ä₄1＝1(单位元)，3Ä₄3^－1＝3Ä₄3＝1(单位元))，但是非0元素2没有逆元。因此，(Z₄,＋₄，Ä₃)不是域。

2. 格

h格设(L，£)是一个偏序集，如果对于"a,bÎL，L的子集{a,b}在L中都有一个最大下界(记为inf{a,b})和一个最小上界(记为sup{a,b}),则称(L，£)是一个偏序格.

子集在L中有上确界和下确界的偏序集，就是格。

h代数格在L定义二元运算*，^o满足：对"a,b,cÎL,有

(1) 交换律 a*b=b*a，a^ob=b^oa

(2) 结合律 (a*b)*c=a*(b*c) , (a^ob)^oc=a^o(b^oc)

(3) 吸收律 a*(a^ob)=a， a^o(a*b)=a

则称(L,*,^o)是代数格.

用代数的语言，格就是在非空集合上定义了两个满足结合律、交换律和吸收律的运算。

h对偶式由1，0，和可以代表格中的任意元素的变量通过＋，×运算连结起来的式子，就是格中的表达式，记作f。将f中的0换成1，1换成0，＋换成×，×换成＋所得的表达式，就是表达式f的对偶式记作f^*。h

h对偶原理若f为真，则f^*为真。

例8.3 试判断(Z,£)是否为格？

解显然(Z,£)是一个偏序集。又皆为整数，仍然属于Z。故对Z的任意子集，在Z中都有上确界和下确界。即(Z,£)是格。

3. 布尔代数

h一个有余分配格称为一个布尔代数

设B是一个至少含有两个元素的集合，·，＋是定义在B上的两种运算，如果对"a,b,cÎB，满足下列公理：

H₁：a·b=b·a a+b=b+a

H₂：a·(b+c)=a·b+a·c a+(b·c)=(a+b)·(a+c)

H₃：B中有元素0和1，对"aÎB,有

a·1=a a+0=a

H₄：对"aÎB,有`aÎB，满足

a·`a=0 a+`a=1

则(B，·，＋，`` ，0，1)是一个布尔代数

h记住布尔代数运算的10条算律。

例8.4 设()是布尔代数，，证明()是B的子布尔代数，而且是布尔代数，其中。

证明对于集合T中的元素作运算见表8－3。

表8－3 T的元素元素表

Ú	0	a	`a	1	Ù	a	`a	1	1
0	0	a	`a	a	0	0	0	0	0	1
a	a	a	1	a	a	a	0	a	a	`a
`a	`a	1	`a	a	`a	0	`a	`a	`a	a
1	1	1	1	1	1	a	`a	1	1	0

由B是布尔代数可知，从表8－3得到T对运算Ú，Ù，` 是封闭的，所以()是子布尔代数。由定理11知()也是布尔代数。

三、实例

例1 非空集合L，其上定义二元运算¡和·，如果是交换群，(L,·)是，而且满足分配律，则L对二元运算¡和·构成环。

答案：(L,¡)；半群；二元运算·对运算¡

解答：见环的定义。

例2 设L是一个集合，·和¡是L上两个二元运算，如果这两个二元运算满足律，

律和律，则(L,·,¡)是格。

答案：交换律；结合律；吸收律

解答：见代数格的定义。

例3 下列图表示的偏序集中，是格的为( )

(A) ¢      ¢ (B) ¢     ¢     (C)    ¢      (D)   ¢

      ¢              ¢           ¢ ¢ ¢      ¢   ¢   ¢

   ¢    ¢     ¢      ¢            ¢            ¢