9学习指导与习题解答-8

离散数学

第八章 格与布尔代数

§8.1 基本要求

1. 掌握半序格、半序子格、代数格、代数子格的定义，了解半序格和代数格的定义是等价

的。

2. 掌握互相对偶的两个关系、互相对偶的两个格的定义，了解二者关系。掌握格中表达式、

对偶格中的对偶表达式、本格中的对偶表达式的定义，掌握并会应用对偶原理1及对偶 原理2。

3. 了解格的其它性质，如格的保序性、分配不等式、模不等式等。

4. 掌握并会应用格同态映射、格的自同态映射、格同构映射的定义。了解格的同态映射一

定是保序映射，同构映射的逆映射也是同构映射等结论。

5. 掌握有界格、有余格、分配格以及模格的定义以及相关的结论。了解一个格为模格的充

要条件。

6. 掌握布尔代数的定义及其16个性质，掌握并会应用Huntington公理来判定一代数系统

是否为布尔代数。了解电路代数、集合代数、命题代数、开关代数。掌握并会应用布尔 代数的子集是其子代数的充要条件。

7. 掌握可唯一表示布尔代数中元素的基底的定义及其性质。掌握极小元的定义及其性质。

掌握布尔代数的生成、极小项、多项式、多项范式、布尔代数中一组元素互相独立等概 念，了解布尔代数中元素与多项范式的关系和极小项、基底、极小元间的关系。

8. 掌握布尔代数中同态、同构的概念及其相应结论。了解如果两个有限布尔代数的维数相

同，则这两个代数同构；任意n维布尔代数（B，·，+，ˉ，0，1）与开关代数（Bn，·， +，ˉ，0n，1n）同构；Stone定理。

9. 掌握电路函数、布氏式的概念，了解任意一个电路函数，都可表为一个布氏式。掌握最

简多项式、极简多项式的概念。掌握两种得到组成极简多项式的极简项的方法：Quine 方法、Karnaugh图法，会应用这两种方法求极简项，对布尔代数进行化简。 10. 了解格与布尔代数在计算机科学中的应用。

离散数学

§8.2 主要解题方法

8.2.1 应用格的性质

这部分习题要求读者熟记格及特殊的格的性质，并能灵活应用。 例8.2.1 请判断下面关于格的命题的真假性

⑴ 设（L，×， ）是格，则（L，×）和（L， ）均为交换半群。

⑵ 设（L，×， ）是格，a，b∈L，那么，a b=a和a b=b至少有一个成立。 ⑶ 设（L，×， ）是格，a∈L，若a有余元素，那么该余元素是唯一的。 ⑷ 设N为正整数集合，| 为其上的整除关系，则（N，|）为有余分配格。 解：

⑴ 该命题为真命题。

因为若（L，×， ）是格，则×和 均满足交换律、结合律和运算的封闭性，所以（L，×）和（L， ）均为交换半群。。

⑵ 该命题为假命题。

设L={ ，{x},{y},{x，y}}，则（L，∩，∪）是一个格，若令a={x}，b={y}，则a∪b=a和a∪b=b两者均不成立。

⑶ 该命题为假命题。

因为一个元素可能有两个以上的余元素。 ⑷ 该命题为假命题。

因为根据有余格的定义，有余格一定是有界格，而（N，|）显然不存在上界，因而不可能是有余分配格。

例8.2.2 证明：若一个有界格（L，×， ，0，1）含有不只一个元素，则该有界格中任何一个元素的余元素必不是它自身。

证明：我们已经知道在有界格中0，1互为余元素。若存在x≠0，x≠1，但x以自身为余元素，则有

x×x=0， x x=1，

而又由于

x×x=x， x x=x，

所以，x=0，x=1，即0=1。由题设有界格（L，×， ，0，1）含有不止一个元素知，0=1显然是矛盾的。因此，若一个有界格含有不只一个元素，则任何一个元素的余元素必不是它自身。

例8.2.3 证明：若一个有限的全序格含有不只两个元素，则这个格必定不是有余格。

离散数学

证明：因为全序关系是特殊的部分序关系，所以可以定义全序关系的格，设为（L，×， ，0，1），相应的全序关系为≤。在全序格中任取非0、1的元素x。由于

x×0=0，但x 0=x≠1， x 1=1，但x×1=x≠0，

所以0和1均不是x的余元素。对任意非0、非1的元素y，由全序格中任意两个元素可比较大小知，或者有x≤y，或者有y≤x，不妨设前者成立，则x×y=x≠0，因此，x无余元素。即，若一个有限的全序格含有不只两个元素，则其中非0、非1元均无余元素，，故不是有余格。

例8.2.4 设（L，×， ，0，1）是有界格，相应的部分序关系是≤，证明：对于a，b∈L，

（1）若a b=0，则a=b=0， （2）若a×b=1，则a=b=1。 证明：（1）因为a≤a b，由题设a b=0，所以a≤0。另一方面，因0是L上的最小元，有0≤a。由≤的反对称性知，a=0。同理可证b=0。

（2）因为a×b≤a, 由题设a×b=1，所以1≤a。另一方面，因1是L上的最大元，有a≤1。由≤的反对称性知，a=1。同理可证b=1。

也可用对偶原理证。

8.2.2 子格的判断

判断一个格中的一个子集是其格的办法是根据格的定义来进行判断，即证明该子集中任意两个元素构成的集合的最小上界和最大下界都在该子集中，即运算封闭。

例8.2.5 设（L，×， ，0，1）是有界分配格，证明：L中拥有余元素的的各元素构成一个代数子格。

证明：设L中拥有余元素的的各元素构成的集合为L’，对于任意的a，b∈L’，它们的余元素分别记为a’和b’。

首先考察a×b，因为

(a×b)×(a’ b’)=(a×b×a’) (a×b×b’)=0 0=0 (a×b) (a’ b’)=(a a’ b’)×(b a’ b’)=1×1=1 所以a×b有余元素a’ b’，a×b∈L’。

同理，a b有余元素a’×b’，所以，a b∈L’。 因此，L’对运算×， 封闭，故L’是L的代数子格。

例8.2.6 设（L，×，+）是格，L’是L的非空子集，如果： ⑴ 对于任意的a，b∈L’，有a+b∈L’;

⑵ 对任意的a∈L’和任意x∈L，若x≤a，则x∈L’。 那么称L’是格L的理想。

试证明：格L的理想是一个子格。 证明：根据（1），有L’对运算+是封闭的。

因为（L，×，+）是一个格，L’是L的子集，所以对任意的a，b∈L’，有a×b≤a，再根据（2），得a×b∈L’。因此L’对运算×亦封闭。

故格L的理想是一个子格。

离散数学

例8.2.7 设f是格（L，×，+）到格（S，∧，∨）的同态映射，试证明（L，×，+）的同态象是（S，∧，∨）的子格。

证明：（L，×，+）的同态象是f(L)={f(x)|x∈L}。任取s1，s2∈f(L)，则有l1，l2∈L，满足f(l1)=s1，f(l2)=s2。由f是格（L，×，+）到格（S，∧，∨）的同态映射，知：

s1∧s2 = f(l1)∧f(l2)

= f(l1×l2)，

s1∨s2 = f(l1)∨f(l2) = f(l1+l2)。

由（L，×，+）是格知，l1×l2∈L，l1+l2∈L，因此，f(l1×l2)∈f(L)，f(l1+l2)∈f(L)，即，s1∧s2∈f(L)，s1∨s2∈f(L)，故，f(L)对运算∧和∨封闭。（L，×，+）的同态象是（S，∧，∨）的子格。

8.2.3 格的同态

判断一映射为格的同态映射，需注意验证加同态与乘同态两条。要记住格的同态映射一定是保序映射，但保序映射未必是同态映射。

例8.2.8 设（L …… 此处隐藏：14852字，全部文档内容请下载后查看。喜欢就下载吧 ……