193特殊的格 ■模格 分配格 ■有界格 ■有补格 ■布尔格
1 19.3 特殊的格 模格 分配格 有界格 有补格 布尔格
模格 定义L为格,若a,b,c∈L, Kb→a(c∧b)=(Nvc)b 则称L为模格. 实例: b 钻石格为模格 五角格不是模格 模格-模律:∝Kb→V(Ab)=(aVcl)b 格-模不等式:“Kb→W(cAb)<(Vc)^b
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
模格判别条件 L为模格当且仅当L不含有与五角格同构的子格. 充分性:假设L不是模格,则存在ab,c∈L,使得 a≤b,(cAb)<(Nc)∧b, 取5个元素x,y,z,ν如图 证明思路: Y=aVc x<y≤,W≤C≤ν x∧c=y∧c=, XVc-VVc=ν =(vc)∧b Z=< xy乙,ν两两不等 x=V(c∧b) 构成L的5元子格 U=C∧b
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
模格判别条件(续) L为模格当且仅当 Va,b,C∈L,a≤b,aC=bvc,ac=bc→a=b 证:“<”若不是模格,则存在子格与五角格同构 必有a,b,c构成如图的子格,与条件矛盾 “→”设L为模格, V,b,C∈L,a≤b,NC=bvc,a∧C=b入C =av(入c)=(bc) b N∨(c入b)=(c)∧b (bve)∧b=b
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
分配格 定义设L为格,若a,b,c∈L有 a入(bvc)=(aAbv(ac)或a(b∧c)=(ab)(Vc) 则L为分配格. 注:在任何格中两个分配不等式是等价的 例如a(bc)=(ab√(ac)→m(bc)=(avb)(avc) 证ab^(ac) (Nb)a)v(NVb)入c) (对v的分配律) aN(a入c)y(b∧c)(吸收律,∧对v的分配律) (aN(a^cv(bc)=mN(b∧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) (结合律, 吸收律) 反之，同理可证. 分配格
分配格判别定理 定理1设L为模格,L为分配格当且仅当 若ab,C∈L有 (a入b)y(b∧c)(c)=(Nvb)∧(bvc)∧(cva) 注:一般格成立不等式 (a入b)y(b∧c)(a)≤(Nvb)∧(bvc)∧(cva) 定理2设L为模格,L为分配格当且仅当L不含 有与钻石格同构的子格
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 不含 有与钻石格同构的子格. 分配格判别定理
判别定理一的证明 证:“<”Va,b,C∈L a入(bvc)=aA(b)(bvc)∧(cva)(吸收律) =(aAbb^cMcA)∧(等式替代) =(a∧b)(b^cN√ca)∧a)(模律ab≤a) (aAb)((c∧a(bAC)入) (交换律) =(a入b)v(cAa)(b∧CAm) (模律) (aAbvaAc
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) 判别定理一的证明
判别定理一的证明(续) ∧bv(b∧cyV(c I(abb)∧(ab)vc)v(cAa)(分配律) =[∧(vc)( bvdv(cAa) (吸收、分配律) =(b∧vcv(ca) (吸收律) (bvc)∧(bva)∧(acvc)∧(acva)(分配律) (NVb)∧(bve)(cva) (交换、幂等律)
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) (交换、幂等律) 判别定理一的证明（续）
判别定理二的证明 充分性.假设模格L不是分配格,则彐ab,c∈L使得 (a入b)v(bAc)y(cA)<(Nb)∧(bc)∧(cva) u=(abv(bAcV(cAa) v=(vb)入(bvc)/(cva) x=Uv(aAv y=Wv(b∧v z=LV(C∧v 则可以证明L,vxyz构成钻石格. 注:所有的链为分配格,4元以下的格为分配格
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 y z
模格、分配格之间的关系 C=b∧c →=b aVC=bVc 分配律 格 心模格〓 不含与五角 不含与钻石 分配格 格同构子格 格同构子格 ∧C=b∧c b,cNe=bvc→=b (aAb)V(b∧c)v(cAa) (NVb)∧(bvc)(cva) b,(vc)入b=N(cAb)
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 )
