内容发布更新时间 : 2024/5/19 9:08:55星期一 下面是文章的全部内容请认真阅读。

离散数学习题解 49

习题十三

13.1.

1.图 13.9 中给出 6 个偏序集的哈斯图.判断其中哪些是格. 如果不是格, 说明理由.

d

f d c b a (b) (c) e d f e

c b a (a) g f d e b a c

f d d c e b b f e

c a (f) b a

c a (d) (e)

13.9 图

(a), (c), (f)是格. (b)中的{e, d}没有最大下界. (d)中的{d, e}没有最大下界. (e)中的{a, b}没有最大下界.

13.2.2.下列各集合对于整除关系都构成偏序集, 判断哪些偏序集是格.

(1) L = {1, 2, 3, 4, 5} (2) L = {1, 2, 3, 6, 12}

(3) L = {1, 2, 3, 4, 6, 9, 12, 18, 36} (4) L = {1, 2, 22, ..., 2n}, n??+ (1)不是格, 其他都是.

13.3.3. (1)群??12, ??的子群格.

(2)画出 3 元对称群 S3 的子群格. 见答图.

离散数学习题解 50

?12

S3

?2?? ?3??

?(12)??

?4??

?(123)???(23)???(13)??

?6??

?0??(1)

?(1)??

(2)

第 3 题答图

13.4.4.设 L 是格, 求以下公式的对偶式:

(1) a??(a?b)? a

(2) a??(b?c) ? (a?b) ??(a?c)

(3) b??(c?a) ? (b?c) ?a. (1) a?(a?b) “a

(2) a??(b?c) “ (a?b) ??(a?c) (3) b??(c?a) “ (b?c) ?a

13.5.5.设?为集合 S 上可交换, 可结合的二元运算, 若 a, b 是 S 上关于?运算的幂等元, 证明 a?b 也是关于?运

算的幂等元. 证

a ??b = b ??c

(a ??b) ??(a ??b) = ((a ??b) ??a) ??b = (a ??(a ??b)) ??b = ((a ??a) ??b) ??b = (a ??a) ??(b ??b) = a ??b.

13.6.6.设 L 是格, a, b, c?L, 且 a ? b ? c, 证明

a ??b = b ??c

a ??b = b; b ??c = b.

13.7.7.针对图 13.4 中的格 L1, L2 和 L3, 求出他们的所有子格. d b a c a1 L2 L3 d1 d1 c2 b2 a2

L1

图 13.10

L1 的子格: {a}, {b}, {c}, {d}, {a, b}, {a,c}, {a, d}, {b, d}, {c, d},{a, b, d},{a, c, d}, L1. L2 的子格: {a1}, {d1}, L2

L3 的子格: {a2}, {b2}, {c2}, {d2}, {a2, b2}, {a2, c2}, {a2, d2}, {b2, c2}, {b2, d2}, {c2, d2}, {a2, b2, c2}, {a2, b2, d2}, {a2, c2, d2}, {b2, c2, d2}, L3

离散数学习题解

13.8.8. 设?L, ??是格, 任取 a?L. 令

51

S = {x | x?L??x?a}.

证明?S, ??是?L, ??的子格.

S 非空. ?x, y ?S, 有 x ? a, y ? a, 从而 x ??y ? x ?a, x ??y ? a ??a = a ? a, 于是 x ??y ??S, x ??y ??S, 即 S 对运算 ?, ??是封闭的. 因此 ?S, ???是 ?L, ???的子格.

13.9.9.针对图 13.9 中的每个格, 如果格中的元素存在补元, 则求出这些补元.

(b), (d), (e)不是格. (a)a 与 d 互补; b, c 没有补元. (c)a 与 f 互补; b 的补元为 c, d; c 的补元为 b, e; d 的补元为 b, e; e 的补元为 c, d. (f)a 与 f 互补; b 的补元为 e; c 和 d 没有补元; e 的补元为 b.

13.10.

10.说明图 13.9 中的每个格是否为分配格, 有补格和布尔格, 并说明理由.

(b), (d), (e)不是格.

(a)是分配格, 因为不包含与钻石格和五角格同构的子格; 不是有补格和布尔格, b, c 没有补元. (c)不是分配格, 不是布尔格, 因为包含五角格作为子格; 是有补格, a 与 f 互补, b 和 e 的补元有 c, d; c, d 的补 元有 b, e. (f)是分配格, 因为没有 5 元子格与钻石格或五角格同构; 不是有补格, 也不是布尔格, 因为 c 和 d 没有补元. 13.11. 11. 证明定理 13.8. 13.12. 12.对以下各小题给定的集合和运算判断它们是哪一类代数系统(半群, 独异点, 群, 环, 域, 格, 布

尔代数), 并说明理由.

(1) S1 = {0, 1, ?1}, 运算为普通加法和乘法.

(2) S2 = {a1, a2, ..., an}, ?ai, aj?S2, ai*aj = ai.这里的 n 是给定的正整数, 且 n≥2. (3) S3 = {0, 1}, *为普通乘法.

(4) S4 = {1, 2, 3, 6}, ○和*分别表示求最小公倍数和最大公约数运算.

(5) S5 = {0, 1}, *为模 2 加法, ○为模 2 乘法.

(1)不是代数系统, 对于加法不封闭. (2)是半群但不是独异

点, 运算封闭, 有结合律, 没有单位元.

(3)是独异点但不是群, 乘法封闭, 有结合律, 单位元是 1, 但是 0 没有逆元.

(4)是布尔代数. 因为这两个运算满足交换, 相互分配, 同一律(求最小公倍数的幺元是 1, 求最大公约数的幺 元是 6), 补元律.

(5)是域. 因为{0, 1}关于模 3 加构成交换群, {1}关于模 3 乘构成交换群, 模 3 乘关于模 3 加有分配律. 13.13.

13.设 B 是布尔代数, B 中的表达式 f 是

( a ??b) ??(a ??b ??c) ??(b ??c)

(1)化简 f. (2)求 f 的对偶式 f *.

(1) (a?b) ??(a?b?c) ??(b?c) = (a?b) ??(b?c) (2) f *= (a?b) ??(b?c) 13.14. 13.15.

14. 缺. 15.对于 n = 1, ..., 5, 给出所有不同构的 n 元格, 并说明哪些是分配格, 有补格和布尔格.

离散数学习题解 52

(a)

(b)

(c)

(d)

(e)

(f) (g) (h) (i) (j)

第 15 题答图

布尔格: (a), (b), (e)

分配格: (a), (b), (c), (d), (e), (f), (g), (h) 有补格: (a), (b), (e), (i), (j)

13.16.

16.设?B, ?, ?, ?, 0, 1?是布尔代数, 在 B 上定义二元运算?, ?x, y?B 有

x?y = (x?y?) ??(x??y)

问?B, ??能否构成代数系统? 如果能, 指出是哪一种代数系统.为什么?

构成群, 运算封闭. 下面证明结合律. 任取 a, b, c

(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????a ??c) ??(a????b????c) ??(b ??a ??c) ??(b ??b????c)

??(a ??b????c?) ??(a????b ??c?) ??0 ??(a????b????c) ??(a ??b ??c) ??0 ??(a ??b????c?) ??(b ??c????a?) ??(c ??a????b) ??(a ??b ??c)

a ??(b ??c) ??(b ??c) ??a ??(b ??c????a?) ??(c ??a????b?) ??(a ??b????c?) ??(b ??c ??a)

易见结合律成立.

由 a ??0 ??(a ??0?) ??(a????0) ??(a ?1) ??0 ??a , 知 0 为单位元.

由 a ??a ??(a ??a?) ??(a????a) ??0 ??0 ??0 , 知 a 为本身的逆元.

同理有

13.17. 13.18.

17. 缺. 18. 缺.