ch10 格与之布尔代数.ppt

③有补分配格满足德.摩根定律，即 ⅰ（1）(a?b)’=a’?b’ ⅱ（2）(a?b)’=a’?b’ 证明：(a?b)?(a’?b’)=(a?a’?b’)?(b?a’?b’) =0?0=0 (a?b)?(a’?b’)=(a?b?a’)?(a?b?b’) =1?1=1 由有补分配格的补元唯一性，(a?b)’=a’?b’ 由对偶原理 (a?b)’=a’?b’ 返回有补格 返回目录 §10.3 有补格 §10.4 布尔代数 一 .基本概念1.2.3 二 .STONE定理1.2.3.4.5 返回目录 一.基本概念 　　　　1.有限布尔代数 　　　　2.同构 　　　　3.原子 §10.4 布尔代数 二. 格是代数系统 a)??? 因为(a?b)?a = (a?a)?b=a?b ?a?b≤a 同理a?b≤b ?a?b 是a,b的下界。 结合律交换律 等幂律 偏序集合的格、代数系统的格二者定义是等价的证明 2）证明 ?a,b?L, {a,b}的最大下界存在， 且 a?b=glb(a,b)。 b) 设c 是a,b 的任一下界， 即c≤b, c≤a 则c≤a?b 因为c?(a?b)= (c?a)?b=c?b=c c≤a?b ?a?b 是a,b的下界。 二. 格是代数系统 二. 格是代数系统 3) 同理可证：?a,b?L, {a,b}的最小上界存在， 且lub(a,b)=a?b ?由1）2）3）知：L,≤是一个格。 ? 以后可根据需要， 随意使用这二种定义和记法。 二. 格是代数系统 返回格 三 子格、格同态 1. 定义： L, ?,?是个格，S?L, 若S对运算?和?封闭， 则称S, ?,?是L, ?,?的子格。 子格是个格，因结合律、交换律、吸收律是继承的。 则 {b,c,d}, ?,?不是{a,b,c,d}, ?,? 的子格 {b,d}, ?,?是{a,b,c,d}, ?,? 的子格 {a,d}, ?,?是{a,b,c,d}, ?,? 的子格 例： d c a b 三 子格、格同态 三 子格、格同态 ? 定义： S,*,? ,L, ?,?是二个格， f: L? S 且?a,b?L 有f(a*b)=f(a)?f(b) f(a?b)=f(a)?f(b) 称f是L, *,?到S, ?,?的格同态； 若f是双射则称L,*,?和S,?,?是同构的。 2 格同态 三 子格、格同态 定理:若a,b?L，a≤ b 则f(a)≤’f(b) 证： a≤b ? a*b=a ? f(a)?f(b)=f(a*b)=f(a) ? f(a)≤’f(b) 注1：保序的函数不一定是同态的。 ? 格同态是保序的 〈S12，整除* 〉 〈S12，小于等于? 〉 f: S12 ? S12 ,f(x)=x 则f是保序的 即a≤b ? f(a)≤f(b) 但f不是同态的: f(3*2)=f(1)=1 f(3)?f(2)=2 例1： 12 4 2 1 6 3 12 6 4 2 3 1 三 子格、格同态 三 子格、格同态 证：? f是格同构 由?知 a≤b ? f(a) ≤’f(b) 反之 设f(a) ≤’f(b) 则 f(a)=f(a)*f(b)=f(a?b) 因为f是双射, a= a?b ? a≤b ③设f是双射， 则f是A1,≤到A2,≤’的格同构， 当且仅当 ?a,b? A1, a≤b ? f(a)≤’f(b)  ? 已知?a,b? A1, a≤b ? f(a)≤’f(b) 需证f是同构, 即证:f(a?b)= f(a)*f(b) 证明: 令 c= a?b 则 c≤a ? f(c)≤’f(a) c≤b ? f(c)≤’f(b) ? f(c)≤’f(a)*f(b)