离散数学---几个典型的代数系统6.2-3.ppt

6.2 环与域n环的定义与实例n特殊的环¨ 交换环¨ 含幺环¨ 无零因子环¨ 整环¨ 域 1环的定义定义 设是代数系统，+和·是二元运算. 如果满足以下条件: ￿￿ （1）构成交换群 ￿￿ （2）构成半群 ￿￿ （3）·运算关于+运算适合分配律则称是一个环.2环中的术语通常称+运算为环中的加法，· 运算为环中的乘法. 环中加法单位元记作 0 乘法单位元（如果存在）记作 1. 对任何元素 x，称 x 的加法逆元为负元，记作x. 若 x 存在乘法逆元的话，则称之为逆元，记作 x1. 3环的实例(1) 整数集、有理数集、实数集和复数集关于 普 通的加法和乘法构成环，分别称为整数环Z， 有 理数环Q，实数环R 和 复数环C. (2) n(n≥2)阶实矩阵的集合Mn(R)关于矩阵的 加 法和乘法构成环，称为n阶实矩阵环. ￿￿ (3) 集合的幂集P(B)关于集合的对称差运算和 交运算构成环. (4) 设Zn＝{0,1,.,n－1}，和分别表示模n 的 加法和乘法，则构成环，称为模n的 整 数环. 4特殊的环定义 设是环， (1) 若环中乘法·适合交换律，则称 R是交换环. (2) 若环中乘法·存在单位元，则称 R是含幺环. (3) 若a, b∈R，a b=0  a=0∨b=0，则称R是 无零因子环. (4) 若 R 既是交换环、含幺环，也是无零因子 环，则称 R 是整环.(5) 若 R为整环，|R|>1, 且aR*=R{0}， a1R, 则称 R 为域. 5零因子的定义与存在条件设是环，若存在 ab =0, 且 a0, b0, 称 a 为左零因子，b为右零因子，环 R 不是无零因子 环. 实例 ，其中 23=0，2 和 3 都是零因 子. 无零因子环的条件： 可以证明：ab = 0  a=0  b=0  消去律 6特殊环的实例(1)整数环Z、有理数环Q、实数环R、复数环C都是 交换环、含幺环、无零因子环和整环. 其中除Z 之外都是域 (2)令2Z={ 2z | z∈Z }，则构成交换环和无 零因子环. 但不是含幺环和整环. (3)设nZ, n2, 则 n 阶实矩阵的集合 Mn(R)关于矩 阵加法和乘法构成环，它是含幺环，但不是交换 环和无零因子环，也不是整环. (4)构成环，它是交换环、含幺环，但不 是无零因子环和整环. 注意：对于一般的 n, Zn是整环且是域  n是素数. 7例题判断下列集合和给定运算是否构成环、整环和域. (1) A={a+bi |a,bQ}, i2= 1, 运算为复数加法和乘法 .(2) A={2z+1 | zZ}, 运算为普通加法和乘法(3) A={2z | zZ}, 运算为普通加法和乘法(4) A={ x | x≥0 ∧ xZ}, 运算为普通加法和乘法.(5) ，运算为普通加法和乘法解 (2), (4), (5) 不是环. 为什么？ (1) 是环, 是整环, 也是域. (3) 是环, 不是整环和域. 8环的性质定理 设是环，则 (1) a∈R， a·0 = 0·a = 0 (2) a,b∈R， (a)b = a(b) = ab (3) a,b∈R， (a)(b) = ab (4) a,b,c∈R，a(bc) = abac，(bc)a = baca9环中的运算例 在环中计算 (a+b)3, (ab)2解 (a+b)3 = (a+b)(a+b)(a+b)￿￿ = (a2+ba+ab+b2)(a+b) ￿￿ = a3+ba2+aba+b2a+a2b+bab+ab2+b3 (ab)2 = (ab)(ab)=a2baab+b2 106.3 格与布尔代数n格的定义与实例n格的性质¨ 对偶原理¨ 交换律、结合律、幂等律、吸收律n 格的等价定义n 子格n 格的同构n 特殊的格：分配格、有界格、有补格、布尔格 11格的定义定义 设是偏序集，如果x,y≼S，{x,y}都有 最小上界和最大下界，则称S关于偏序≼作成一个 格. 由于最小上界和最大下界的惟一性，可以把求 {x,y} 的最小上界和最大下界看成 x 与 y 的二元运算∨ 和 ∧，即 x∨y 和 x∧y 分别表示 x 与 y 的最小上界 和 最大下界. 注意：这里出现的∨和∧符号只代表格中的运算 ， 而不再有其他的含义. 12格的实例例 设n是正整数，Sn是n的正因子的集合. D为 整除关系，则偏序集构成格.x,y∈Sn ， x∨y 是 lcm(x,y)，即 x 与 y 的最小公倍数. x∧y 是 gcd(x,y)，即 x 与 y 的最大公约数. 下图给出了格，和.￿￿13例 判断下列偏序集是否构成格，并说明理由.(1) ，其中P(B)是集合B的幂集.(2) ，其中Z是整数集，≤为小于等于关系.(3) 偏序集的哈斯图分别在下图给出.格的实例（续）解 (1) 是格. 称为B的幂集格. (2) 是格. (3) 都不是格. 14格的性质：对偶原理定义 设 f 是含有格中元素以及符号=,≼ ,≽ ,∨和∧的 命题. 令 f*是将 f 中的≼替换成≽,≽替换成≼,∨替换成 ∧,∧替换成∨所得到的命题. 称 f* 为 f 的对偶命题. 例如, 在格中： f 是 (a∨b)∧c≼c, f* 是 (a∧b)∨c≽c .格的对偶原理：设 f 是含格中元素以及符号=,≼,≽,∨ 和∧等的命题. 若 f 对一切格为真, 则 f 的对偶命题 f*也对一切格为真. 例如, 若对一切格L都有 a,b∈L, a∧b≼a，那么对一 切格L都有 a,b∈L, a∨b≽a15格的性质：算律定理 设是格,则运算∨和∧适合交换律、 结 合律、幂等律和吸收律,即 (1) a,b∈L 有 a∨b=b∨a, a∧b=b∧a (2) a,b,c∈L 有 ￿￿￿￿ (a∨b)∨c=a∨(b∨c), (a∧b)∧c=a∧(b∧c) (3) a∈L 有 ￿￿ a∨a=a, a∧a=a (4) a,b∈L 有 ￿￿￿￿ ￿￿ a∨(a∧b)=a, a∧(a∨b)=a 16算律的证明证 (1) 交换律. a∨b 是 {a,b} 的最小上界b∨a 是 {b,a}的最小上界{ a, b } = { b, a }  a∨b = b∨a. 由对偶原理, a∧b = b∧a 得证. 17算律的证明（续）(2) 结合律. 由最小上界的定义有(a∨b)∨c≽a∨b≽a ￿￿ (I)￿￿(a∨b)∨c≽a∨b≽b ￿￿ (II)￿￿￿￿￿￿￿￿(a∨b)∨c≽c ￿￿￿￿￿￿ (III)￿￿￿￿￿￿￿￿由式 (II) 和 (III) 有 (a∨b)∨c≽b∨c ￿￿￿￿ (IV)由式 (I) 和 (IV) 有 (a∨b)∨c≽a∨(b∨c). 同理可 证 (a∨b)∨c ≼ a∨(b∨c). 根据偏序的反对称性得到 (a∨b)∨c = a∨(b∨c). 由对偶原理, (a∧b)∧c = a∧(b∧c) 得证.18算律的证明（续）(3) 幂等律. 显然 a ≼ a∨a, 又由 a ≼ a 得 a∨a ≼ a. 由反对称性 a∨a = a. 用对偶原理, a∧a = a 得证. (4) 吸收律. 显然有a∨(a∧b) ≽ a (V)由 a ≼ a, a∧b ≼ a 可得a∨(a∧b) ≼ a (VI) 由式 (V) 和 (VI) 可得 a∨(a∧b) = a根据对偶原理, a∧(a∨b) = a 得证.19格作为代数系统的定义定理 设是具有两个二元运算的代数系统, 若对于∗和运算适合交换律、结合律、吸收律, 则 可以适当定义S中的偏序≼,使得构成格, 且 a,b∈S有 a∧b = a∗b, a∨b = ab.根据定理,可以给出格的另一个等价定义. 定义 设是代数系统, ∗和是二元运算, 如果 ∗ 和  运算满足交换律、结合律和吸收律, 则 构成格.20子格的定义及判别定义 设是格, S 是 L 的非空子集, 若 S 关于L中运算∧和∨仍构成格,则称S是L 的子格. 例 设格 L 如图所示. 令S1={ a, e, f, g }, S2={ a, b, e, g }S1不是 L的子格, S2是 L的子格. 因为对于e, fS1，e∧fS1.21格同态定义 设 L1和 L2是格, f: L1→L2, 若a,b∈L1有 f(a∧b) = f(a)∧f(b), f(a∨b) = f(a)∨f(b)成立, 则称 f 为格 L1到 L2的同态映射, 简称格同态. 22分配格定义定义 设是格, 若a, b, c∈L, 有 ￿￿ a∧(b∨c) = (a∧b)∨(a∧c) ￿￿￿￿ a∨(b∧c) = (a∨b)∧(a∨c)则称 L 为分配格.注意：以上条件互为充分必要条件在证明L为分配格时, 只须证明其中的一个等式即 可. 23分配格的定义（续）L1和 L2是分配格, L3和 L4不是分配格. 在 L3中, b∧(c∨d) = b，(b∧c)∨(b∧d) = a 在 L4中, c∨(b∧d) = c，(c∨b)∧(c∨d) = d 称 L3为钻石格, L4为五角格.24分配格的判定及其性质定理 设 L 是格, 则 L 是分配格当且仅当 L 不含 有 与钻石格或五角格同构的子格.证明省略. 定理 格 L 是分配格当且仅当 a, b, c∈L, a∧b=a∧c且a∨b=a∨c  b=c.推论(1) 小于五元的格都是分配格.(2) 任何一条链都是分配格. 25分配格的判定（续）解 L1, L2和 L3都不是分配格. { a, b, c, d, e }是 L1的子格, 并且同构于钻石格； { a, b, c, e, f }是 L2的子格, 并且同构于五角格； { a, c, b, e, f }是 L3的子格, 也同构于钻石格.例 说明图中的格是否为分配格,为什么？26全上界与全下界定义 设L是格, 若存在 a∈L 使得 x∈L 有 a ≼ x, 则称 a 为 L 的全下界； 若存在 b∈L 使得 x∈L 有 x ≼ b, 则称 b 为 L 的全 上界. ￿￿￿￿说明：格 L 若存在全下界或全上界,一定是惟一的. 一般将格 L 的全下界记为 0, 全上界记为 1.27有界格定义及其性质定义 设 L是格,若 L存在全下界和全上界, 则称 L为 有界格, 全下界记为0，全上界记为1 . 有界格 L 记 为 . 注意：有限格 L={a1,a2,…,an}是有界格, a1∧a2∧ …∧ an是 L 的全下界, a1∨a2∨…∨an是全上界. 0 是关于∧运算的零元,∨运算的单位元. 1 是关于∨ 运算的零元,∧运算的单位元. 对于涉及有界格的命题, 如果其中含有全下界0或全 上界1, 求其对偶命题时, 必须将0与1互换. 28补元的定义定义 设是有界格, a∈L, 若存在 b∈L 使得 ￿￿￿￿￿￿￿￿￿￿a∧b = 0 和 a∨b =1成立, 则称 b 是 a 的补元.注意：若 b 是 a 的补元, 那么 a 也是 b 的补元. a 和 b 互为补元. 29实例: 求补元 解：L1中 a, c互补, b没补元. L2中 a, d互补, b, c 互补. L3中 a,e互补, b 的补元是 c和d, c 的补元是 b和d, d 的补元是b和c. L4中的 a,e互补, b 的补元是 c和d, c 的补元是b, d 的补元是 b. 30有界分配格中补元惟一性定理 设是有界分配格. 若L中元素 a 存在补元, 则存在惟一的补元. 证 假设 b, c 是 a。