西交《离散数学》faq（七）

openhelp100

西交《离散数学》FAQ（七）
第五章 格与布尔代数
一、设
是格。

            a*b=a
a
b=b   。
[证].先证

              a
b=（a*b）
b             （条件：a*b=a）
                =b
(b*a)               （交换律）
   =b                     （吸收律）
   此证
       
             a*b=a*（a
b）             （条件：a
b=b）
                =a                      （吸收律）
二、
是格；且其伴随关系是整除关系
。
这里N为自然数集合，





由于两个自然数的最大公约数和最小公倍数是唯一的，且为自然数，故
是N上的两个二元运算。
1）





   故GCD运算和GCD运算满足结合律。
2）





3））

  

  

故GCD运算和LCM运算满足幂等律。
4）

  

  

故GCD运算和LCM运算满足吸收律。
      由格的定义知
是格（代数格）。
      根据定理，其伴随关系
的定义如下：
                           
a整除b。
       因此，格
的伴随关系
就是N上的整除关系
。
三、如图1所示的
是模格
根据定义易知
是格。
它有12个序组：


在这些序组下，充分
必要条件：

中b有5个取值，共计需验证12
5=60个等式。
我们象征性的验证一个等式：
，这时


即

所以，根据定理可知，如图1所示的
是模格。
四、如图2所示的
不是模格
根据定义易知
是格。
但是，在序组
下，取

，这时



                              


即

  所以，根据定理可知，如图1 所示的
不是模格。
五、图2所示的格
不是分配格
因为

即

  所以，根据定义 知
不是分配格。六、
是有界格
根据 一、已知
是格；
又由于

  有
，故
存在着此格的最小元；
  有
，故
存在着此格的最大元
因此，根据定义可知，
是有界格。
七、
不是有补格
这里
是由24的所有乘法因子所组成的集合       
  由右图可知

是格（|是半序，
并且上、下确界存在，就是LCM和GCD）。而且它是一个有界格   ，其最大元为24，最小元为1.此格中各元的补元如下表：

由表1知此格中有些元素没有补元，因此由有补格的定义知此格不是有补格。      八、开关代数（switching algebra）
是布尔代数
  这里
，其运算表如下：
   

通过变元代换，显见表2与表1是完全相同的，即，令


则易证h是一个双射的同态函数。
  因此开关代数
与集合代数

是同构的（这里
），所以开关代数

是一个布尔代数。
九、命题代数
是布尔代数
  这里
，其运算表如下：


通过变元代换，显见表3与表1是完全相同的。即，令

（这里
）
则易证h是一个双射的同态函数。
  因此，命题代数
与集合代数

是同构的（这里
），所以命题代数

是一个布尔代数。本内容由易百网整理发布
网址 www.openhelp100.com
QQ 515224986