格、有界格、分配格

编程入门行业动态更新时间:2024-10-25 09:29:32

格

假设(L,≼)(L, \preurlyeq)(L,≼)为偏序集，如果对于任意a,b∈L,a,ba, b\in L ,{a, b}a,b∈L,a,b 都存在上确界和下确界，则称 <L,≼><L,\preurlyeq><L,≼> 为一个格（lattice）（lattice）（lattice）

显然上确界和下确界有唯一性

上确界L∪B(a,b)L \cup B({a, b})L∪B(a,b)记作a∨\lor∨b，称之为a与b的并（join）（join）（join）

下确界G∩B(a,b)G\cap B({a, b})G∩B(a,b)记作a∧\land∧b，称之为a与b的交（meet）（meet）（meet）

最大元、最小元

最大元：指偏序集的子集中不小于一切的元素
最小元：指偏序集的子集中不大于一切的元素

极大元、极小元

极大元：指偏序集中没有比它更大的可比较的元素
极小元：指偏序集中没有比它更小的可比较的元素

有界格

存在最大元和最小元的格称为有界格。

补元

设<L,≼><L,≼><L,≼>是有界格,a,b是L中的两个元，若a∨b=1,a∧b=0a∨b=1,a∧b=0a∨b=1,a∧b=0，则称a是b的补元或b是a的补元，或称a和b互为补元.

a∨b=1a \lor b=1a∨b=1意思是a和ba和ba和b向上走只有一个共同点111.
a∧b=1a \land b=1a∧b=1意思是a和ba和ba和b向下走只有一个共同点000.

分配格

满足分配率的即为分配格

对于格的任意元素x，y和z，均有x∧(y∨z)=(x∧y)∨(x∧z)x∧(y∨z)=(x∧y)∨(x∧z)x∧(y∨z)=(x∧y)∨(x∧z)。由于格中结运算和交运算的对称性，上述条件等价于x∨(y∧z)=(x∨y)∧(x∨z)x∨(y∧z)=(x∨y)∧(x∨z)x∨(y∧z)=(x∨y)∧(x∨z)，当LLL为分配格时，交运算对于结运算满足分配律，而且反之亦真。
布尔格、除数格、理想格、链等均为分配格。