做英德红茶的网站,江苏建设信息电子证查,揭阳东莞网站建设,网址查询地址查询站长之家16.1 偏序与格
偏序集#xff1a;设P是集合#xff0c;P上的二元关系“≤”满足以下三个条件#xff0c;则称“≤”是P上的偏序关系#xff08;或部分序关系#xff09;
#xff08;1#xff09;自反性#xff1a;a≤a#xff0c;∀a∈P#xff1b;
#xff08;2…16.1 偏序与格
偏序集设P是集合P上的二元关系“≤”满足以下三个条件则称“≤”是P上的偏序关系或部分序关系
1自反性a≤a∀a∈P
2反对称性∀ab∈P若a≤b且b≤a则ab
3传递性∀abc∈P若a≤b且b≤c则a≤c
定义1 格
设 ( L , ⪯ ) (L,\preceq) (L,⪯)为偏序集如果任意的$a,b\in L 有最小上界与最大下界时称 有最小上界与最大下界时称 有最小上界与最大下界时称L 为 ‘ 格 ‘ 以 为格以 为‘格‘以a\lor b lub(a,b) ( l e a s t u p p e r b o n d ) 表示 (least upper bond)表示 (leastupperbond)表示a,b 的最小上界 的最小上界 的最小上界a\land b glb(a,b) g r e a t e s t l o w e r b o n d ) 表示 greatest lower bond)表示 greatestlowerbond)表示a,b$的最大下界。
定义2 覆盖
( L , ⪯ ) (L,\preceq) (L,⪯)为格如果 a ⪯ b , a ≠ b a\preceq b,a\neq b a⪯b,ab记为 a ≺ b a\prec b a≺b且不存在 u ∈ L − { a , b } u\in L-\{a,b\} u∈L−{a,b},使 a ≺ u ≺ b a\prec u \prec b a≺u≺b则称 a a a覆盖 b b b.
链:若 a ≺ b a\prec b a≺b如果有 c 1 , ⋯ , c k ∈ L , k ≥ 1 c_1,\cdots,c_k \in L,k\ge 1 c1,⋯,ck∈L,k≥1 ,使 c i 1 c_{i1} ci1覆盖 c i ( u i 1 , 2 , ⋯ , k − 1 ) c_i(ui1,2,\cdots,k-1) ci(ui1,2,⋯,k−1)且 a c 1 ≺ c 2 ≺ ⋯ ≺ c k b ac_1\prec c_2\prec\cdots\prec c_k b ac1≺c2≺⋯≺ckb 则称 c 1 , ⋯ , c k c_1,\cdots,c_k c1,⋯,ck为连接 a , b a,b a,b的链如果L中的任意两个元素总有连接它们的链则称 L L L是离散的。
有限的离散全序集的哈斯图由一条链组成
定义3 完全格
( L ; ≺ ) (L;\prec) (L;≺)为偏序集当$\forall A\subseteq L 有最大下界、最小上界时 有最大下界、最小上界时 有最大下界、最小上界时L 显然是格称为 ‘ 完全格 ‘ 显然是格称为完全格 显然是格称为‘完全格‘L 自身的最小上界是整个格 自身的最小上界是整个格 自身的最小上界是整个格L 的最大元记为 1 的最大元记为1 的最大元记为1L 自身的最小下界为整个格 自身的最小下界为整个格 自身的最小下界为整个格L 的最小元记为 0. 子集 的最小元记为0.子集 的最小元记为0.子集A$可以是有限的也可以是无限的。
定理1 格的关系运算 ( L , ⪯ ) (L,\preceq) (L,⪯)为格则对任意 a , b ∈ L a,b\in L a,b∈L有 a ≺ a ∨ b , a ∧ b ≺ a a\prec a\lor b ,a\land b \prec a a≺a∨b,a∧b≺a a ⪯ b ⟺ a ∨ b b a\preceq b \Longleftrightarrow a\lor b b a⪯b⟺a∨bb a ⪯ b ⟺ a ∧ b a a\preceq b \Longleftrightarrow a\land b a a⪯b⟺a∧ba 画个哈斯图是显然的或者注意到按照定义我们有 a ∨ b l u b ( a , b ) , a ∧ b g l b ( a , b ) a\lor blub(a,b),a\land b glb(a,b) a∨blub(a,b),a∧bglb(a,b)且若 a ⪯ b a\preceq b a⪯b,则 l u b ( a , b ) b lub(a,b)b lub(a,b)b就容易得到了 定理2 格的运算律
幂等律 a ∧ a a , a ∨ a a a\land a a, a\lor a a a∧aa,a∨aa交换律 a ∨ b b ∨ a , a ∧ b b ∧ a a\lor bb\lor a,a\land bb\land a a∨bb∨a,a∧bb∧a结合律 a ∨ ( b ∨ c ) ( a ∨ b ) ∨ c , a ∧ ( b ∧ c ) ( a ∧ b ) ∧ c a\lor(b\lor c)(a\lor b )\lor c,a\land(b\land c)(a\land b)\land c a∨(b∨c)(a∨b)∨c,a∧(b∧c)(a∧b)∧c吸收律 a ∨ ( a ∧ b ) a , a ∧ ( a ∨ b ) a a\lor(a\land b)a,a\land(a\lor b) a a∨(a∧b)a,a∧(a∨b)a P211 那么我们可以将 [ L ; ∧ , ∨ ] [L;\land,\lor] [L;∧,∨]视为代数系统
引理 1 代数系统L中的等价关系
在 [ L ; ∨ , ∧ ] [L;\lor,\land] [L;∨,∧]中二元关系 ∨ , ∧ \lor,\land ∨,∧满足上述4条运算律则 ∀ a , b ∈ L , a ∧ b a ⟺ a ∨ b b \forall a,b\in L ,a\land b a\Longleftrightarrow a\lor bb ∀a,b∈L,a∧ba⟺a∨bb KaTeX parse error: Undefined control sequence: \and at position 38: …row a\lor b (a\̲a̲n̲d̲ ̲b )\lor b b(最后一步是吸收律) a ∨ b b ⇒ a ∧ b a ∧ ( a ∨ b ) a a\lor b b\Rightarrow a\land b a\land(a\lor b )a a∨bb⇒a∧ba∧(a∨b)a 引理2 通过L构造偏序集
在 [ L ; ∧ , ∨ ] [L;\land,\lor] [L;∧,∨]中 ∧ , ∨ \land,\lor ∧,∨满足4条运算规律定义关系 ⪯ \preceq ⪯如下: ∀ a , b ∈ L , a ⪯ b \forall a,b \in L ,a\preceq b ∀a,b∈L,a⪯b当且仅当 a ∨ b b a\lor b b a∨bb.则 ( L ; ⪯ ) (L;\preceq) (L;⪯)为偏序集 证明自反性反对称性传递性 P211 定理3 引理2中的偏序集是格 证明 a ∨ b l u b ( a , b ) , a ∧ b g l b ( a , b ) a\lor b lub(a,b),a\land b glb(a,b) a∨blub(a,b),a∧bglb(a,b) P211 定义4 格的另一种定义方式
[ L ; ∨ , ∧ ] [L;\lor,\land] [L;∨,∧]是一代数系统 ∨ , ∧ \lor,\land ∨,∧是定义在 L L L上的二元运算当其满足 L 1 L_1 L1到 L 4 L_4 L4时称 L L L为格并称 ∧ \land ∧为积(交), ∨ \lor ∨为和(或并)
定理4 保序性
格 [ L ; ∨ , ∧ ] , ∀ a , b , c ∈ L [L;\lor,\land],\forall a,b,c\in L [L;∨,∧],∀a,b,c∈L,当 b ⪯ c b\preceq c b⪯c时有 a ∧ b ⪯ a ∧ c a\land b \preceq a\land c a∧b⪯a∧c及 a ∨ b ⪯ a ∨ c a\lor b\preceq a\lor c a∨b⪯a∨c
定义5 子格
[ L ; ∨ , ∧ ] [L;\lor,\land] [L;∨,∧]为格 T ≠ ∅ , T ⊆ L T\neq\varnothing,T\subseteq L T∅,T⊆L, T T T关于 ∨ , ∧ \lor,\land ∨,∧封闭(即 a , b ∈ T , a ∨ b ∈ T , a ∧ b ∈ T a,b\in T,a\lor b \in T,a\land b \in T a,b∈T,a∨b∈T,a∧b∈T)时称 T T T为 L L L的子格
注意当 T T T为 L L L的子格时 T T T一定是格但当 T ⊆ L T\subseteq L T⊆L, T T T关于 L L L中的偏序关系 ⪯ \preceq ⪯为格时 T T T不一定是 L L L的子格因为 T T T中的运算关系可能不同
例如一个群 G G G的子群全体 S ( G ) S(G) S(G)关于 ⊆ \subseteq ⊆关系所构成的格不是 G G G的幂集关于 ⊆ \subseteq ⊆关系所构成的格的子格因为子群的并不一定是子群
定义6 格的同态与同构
设 [ L ; ∨ , ∧ ] [L;\lor,\land] [L;∨,∧]与 [ S ; , ∘ ] [S;,\circ] [S;,∘]为两个格如果存在映射 φ : L → S ∀ a , b ∈ L \varphi:L\rightarrow S\forall a,b\in L φ:L→S∀a,b∈L,有 φ ( a ∧ b ) φ ( a ) ∘ φ ( b ) φ ( a ∨ b ) φ ( a ) φ ( b ) \varphi(a\land b )\varphi(a)\circ\varphi(b)\\ \varphi(a\lor b)\varphi(a)\varphi(b) φ(a∧b)φ(a)∘φ(b)φ(a∨b)φ(a)φ(b) 则称 φ \varphi φ为 L L L到 S S S的同态映射当 φ ( L ) S \varphi(L)S φ(L)S时(满射)则说两个格同态当 φ \varphi φ是一一对应(双射),说同构。如果 L S LS LS,则称为自同态和自同构。
定理 5 同态映射是保序的
若 φ \varphi φ是格 L , S L,S L,S间的同态映射则 φ \varphi φ是同态映射即 ∀ a , b ∈ L \forall a,b\in L ∀a,b∈L若 a ⪯ b a\preceq b a⪯b,则 φ ( a ) ⪯ φ ( b ) \varphi(a)\preceq\varphi(b) φ(a)⪯φ(b)注意不是当且仅当
定理6 同构映射的保序性
a ⪯ b ⟺ φ ( a ) ⪯ φ ( b ) a\preceq b \Longleftrightarrow \varphi(a)\preceq\varphi(b) a⪯b⟺φ(a)⪯φ(b)
定理7 对偶原理
设 P P P是对任意偏序集都为真的一个命题 P ′ P P′是将 P P P中所有 ⪯ , ⪰ \preceq,\succeq ⪯,⪰对换得到的对偶命题则 P ′ P P′对任意偏序集也为真设 P P P是从格 [ B ; ∨ , ∧ ] [B;\lor,\land] [B;∨,∧]推出的命题 P ′ P P′是将 P P P中 ∨ \lor ∨与 ∧ \land ∧对换得到的对偶命题则 P ′ P P′对格 [ B ; ∧ , ∨ ] [B;\land,\lor] [B;∧,∨]也为真 偏序反转后自然从P得到了P‘ 16.2 有补格及分配格
定义7 有界格
一个具有最大元1和最小元0的格 [ L ; ∨ , ∧ ] [L;\lor,\land] [L;∨,∧]称为有界格
定理8 最大元和最小元的性质
有界格中 ∀ a ∈ L : a ∨ 1 1 , a ∧ 0 0 , a ∧ 1 a , a ∨ 0 a \forall a\in L:a\lor 1 1,a\land 0 0,a\land 1 a,a\lor 0 a ∀a∈L:a∨11,a∧00,a∧1a,a∨0a
定义8 有补格
[ L ; ∨ , ∧ ] [L;\lor,\land] [L;∨,∧]为有界格$\forall a \in L , 若 ,若 ,若\exist b\in L , 有 ,有 ,有a\lor b 1,a\land b 0 则称 则称 则称b 为 为 为a 的 ‘ 补元 ‘ , 记 的补元,记 的‘补元‘,记b 为 为 为a’ . 若 .若 .若L 中的每个元有补元称 中的每个元有补元称 中的每个元有补元称L$为有补格
我们可以发现对任意格成立分配不等式即格 [ L ; ∨ , ∧ ] [L;\lor,\land] [L;∨,∧]中任意 a , b , c ∈ L a,b,c\in L a,b,c∈L,有 a ∨ ( b ∧ c ) ⪯ ( a ∨ b ) ∧ ( a ∨ c ) a\lor (b\land c)\preceq (a\lor b)\land(a\lor c) a∨(b∧c)⪯(a∨b)∧(a∨c)KaTeX parse error: Undefined control sequence: \and at position 34: …and c)\preceq a\̲a̲n̲d̲(b\lor c)
怎么说了这个不等关系很容易记反就画哈斯图吧
定义9 分配格
我们可以发现对任意格成立分配不等式即格 [ L ; ∨ , ∧ ] [L;\lor,\land] [L;∨,∧]中任意 a , b , c ∈ L a,b,c\in L a,b,c∈L,有 a ∨ ( b ∧ c ) ( a ∨ b ) ∧ ( a ∨ c ) a\lor (b\land c) (a\lor b)\land(a\lor c) a∨(b∧c)(a∨b)∧(a∨c)KaTeX parse error: Undefined control sequence: \and at position 28: …or(a\land c) a\̲a̲n̲d̲(b\lor c)
则称格L为分配格
两个典型的非分配格 只要哈斯图中含有这种子结构就可以判断它不是分配格
定理9 分配格的判断 [ L ; ∨ , ∧ ] [L;\lor,\land] [L;∨,∧]为任意格则下述条件等价 ∀ a , b , c ∈ L , a ∧ ( b ∨ c ) ( a ∧ b ) ∨ ( a ∧ c ) \forall a,b,c\in L,a\land(b\lor c)(a\land b)\lor(a\land c) ∀a,b,c∈L,a∧(b∨c)(a∧b)∨(a∧c) ∀ a , b , c ∈ L , a ∨ ( b ∧ c ) ( a ∨ b ) ∧ ( a ∨ c ) \forall a,b,c\in L,a\lor(b\land c)(a\lor b)\land(a\lor c) ∀a,b,c∈L,a∨(b∧c)(a∨b)∧(a∨c) ∀ a , b , c ∈ L , ( a ∧ b ) ∨ ( b ∧ c ) ∨ ( c ∧ a ) ( a ∨ b ) ∧ ( b ∨ c ) ∧ ( c ∨ a ) \forall a,b,c\in L,(a\land b)\lor (b\land c)\lor(c\land a)(a\lor b)\land(b\lor c)\land(c\lor a) ∀a,b,c∈L,(a∧b)∨(b∧c)∨(c∧a)(a∨b)∧(b∨c)∧(c∨a)不含 M 5 M_5 M5或 N 5 N_5 N5同构的子格
