格与布尔代数.ppt

11.1格的定义与性质定义11.1设S,?是偏序集，如果?x,y?S，{x,y}都有最小上界和最大下界，则称S关于偏序?作成一个格.（偏序关系P126）求{x,y}最小上界和最大下界看成x与y的二元运算∨和∧，例1设n是正整数，Sn是n的正因子的集合.D为整除关系，则偏序集Sn,D构成格.?x,y∈Sn，x∨y是lcm(x,y)，即x与y的最小公倍数.x∧y是gcd(x,y)，即x与y的最大公约数.第2页,共20页，星期六，2024年，5月图2例2判断下列偏序集是否构成格，并说明理由.

(1)P(B),?，其中P(B)是集合B的幂集.

(2)Z,≤，其中Z是整数集，≤为小于或等于关系.

(3)偏序集的哈斯图分别在下图给出.实例(1)幂集格.?x,y∈P(B)，x∨y就是x∪y，x∧y就是x∩y.(2)是格.?x,y∈Z，x∨y=max(x,y)，x∧y=min(x,y)，(3)都不是格.可以找到两个结点缺少最大下界或最小上界第3页,共20页，星期六，2024年，5月格的性质：算律定理11.1设L,?是格,则运算∨和∧适合交换律、结合律、幂等律和吸收律,即(1)?a,b∈L有a∨b=b∨a,a∧b=b∧a(2)?a,b,c∈L有

(a∨b)∨c=a∨(b∨c),(a∧b)∧c=a∧(b∧c)(3)?a∈L有

a∨a=a,a∧a=a(4)?a,b∈L有

a∨(a∧b)=a,a∧(a∨b)=a第4页,共20页，星期六，2024年，5月格的性质：序与运算的关系定理11.3设L是格,则?a,b∈L有

a?b?a∧b=a?a∨b=b可以用集合的例子来验证幂集格P(B),?，其中P(B)是集合B的幂集.幂集格.?x,y∈P(B)，x∨y就是x∪y，x∧y就是x∩y.第5页,共20页，星期六，2024年，5月格的性质：保序定理11.4设L是格,?a,b,c,d∈L，若a?b且c?d,则a∧c?b∧d,a∨c?b∨d例4设L是格,证明?a,b,c∈L有a∨(b∧c)?(a∨b)∧(a∨c).证a∧c?a?b,a∧c?c?d因此a∧c?b∧d.同理可证a∨c?b∨d证由a?a,b∧c?b得a∨(b∧c)?a∨b由a?a,b∧c?c得a∨(b∧c)?a∨c

从而得到a∨(b∧c)?(a∨b)∧(a∨c)（注意最大下界）注意：一般说来,格中的∨和∧运算不满足分配律.第6页,共20页，星期六，2024年，5月格作为代数系统的定义定理11.4设S,?,?是具有两个二元运算的代数系统,若对于?和?运算适合交换律、结合律、吸收律,则可以适当定义S中的偏序?,使得S,?构成格,且?a,b∈S有a∧b=a?b,a∨b=a?b.证明省略.根据定理11.4,可以给出格的另一个等价定义.?定义11.3设S,?,?是代数系统,?和?是二元运算,如果?和?满足交换律、结合律和吸收律,则S,?,?构成格.第7页,共20页，星期六，2024年，5月11.2分配格、有补格与布尔代数定义11.5设L,∧,∨是格,若?a,b,c∈L,有

a∧(b∨c)=(a∧b)∨(a∧c)a∨(b∧c)=(a∨b)∧(a∨c)则称L为分配格.注意：可以证明以上两个条件互为充分必要条件L1和L2是分配格,L3和L4不是分配格.称L3为钻石格,L4为五角格.实例第8页,共20页，星期六，2024年，5月有界格的定义定义11.6设L是格,(1)若存在a∈L使得?x∈L有a?x,则称a为L的全下界(2)若存在b∈L使得?x∈L有x?b,则称b为L的全上界?说明：格L若存在全下界或全上界,一定是惟一的.一般将格L的全下界记为0