离散数学 格与布尔代数

1、2022-4-12回头看R， 是一个代数系统，（）R，是一个Abel群（）R， 是一个半群（） 对 满足分配律，即 a（bc）（ab）（ ac） （bc）a （ba）（ac） 整数环 、高斯环 、模m剩余环 、零环零环 回头看有单位元、无零因子的交换环称为整环 设R是一个有的环， 如果， 是一个群，则称R为除环，可交换的除环称为域 有限整环必为域若p为素数，则Zp，p，p 为域 0RR域F的特征 设F， 是一个域，则：（）在加法群F，中，每个非零元都具有同样的周期（阶）（）如果F，中非零元素的周期为有限数p，则p必为素数2022-4-12Chapter 7格与布尔代数Lattices &

2、;Boolean Algebra输入A B输出S C0 00 00 11 01 01 01 10 1 C S A B )()(BABABABASBAC C S A B Half adder 半加器 half adder 被加数 +）加数 进位 An Ai A2 A1 Bn Bi B2 B1 Cn+1 Cn Ci+1 Ci C2 C1 和 Sn+1 Sn Si+1 Si S2 S1 全加器 Full adder 全加器 Full adder InputA B CinOutputS Cout0 0 00 00 0 11 00 1 01 00 1 10 11 0 01 01 0 10 11 1 00

3、 11 1 11 1ininininCBACBACBACBASininininoutCBACBACBACBAC S Cout AB A B Cin Half adder Half adder AB C0 C1 Cn-1 Sn Bn An Cn Cout Cin S2 B2 A2 C2 Cout Cin S1 B1 A1 Cout Cin n位加法器 n-adder ininininCBACBACBACBASininininoutCBACBACBACBAC布尔表达式布尔代数Boolean Algebra偏序集 Posets（布尔）代数系统L，* 格L ,P， 格与布尔代数Lattice&

4、Boolean Algebra7.1 格 (1) 偏序集 Posets例 1:S30 = 1,2,3,5,6,10,15,30| = | x,yS30 且 x|y S6=1,2,3,6 S30 30 15 10 6 5 3 2 1 S15=1,3,5,15 S30 偏序集:, 2022-4-127.1 格 定义设L ,是一个偏序集，如果 x , yL ,x , y必有最小上界和最大下界，则称L ,为格 2022-4-12例例 集合集合S S的幂集的幂集P(S)P(S)和定义在其上的包含关系构成和定义在其上的包含关系构成 偏序集偏序集 P(S) .对于任意子集对于任意子集A,BA,Bp(S)S)

5、，因为，因为A A A AB,BB,B A AB B，而且若而且若A A C,B C,B C, C,则则A AB B C C。因此，因此， A,BA,B的最小上界的最小上界A A B=AB=AB B。 同理同理A,BA,B的最大下界的最大下界A A * * B=ABB=AB。于是，于是， P(S) 是格是格 ; ; ()。由集合由集合S=S=a,b,ca,b,c 得到的格得到的格L 的的HassHass图，如下图所示。图，如下图所示。7.1 格 2022-4-12a,b,ca,bb,cca,cab7.1 格 2022-4-1230611551023Example :, ,7.1 格 2022-

6、4-12例 判断图中的哈斯图表示的偏序集是否构成格,说明为什么。(b)(c)(d)(e)aaaabbbbccccddddeeeef(a)abcd7.1 格 例 设Z+为正整数集合，对于a,b Z+，关系“”定义为： ab当且仅当a整除b。则偏序集构成格， 其中: a b是a,b的最小公倍数(记作LCM,Least Common Multiple) a * b是a,b的最大公因数(记作GCD, Greatest Common Divisor) 即 a b= LCM(a,b)， a * b=GCD(a,b)7.1 格 x,yL ,x , y必有最小上界和最大下界30611551023并运算与交运算

7、在格L，中，a, b的最小上界用 ab 表示，a, b的最大下界用 a*b表示. a, bL，由最小上界、最大下界的唯一性，ab，a*b都在L上唯一确定将 , * 视为L上的两个运算，通常称为L，上的并(Join,)运算与交(Meet,)运算 并、交 运算的性质 定理设L，是一个格，并运算与交运算 * 满足如下性质：L1 a a a a * a a （幂等律）L2 a b b a a * b b * a （交换律）L3 （a b） c a （b c） (a * b) * c a *（b * c） （结合律）L4 a ( a * b ) a a*（a b） a （吸收集）L1：a * a a a

8、 a a 证明由于aa，故a是a，a的下界，又设c是a，a的任一下界，则ca，故a是a，a的最大下界，即a * a a，同理可证 a a a，即L1成立L2：a * b b * a， a b b a证明由于a，bb，a，故a * b b * a，同理a b b a即L2成立L3： (a * b) * c a *（b * c）( a * b ) * c a * b a( a * b ) * c a * b b( a * b ) * c c因此，(a*b) *c是b，c的下界，从而小于等于其最大下界，即( a * b ) * c b * c (xa且xb,则x bc )因此又知 ( a * b )

9、 * c 是a，b * c 的下界，从而 ( a * b ) * c a * ( b * c ) 同理 a * ( b * c ) ( a * b ) * c所以 a * ( b * c ) ( a * b ) * cL4： a*（a b） a由于a是a，ab的下界，故aa*(ab)，再由*的定义，a*(ab) a，从而a*(ab)a 设设是一个代数系统是一个代数系统, 和和*是是L上的两个二上的两个二元运算元运算,如果这两个运算满足幂等律（如果这两个运算满足幂等律（L1）、交换）、交换律律(L2)、结合律（、结合律（L3）和吸收律）和吸收律(L4),则称则称是一个是一个格格(Lattice)

10、。7.1 格 格与代数系统的关系 例例 是格是格表示为表示为又可表示为又可表示为7.1 格 例例 Z,或或 Z ,|7.2 格代数系统格L，中自然存在自然存在两个运算 和 * ，从而派生出一个代数系统L，*与 *满足LL。反之，若给定一个代数系统L，* ，其中，运算 与 * 满足LL，是否一定能找到一个与该代数系统对应的格？ 是，一定能。定理设L，是一个格，则对任意a，bLab a*ba abb证明： ab a*ba设ab，则a是a，b的下界，故aa*b， 又a*ba，从而a*ba； 反之，设a*ba，则由a*bb 即知 ab同理可证 ab，abb ab7.2 格代数系统如何定义偏序？偏序 必

11、须满足ab a * ba a bb 用ab a * ba a bb定义偏序首先要求给定的运算 与 *满足a * ba a bb 7.2 格代数系统引理设L，* 是一个代数系统，* 满足LL，则a * ba a bb证明设a * ba，则a b（a * b） bb（b * a）b反之，设a bb 则a * ba *（a b）a。7.2 格代数系统引理告诉我们在偏序关系上寻找* 是可行的。用 ab a * ba（ a bb ）规定关系 是可行的但这样规定的关系 是否一定是要求的偏序关系呢？ 7.2 格代数系统定理定理设L，* 是一个代数系统，运算 与 * 满足LL令 L上的关系 定义如下：a b

12、a * ba则 是一个偏序关系，且 a，bL，a*b，ab分别为a, b在L，中的最大下界与最小上界，即 a * binfa，b； a bsupa，b从而L，是一个格，其中的并、交运算恰为给定的 与 *7.2 格代数系统证明 为偏序关系(1)自反性;aL，因为a * aa，故aa，即满足自反性；(2)反对称性;a，bL，设ab，ba，则a * ba，b * ab，因为a * bb * a，故ab，即 满足反对称性；(3)传递性a，b，cL，设ab，bc，则a * ba，b * cb，故a * c（a * b）* ca *（b * c）a * ba，即ac，故满足传递性 7.2 格代数系统证L，

13、为要求的格 a，bL，（a * b）* a a*（a * b）（a * a）*ba*b，故a*ba，同理a*bb，因此a*b是a，b的下界，又设c是a，b的任一下界，即ca，cb，则a * cc，b * cc，于是（a * b）* ca *（b * c）a * cc，即ca * b，所以a * b是a，b的最大下界，即a * binfa，b，同理可证a bsupa，b，这就证明了L，是格且其中的并、交运算分别为 ，*. L3L17.2 格代数系统代数格定义设定义设L， ，* 是一个代数系统，是一个代数系统，如果如果 ，*满足满足LL，则称，则称L， ，* 为格为格7.2 格代数系统例设N是自然

14、数集合，对任意a，bN，规定a ba，b（即a，b的最小公倍数）， a*b（a，b）（即a，b的最大公因数）， 由于任意两自然数a，b都有唯一确定的最大公因数与最小公倍数，故 *， 是N上的两个运算L1、L2、L3、L4 是不是成立？7.2 格代数系统例设S是一个集合，为集合的并、交运算，则P（S），是格，且其中的偏序为集合的包含关系7.2 格代数系统定理设L，是格，a ，bL，则（）a*baa*bb（）aab bab7.2 格代数系统定理设L，是格，a，b，cL若ca，cb则ca*b若ac，bc则abc 以上两定理由并、交运算的定义可得到7.2 格代数系统定理设L，是一个格，a，a ，b ，

15、b L，如果 ab，ab，则 a* ab* b，a a b b证明：a * a ab，a* a a b 故 (a* a) b* b又 a b b b，a b b b故 a a(bb)7.2 格代数系统推论设L，是一个格，a，b，cL， 若ab， 则a*cb*c，acbc7.2 格代数系统定理设L是一个格，a，b，cL，则a *（b c）（a * b）（a * c）a （b * c）（a b）*（a c）b *（cd）b * ab （b * c）（b * d） b ec *（bd）c * ac（c * b）（c * d）e ddc d7.2 格代数系统证明：因为 b b c故 a * b a *

16、（b c）-(1)又 c b c故 a * c a *（b c）-(2)所以（a * b）（a * c） a *（b c）（依据定理5）即 a *（b c）（a * b）（a * c） 同理 a （b * c）（a b）*（a c）7.2 格代数系统2022-4-12定义子格子格(Sublattice):设设是一个格是一个格,如果如果是是的子代数的子代数,则称则称是是的子格的子格Sublattice)。子格也是一个格子格也是一个格,因为当运算因为当运算和和*限制在限制在S上时上时,交交换律、结合律和吸收律也是成立的。换律、结合律和吸收律也是成立的。7.3 子格与格同态2022-4-12不是不是

17、的子格，这的子格，这是因为是因为 abdcfeg3*Scfe子格子格(Sublattice):例设例设是一个格是一个格,其中其中 ，如下图，如下图gfecS,1gebaS,2gfeaS,3令令则则 和和是是的一个子格的一个子格, L， S，S，a ，c，S，本身是一个格，但它不是L，的子格 7.3 子格与格同态例，* 对任意a，bN，规定a * b（a，b）（即a，b的最大公因数）， a ba，b令S为N中所有偶数构成的集合S是N的子格 7.3 子格与格同态定义设L，* ，L，是两个格f：LL，如果 a , bL，有f（a b） f（a）f（b）f（a * b） f（a）f（b）则称f是格L到

18、L 的同态单、满同态，同构f：LL，f：L L 7.3 子格与格同态同态映射一定是保序映射。定理设f是格L到L 的同态，则f是偏序集L到L 的保序映射，即 x，yL，当xy时，f（x）f（y） xyx*yxf(x)* f(y)f(x * y)f(x)f(x)f(y) 7.3 子格与格同态保序映射未必是同态 f：a |，b|，c|，d|则f是L到L 的保序映射，但f（b * c）,f（b）* f（c）因此，f不是L到L 的同态 定理设f是格L到L 的双射，则f是L到L 的同构，当且仅当 a，bL， ab f（a）f（b）7.3 子格与格同态证明（1）若f（a）f（b），则ab；若f（a）f（b）

19、，则f（a）* f（b） f（a），f（a*b）f（a），故a*ba，ab（2） x，yL, xy,则x*y x，x*y y， 故 f（x*y）f（x）， f（x*y）f（y）， f（x*y）f（x）* f（y）；设 f（x）* f（y）f（z），此时必有，f（z）f（x），f（z）f（y），从而 z x，z y，于是 zx*y，f（z）f（x * y），即f（x）* f（y）f（x*y） 7.3 子格与格同态定义设L，是一个格，如果L的任意子集均有最小上界和最大下界，则称其为完全格有限格必为完全格整数集Z在通常数的小于等于关系下是一个格，其子集E，既无最小上界也无最大下界 7.4 完全格、有

20、界格、补格例 实数闭区间，在通常的小于等于关系 下是完全格， 实数开区间（，）则不然例 集合A的幂集格P（A），是完全格7.4 完全格、有界格、补格定义设L，是一个格，如果L中存在最大元与最小元，则称L是有界格最大元也称为全上界全上界或单位元，用表示；最小元也称为全下界全下界或零元，用表示，对应地，有界格也称为有单位元和零元的格 有界格有界格 L , ,*,0,1 完全格必为有界格. 7.4 完全格、有界格、补格例设A是集合，A的幂集格P（A）， 是有界格，其单位元为A，零元为例实数开区间（，）在通常小于等于关系下构成的格不是有界格7.4 完全格、有界格、补格定理设L是一个有界格，则对任意xL

21、，有x x，x x *， x * x7.4 完全格、有界格、补格01x定义设L是一个有界格，aL，如果存在bL使a b；a * b则称b是a的补元 7.4 完全格、有界格、补格例P（A）， 是A的幂集格，则对P(A)中任意元素S，有AS是S的补元 7.4 完全格、有界格、补格例定理设L是有界格，则单位元是零元的唯一补元 。7.4 完全格、有界格、补格01x定义设L是一个有界格，如果L中每个元素都有补元，则称其为补格补格或有补格有补格例如：集合A的幂集格P（A）是补格 7.4 完全格、有界格、补格补格 非补格 完全格、有界格、补格讨论为是元素之间的结构关系，并不涉及运算之间的关系。 7.4 完全

22、格、有界格、补格定理设L是一个格，a，b，cL，则a *（b c）（a * b）（a * c）a （b * c）（a b）*（a c）a *（b c）=（a * b）（a * c）a （b * c）=（a b）*（a c）7.5 分配格与模格 定义设L是一个格，如果L中的并、交运算互相可分配，即对任意a，b，cLa*(bc)(a*b)(a*c)a(b*c)(ab)*(ac)则称L是分配格a*(bc)a*1=a(a*b)(a*c)=0a=aa(b*c) a0=a(ab)*(ac)=1*a=a定理设L是一个格，如果L中的交对并可分配，则并对交必可分配反之亦然7.5 分配格与模格分配格与模格 证明：

23、a *（bc）（a * b）（a * c）则（a b）*（ac）（ab）* a）（ab）* c） a（ab）* c） a（a * c）（b * c）（ a（a * c）（b * c） a（b * c） 可分配吸收率可分配结合律吸收率例下图所示的两个格都不是分配格 7.5 分配格与模格分配格与模格 例集合A的幂集格P（A）是分配格 b *（cd）b * ab （b * c）（b * d）c *（bd）c * ac（c * b）（c * d）e dd定理设L，*是一个分配格，a，b，cL，如果a * ba * c ，abac则bc.bb *（b a）b *（a b）b *（a c）（b * a）（

24、b * c）（a * c）（b * c）（a b）* c（a c）* cc 证明：7.5 分配格与模格分配格与模格 交换律吸收率代入分配律代入分配律代入吸收率推论设L，* 是一个分配格，aL，a的补元若存在则是唯一的证明设a，a都是a的补元，则由补元的定义，有 a * aa * a a aa a 由定理2可得。 a a7.5 分配格与模格分配格与模格 例a * ba * cdabac但bc 7.5 分配格与模格分配格与模格 b *（ac）b * 1b（b * a）（b * c）d cc不是分配格。定义设L，*是一个格，如果 当ab时必有La *（b c） b （a * c） （模律）则称L为模

25、格 （或Demekind格）7.5 分配格与模格分配格与模格 定理分配格必是模格7.5 分配格与模格分配格与模格 证明设L，*是一分配格，a，b，cL若ab，则a*bb，从而a*(bc)=(a*b)(a*c)=b(a*c)所以L是模格 定理L是模格当且仅当由ab，a * cb * c，acbc，可推出 ab7.5 分配格与模格分配格与模格 证明:L，*是模格，ab，a * cb * c，acbc则 aa *（ac） a *（bc） b（a * c） b（b * c）b （模律）当ab时必有L5a *（b c）= b （a * c） 代入吸收吸收模律代入证明:设ab，则b（a * c） a （a

26、 * c）a因此（b（a * c）* ca*c又（b （a * c）* c（a * c）* ca * c故（b（a * c）* ca * c另一方面 （a *（bc）* ca *（bc）* c）a * c所以 （a *（bc）* c（b（a * c）* c （）（）同理 （a *（bc） c（b（a * c） c （）（）又因为ab，aa * c ,故ab（a * c）又 bcb（a * c）,所以 a *（bc）b（a * c）注意（），（）及定理条件便知 a *（bc）b（a * c）7.5 分配格与模格分配格与模格 例 在有界分配格中，所有有补元构成的集合为一个子格。7.5 分配格与模格

27、分配格与模格 2022-4-127.6 布尔代数 布尔格-有补分配格 Boolean lattice 定义:有补分配格中每元的补元唯一,从而可定义一个“取补”的一元运算.因此,此种格是一个有两个二元运算,一个一元运算和常数0,1的代数 L, *, ,0,1,称为布尔代数.(例如,幂集格(S), , ,S是布尔代数.)2022-4-12定义1: 布尔代数是有补分配格.7.6 布尔代数 定义2(公理化定义): 有两个二元运算的代数B, , * 称为布尔代数,如果对任意元素a,b,cB,成立:2022-4-12(交换律) a*b=b*a,ab=ba; (分配律) a*(bc)=(a*b)(a*c),

28、 a(b*c)=(ab)*(ac); (有界) 存在0,1B,使得 a*1=a,a0=a,aB; (有补) B的每一元a都有(唯一)aS,使得 a*a=0 , aa=1.7.6 布尔代数 2022-4-12例如:1 幂集代数: (S), , ,S; 2 命题代数: B, , ,F,T;7.6 布尔代数 2022-4-12例题：设集合L=1，2，5，10，11，22，55，110， 是110的正因子集合， 是整除关系，偏序集是否构成布尔代数，为什么？7.6 布尔代数 2022-4-12布尔表达式定义：定义：假设假设 B 是一个布尔代数，是一个布尔代数，x1,x2,xn是是 B 上的变量，上的变量

29、，B上由上由x1,x2,xn生成的布尔表达式归纳定义如下：生成的布尔表达式归纳定义如下：(1) B中的元素是中的元素是B上由上由x1,x2,xn生成的布尔表达式；生成的布尔表达式；(2) B上任意变量上任意变量xi（i=1,2,n）是是B上由上由x1,x2,xn生成生成的布尔表达式；的布尔表达式；(3)如果如果 ， 是是B上由上由x1,x2,xn生成的布尔表达式，则生成的布尔表达式，则， * ， （ 的补元）是的补元）是B上由上由x1,x2,xn生成的布尔生成的布尔表达式；表达式；(4)只有通过有限次使用只有通过有限次使用(1),(2),(3)得到的符号串是得到的符号串是B上由上由x1,x2,xn生成的布尔表达式。生成的布尔表达式。7.6 布尔代数 2022-4-12布尔表达式例：例：假设假设 B=0,1, 是由图是由图示确定的一个布尔代数，示确定的一个布尔代数，x,y 是是B