格子（lattices）

本文概述

• 二元性
• 有界格子
• 有界格的性质
• 子格
• 同构格
• 分配格
• 补和补格
• 模块化格
• 格的直接积

令L是在称为met和join的两个二进制操作下闭合的非空集, 用∧和denoted表示。如果以下公理成立, 则将L称为晶格, 其中a, b, c是L中的元素：

1）交换律：-（a）a b = b a（b）a b = b a

2）关联法则：-（a）（a∧b）∧c = a∧（b∧c）（b）（a∨b）∨c = a∨（b∨c）

3）吸收定律：-（a）a∧（a∨b）= a（b）a∨（a∧b）= a

二元性

格（L, ∧, ∨）中任何语句的对偶定义为通过互换∧an obtained获得的语句。

例如, a（b∨a）= a∨a的对偶是a∨（b∧a）= a∧a

有界格子

如果晶格L具有最大元素1和最小元素0, 则称为有界晶格。

例：

1. 由于intersection是P（S）的最小元素, 而集合S是P（S）的最大元素, 因此在交集和并集运算下的集合S的幂集P（S）是有界晶格。
2. 通常≤的+ ve整数I +的集合不是有界晶格, 因为它的最小元素为1, 但最大元素不存在。

有界格的性质

如果L是有界晶格, 则对于任何元素a∈L, 我们具有以下恒等式：

1. a∨1 = 1
2. ∧1= a
3. ∨0= a
4. ∧0= 0

定理：证明每个有限格L = {a1, a2, a3 …. an}是有界的。

证明：我们给出了有限格：

L = {a1, a2, a3 …. an}

因此, 格L的最大元素是a1∨a2∨a3∨…. an。

而且, 晶格L的最小元素是a1∧a2∧a3∧….∧an。

由于每个有限晶格都存在最大和最小元素。因此, L是有界的。

子格

考虑一个格子L的非空子集L1。如果L1本身是一个格子, 则L1被称为L的子格子。 L1和b∈L1

示例：考虑在除数运算下所有+ ve整数I +的晶格。 n> 1的所有除数的晶格Dn是I +的子晶格。

确定D30包含至少四个元素的所有子晶格, D30 = {1, 2, 3, 5, 6, 10, 15, 30}。

解决方案：D30的子晶格至少包含四个元素, 如下所示：

1. {1, 2, 6, 30} 2. {1, 2, 3, 30} 3. {1, 5, 15, 30} 4. {1, 3, 6, 30} 5. {1, 5, 10, 30} 6. {1, 3, 15, 30} 7. {2, 6, 10, 30}

同构格

如果从L1到L2存在双射, 则两个晶格L1和L2称为同构晶格, 即f：L1⟶L2, 使得f（a∧b）= f（a）∧f（b）和f（a∨b ）= f（a）∨f（b）

示例：确定图中所示的晶格是否同构。

解决方案：图中显示的晶格是同构的。考虑映射f = {（a, 1）, （b, 2）, （c, 3）, （d, 4）}。例如f（b∧c）= f（a）=1。此外, 我们有f（b）∧f（c）= 2∧3 = 1

分配格

如果对L的任何元素a, b和c都满足以下分布特性, 则称该晶格L为分布晶格：

1. a∧（b）c）=（a∧b）∨（a∧c）
2. a∨（b）c）=（a∨b）∧（a∨c）

如果晶格L不满足上述特性, 则称其为非​​分布晶格。

例：

1. 在交会和并集操作下的集合S的幂集合P（S）是分布函数。由于对于任何集合a, b和P（S）的c。
2. 图II中所示的晶格是分布式的。因为, 它满足了从1、2、3和4中获取的所有有序三元组的分布特性。

补和补格

令L为下界为o且上界为I的有界晶格。令a为L的元素。如果a∨x = I和a∧x = 0, 则L中的元素x称为a的补数。

如果L有界且L中的每个元素都具有补码, 则称晶格L是互补的。

示例：确定图中a和c的补码：

解：a的补数是d。因为a d = 1和a d = 0

c的补码不存在。由于不存在任何元素c, 使得c∨c’= 1且c∧c’= 0。

模块化格

如果a∨（b∧c）=（a∨b）∧c每当a≤c时, 格子（L, ∧, ∨）称为模块化格子。

格的直接积

令（L1∨1∧1）和（L2∨2∧2）是两个晶格。那么（L, ∧, ∨）是晶格的直接积, 其中L = L1 x L2, 其中L的二元运算∨（join）和∧（meet）使得对于（a1, b1）和（a2 , b2）在L中。

（a1, b1）∨（a2, b2）=（a1∨1a2, b1∨2b2）和（a1, b1）∧（a2, b2）=（a1∧1a2, b1∧2b2）。

示例：考虑一个晶格（L, ≤）, 如图2所示。其中L = {1, 2}。确定晶格（L2, ≤）, 其中L2 = L xL。

解决方案：晶格（L2, ≤）如图所示：