发布时间 : 星期日 文章最新洪帆《离散数学基础》(第三版)课后习题答案更新完毕开始阅读
精品文档
(b) 是格，因为任何两个元素都有下确界和上确界。
不是格，因为最上层两个元素没有上确界。
6、设?L,?,??是格，试证明对于所有的a,b,c?L，则有：
(a?b)?(a?(b?c))?b?(a?c))
证明：根据格的分配律，我们有 a?(b?c)?(a?b)?(a? c) 因为a?b，所以a?b?b，所以(a?(b?c))?b?(a?c))。
7、 设?L,?,??是一个格，如果对于所有的a,b,c?L，有 (a?b)?(a?(b?c))?b?(a?c))
则称?L,?,??是模式格，下图所给出的格是模式格吗？证明你的结论。
解：不是模式格，因为对于b,d,c这三个元素，b?d，但是b?(d?c)?b?a?b，
而d?(b?c)?d?e?d，并不满足模式格的要求，因此不是模式格。
8、证明具有两个或更多个元素的格中，不会有元素是它自身的补。
证明：因在格中求补元，此格必为有界格，设?L,??为有界格，若#(L)?2，则
L?{0,1}。因为0?0?0,0?0?0,1?1?1,1?1?1,0?1?0,0?1?1，因此0和
精品文档
精品文档
1互为补元，即具有两个元素的格中不存在以自身为补元的元素。若#(L)?2，设存在l?L，l?0且l?1，若l以自身为补元，则由补元的定义：
l?l?0?l?l?l?1，可得l?0?1，与假设矛盾。因此不存在以自身为补元的元素。
9、设?L;?,??是一个格，#(L)?1，试证明如果?L;?,??有元素1和元素0，
则这两个元素必定是不相同的。
证明：反证，假设这两个元素是相同的，并记l?0?1，则根据最大元素和最小
元素的定义，我们有对?l1?L，0?l?l1?l?1，则l?l1，因此#(L)?1，这
与条件矛盾。
10、举例说明并非每一有补格都是分配格；并非每个分配格都是有补格。 解：由下图(a)表示的格由于元素z无补元，因此不是有补格；但是对任意三个元
素都满足分配等式，因此是分配格。
(a)
下图(b)表示的格中，0和1互为补元， x,y两两互补，因此是有补格。又 因为x?(y?z)?x?1?x，(x?y)?(x?z)?0?0?0，即
x?(y?z)?(x?y)?(x?z)
所以不是分配格。
(b)
11、 设?L,??是一个格，a,b?L，且a?b(即a?b，但是a?b)，令集合
精品文档
精品文档
La? B?{x|x?且证明?B,??也是一个格。
x?} bl1?l2?lub(l1,l2)。，
l2?b(gl,l)证明：因为?L,??是格，所以对任意l1,l2?L，有l1?1l2由B的定义知B?L，a?B，所以B??。对任意x,y?B， 由于?L,??是格，所以x?y和x?y在L中存在且唯一。 下证x?y?B,x?y?B。
由B的定义知a?x?b，a?y?b。所以a?x且a?y，根据格的保号性及
等幂性有a?a?a?x?y，所以a?x?y。类似地，x?b,y?b得x?y?b，所以
a?x?y?，即bx?y?B。类似地可证明a?x?y?b，即x?y?B。
12、设?L;??是一个格，试证明对于任意的元素a,b,c?L，有下列命题成立： (1) 若a?b?a?b，则a?b
(2) 若a?b?c?a?b?c，则a?b?c (3) a?[(a?b)?(a?c)]?(a?b)?(a?c)
证明：(1) 因为a?a?b?a?b?a，所以a?a?b，同理有b?a?b，因此a?b。
a?a?b?c?a?b?c?a (2) 因为b?a?b?c?a?b?c?b，所以a?b?c?a?b?c?a?b?c。
c?a?b?c?a?b?c?c (3) 由格的分配律
a?[(a?b)?(a?c)]?(a?(a?b))?(a?(a?c))?(a?b)?(a?c)
又因为a?[(a?b)?(a?c)]为(a?b)?(a?c)和a的上确界，因此
a?[(a?b)?(a?c)]?(a?b)?(a?c)
因此得证。
13、设a和b是格?L;??中的两个元素，试证明当且仅当a,b不可比时，。 a?b?a,a?b?b证明：必要性：(反证)已知 a,b不可比，因为一定有a?b?a，所以若a?b?a，
则a?b，因此a,b可比，因此矛盾。
充分性：(反证)假设a,b可比，则由格的性质，a?b?a且a?b?b，矛盾。
14、设集合A?{a,b,c}，集合A上所有分划所构成的集合为P(A)，你能否适当定义P(A)上一个偏序关系?,使得?P(A);??成为一个格？
解：记P(A)?{?i}，其中?i为A的一种分划，定义P(A)上的偏序关系为，若分
精品文档
精品文档
划?i是?j的一个细分，则?i??j。显然有，对任意?i?P(A)，?i??i因此具有自反性；若?i??j,?j??i，则?i??j因此具有反对称性；若?i??j,?j??k，则?i??k(根据细分的定义很容易得出)，所以具有可传递性，因此是偏序关
?1?{{a},{b},{c}},?2?{{a,b},{c}}系。A?{a,b,c}中3个元素，共5种：?3?{{a},{b,c}},?4?{{a,c},{b}}
?5?{{a,b,c}} 则对定义二元运算?i??j??i(若?i??j)，?i??j??1(若?i和?j不可比) ?i??j??(j若?i??j)，?i??j??5(若?i和?j不可比) 可以画出该偏序关系的次序图如下：
显然定义的偏序关系是格。
15、试证明在格中对任意元素a,b,c，有
(a?b)?(b?c)?(c?a)?(a?b)?(b?c)?(c?a)
证明:因为a?b?a，b?c?b，c?a?a，所以(a?b)?(b?c)?a?b， (( a?b)?(b?c)?)c(?a)?a(?b?)a?，所以可得：a?b (a?b)?(b?c)?(c?a)?a， ?同理有：b (a?b)?(b?c)?(c?a)?b?，和c(a?b)?(b?c)?(c?a)?a?c 所以(a?b)?(b?c)?(c?a)?(a?b)?(b?c)?(a?c)成立。
16、试证明在格中对于任意元素a,b,c?L，有：
(a?b)?(b?c)?(c?a)?(a?b)?(b?c)?(c?a)
时，格?L,??是分配格。
证明：必要性：设?L,??是分配格，则对于任意a,b,c?L有：
(a?b)?(b?c)?(c?a)?[(a?b)?(b?c)?c)?][a(?b?)b(?c?a?[(a?b)?c]?[b(?c)?a]
?(a?c)?(b?c)?(b?a)?(c?a)?(a?b)?(b?c)?(c?a)充分性：对于任意a,b,c?L，令a??(a?b)?(a?c)，b??b?c，c??a，则
精品文档