1计算机数学基础离散数学辅导(8)第 8 章其它代数系统(2021 级用) 中央电大 冯 泰本章重点：格与布尔代数概念，布尔代数运算、化简和恒等式证明. 一、重点内容1. 环与域环，设 G 是非空集合，在 G 上定义加法和乘法两种运算，如果满足：(1) (G,+)是交换群(阿贝尔群)； (2) (G,)是半群；(3) 乘法对加法适合左、右分配律，即对a,b,cG,有a(b+c)=ab+ac (a+b)c=ac+bc则代数系统(G,+,)为环.环就是定义了代数运算， ，其中“” 满足交换律，“”满足结合律， 对满足左右分配律的代数系统. 交换环，环(G,+,)的乘法满足交换律： ab=ba. 则( G,+,)是交换环. 交换环就是两个代数运算都满足交换律的环. 除环，环(G,+,)的乘法 存在单位元；非 0 元对有逆元的环. 域 设(S,+, )是代数系统，如果满足：(1) (S， )是交换群； (2) (S0，)是交换群；(3) 运算 对运算是可分配的. 则(S,+, )为域. 交换除环是域. 环与域关系图 域除 环或代 数 系 统 可 分 配对） 是 交 换 群，（） 是，（：，运 算 元 有 逆 元存 在 单 位 元 ， 非；），； （， （， )3(;0)2(;)1( 0),(), SS GGSG交 交交交交交 交环的同态、同构注意：群是定义了一个代数运算的代数系统；环、域是是定义了两个代数运算的代数系统. 2. 格偏序格，设(L ，)是一个偏序集，如果对于a,bL， L 的子集 a,b在 L 中都有一个最大下界(记为 infa,b)和一个最小上界(记为 supa,b),则( L，)是一个偏序格.子集在 L 中有上确界和下确界的偏序集，就是格. 代数格，在 L 定义二元运算*，满足：对a,b,cL,有 (1) 交换律 a*b=b*a， ab=ba (2) 结合律 (a*b)*c=a*(b*c) , (ab) c=a (bc)(3) 吸收律 a*(ab)=a， a (a*b)=a则(L,*, )是代数格 . 用代数的语言，格就是在非空集合上定 义了两个满足 结合律、交 换律和吸收律的代数系统. 偏序格代数格. 对偶式，由 1，0 和可以代表格中的任意元素的变量通过，运算连结起来的式子，就是格中的表达式，记作 f. 将 f 中的 0 换成 1，1 换成 0，换成，换成所得的表达式，就是表达式 f 的对偶式记作 f*. 2对偶原理 若 f 为真，则 f*为真. 3. 特殊格有界格，设(L ，)是格，如果 L 有最大元素( 记作 1)和最小元素(记为 0)，则(L，)称为有界格，记作(L ,1,0)或(L,*, ,0,1). 存在最大和最小元素的格，就是有界格. 有余格，设(L ，*， ，0， 1)是有界格，如果 L 中的每一个元素都至少有一个余元素，则(L，* ， ，0 ，1) 为有余格(或称为有补格). 有最大和最小元素，且存在余元的格.亦即有余元的有界格就是有余格 . 它们的关系：格 有界格 有余格. 有 最 大 元 、 最 小 元 有 余 元分配格， (L，*， )是格，如果对 a,b,cL，有a*(boc)=(a*b) (a*c) a (b*c)=(ab)*(ac) 则（L，*,) 为分配格 . 满足左、右分配律的格就是分配格. 格的运算性质(1) (L， )是一个格，a, bL，有 aba*b=aab=b(2) (L， )是一个格，a, bL，如果 bc，有 a*ba*c， abac(3) (L，) 是一个格，a,b,cL，有分配不等式：a (b*c)(ab)*(ac) a*(bc)(a*b) (a*c)(4) (L，) 是一个格，a,b,cL，有 aba (b*c)b*(ac)在格中德摩根律成立： 4. 布尔代数布尔代数，一个有余分配格就是一个布尔代数布尔代数的公理定义，设 B 是一个至少含有两个元素的集合，是定义在 B 上的两种运算，如果对a,b,c B，满足下列公理(定理 10)：H1：ab =ba a+b=b+a (交换律 )H2：a(b+c)=a b+ac a+(bc)=(a+b)(a+c) (分配律)H3：B 中有元素 0 和 1，对aB,有a1=a a+0=a (有最大元、最小元 )H4：对aB ,有 aB，满足aa=0 a+a=1 (有余元 )则(B， ， ，0，1)是一个布尔代数记住布尔代数运算的 10 条算律(P289. 定理 9). 二、实例例 8.1 证明 是环，其中 Z 是整数集，运算 定义如下：),(Z,ababa1证明 (1)证(Z, )是交换群. ，c)()( 21cbacba显然有 又 ，即 1 是运算 的单位元. 1，即 2a 是 a 关于运)(1)2()(,2, 单 位 元有 Za3算 的逆元. 所以，(Z, )是交换群. (2)证 (Z， )是半群. ，cba)()( )()()()(cbacb bcabcab所以运算 是可结合的. 那么(Z ， )是半群. (3) 证运算 对 适合分配律. ，ca, )( 12(1)()1()( cbacb bcacba)( 12(12)()1(bcabc bcaba故运算 对 适合分配律. 总之，( )是环. ,Z例 8.21 设 ，其中 Q 是有理数集，证明(Q.，+，) 是域，,3(Q和分别是数的加法和乘法.证明 )3()()(3()(), 111121 Qbababa 且惟一，故运算是 Q( )上的二元运算，加法满足结合律、交换律. . Q( )的 0 元是00 . ,即存在逆元. 3 03,有所以(Q( ), )是交换群. 且惟一，)3()()3()()(,3, 1211121 babababa 故是 Q( )上的二元运算. 容易验证在 Q( )上满足交换律、结合律. Q( )的单位元是 10 . 任给非 0 元 (a,b 至少一个不为 0)，33)(3)( 221 baba运算在 Q( )上非 0 元存在逆元.所以(Q( ) 0，)是交换群.可以验证，运算对满足分配律. 所以(Q( )， )是域.3例 8.3 试判断(Z ,)是否为格？其中是数的小于或等于关系. 解 显然( Z,)是一个偏序集 . 又 ，x, y 的最小上界为 , x, y 的最大下Z, )ma(1 本例可以作为提高要求.4界为 ，皆为整数，仍然属于 Z. 故对 Z 的任意子集，在 Z 中都有上确界和下确界. ),min(yx即(Z,)是格. 例 8.4 设非空集合 A，验证( )是布尔代数，AP,)(证明 因为集合 A 非空，故 P(A)至少有两个元素，显然 ，是 P(A)上的二元运算. 由定理 10 ，任给 B,C,DP(A),H1 BD=DC CD=DC H2 B(CD)=(BC)(BD) B(CD)=(BC)(BD)H3 P(A)存在 和 A，BP(A), 有 BB ， BABH4，B P(A), BA，存在 AB，有BAB)= A B(AB)= 所以( )是布尔代数. ,)例 8.5 是布尔代数， ，化简 . 10cba, cbacab解 bcaabcbc)()(例 8.6 单项选择题 1. 下列图(如图 81)表示的偏序集中，是格的为( ) 图 81答案：(C)解答：所给(A),(B),(D) 的偏序集，都有两个极大元，不存在上确界，都不是格，只有(C)的偏序集有上确界和下确界，是格. 故选择(C)正确. 2. 设 是布尔代数， ，则下式不成立的是( )1,0,(BbaB,1)D)C()Ababa答案：(D)解答：因为 B 是偏序集， . 故； 否 则 ， 不 成 立则若那 么 ,选择(D)正确. 3. 布尔代数式 =( )(cbacbba (C)()(答案：(B)解答： . ac)1)(故选择(B)正确. 例 8.7 填空题1. 非空集合 L，其上定义二元运算和，如果 是交换群，(L, )是 ，而且 满足分配律，则 L 对二元运算和构成环. (A) (B) (C) (D) 5答案：(L, )；半群；二元运算 对运算解答：见环的定义. 2. 设 L 是一个集合，和是 L 上两个二元运算，如果这两个二元运算满足 律，律和 律，则(L ,)是格. 答案：交换律；结合律；吸收律解答：见代数格的定义. 3. 在布尔代数中，有 成立. 则该式的对偶式 也ba)(一定成立. 答案： ba)(解答：见对偶原理，知 是原式的对偶式，也是成立的. )(三、练习题1.设 R 是实数集，“”为数的加法，“”定义为 . 试问 R 对二元运算ba和是否构成环？2. 回答下列代数系统是环吗？是交换环吗？(1) (Zm,， *),其中 Zm 0,1,2,m1 ，和*是模 m 加法和乘法. (2) (Mn(R)， ), 其中 Mn(R)是 n 阶实矩阵全体，分别是矩阵的加法和乘法. 3*. 给定代数系统(G,+,*), 二元运算见表 81，表 82. 表 81 表 82+ a b cd * a b c dA a b a a a a aB b a b a b c dc da b c a c d bd d cb a d a d b c证明(G,+,*)是域. 4. 设 143)(,12)( 23 xxQxP是定义在 Z5( 0,1,2,3,4)上的多项式( 即系数是 Z5的元素的多项式)，试计算 P(x)+Q(x)，P (x)Q(x). 5.下列给定的偏序集(如图 82) 是格吗？为什么？ 图 826. 化简布尔代数式 ba7. 在布尔代数( )中，对 有,B,Bc)()(bcba四、练习题答案1. (1)显然实数 R 对加法满足交换律，( R，) 是交换群. ，有c, cbacba)()()2(所以， ，即(R,) 是半群. (3) , )(6满足左分配律；，acbcb)( acb