格论

格论论述次序及包含的性质,是布尔代数的推广,现已成为代数的重要组成部分,并在泛函分析、赋值论、几何、逻辑、计算机科学、图论等方面有广泛的应用。

格论

• 格的定义
  • L是非空集合，+与o是L上两个二元运算，如果它们满足交换律、结合律及吸收律，即对任意a, b, c ∈L有 交换律：a+b = b+a, a o b = b o a; 结合律：(a+b)+c = a+(b+c), (a o b) o c = a o(b o c); 吸收律：a+(a o b) = a, a o(a+b) = a; 则称代数系统 (L, +, o)是格，亦称代数格。
• 格的性质
  • 格满足幂等律。
    • 设有格(L,+, o )，则对每个a∈L必有 a+a = a， a o a = a
      • 由吸收律，有 a+a = a+(a o(a+a)) = a 同理有 a o a = a o(a +(a o a)) = a 由此定理得证。
  • 格的子代数必为格。
    • 设有格(L,+，o )及其子代数(H,+，o )（其中Ф 包含于 H包含于 L），则(H,+，o )必为格，称为(L,+，o )的子格。
      • 设a,b,cH，则a,b,cL，因为L是格，所以有 a+b=b+a a o b=b o a (a+b)+c=a+(b+c) (a o b) o c=a o(b o c) a+(a o b)=a a o(a+b)=a 因此(L,+，o )是格。
  • 格满足对偶律
    • 格(L,+， o )的任意公式中，出现+， o 处分别用o与+替换后所得的公式称为该公式的对偶式。
• 偏序格
  • 定义:集合P上的偏序关系“≼”所组成的偏序集(P,≼ )中，如果任意P的子集均有上确界与下确界，则称(P,≼ )为偏序格。
  • 代数格必是偏序格，反之亦然。 因此，今后不再区分代数格与偏序格，并统一称格。
    • 设有代数格 (L,+， o ),在其上定义“≼”关系如下：≼ = {(a,b) | a+b=a} 即 a≼b ： a+b=a 因a+a=a成立，即a≼a ， 故≼ 是自反的。 设a≠b,若a≼b ， 则b≼a 必不成立，否则由a+b=a及b+a=b得到a=b,矛盾。故≼ 是反对称的。 若a≼b ， b≼c，即a+b=a, b+c=b成立，则 a+b+c = a+c a+b = a+c a = a+c 即a+c=a, a≼c 成立，故≼ 是传递的。 因此，(L, ≼ )是偏序格。
• 分配格
  • 格(L,+,o)满足分配律，即对任意a,b,c∈L，有 a+(b o c) = (a+b) o(a+c) a o(b+c) = (a o b)+(a o c) 则称代数系统 (L, +, *)是分配格。
• 有界格
  • 设格(L,+,o)中有+的单位元素1及o的单位元素0，即对a∈L，有a+1 = a, a o 0 = a，则称此格为有界格。
  • 设(L,+,o)是有界格，则对任意a∈L，有 a o 1 = 1, a o 0 = a a+1 = a, a+ 0 = 0
    • 证明： a+1=a及a o 0=a可由有界格定义而得。 由a o 0=a得到 a+0 = (a o 0)+0 再由吸收律可得结果 a+0 = 0， 同理有 a o 1 = (a + 1) o 1 = 1。 由此定理得证。
• 有补格
  • 设(L, +, o)是有界格，如果对每个a ∈ L必有 a-∈L 且满足 a o a- = 1（o的零元素）， a + a- = 0，则称此(L, +, o)是有补格，其中a-是a的补元素。显然 0-= 1, 1- = 0
• 有补分配格
  • 如果一个格是有补格又是分配格，则称此格为有补分配格。
  • 设(L,+,o)是有补分配格，如果对每个a∈L，它的补元素是唯一的
    • 用反证法。设aL有两个补元素a1,a2L，则 a o a1 = 1, a+a1 = 0 a o a2 = 1, a+ a2 = 0 因此有 a1 = a1+1 = a1+(a o a2) = (a1+a) o(a1+ a2) = 0 o(a1+ a2) = (a2+a) o(a2+ a1) = a2+(a o a1) = a2+1 = a2 由此定理得证
  • 设(L,+,o)是有补分配格，对任一a∈L，必有 a-- = a。因为：（a-）+ a = 0及 （a-）o a = 1同时成立
  • （德·摩根律） 设(L,+,o)是有补分配格，如果对每个a,b∈L，有
• 由最小项所表示的布尔积所组成的和，称为积之和表达式，也可称为积之和展开式。
  • 布尔函数可用一个积之和展开式表示
  • 一个布尔函数的积之和展开式可通过布尔函数的十条性质化简成一个布尔表达式
• 布尔变元或其补称为文字，布尔变元x1,x2,…,xn的最小项是一个布尔积y1 o y2 o … o yn ，其中yi =xi或yi =（xi）- (i=1,2,…,n)。
• 布尔表达式
  • 布尔表达式可由下面的公式组成： （1）0与1是布尔表达式； （2）布尔变元x1,x2,…,xn是布尔表达式； （3）如E1,E2是布尔表达式，则E1 o E2,E1+E2及 是布尔表达式； （4）布尔表达式由且仅由上述三种方式在有限步骤内组成。 这种公式的组合方式称为合式公式。
• 布尔函数
  • 设有B={0,1}，可用它构造一个函数Y=f(x1,x2,…,xn)，其中f:B^n->B，这个函数称为n元布尔函数，而xi(i=1,2,…,n)称为该函数的布尔变元。
  • 布尔函数可以用表的形式来表示，这种表称为布尔映射表
• 子布尔代数
  • 设有布尔代数(B,+,o)，H包含于B且H≠Ф，如(H,+,o)是(B,+,o)的子代数，则它必定为布尔代数，并称其为(B,+,o)的子布尔代数。
    • 开关代数({0,1},+,o)是所有布尔代数的最小子代数。
• 有限布尔代数
  • 定义：设有布尔代数( B, +, o )，如|B|有限，则称其为有限布尔代数。
  • 有限布尔代数( B, +, o )必与(ρ(S),∩,∪) 同构。此定理称为斯通表示定理
    • 推论1 有限布尔代数的元素个数必为2的幂，即必有n>0，使其元素个数为2^n 。
    • 推论2 具有2^n个元素的布尔代数必同构。
    • 推论3 布尔代数的最小元素个数为2，此类布尔代数称为最小布尔代数。
• 布尔代数性质
  • （1）交换律：a+b=b+a, a o b=b o a （2）结合律：a+(b+c)=(a+b)+c, a o(b o c)=(a o b) o c （3）幂等律：a+a=a, a o a=a （4）吸收律：a+(a o b)=a, a o(a + b)=a （5）分配律：a o(b + c)=(a o b)+(a o c) a +(b o c)=(a + b) o (a + c) （6）零一律：a+1=1, a o 0=0 （7）同一律：a+0=a, a o 1=a （8）互补律：a +（a-）= 1, a o（a-）= 0 （9）双补律：a- = a （10）德·摩根律
• 布尔代数
  • 定义：一个有补分配格称为布尔代数，记为( B, +, o )。
  • 定义：代数系统(B,+,o)如满足交换律、同一律、分配律及互补律，则称是布尔代数。 满足交换律 由同一律知有界 满足分配律 由互补律知有补