哈尔滨理工大学：《离散数学 Discrete Mathematics》课程教学资源（PPT课件讲稿）15 有补格

6-3有补格 有界格 在介绍有补格之前,先介绍有界格 定义6-31设是一个格,如果存在元素a∈A, 对于任意的x∈A,都有a≤x,则为格的全下界记为“0”。 定理6-3.1格<A,s若有全下界,则全下界是唯一的。 口证明:用反证法 如果有两个不相等的全下界a和b,a,b∈A且b≠a 因为a是全下界,b∈A,所以a≤b 又因为b是全下界,a∈A,所以b≤a 由此得a=b 与有两个不相等的全下界a和b矛盾。口

一、有界格 在介绍有补格之前，先介绍有界格。 定义6-3.1 设是一个格，如果存在元素aA , 对于任意的xA,都有a ≤ x,则为格的全下界,记为“0” 。 定理6-3.1 格若有全下界,则全下界是唯一的。  证明：用反证法 如果有两个不相等的全下界a和b，a,bA 且b≠a 因为 a 是全下界， bA ，所以 a ≤ b 又因为 b 是全下界， aA ，所以 b ≤ a 由此得 a=b 与有两个不相等的全下界a和b 矛盾。  6-3 有补格

定义6-32设是一个格,如果存在元素b∈A, 对于任意的x∈A,都有xsb,则为格的全上界,记为“1”。 口证明:用反证法 如果有两个不相等的全上界a和b,a,b∈A且 b≠a 因为a是全上界,b∈A,所以b≤a 又因为b是全上界,a∈A,所以a≤b 由此得a=b 与有两个不相等的全上界a和b矛盾

定义6-3.2 设是一个格，如果存在元素bA, 对于任意的xA,都有x≤b,则为格的全上界,记为“1” 。  证明：用反证法 如果有两个不相等的全上界a和b ，a,bA 且 b≠a 因为 a 是全上界， bA ，所以 b ≤ a 又因为 b 是全上界， aA ，所以 a ≤ b 由此得 a=b 与有两个不相等的全上界a和b 矛盾。 

例1设有限集合S,那么在格中,空 集就是该格的全下界,集合S就是该格的全上界。 例2在图6-3.1所示的格中,h是全下界,a是全 上界

例2 在图6-3.1所示的格中，h是全下界，a是全 上界。 例1 设有限集合S，那么在格中，空 集就是该格的全下界，集合S就是该格的全上界

定义6-33设是一个格,如果存在全下界 和全上界,则称该格为有界格。 定理6-33设是一个有界格,则对于任意 的a∈A,都有 a∨1=1a∧1a(1是∨运算的零元,∧运算的 幺元) a∨0=aa∧0=0(0是∨运算的幺元,∧运算的 零元)

定义6-3.3 设是一个格，如果存在全下界 和全上界，则称该格为有界格。 定理6-3.3 设是一个有界格，则对于任意 的aA,都有 a∨1=1 a∧1=a (1是∨运算的零元,∧运算的 幺元) a∨0=a a∧0=0 (0是∨运算的幺元,∧运算的 零元)

口证明:(1)证aV1=1 因为a∨1∈A且1是全上界,所以a∨1≤1 又因为1≤a∨1,所以aV1=1 (2)证a∧1=a 因为asa,a≤1,所以a≤a∧1 又因为a∧1≤a,所以a∧1=a (3)证aV0=a(略) (4)证a∧0=0(略)口 由aV0=0∨a=a和a∧1=1a=a说明0和1分别是 关于运算∨和∧的幺元。另外,0和1分别是关于运算 ∧和∨的零元

 证明：(1) 证 a∨1=1 因为 a∨1A且1是全上界，所以 a∨1 ≤ 1 又因为 1 ≤ a∨1，所以 a∨1=1 (2) 证 a∧1=a 因为 a ≤ a， a ≤ 1, 所以 a ≤ a∧1 又因为 a∧1 ≤ a， 所以 a∧1=a (3) 证a∨0=a (略) (4) 证a∧0=0 (略)  由a∨0=0∨a=a和a∧1=1∧a=a说明0和1分别是 关于运算∨和∧的幺元。另外，0和1分别是关于运算 ∧和 ∨的零元

二、有补格 定义6-34设<A,s是一个有界格,对于A中任意 的a,如果存在be∈A,使得aVb=1和a∧b=0,则称元 素b是元素a的补元。此时称a和b是互补的。 显然,上述定义中,a和b是对称的,即如果a是b 的补元,则b也是a的补元,因此,可以说,a和b这 两个元素是互补的。 必须注意的是:对于元素a∈A,可以存在多个 补元,也可以不存在补元

二、有补格 定义6-3.4 设是一个有界格，对于A中任意 的a,如果存在bA ，使得a∨b=1和a∧b=0 ，则称元 素b是元素a的补元。此时称a和b是互补的。 显然，上述定义中，a和b是对称的，即如果a是b 的补元，则b也是a的补元，因此，可以说，a和b这 两个元素是互补的。 必须注意的是：对于元素aA ，可以存在多个 补元，也可以不存在补元

例3在图6-3.2所示的有界格中,因为dVc=1和 d∧c=0,所以,d和c是互补的。但是b是没有补元 的。此外,a和d都是e的补元;c和e都是d的补元。 显然,在有界格中,0是1的唯一补元,1是0的 唯一补元

例3 在图6-3.2所示的有界格中，因为d∨c=1和 d∧c=0，所以，d和c是互补的。但是b是没有补元 的。此外，a和d都是e的补元；c和e都是d的补元。 显然，在有界格中，0是1的唯一补元，1是0的 唯一补元

定义635在一个有界格中,如果每个元素都至 少有一个补元素,则称此格为有补格 例4图688中给出了一些有补格。 b a Q6 〔b) () 图6-3.3

定义6-3.5 在一个有界格中，如果每个元素都至 少有一个补元素，则称此格为有补格

定理6-34在一个有界分配格中,如果有一个元 素有补元素,则必是唯一的。 口证明:设a有两个补元素b和c,即有 aVb=1和a∧b=0 aVc=1和a∧c=0 由定理6-23即得b=c 定义6-3.6一个格如果如果它即是有补格,又是 分配格,则称此格为有补分配格。一般把任一元素a 的唯一补元记为a(或a)

定理6-3.4 在一个有界分配格中，如果有一个元 素有补元素，则必是唯一的。  证明：设 a有两个补元素b和c，即有 a∨b=1 和 a∧b=0 a∨c=1 和 a∧c=0 由定理6-2.3即得 b=c  定义6-3.6 一个格如果如果它即是有补格，又是 分配格，则称此格为有补分配格。一般把任一元素a 的唯一补元记为 a (或a - )

练习:P252(

练习：P252 (1)