1 19.3 特殊的格 ?模格 ?分配格 ?有界格 ?有补格 ?布尔格 2 定义L为格，若?a,b,c∈L, a?b ? a∨(c∧b)=(a∨c)∧b 则称L为模格. 实例： 钻石格为模格 五角格不是模格 模格---模律：a?b ? a∨(c∧b)=(a∨c)∧b 格--模不等式：a?b ? a∨(c∧b)?(a∨c)∧b 模格 b a c 3 模格判别条件 L为模格当且仅当L不含有与五角格同构的子格. 充分性：假设L不是模格，则存在a,b,c∈L, 使得 a?b, a∨(c∧b)?(a∨c)∧b, 取5个元素x, y, z, u, v 如图. 证明思路： u?x?y?v，u?c?v x∧c=y∧c=u，x∨c=y∨c=v u, x, y, z, v两两不等， 构成L的5元子格 y=(a∨c)∧b x=a∨(c∧b) z=c u=c∧b v=a∨c 4 L为模格当且仅当 ?a,b,c∈L, a?b, a∨c=b∨c, a∧c=b∧c ? a=b 证：“?” 若不是模格，则存在子格与五角格同构， 必有a, b ,c 构成如图的子格，与条件矛盾. “?” 设L为模格， ?a,b,c∈L, a?b, a∨c=b∨c, a∧c=b∧c a = a∨(a∧c) = a∨(b∧c) = a∨(c∧b) = (a∨c)∧b = (b∨c)∧b = b 模格判别条件（续） b a c 5 定义 设L为格，若?a,b,c∈L有 a∧(b∨c) = (a∧b)∨(a∧c) 或 a∨(b∧c) = (a∨b)∧(a∨c) 则L为分配格. 注：在任何格中两个分配不等式是等价的. 例如 a∧(b∨c)=(a∧b)∨(a∧c) ? a∨(b∧c)=(a∨b)∧(a∨c) 证 (a∨b)∧(a∨c) = ((a∨b)∧a)∨((a∨b)∧c) (∧对∨的分配律) = a∨((a∧c)∨(b∧c)) (吸收律, ∧对∨的分配律) = (a∨(a∧c))∨(b∧c) = a∨(b∧c) (结合律, 吸收律) 反之，同理可证. 分配格 6 定理1 设L为模格，L为分配格当且仅当 若?a,b,c∈L有 (a∧b)∨(b∧c)∨(c∧a) = (a∨b)∧(b∨c)∧(c∨a) 注：一般格成立不等式 (a∧b)∨(b∧c)∨(c∧a) ? (a∨b)∧(b∨c)∧(c∨a) 定理2设L为模格，L为分配格当且仅当L不含 有与钻石格同构的子格. 分配格判别定理 7 证：“?” ?a,b,c∈L a∧(b∨c) = a∧(a∨b)∧(b∨c)∧(c∨a) （吸收律） = ((a∧b)∨((b∧c)∨(c∧a)))∧a （等式替代） = (a∧b)∨(((b∧c)∨(c∧a))∧a ) （模律a∧b?a） = (a∧b)∨(((c∧a)∨(b∧c))∧a ) （交换律） = (a∧b)∨(c∧a)∨(b∧c∧a) （模律） = (a∧b)∨(a∧c) 判别定理一的证明 8 “?” (a∧b)∨(b∧c)∨(c∧a) = [((a∧b)∨b)∧((a∧b)∨c)]∨(c∧a) (分配律) = [b∧(a∨c)∧(b∨c)]∨(c∧a) (吸收、分配律) = (b∧(a∨c))∨(c∧a) (吸收律) = (b∨c)∧(b∨a)∧(a∨c∨c)∧(a∨c∨a) (分配律) = (a∨b)∧(b∨c)∧(c∨a) (交换、幂等律) 判别定理一的证明（续） 9 充分性. 假设模格L不是分配格，则?a,b,c∈L使得 (a∧b)∨(b∧c)∨(c∧a) ? (a∨b)∧(b∨c)∧(c∨a) 令 u = (a∧b)∨(b∧c)∨(c∧a) v = (a∨b)∧(b∨c)∧(c∨a) x = u∨(a∧v) y = u∨(b∧v) z = u∨(c∧v) 则可以证明u, v, x, y, z构成钻石格. 注：所有的链为分配格，4元以下的格为分配格. 判别定理二的证明 u v x yz 10 模格、分配格之间的关系 a∧c=b∧c a∨c=b∨c ?a=b 分配律 格 模格 分配格 不含与五角 格同构子格 不含与钻石 格同构子格 a∧c=b∧c a∨c=b∨c a?b, ?a=b a?b, (a∨c)∧b=a∨(c∧b) (a∧b)∨(b∧c)∨(c∧a) =(a∨b)∧(b∨c)∧(c∨a) 11 全下界0和全上界1 全上界是格的最大元，全下界是格的最小元 有界格 有界格的定义 有界格的表示： <L, ∧, ∨, 0, 1> 有限格一定有界，无限格不一定（幂集格有界） 有界格的性质： (1) a∧1=a, a∨0=a, a∨1=1, a∧0=0, (2) 对偶命题： 如果有0,1，则0与1互换. 有界格与有补格 12 补元与有补格 0 c b a 1 0 1 a bc 0 1 a b c a∧b=0, a∨b=1, 则a与b互为补元. 0与1互补 a, b, c 没补元 0与1互补 a, b, c中任两 个元素都互补 0与1互补 a与b,c互补 13 有补格 补元性质： 有界分配格中的元素x 如果存在补元，则是唯 一的 有补格定义：每个元素都有补元的有界格 思考： 求补是否为有补格上的一元运算？ 求补是否为分配格上的一元运算？ 14 19.4布尔代数 ?布尔代数定义 ?布尔代数性质 ?布尔代数的同态 ?有限布尔代数的结构 15 定义 有补分配格称为布尔格（布尔代数） 实例：幂集格 定理 设<B,?,?,?, a,b>是代数系统，其中?,?为二元运算, ?为一元运算，a,b为0元运算. 如果满足以下算律： 交换律 x*y=y*x, x?y=y?x 分配律 x*(y?z)=(x*y)?(x*z) x?(y*z)=(x?y)*(x?z) 同一律 x?b=x, x?a=x 补元律 x??x=a, x??x=b 则<B,?,?, ?, a,b>构成布尔格. 布尔代数的定义 16 证明思路：由b,a分别为*和?运算的单位元， 证b和a恰为?和*运算的零元 吸收律、结合律 证：（1）x?b = (x?b)*b = (x?b)*(x??x) = x?(?x*b) = x??x = b x*a = (x*a)?a = (x*a)?(x*?x) = x*(?x?a) = x*?x = a （2）证吸收律 x?(x*y)=(x*b)?(x*y) = x*(b?y) = x*b = x x*(x?y)=(x?a)*(x?y) = x?(a*y) = x?a = x 定理证明 17 定理证明（续） （3）证结合律命题x°y=x°z, ?x°y=?x°z ? y=z x°(x?(y?z)) = x， x°((x?y)?z) = (x°(x?y))?(x°z) = x， (x°y)?(?x°y) = (x°z)?(?x°z) ? a°y = a°z ?x°(x?(y?z))=(?x°x)?(?x°(y?z))= ?x°(y?z) ?x°((x?y)?z)=(?x°(x?y))?(?x°z) = ?x°(y?z) ? y=z ? x°(x?(y?z))= x°((x?y)?z) ??x°(x?(y?z))= ?x°((x?y)?z) ?(x??x)°y=(x??x)°z 18 定理的证明（续） <B, ?, ?>构成分配格， 可定义偏序使得 ?，?分别表示求下界和上界运算. 由同一律知道a为全下界，b为全上界. 由补元律知道?x就是x的补元. 因此B构成布尔格. 19 布尔代数的性质 双重否定律 D.M律 等价条件1 a?b 等价条件2 a?b 10 =∨?=∧? baba bbaaba =∨?=∧? b? a ? 20 定义 B 1 ,B 2 为布尔代数，f :B 1 →B 2 , 若 )()( )()()( )()()( xfxf yfxfyxf yfxfyxf = ∨=∨ ∧=∧ 则称f为B 1 到B 2 的同态 同态判定： 三个等式仅需要两个，其中等式1和2不独立. 布尔代数的同态 21 命题的证明 证明 )()()( )()(),()()( yfxfyxf xfxfyfxfyxf ∨=∨? =∧=∧ )()( )()()()( )()( )()( yfxf yfxfyfxf yxfyxf yxfyxf ∨= ∧=∧= ∧=∧= ∨=∨ 22 有限布尔代数的结构 有限布尔代数的表示定理 设B是有限布尔代数，A是B的全体原子的集 合，则B与P(A)同构. 证明思路：小于b的原子为a 1 , a 2 , … , a k ， 那么b = a 1 ∨ a 2 ∨…∨ a k 映射f 满足：f(b) = { a 1 , a 2 , … , a k } 可以证明f：B→P(A)为同构映射 任何有限布尔代数元素数为2 n . 任何有限布尔代数都同构于{0,1} n . 23 例题 例1设?是布尔代数B 1 到B 2 的满同态映射， ～是?导出的B 1 上的同余关系. g: B 1 →B 1 /～是自然 映射，?x∈B 1 , g(x)=[x]={ y | y, x∈B 1 且?(y)=?(x) }. 证明存在惟一的同构映射f :B 1 /～→B 2 使得f°g=?. g ? f B 1 B 2 B 1 /～ x [x] ?(x) 24 同构f 的存在性 证：令f :B 1 /～→B 2 , f([x]) = ?(x), 则 [x]=[y] ? x～y ??(x) =?(y) 于是f 为良定义的，且为单射. 对于y∈B 2 , 由于?为满射，?x∈B 1 , 使得?(x)=y, 从而有 f([x]) = ?(x) = y. 于是f 为满射. 下面证明f 为同态映射. ?[x],[y]∈B 1 /～, f([x]∧[y])=f([x∧y])= ?(x∧y)= ?(x)∧?(y)=f([x])∧f([y]) 综合上述有B 1 /～?B 2 . （同态基本定理） ])([)()(])([)][( xfxxxfxf ==== ?? 25 同构f 的性质 下面证明f°g=?. ?x∈B 1 , f°g(x)=f(g(x))=f([x])= ?(x) 于是f°g=?. 再证明满足这一条件的f 是惟一的. 假设存在f 1 , f 2 使得f 1 °g=?, f 2 °g=?. 那么?x∈B 1 , f 1 °g(x) =f 2 °g(x). 于是 f 1 (g(x))=f 2 (g(x)) ? f 1 ([x])=f 2 ([x]) 由于x的任意性，必有f 1 =f 2 . 26 作业 ?复习要点： 模格、分配格、有补格、布尔格定义 以上特殊格的判别定理 布尔代数的性质 布尔代数的同态 有限布尔代数结构的唯一性 ?书面作业： 习题十九，21, 27, 33, 36.