格子（lattices）格子（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, 则称为有界晶格。
例：

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

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

a∨1 = 1
∧1= a
∨0= a
∧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为分布晶格：

a∧（b）c）=（a∧b）∨（a∧c）
a∨（b）c）=（a∨b）∧（a∨c）

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

在交会和并集操作下的集合S的幂集合P（S）是分布函数。由于对于任何集合a, b和P（S）的c。
图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。
模块化格 【格子（lattices）】如果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, ≤）如图所示：