洪帆《离散数学基础》(第三版)课后习题答案

(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和

37

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),令集合

38

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)上的偏序关系为,若分

39

划?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,则

40

联系客服:779662525#qq.com(#替换为@)