西交《离散数学》faq（七）
西交《离散数学》FAQ（七）第五章 格与布尔代数
一、设是格。
a*b=a ab=b 。
[证].先证
ab=（a*b）b （条件：a*b=a）
=b(b*a) （交换律）
=b （吸收律）
此证
a*b=a*（ab） （条件：ab=b）
=a （吸收律）
二、是格；且其伴随关系是整除关系。
这里N为自然数集合，
由于两个自然数的最大公约数和最小公倍数是唯一的，且为自然数，故是N上的两个二元运算。
1）
故GCD运算和GCD运算满足结合律。
2）
3））
故GCD运算和LCM运算满足幂等律。
4）
故GCD运算和LCM运算满足吸收律。
由格的定义知是格（代数格）。
根据定理，其伴随关系的定义如下：
a整除b。
因此，格的伴随关系就是N上的整除关系。
三、如图1所示的是模格
根据定义易知是格。
它有12个序组：
在这些序组下，充分
必要条件：
中b有5个取值，共计需验证125=60个等式。
我们象征性的验证一个等式：，这时
即
所以，根据定理可知，如图1所示的是模格。
四、如图2所示的不是模格
根据定义易知是格。
但是，在序组下，取
，这时
即
所以，根据定理可知，如图1 所示的不是模格。
五、图2所示的格不是分配格
因为
即
所以，根据定义 知不是分配格。六、 是有界格
根据 一、已知是格；
又由于
有，故存在着此格的最小元；
有，故存在着此格的最大元
因此，根据定义可知，是有界格。
七、 不是有补格
这里是由24的所有乘法因子所组成的集合
由右图可知
是格（|是半序，
并且上、下确界存在，就是LCM和GCD）。而且它是一个有界格 ，其最大元为24，最小元为1.此格中各元的补元如下表：
由表1知此格中有些元素没有补元，因此由有补格的定义知此格不是有补格。 八、开关代数（switching algebra）是布尔代数
这里，其运算表如下：
通过变元代换，显见表2与表1是完全相同的，即，令
则易证h是一个双射的同态函数。
因此开关代数与集合代数
是同构的（这里），所以开关代数
是一个布尔代数。
九、命题代数是布尔代数
这里，其运算表如下：
通过变元代换，显见表3与表1是完全相同的。即，令
（这里）
则易证h是一个双射的同态函数。
因此，命题代数与集合代数
是同构的（这里），所以命题代数
是一个布尔代数。本内容由易百网整理发布
网址 www.openhelp100.com
QQ 515224986
页:
[1]