离散数学习题解 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. 缺.