离散数学左孝陵第六章

经典的教程

代数系统

第六章

格和布尔代数

§1格的概念 §2分配格 §3有补格 §4*布尔代数

经典的教程

§1格的概念1.偏序集合格《定义》格是一个偏序集合 L, ,其中每一对元素 a, b L 都拥有一个最小上界和最大下界。通常用a b 表示a和b的最大下界，用 a b 表示a和b的最小 GLB 上界。即： {a, b} a b

——称为元素a和b的保交运算， LUB{a, b} a b ——称为元素a和b的保联运算。

经典的教程

§1格的概念例：以下均为偏序集合格(D为整除关系，Sn为n的因 子集合)。

经典的教程

§1格的概念2.代数系统格 《定义》:设 L, 是一个格，如果在A上定义两个 二元运算 和 ,使得对于任意的a,b A,a b等 于a和b的最小上界，a b等于a和b的最大下界，那 么就称<L, , > 为由格 L, 所诱导的代数系统。

经典的教程

§1格的概念3.格的主要性质： (1)格的对偶原理 设<L,≤>是格，“≤”的逆关系“≥”与L组成的偏序集 <L, ≥>也是格。两者互为对偶。前者的GLB,LUB恰好 是后者的LUB,GLB。如有关于<L,≤>的有效命题， 将“≤”换成“≥”,“ ”换成“ ”, “ ”换成 “ ”,便能得到<L, ≥>的有效命题。反之亦然。

经典的教程

§1格的概念(2)对格<L,≤>中任意a和b,有a≤a b及a b≤a。

(3) <L,≤>是格。对任意a,b,c,d L,如a≤b, c≤d,则 a c≤ b d, a c≤b d

经典的教程

经典的教程

§1格的概念(4)(交换律)交和并运算是可交换的。 (5)(结合律)交和并运算是可结合的。

经典的教程

§1格的概念(6)(幂等律)对L中每一个a,有a a=a,a a=a。 (7)(吸收律)对L中任意a,b, 有a (a b)=a a (a b)=a。

经典的教程

§2分配格对格所定义的代数系统<L, , >,其运算 和 不一定满 足分配律。 《定义》设<L, , >是由<L,≤>所诱导的代数系统。如果 对任意的a,b,c L,满足： a (b c)=(a b) (a c)

及 a (b c)=(a b) (a c) 则称<L,≤>是分配格。

经典的教程

§2分配格讨论定义： (1)定义中的两式互为对偶式。 (2)如<L,≤>非为分配格，则有下面的分配不等式： a (b c) ≤ (a b) (a c) a (b c) ≥ (a b) (a c) 以及模不等式：

a≤c a (b c) ≤ (a b) c

经典的教程

§2分配格《定义》如对L中任意a,b,c有： a≤c a (b c) = (a b) c 则称<L,≤>为模格。 例：

经典的教程

§2分配格《定理》如果格中交对并是分配的，那么并对交也是分 配的，反之亦然。 证明：已知a (b c) = (a b) (a c) (a b) (a c)=((a b) a) ((a b) c) =a ((a b) c) =a ((a c) (b c)) =(a (a c)) (b c) =a (b c) 即：并对交也是分配的。13

经典的教程

§2分配格《定理》分配格是模格。 证

明：由于a (b c) = (a b) (a c) (1)若a≤c,则a c=c,代入上式得

a (b c) = (a b) c(2)若a (b c) = (a b) c,则 a≤ a (b c) = (a b) c≤c,即： a≤c ∴分配格是模格

经典的教程

§2分配格《定理》每个链均是分配格。 证明：设<L,≤>是链。对任意a,b,c L (1)若a≤b或a≤c,则 a (b c) = a, (a b) (a c)=a 即： a (b c) = (a b) (a c) (2)若a≥b且a≥c,则 a (b c) = b c, (a b) (a c)= b c 即：a (b c) = (a b) (a c)。得证。15

经典的教程

§3有补格《定义》设<L,≤>是一个格，如果存在元素a L,对于任 意的x L,都有： a≤x 则称a为格<L,≤>的全下界，记格的全下界为0。 例：

经典的教程

§3有补格《定理》如果格<L,≤>有全上界(全下界),那么它是 唯一的。 证明：(反证法)设有两个全上界a和b,则由定义 a≤b,且b≤a,由“≤”的反对称性， a=b。 《定义》设<L,≤>是一个格，格中存在全上界和全下界， 则称该格为有界格。

经典的教程

§3有补格《定理》如果<L,≤>是有界格，全上界和全下界分别是1 和0,则对任意元素a L,有： a 1=1 a=1 ,a 1= 1 a=a, a 0=0 a=a ,a 0= 0 a=0。 证明：因为1≤a 1, 又因 (a 1) L且1是全上界，∴ a 1≤1, ∴ a 1=1。由交换律：1 a=a 1=1。 因为a≤a,a≤1,∴a a≤a 1,即： a≤a 1, 又 a 1≤a, ∴ a 1= a。仿此可得另两式。18

经典的教程

§3有补格《定义》设<L,≤>是一个有界格，对于L中的一个元素a, 如果存在b L,使得a b=1和a b= 0,则称元素b是 元素a的补元。 讨论定义： (1)∵ 和 是可交换的，∴补元是相互的。 (2) 0 1 0 1 0 0,0 1 1 1 0 1 ,即在有 界格中，1和0互为补元； (3)由定义可知L中一个元素的补元不一定是唯一的； 例：19

本文来源：https://www.bwwdw.com/article/o1hi.html