第六章格与布尔代数

是否是分配格？ （2）设P为命题公式集合，∧与∨分别是命题公式的合取与析取运算，格是否是分配格？ 解 （1）因集合的交、并运算满足分配律，所以，格是一个分配格。 （2）因命题公式的析取、合取运算满足分配律，所以，格是分配格。 定理6.2.4*定理6.2.4所有链都是分配格。 证明 设是链，因此是格，任取a, b, c∈L，只有以下两种情况： （1）a是三者中最大的，即b ≤ a，c ≤ a； （2）a不是三者中最大的，即a ≤ b或a ≤ c。 在情况(1)中，b∨c≤ a，故a∧(b∨c) = b∨c。显然，a∧b = b，a∧c = c。所以 a∧(b∨c) = b∨c =(a∧b)∨(a∧c)。 , 定理6.2.4（续）*定理6.2.4（续）在情况(2)中，a≤b∨c，而a∧b=a或a∧c=a，从而(a∧b)∨(a∧c) = a，所以 (a∧b)∨(a∧c)= a = a∧(b∨c) 所以是分配格。 例6.2.8*例6.2.8右图所示的两个格都不是分配格。 分析 由于链是分配格，因此在同一条链上的元素都满足分配等式，最有可能不满足分配等式的元素不在同一条链上。选取b, c, d来验证即可。例6.2.8（续）*例6.2.8（续）解 取图中b, c, d三个元素验证。在图 (a)中， b∧(c∨d)=b∧e=b，而 (b∧c)∨(b∧d)=a∨a = a。 在图 (b)中， b∧(c∨d)=b∧e= b，而 (b∧c)∨(b∧d)=a∨a=a。 因此，在图 (a)和(b)中都有， b∧(c∨d)≠(b∧c)∨(b∧d) 故它们都不是分配格。定理6.2.5*定理6.2.5一个格是分配格的充分必要条件是该格中没有任何子格与6例15.2.86中的两个五元素格中的任何一个同构。性质6.2.2*性质6.2.2（1）四个元素以下的格都是分配格； （2）五个元素的格仅有两个格是非分配格(图6.2.8(a)和(b))，其余三个格(右图 (a), (b)和(c))都是分配格。定理6.2.6*定理6.2.6设是分配格，对于任何a, x, y∈L，如果ax = ay且ax = ay，则x = y。 证明 x = x (ax) (吸收律) = x (ay) (已知ax = ay) = (xa)  (xy) (分配律) = (ay)  (xy) (已知ax = ay) = y (ax) (交换律，分配律) = y (ay) (已知ax = ay) = y (吸收律) 定义6.2.7*定义6.2.7设是格，如果对任意a, b, c∈L，有 a≤b a(bc)=b(ac)或 (模律) a≥b a(bc)=b(ac) 则称为模格，也称为戴德金格 定理6.2.7*定理6.2.7分配格是模格。 证明 设是分配格，对任意a, b, c∈L，如果a ≤ b，那么ab = b，由分配律得 a (bc) = (ab)(ac) = b(ac) 故是模格。性质6.2.3*性质6.2.3（1)每一个链格都是模格； （2）四个元素以下的格都是模格；定义6.2.8*定义6.2.8设是一个格，若存在元素a∈L，使得对任意x∈L，都有： a ≤ x(或x ≤ a)， 则称a为格的全下界(或全上界)，分别记为0(或1)，具有全上界和全下界的格称为有界格。 显然，对任意x∈L，有 1x = x1 = x，1x = x1 = 1 0x = x0 = 0，0x = x0 = x有限格与有界格*有限格与有界格若是有限格，设L = {a1, a2, …, an}，由于运算“”和“”满足结合律，所以有 ((a1a2)…an) = a1a2…an ((a1a2)…an) = a1a2…an 此时， a1a2…an和a1a2…an分别是格L的全下界和全上界，即有 a1a2…an = 0 a1a2…an = 1 所以，有限格一定是有界格。 定理6.2.8*定理6.2.8在格中，全下界和全上界分别是集合L的最小元和最大元，由于最大元和最小元的惟一性，有下面的定理： 定理6.2.8 设是一个格，若格的全上界和全下界存在，则必惟一。定义6.2.9*定义6.2.9设为有界格，1和0分别为它的全上界和全下界，a∈L。如果存在b∈L，使得 ab = 0，ab = 1， 则称b为a的补元，记为a'。若有界格中的所有元素都存在补元，则称为有补格。例6.2.9*例6.2.9如下图有界格，求其所有元素的补元(如果有的话)。例6.2.9（续）*例6.2.9（续）解 对于图a中,d与c互补,a,d都是e的补元,c和e都是d的补元, b无补元。 对于图b: 0' = 1，1' = 0， a' = b，a' = d， b' = a，b' = c， c' = d，c' = b， d' = a，d' = c 则图a不是有补格，图b是有补格。定理6.2.9*定理6.2.9在有界分配格(既是有界格又是分配格，简称为有界分配格)中，如元素a∈L有补元存在，则此元素的补元必惟一。 证明 设a有两个补元b和c，由补元的定义知 ab = 0 = ac，ab = 1 = ac 由定理知，b = c。 推论6.2.1 在有补分配格(既是有补格又是分配格，简称为有补分配格)中，每个元素都存在惟一的补元。定理6.2.10*定理6.2.10设是有补分配格，“ ≤ ”是该格的偏序，则对任意a, b∈L，都有 （1）(a')' = a； (对合律) （2）(ab )' = a'  b' ， (ab)' = a'b'； (De Morgan律) （3）a ≤ b  b' ≤ a'； （4）a ≤ b  ab' = 0  a'b = 1。定理6.2.10（续）*定理6.2.10（续）证明 （1）因a'是a的补元，反过来，a也是a'的补元，由推论15.2.1得，(a')' = a。 （2）因为 (ab)  (a'b') = ((ab) a')  ((ab) b') (分配律) = ((aa')b)  (a (bb'))(交换律，结合律) = (0b)  (a0) = 00 = 0定理6.2.10（续）*定理6.2.10（续）(ab)  (a'b') = (a (a'b')) * (b (a'b'))(分配律) = ((aa') b') * (a' (bb'))(交换律，结合律) = (1b')  (a'1) = 11 = 1 所以， a'b'是ab的补元，由补元的惟一性得，(ab)‘ = a’b‘。 同理可证，(ab)' = a'b'。定理6.2.10（续）*定理6.2.10（续）（3）“”，由a ≤ b，可得ab = a，则有 (ab)' = a' 由De Morgan律(即(2))，有 a‘b’ = a' ，即是 b' ≤ a' “”，上述过程可逆，故成立。 （4）“”由a ≤ b，根据(3)，有 b‘ ≤ a'则 ab' ≤ aa' = 0，即是定理6.2.10（续）*定理6.2.10（续）ab' ≤ 0， 又0是全下界，有 0 ≤ ab' 则根据偏序关系“ ≤ ”的反对称性，有 ab' = 0， 对上式使用De Morgan律，自然有 a'b = 1定理6.2.10（续）*定理6.2.10（续）“”如果a'b = 1，由De Morgan律，有 ab' = 0，则有 a'(ab') = a'0 = a' 对上式的左边使用分配律，可得 a'(ab') = (a'a)  (a'b') = 1 (a'b') = a'b' 即是 a‘b’ = a‘，所以有 b’ ≤ a‘，由(3)可得 a ≤ b。定义6.3.1*定义6.3.1称有补分配格为布尔格。 定义6.3.2 由一个布尔格所诱导的一个代数系统称为布尔代数。若一个布尔代数的元素个数是有限的，则称此布尔代数为有限布尔代数，否则称为无限布尔代数。布尔代数*布尔代数布尔代数是有补分配格，有补分配格必须满足它是格、有全上界和全下界、分配律成立、每个元素都有补元存在。显然，全上界1和全下界0可以用下面的同一律来描述： 同一律： 在L中存在两个元素0和1，使得对任意a∈L，有 a1 = a，a0 = a。布尔代数*布尔代数补元的存在可以用下面的互补律来描述。 互补律：对任意a∈L，存在a‘∈L，使得 aa’ = 0，aa‘ = 1。 格可以用交换律、结合律、吸收律来描述。 因此，一个有补分配格就必须满足交换律、结合律、吸收律、分配律、同一律、互补律。 另外，可以证明，由交换律、分配律、同一律、互补律可以得到结合律、吸收律。所以布尔代数有下面的等价定义： 定义6.2.3*定义6.2.3设是代数系统，其中、是B中的二元运算，如果对任意a, b, c∈B，满足 （1）交换律：ab = ba，ab = ba； （2）分配律：a (bc) = (ab)  (ac)， a (bc) = (ab)  (ac)； （3）同一律：在B中存在两个元素0和1，使得对任意a∈B，有 a1 = a，a0 = a； （4）互补律：对任意a∈B，存在a‘∈B，使得 aa' = 0，aa' = 1。 则称为布尔代数。定义6.2.3（续）*定义6.2.3（续）通常将布尔代数记为。为方便起见，也简称B是布尔代数。定义6.2.4*定义6.2.4设是布尔代数，S是B的非空子集，如果运算，和 ’ 都对S是封闭的，则称为的子布尔代数，简称S为B的子布尔代数。 显然，对任意布尔代数，子集{0, 1}和B总能构成B的子布尔代数，这两个子布尔代数称为的平凡子布尔代数。例6.3.1*例6.3.1考察下图所示的布尔代数。S1 = {a, a', 0, 1}，S2 = {a, b', c, 0} ，S3 = {a, b, 0, 1}，试问S1, S2, S3能否构成B的子布尔代数？ 例6.3.1（续）*例6.3.1（续） 解 由于S1对运算、和‘ 都是封闭的，所以S1能构成B的子布尔代数。 S2仅对运算和封闭，而对运算'不封闭，所以S2只能构成B的子格，而不能构成B的子布尔代数。 由于S3对运算不是封闭的，所以S3既不能构成B的子格，也不能构成B的子布尔代数。定义6.2.5*定义6.2.5设和是两个布尔代数，f是L到S的映射。如果对任意x, y∈B1，都有 f(x*y) = f(x)∧f(y), f(x  y) = f(x)∨f(y) f(x') = ┐f(x) , f(0) = α, f(1) = β 则称f为从布尔代数到的布尔同态映射，简称布尔同态。定义6.2.5（续）*定义6.2.5（续）如果f是格同态，当f分别是单射、满射和双射时，f分别称为单一布尔同态、满布尔同态和布尔同构。 nullhttp://202.115.21.136:8080/lssx/