离散数学6-3..ppt

1. 分配格 定义1：设A,∨,∧是由格A, ≤所诱导的代数系统，如果对?a,b,c?A，满足a∧(b∨c) = (a ∧ b) ∨(a ∧ c) （交对并可分配）a∨(b∧c) = (a ∨ b) ∧(a ∨ c) （并对交可分配）则称A, ≤是分配格。 例1：设 | S | = n，P(S),∪,∩是由格P(S), ?所诱导的代数系统，则格P(S), ?是分配格。 证明：对?A,B,C?P(S)，在集合运算中已经证明了 A∪ (B∩C) = (A∪B) ∩(A∪C) A∩ (B∪C) = (A∩B) ∪(A∩C) ∴ P(S), ?是分配格。 例2：下图所示的两个格都不是分配格。 ∵在左图中， a∧ (b∨c)=a∧1=a (a∧b) ∨(a∧c)=0∨0=0 a∧ (b∨c)≠(a∧b) ∨(a∧c) ∴左图不是分配格 注意：按照定义证明某个格是分配格不容易，但要证明一个格不是分配格，只要找出一组元素不满足某一分配式即可。上例中的两个五元格可用来判断某格是否是分配格。 定理1：一个格是分配格的充要条件是在该格中没有任何子格与这两个五元格中的任一个同构。 定理2：如果在一个格中，交运算对并运算可分配，则并运算对交运算也一定是可分配的，反之亦然。 证明：设A, ≤是格，对?a,b,c?A，若 a∧(b∨c) = (a ∧ b) ∨(a ∧ c)，则 (a∨b)∧(a∨c) = ((a∨b)∧a)∨((a∨b)∧c) = a∨((a∨b)∧c) = a∨(c∧(a∨b)) = a∨((c∧a)∨(c∧b)) = (a∨(c∧a))∨(b∧c) = a∨(b∧c) 若有a∨ (b∧c) = (a ∨ b) ∧(a∨c)，则 (a∧b)∨(a∧c) = ((a∧b) ∨a) ∧((a∧b) ∨c) = a∧(c∨ (a∧b)) = a∧((c∨a) ∧(c ∨b)) = (a∧ (c ∨a)) ∧(b ∨c) = a∧(b ∨ c) 定理3：每个链是分配格。 证明：设A, ≤是一个链，因为链中任两个元素都有最小上界和最大下界，所以链一定是格。下面证明链是分配格。对?a,b,c?A，讨论a最大和a不最大两种情况： (1) 设 b≤a且c≤a，∴a∧b = b，a∧c = c ∴ (a∧b)∨(a∧c) = b∨c 又∵ b∨c≤a，∴ a∧(b∨c) = b∨c ∴ a∧(b∨c) = (a∧b)∨(a∧c) (2) 设 a≤b或a≤c，不论b≤c还是c≤b ，都有a≤b∨c ∴ a ∧( b∨c) = a，(a∧b)∨(a∧c)=a ∴ a∧(b∨c) = (a∧b)∨(a∧c) 由定理1，有a∨ (b∧c) = (a ∨ b) ∧(a∨c) 因此A, ≤是分配格。 定理4：设A, ≤是分配格，则对?a,b,c?A， 若有 a∧b = a∧c且a∨b = a∨c ，则必有b = c 。 证明：∵a∧b≤b ?b = b∨(a∧b) = b∨(a∧c) = (b∨a)∧(b∨c) = (a∨c)∧(b∨c) = (a∧b)∨c = (a∧c)∨c = c ∴b=c 2. 模格 定义2：设A,∨,∧是由格A, ≤所诱导的代数系统，如果对?a,b,c?A，当b≤a时，有a∧(b∨c) = b∨(a∧c)则称A, ≤是模格。 例：下图所示的格是模格，但不是分配格。 定理5：分配格必定是模格。 证明：设A, ≤是分配格，对?a,b,c?A， 若b ≤ a，则a∧b=b， a∧ (b∨c)=(a∧b) ∨(a∧c)=b∨ (a∧c) ∴A, ≤是模格。 3. 有补格 定义3：设A, ≤是格，若存在元素a?A，对于?x?A，都有a≤x(x≤a)，则称 a 为格A, ≤的全下(上)界。 定理6：一个格若有全下（上）界，则是唯一的。 证明：设格A, ≤有两个全下界a和b，且a≠b ∵a是全下界，∴b?A，∴a ≤b， ∵ b是全下界，a?A ，∴b ≤a， 于是a=b，与假设矛盾。 定义4：若一个格中存在全上界1和全下界0，则称该格为有界格。 例： P(S), ?是一个格，全下界为?，全上界是S ∴ P(S), ?是有界格。 R,≤是链，不存在全上界和全下界，不是有界格。 定理7：设A, ≤是一个有界格，则对?a?A ，必有a∨1=1，a∧1=a，a∧0=0，a ∨ 0=a 定义5：设A, ≤是一个有界格，则对a?A，若存在b?A 使得 a∨b=1，a∧b=0，则称元素b是元素a的补元。 注：(1) 定义中a,b是对称的，若a是b的补元，则b也是a的补元； (2)