离散数学：布尔代数-离散数学

布尔代数：称一个有补分配格为布尔代数.具有有限个元素的布尔代数称为有限布尔代数.除了两个二元运算之外，布尔代数中还有一个一元运算（补运算），因此布尔代数常常记为＜L，∨，∧，’，0，1＞.

布尔代数的性质：在布尔代数中＜L，∨，∧，’，0，1＞中，对任意a，b，c∈L，有

（1）交换律：a∧b=b∧a，a∨b=b∨a

（2）结合律：（a∧b）∧c=a∧（b∧c），（a∨b）∨c=a∨（b∨c）

（3）幂等律：a∧a=a，a∨a=a

（4）吸收律：a∧（a∨b）=a，a∨（a∧b）=a

（5）分配律：a∧（b∨c）=（a∧b）∨（a∧c），a∨（b∧c）=（a∨b）∧（a∨c）

（6）同一律：a∨0=a，a∧1=a

（7）零一律：a∧0=0，a∨1=1

（8）互补律：a∧a’=0，a∨a’=1

（9）对合律：（a’）’=a

（10）德·摩根律：（a∨b）’=a’∧b’，（a∧b）’=a’∨b’

原子：在布尔代数＜L，∨，∧，’，0，1＞中，a∈L，若对任意的b∈L有0＜b≤a⇒b=a，则称a是L中的一个原子.

定理8.4　有限布尔代数＜L，∨，∧，’，0，1＞的两个不同原子a和b一定有a∧b=0.

定理8.5　对有限布尔代数＜L，∨，∧，’，0，1＞的任一个元素b，b≠0，则至少存在一个原子a使得a∧b=a，即a≤b.

定理8.6　对有限布尔代数＜L，∨，∧，’，0，1＞，若a是L的一个原子，则对任意元素b，a≤b和a≤b’有且仅一式成立.

定理8.7　设＜L，∨，∧，’，0，1＞为有限布尔代数，对任意的x∈L，x≠0，a1，a2，…，an是满足ai≤x的全部原子，则x=a1∨a2∨…∨an，且在不考虑原子的顺序的情况下该式是唯一的.

定理8.8（Stone有限布尔代数的表示定理）　设＜L，∨，∧，’，0，1＞为有限布尔代数，S=｛a1，a2，…，an｝是它的所有原子的集合，则＜L，∨，∧，’，0，1＞与集合代数＜P（S），∪，∩，C，Ø，S＞同构.

定理8.9　任一有限布尔代数的元素个数一定是2的幂次（若其有n个原子，则它有2n个元素）.

定理8.10　元素个数相同的布尔代数一定是同构的.

重点

1.格中运算的基本性质.

2.分配格的判定.

3.有补格的判定.

4.布尔格的判定，布尔代数的性质，Stone表示定理.

难点

1.分配格的判定.

2.Stone表示定理.

例题解析

例8.1　下列集合对于整除关系都构成偏序集，判断哪些偏序集是格？

（1）L=｛1，2，3，4，5｝.

（2）L=｛1，2，3，4，6，9，12，18，36｝.

（3）L=｛1，2，3，4，5，6，7，8，9，10｝.

【分析】判定一个偏序集构成格的充要条件是任意两个元素组成的集合有上（下）确界.因此要确定一个偏序集不是格，则只需找出两个元素，它们组成的集合要么没有上确界，要么没有下确界.

解：(www.xing528.com)

（1）因为｛3，4｝无上界，从而也没有上确界，故L不是格.

（2）因为任意两个元素组成的集合都有上（下）确界，故L是格.

（3）因为｛8，9｝无上界，从而也没有上确界，故L不是格.

例8.2　设＜L，≤＞是格，证明：若a≤b≤c，则

（1）a∨b=b∧c.

（2）（a∧b）∨（b∧c）=（a∨b）∧（b∨c）.

【分析】利用格＜L，≤＞的运算∧和∨满足的性质：交换律、结合律、幂等律和吸收律.以及a≤b⇔a∧b=a⇔a∨b=b.

证明：

（1）由a≤b得a∨b=b，而由b≤c得b∧c=b，所以a∨b=b∧c.

（2）因为（a∧b）∨（b∧c）=（a∧b）∨b=b，而由a∨b=b和b∨c=c得（a∨b）∧（b∨c）=b∧c=b，所以（a∧b）∨（b∧c）=（a∨b）∧（b∨c）.

例8.3　D90表示90的全体因子的集合，包括1和90，D90与整除关系构成格.

（1）画出格的哈斯图.

（2）计算6∨10、6∧10、9∨30和9∧30.

（3）求D90所有含4个元素且包含1和90的子格.

【分析】S是L的子格⇔S关于L中的运算∨和∧仍构成格.

解：

（1）格＜D90，≤＞所对应的哈斯图如下：

（2）从图中可以看出6∨10=30，6∧10=2，9∨30=90，9∧30=3.

（3）通过对除去1、90之后的10个元素的二元素组合共C210=45个进行验证，可求得满足条件的子格共有24个：｛1，2，6，90｝；｛1，2，10，90｝；｛1，2，18，90｝；｛1，2，30，90｝；｛1，2，45，90｝；｛1，3，6，90｝；｛1，3，9，90｝；｛1，3，15，90｝；｛1，3，18，90｝；｛1，3，30，90｝；｛1，3，45，90｝；｛1，5，10，90｝；｛1，5，15，90｝；｛1，5，18，90｝；｛1，5，30，90｝；｛1，5，45，90｝；｛1，6，18，90｝；｛1，6，30，90｝；｛1，9，10，90｝；｛1，9，18，90｝；｛1，9，45，90｝；｛1，10，30，90｝；｛1，15，30，90｝；｛1，15，45，90｝.

例8.4　设＜L，∨，∧，’，0，1＞是一布尔代数，在L上定义二元运算⊕为：a⊕b=（a∧b’）∨（a’∧b），证明＜L，⊕＞是一个阿贝尔群.

【分析】这是一个综合题目，需要我们掌握布尔代数和群的知识.为了证明＜L，⊕＞是一个阿贝尔群，需要根据布尔代数运算所满足的性质证明运算⊕是可结合和可交换的，存在单位元，每个元素关于⊕有逆元.

证明：

由于∨、∧、’这三个运算在L上都是封闭的，所以⊕在L上也是封闭的.

（1）对任意a，b，c∈L，（a⊕b）⊕c=（（a∧b’）∨（a’∧b））⊕c

=（（（a∧b’）∨（a’∧b））∧c’）∨（（（a∧b’）∨（a’∧b））’∧c）

=（a∧b’∧c’）∨（a’∧b∧c’）∨（（a’∨b）∧（a∨b’）∧c）

=（a∧b’∧c’）∨（a’∧b∧c’）∨（（（a∧b）∨（a’∧b’））∧c）

=（a∧b’∧c’）∨（a’∧b∧c’）∨（a∧b∧c）∨（a’∧b’∧c）

同理可证a⊕（b⊕c）=（a∧b’∧c’）∨（a’∧b∧c’）∨（a∧b∧c）∨（a’∧b’∧c）

所以（a⊕b）⊕c=a⊕（b⊕c），即运算⊕满足结合率.

（2）因为：a⊕b=（a∧b’）∨（a’∧b）=（b∧a’）∨（b’∧a）=b⊕a，所以运算⊕是可交换的.

（3）对任意a∈L，a⊕0=0⊕a=（0∧a’）∨（0’∧a）=0∨（1∧a）=a，故0是L中关于运算⊕的单位元.

（4）对任意a∈L，a⊕a=（a∧a’）∨（a’∧a）=0∨0=0，故L中每个元素都均以自身作为逆元.

综上所述，＜L，⊕＞是一个阿贝尔群.