工科离散数学课件 第六章 6_9_格(3) - 特殊格.pptx

6.9 格-特殊格6.9.3 特殊格 1. 分配格[分配格]设<L,∨,∧>为格，若运算∨和∧满足分配律，即对?a, b, c∈L, 有 a∨(b∧c) = (a∨b)∧(a∨c)，a∧(b∨c) = (a∧b)∨(a∧c)称<L, ? >为分配格。例6-36：说明图中的哪些格是分配格。解： L1和L2是分配格，L3和L4不是分配格。 L3：b∧(c∨d) = b∧e = b， (b∧c)∨(b∧d) = a∨a = a L4： c∨(b∧d) = c∨a = c，(c∨b)∧(c∨d) = e∧d = dcL2badbcaL1L3ebdacL4ebdac钻石格五角格2个重要的非分配格 6.9 格-特殊格定理-判别分配格：若L是格，则L是分配格当且仅当L不含有与钻石格和五角格同构的子格。Try it：怎么理解格同构？例6-37：说明图中的格都不是分配格。答：两个格中元素的名字、左右位置可不同，但元素间大小关系一致。解：A1含与钻石格同构的子格，A2和A3含与五角格同构的子格。fdcA3abegcA2aefdbA1ebdachfg问：对A3 ，用S = {f, b, d, e, a}与钻石格同构，能判定A3不是分配格吗？答：否。S是子集而非子格。 6.9 格-特殊格定理：链是分配格。证明：设<L, ?>是链，则<L, ?>显然是格。对?a, b, c∈L，可能有如下两种关系：(1) a最大，即b ? a 且 c ? a 。有 b∨c ? a，a∧(b∨c) = b∨c = (a∧b)∨(a∧c) (2) a非最大，即a ? b 或a ? c，不妨设a ? b。因为 b ? b∨c，有 a∧(b∨c) = a因a∧b = a， a∧c ? a，有 (a∧b)∨(a∧c) = a 即a∧(b∨c) = (a∧b)∨(a∧c) 。 6.9 格-特殊格2. 有界格[全下界&全上界] 设<L, ?>是格，若?a∈L，使得?x∈L，a ? x，称a 为L 的全下界。若?b∈L ，使得x∈L，x ? b ，称b 为 L的全上界。示例：图A中，a 和h 分别是格A的全下界和全上界。问：格的全下（上）界一定存在？一定唯一？答：否；若存在，一定唯一。 Aebdachfg 6.9 格-特殊格[有界格] 设<L, ? >是格，且存在全上界和全下界，则称L 为有界格。通常，格的全下界和全上界分别记作0和1，有界格所诱导的代数系统记作< L,∨,∧, 0, 1>。示例：(1) <?(S)，?>为有界格，?和S 分别为全下界和全上界。(2) <{x | x∈?且0≤ x ≤1}, ≤ >是有界格，0和1是全下界和全上界。 6.9 格-特殊格长见识：任意有限格L = {a1, a2,…, an}是有界格，a1∧a2∧…∧an和a1∨a2∨…∨an 分别为全下界和全上界。定理：设< L,∨,∧, 0 , 1>为有界格，对?a∈ L ，有(1)同一律：a∨0 = a ， a∧1 = a。(2)零律：a∨1 = 1， a∧0 = 0。 证明：因0是全下界，0 ? a ，且a ? a ，有a∨0 ? a因a∨0为a 和0 的上界，有a ? a∨0得a∨0 = a 。其他等式的证明类似。 6.9 格-特殊格3. 有补格[补元]设<L,∨,∧, 0, 1>为有界格，对?a∈L ，若?b∈L ，使a∧b = 0， a∨b = 1称b 为 a 的补元，记作ā。 ——补元是相互的，且0和1总是互为补元[有补格] 设< L, ? >为有界格，若L 的所有元素都存在补元，称L 为有补格。[互补律]在一个有补格<L, ?>中，对?a∈L，?ā∈L，使得a∧ā = 0，a∨ā = 1——此算律称为“互补律”或“补元律” 6.9 格-特殊格例6-38：说明L1~L4是否为有补格。解：格L1：a和c分别为0和1，且互为补元，b没有补元，不是有补格。cL2badbcaL1L3ebdacL4ebdac 五角格L4：a和e分别为0和1，且互为补元，b的补元为c和d，c和d的补元都是b，是有补格。 格L2和L3也是有补格。