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

170 第八章 格与布尔代数 本要求 1. 掌握半序格、半序子格、代数格、代数子格的定义，了解半序格和代数格的定义是等价 的。 2. 掌握互相对偶的两个关系、互相对偶的两个格的定义，了解二者关系。掌握格中表达式、 对偶格中的对偶表达式、本格中的对偶表达式的定义，掌握并会应用对偶原理 1 及对偶 原理 2。 3. 了解格的其它性质，如格的保序性、分配不等式、模不等式等。 4. 掌握并会应用格同态映射、格的自同态映射、格同构映射的定义。了解格的同态映射一 定是保序映射，同构映射的逆映射也是同构映 射等结论。 5. 掌握有界格、有余格、分配格以及模格的定义以及相关的结论。了解一个格为模格的充 要条件。 6. 掌握布尔代数的定义及其 16 个性质，掌握并会应用 理来判定一代数系统 是否为布尔代数。了解电路代数、集合代数、命题代数、开关代数。掌握并会应用布尔 代数的子集是其子代数的充要条件。 7. 掌握可唯一表示布尔代数中元素的基底的定义及其性质。掌握极小元的定义及其性质。 掌握布尔代数的生成、极小项、多项式、多项范式、布尔代数中一组元素互相独立等概 念，了解布尔代数中元素与多项范式 的关系和极小项、基底、极小元间的关系。 8. 掌握布尔代数中同态、同构的概念及其相应结论。了解如果两个有限布尔代数的维数相 同，则这两个代数同构；任意 n 维布尔代数（ B， ， +， ， 0， 1）与开关代数（ ， +， ， 0n， 1n） 同构； 理。 9. 掌握电路函数、布氏式的概念，了解任意一个电路函数，都可表为一个布氏式。掌握最 简多项式、极简多项式的概念。掌握两种得到组成极简多项式的极简项的方法： 法、 法，会应用这两种方法求极简项，对布尔代数进行化简。 10. 了 解 格与布尔代数在计算机科学中的应用。 171 要解题方法 应用格的性质 这部分习题要求读者熟记格及特殊的格的性质，并能灵活应用。 例 请判断下面关于格的命题的真假性 设（ 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，则 ab=a 和 a b=b 两者均不成立。 该命题为假命题。 因为一个元素可能有两个以上的余元素。 该命题为假命题。 因为根据有余格的定义，有余格一定是有界格，而（ N， |）显然不存在上界，因而不可能是有余分配格。 例 明：若一个有界格（ 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显然是矛盾的。因此，若一个有界格含 有不只一个元素，则任何一个元素的余元素必不是它自身。 例 明：若一个有限的全序格含有不只两个元素，则这个格必定不是有余格。 172 证明 ：因为全序关系是特殊的部分序关系，所以可以定义全序关系的格，设为（ 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 元均无余元素，故不是有余格。 例 （ 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。 也可用对偶原理证。 子格的判断 判断一个格中的一个子集是其格的办法是根据格的定义来进行判断，即证明该子集中任意两个元素构成的集合的最小上界和最大 下界都在该子集中，即运算封闭。 例 设（ 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 的代数子格。 例 设（ 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 的理想是一个子格。 173 例 f 是格（ L， +）到格（ S，）的同态映射，试证明（ L， +）的同态象是（ S，）的子格。 证明： （ L， +）的同态象是 f(L)=f(x)|x L。任取 f(L)，则有 L，满足 f(f( f 是格（ L， +）到格（ S，）的同态映射，知： f( f(= f( f( f(= f(l1+ 由（ L， +）是格知， L， l1+L，因此， f( f(L)， f(l1+ f(L)，即，f(L)， f(L)，故， f(L)对运算和封闭。（ L， +）的同态象是（ S，）的子格。 格的同态 判断一映射为格的同态映射，需注意验证加同态与乘同态两条。要记住格的同态映射一定是保序映射，但保序映射未必是同态映射。 例 （ L， +）是一 分配格， a L，设 f(x)=x+a， x L， g(x)=x a， x L， 证明： f 和 g 都是（ L， +）到自身的格同态映射。 证明： 对任意的 x， y L，有： f(x)+f(y)=(x+a)+(y+a) = (x+y)+a =f(x+y) f(x) f(y)= (x+a) (y+a) =(x y)+a L 是分配格 = f(x y)。 因此， f 是（ L， +）到自身的格同态映射。 同理可证， g 是（ L， +）到自身的格同态映射。 例 f 是格（ L， 1）到格（ S， 2）的满同态映射。证明：若（ L， 1）是有界格，则（ S， 2）也是有界格。 证明： 因（ L， 1）是有界格，设最大元为 1，最小元为 0。令 f(1)=1,f(0)=0，则 1，0 S。因 f 是满设，故对任意的 x S，都有 x L，使得 f(x)=x。又因为 f 是同态映射 ，因此亦是保序映射，故由 0 1x 11，有 f(0) 2f(x) 2f(1)，即 0 2x 21，这就是说 1和0分别是（ S， 2）的最大元和最小元。因此，（ S， 2）是有界格。 例 （ L， +）是一个分配格，相应的部分序关系为， a， b L。设 R=x|x L， a b x a， S=y|y L， b y a+b， 令 f(x)=x+b， x R， g(y)=y a， y S。 试证明： f 和 g 是 R 与 S 之间一对互逆的格同构映射。 174 证明： （ 1）首先证明 f 是 R 到 S 的映射， g 是 S 到 R 的映射。 任取 x R，由 R 的定义知， a b x a。因此， （ a b） +b x+b a+b， 而（ a b） +b=b， f(x)=x+b，故 b f(x) a+b， 由 S 的定义知， f(x) S。所以， f 是 R 到 S 的映射。 任取 y S，由 S 的定义知， b y a+b。因此， a b a y a (a+b)， 而 a (a+b)=a， g(y)=y a =a y，由交换律。 故 a b g(y) a， 由 R 的定义知， g(y) S。所以， g 是 S 到 R 的映射。 (2)往证 f 和 g 都是 1射而且互为逆映射。 任取 x R，有 g(f(x)=(x+b) a 由 f,g 定义 =(x a)+(b a) 由 L 是分配格 =x+(b a) 由 x a =x+(a b) 由交换律 =x 由 a b x 任取 y S，有 f(g(y)=(y a)+b 由 f,g 定义 =(y+b) (a+b) 由 L 是分配格 =y (a+b) 由 b y =y 由 y a+b 因此， f 和 g 都是 1射而且互为逆映射。 （ 3）往证 f 是 R 到 S 的格同态映射 ， g 是 S 到 R 的格同态映射。 显然，（ R， +）和（ S， +）均是格。 任取 x,y R，有 f(x)+f(y)=(x+b)+(y+b) =(x+y)+b =f(x+y), f(x) f(y)= (x+b) (y+b) = (x y)+b =f(x y)， 所以， f 是 R 到 S 的格同态映射。 任取 x,y S，有 g(x)+g(y)=(x a)+(y a) =(x+y) a =g(x+y), g(x) g(y)= (x a) (y a) = (x y) a 175 =g(x y)， 所以， g 是 S 到 R 的格同态映射。 综上， f 和 g 是 R 与 S 之间一对互逆的格同构映射。 下面是一道综合题，考察读者对第一章介绍的等价类、第六章介绍的二元代数运算的概念及本章中的代数格、格同构映射等概念的理解。注意证明一个映射是格同构映射，它必须是 1射而且是格同态映射。 例 f 是（ L， 1， 1） 到（ S， 2， 2） 的格同态映射。考虑商集 L/f=a|a L，其中 a=x|x L 且 f(x)=f(a)。在 L/f 上规定运算和如下：对任意的 a， b L/f，定义 a b=a 1b， a b=a 1b。证明： （ 1）和是 L/f 上的二元代数运算。 （ 2）（ L/f，）是一个代数格。 （ 3）令 g： a f(a)， a L/f，则 g 是 L/f 到 f(L)的格同构映射。 证明： （ 1）任取 x， y L，规定 x y f(x)=f(y)。显然， 是 L 上的等价关系，其等价类集合就是 L/f。 由和的定义，运算封闭性显然。 对任意的 L，若 往证 由 知 f(f( f(f( 又因 f 是同态映射，所以 f(1f( 2f(=f( 2f(=f(1 因此， 11 再由的定义 a b=a 1b，得 同理可证 这说明运算和与等价类的代表选取无关，它们确实是 L/f 上的二元代数运算。 （ 2）根据 1， 1 具有交换律、结合律、吸收律，不难验证和也具有这些性质。从而，（ L/f，）是一个代数格。例如，任取 a， b L，则 a b=a 1b=b 1a=b a， a b=a 1b=b 1a=b a。 故，满足交换律。 （ 3）首先证明（ f(L)， 2， 2） 是（ S， 2， 2）的子格。任取 a,b f(L)，存在 a，b L，使得 a=f(a),b=f(b)。于是，由 f 是同态映射，得 a 2b=f(a) 2f(b)= f(a 1b) f(L)， a 2b=f(a) 2f(b)= f(a 1b) f(L)， 因此，（ f(L)， 2， 2） 是（ S， 2， 2）的子格。 再证明 g 是 L/f 到 f(L)的 1射。任取 a， b L/f，有 a=b f(a)=f(b)， 故 g 是 L/f 到 f(L)的映射且是单射，又，显然 g 是 L/f 到 f(L)的满射，因而为 1射。 最后证明 g 是 L/f 到 f(L)的同态映射。任取 a， b L/f，有 g(a b)=g(a 1b)=f(a 1b)=f(a) 2f(b)= g(a) 2g(b)， g(a b)=g(a 1b)=f(a 1b)=f(a) 2f(b)= g(a) 2g(b)。 综上， g 是 L/f 到 f(L)的格同构映射。 176 尔代数 布尔代数是特殊的格 格、分配格、有余格所具有的性质，它都有，要熟记其性质并灵活应用。正是由于其特殊性，布尔代数间同态映射的要求更严格了。 还要注意到布尔代数的子代数一定含有原布尔代数的最大、最小元，并且应该保持原来的运算，一个元素若在子代数中，它的余元素也一定在该子代数中。 布尔代数的化简问题教材中讲得比较详细，在此不再赘述。 例 f 是布尔代数（ B， ， +， ， 0， 1） 到布尔代数（ S， ， ， ） 的同态映射，令 L= )=x|x B， f(x)= ， 试证明： （ 1） 0 L。 （ 2）若 b L，则对任意的 x B，只要 x b，就有 x L。 （ 3）对于任意的 x,y L，有 x+y L。 证明： （ 1）因为 f(0)=f(0 0 ) = f(0) f(0 ) 由 f 是同态映射 = f(0) （ f(0)） 由 f 是同态映射 = ， 所以，由 L 的定义知， 0 L。 （ 2）因为 b L，所以， f(b)= 。对任意的 x B，若 x b，则 x+b=b，于是， f(x+b)=f(b) = 。 另一方面，由 f 是同态映射知， f(x+b)=f(x) f(b) =f(x) 。 因此，有 f(x) = ， 故 f(x)= ，即 x L。 （ 3）任取 x,y L，有 f(x)= ， f(y)= 。于是， f(x+y)=f(x) f(y)= = ， 故 x+y L。 例 出含有 8 个元素的布尔代数的全体子代数。 解： 由教材中定理 理）知，若取 A=a,b,c，则 8 个元素的布尔代数必同构于（ （ A） , ）。故，只需给出（ （ A） , ）的全部子代数。 （ A） = ， a,b,c,a,b,a,c,b,c,a,b,c。 注意到它的子代数必然含有最小元 ，和最大元 a,b,c。 a和 b,c互为余元素， b和 a,c互为余元素， c和 a,b互为余元素。故全部子代数为： 177 ， a,b,c， ， a， b,c， a,b,c， ， b， a,c， a,b,c， ， c， a,b， a,b,c， ， a,b,c,a,b,a,c,b,c,a,b,c。 例 设（ L， ， 0， 1） 是一个布尔代数，如果在 L 上定义二元运算 +如下： a+b=(a ( b) ( a) b) 证明：（ 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 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），即运算满足结合律。故（ L,+）是半群。 （ 2）往证运算 +满足交换律。 由， 运算满足交换律，得 a+b=(a ( b) ( a) b) =（ b ( a)）（ ( b) a） = b+a, 故运算 +是可交换的。 （ 3）往证（ L,+）有壹（单位元）。 任取 a L，有 a+0=0+a=（ 0 ( a)）（ ( 0) a） =0 (1 a)=0 a=a， 故， 0 是（ L,+）的单位元。 （ 4）往证 L 中任意元素有逆。 任取 a L，有 a+a=（ a ( a)）（ ( a) a） =0 0=0， 故 L 中每个元素都以自身为逆元素。 综上，（ L,+）一个交换群。 例 设（ L， ， 0， 1） 是一个布尔代数，相应的部分序关系为“”。若 a,b1,b 证明： a 且仅当 存在 i， 1 i r， a= 证明：