大连理工大学软件学院 离散数学 第六章 代数系统3.ppt

* * * * * * * * * * * * * 解 2．求图中格的所有子格. 1元子格：{ a },{ b },{ c },{ d },{ e }； 2元子格：{ a, b },{ a, c },{ a, d }, { a, e },{ b, c },{ b, d }, { b, e },{ c, e },{ d, e }； 3元子格：{ a, b, c },{ a, b, d }, { a, b, e },{ a, c, e }, { a, d, e },{ b, c, e }, { b, d, e }； 4元子格：{ a, b, c, e },{ a, b, d, e }, { b, c, d, e }； 5元子格： { a, b, c, d, e } 练习2 e a b c d * 图13 3．判别下述格L是否为分配格. L1不是分配格, 因为它含有与钻石格同构的子格. L2和L3不是分配格, 因为它们含有与五角格同构的子格. L1 L2 L3 练习3 * L1 L2 L3 图12 4．针对下图，求出每个格的补元并说明它们是否为有补格 L1中, a与h互为补元, 其他元素没补元. L2中, a与g互为补元. b的补元为c, d, f；c的补元为b, d, e, f；d的补元为b, c, e；e的补元为c, d, f；f的补元为b, c, e. L3中, a与h互为补元, b的补元为d；c的补元为d；d的补元为b, c, g；g的补元为d. L2与L3是有补格. 练习4 * 5．对于以下各题给定的集合和运算判断它们是哪一类代数 系统（半群、独异点、群、环、域、格、布尔代数）, 并说 明理由. (1) S1 = {1, 1/2, 2, 1/3, 3, 1/4, 4}, ?为普通乘法. (2) S2 = {a1, a2, ..., an}, ?ai, aj∈S2, ai°aj = ai, 这里的 n 为给定 正整数, n1. (3) S3 = {0, 1},?为普通乘法. (4) S4 = {1, 2, 3, 6}, ?x,y∈S4, x°y与x?y分别表示 x 与 y 的最小公倍数和最大公约数. (5) S5 = {0, 1}, ?为模2加法, °为模2乘法. 练习5 * 解： 解答 (1) 不是代数系统, 因为乘法不封闭, 例如4?4=16. (2) 是半群但不是独异点, 因为?运算满足结合律, 但是没有单 位元. (3) 是独异点但不是群. 因为?运算满足结合律, 单位元是1, 可 是0没有乘法逆元. (4) 是格, 也是布尔代数. 因为这两个运算满足交换律和分配 律；求最小公倍数运算的单位元是1, 求最大公约数运算 的单位元是6, 满足同一律；两个运算满足补元律. (5) 是域. 对于模 n 的环Zn, 当n为素数时构成域. * 证 (2) 由 反之也对.下面证 明它们都等价于a≤b. 由 得 即 a≤b, 又由 a≤b 得 6．设B,∧,∨,-,0,1是布尔代数, 证明对于B中任意元素 a,b 练习6 * 练习7 7. 判断下述代数系统是否为格？是不是布尔代数？ (1) S = {1, 3, 4, 12}; 任给 x, y∈S, x°y = lcm(x,y), x?y = gcd(x,y), 其中 lcm 是求最小公倍数, gcd 是求最大公约数. (2) S = {0, 1, 2}; °是模3加法, ?是模3乘法 (3) S = {0, ..., n}, 其中n≥2; 任给 x, y∈S, x°y = max(x,y), x?y = min(x,y) (1) 是布尔代数. (2) 不是格. (3) 是格, 但不是布尔代数. * * * * * * * * * * * * * * * * * * * * * * * * * * 第六章3 格与布尔代数 主要内容 格的定义及性质 子格 分