第十章格与布尔代数.ppt

第十章 格与布尔代数,10.1 格的定义与性质1.定义与群，环，域，不同，格与布尔代数的基集都是一个偏序集，格是具有两个二元运算的代数系统，是一个特殊的偏序集，布尔代数是一个特殊的格。定义10.1：设是偏序集，若都有上下确界，则称为格(Lattice)(1)偏序集的任一子集并非都有上下确界，(2)偏序集的某一子集的上下确界若存在，则唯一，格的定义确定了上下确界的存在性，(3)x,y的上确界记为xy，下确界记为xy,10.1 格的定义与性质,定义10.2：设f是含有格中元素及符号=,的命题，令 是将f中,分别替换为,所得到的命题，则称 是f的对偶命题或称对偶式。格的对偶原理：若f对一切格为真，则 也对一切格为真。例：定理10.1：设是格，则运算,满足交换律，结合律，幂等律，吸收律，即,10.1 格的定义与性质,10.1 格的定义与性质,由定理10.1知，格的两个运算满足交换律，结合律，幂等律，因此可以考虑用带有这4条性质的2个二元运算,，来像群，环，域，一样定义格，即用来定义格，可以证明这是可行的。定理10.2：设是具有二个二元运算的代数系统，且*,运算满足交换律，结合律，吸收律，则可以适当定义S中的偏序，使得构成一个格，,10.1 格的定义与性质,10.1 格的定义与性质,10.1 格的定义与性质,由定理10.1,10.2可知：,10.1 格的定义与性质,因此，根据定理10.1，10.2，可以用代数系统的方式来定义格。定义10.3：设是代数系统，*,是二元运算且满足交换律，结合律，吸收律(幂等律)，则构成一个格。2.性质定理10.3：设是格，则，有,10.1 格的定义与性质,10.1 格的定义与性质,10.2 子格与格同态,1.子格定义10.4：设代数系统是一个格，若S满足：，则称是的子格。定义10.5：设是一个格，若S满足：，则称是的子格。例10-1：(1)设是一个格，其中L=a,b,c,d,e，其哈斯图如右图。,b,a,e,c,d,10.2 子格与格同态,2.格同态定义10.6：设 和 是格，若 有，则称 为格 到 的同态映射，简称格同态，若 是双射，则称 为格同构。定义10.7：设 和 是格，其中 分别为格 上的偏序关系，存在映射，若，称f是序同态，若f是双射，则称f是序同构。(格同态定理)定理10.4：(1)设 是格 到格 的同态，则 是序同态，即同态是保序的，即,10.2 子格与格同态,(2)是双射，则 是 到 的同构的充要条件是,10.2 子格与格同态,例10-2：在同构意义下：具有1，2，3个元素的格分别同构于元素个数相同的链，4个元素的格必同构于下图4元素格之一，5个元素的格必同构于下图5元素格之一,(2),(3),(4),(5),(6),(7)五角格,(9),(8)钻石格,(10),(1),10.2 子格与格同态,定义10.8：设 和 是格，定义 上的二元运算：对，有：则称 为 和 的直积。直积仍是格(证明满足交换，结合，吸收律即可),10.3 特殊格,1.分配格一般来说，对格，有，则定义10.9：设 是格，若，有 则称L为分配格。例：(1)(2),是,是,非,非,10.3 特殊格,定理10.5：L是格，则L是分配格L中不含有与钻石格或五角格同构的子格。推论：(1)小于五元的格都是分配格；(2)任何一条链都是分配格。(分配格的性质)定理10.6：若L是格，则L是分配格当且仅当,10.3 特殊格,命题条件 同时成立，否则不正确。反例：分配格 中：,10.3 特殊格,2.模格定义10.10：设 是格，若，有：(模律)，则称 为模格，也称为戴德金格。定理10.7：格L是模格的充要条件是它不含有同构于五角格的子格。定理10.8：设 为分配格，则 是模格,10.3 特殊格,3.有界格定义10.11：设L是格，若存在，使得，有，则称a为L的全下界，若存在，使得，有，则称b为L的全上界。(1):有限格 一定是有界格，全下界，全上界；(2):无限格可以为有界格，如 全下界，全上界B；(3):全上界，全下界唯一，分别记为1和0定义10.12：设L是格，若L存在全上界和全下界，则称L为有界格，记为,10.3 特殊格,定理10.9：设 为有界格，则，有4.有补格定义10.13：设 是有界格，若存在，使得 且，则称b是a的补元。补元的性质：(1):补元素相互的；(2):并非有界格的每个元素都有补元，而有补元也不一定唯一；(3):0，1互为补元，且唯一。,10.3 特殊格,定理10.10：设 是有界分配格，若 且对于a存在补元b，则b是a的唯一补元。定义10.14：设 是有界格，若 在L中都有a的补元存在，则称L是有补格。,10.4 布尔代数,1.概念定义10.15：如果一个格是有补分配格，则称它为布尔代数。有补格保证每个元素有补元，分配格保证每个元素的补元的唯一性，因此，可将求补元看作是布尔代数的一元运算，即例：定理10.11：设 是布尔代数，则,10.4 布尔代数,布尔代数：交换律，结合律，吸收律，分配律，存在补元，可用交换律，分配律，同一律，补元律代替。另一等价定义：定义10.16：是代数系统，是二元运算，且 满足：(1)交换律，(2)分配律，(3)同一律：存在(4)补元律：则称 是布尔代数。,10.4 布尔代数,(1):幺元为1；：幺元为0(同一律)。可证：:零元为0；：零元为1。(2):吸收律成立。结合律成立。,10.4 布尔代数,2.子布尔代数定义10.17：设 是布尔代数，若，且S对，封闭，则称S是B的子布尔代数。例：(1)对任何布尔代数 恒有子布尔代数 和 均为B的平凡布尔代数。,10.4 布尔代数,(2)定理10.12(判定定理)：设 是布尔代数，若，则S是B的子布尔代数，记作,1,f,d,e,c,b,a,0,10.4 布尔代数,3.布尔代数的同态定义10.18：设 和 是两个布尔代数，若，有：则称 为 到 的布尔同态，若 为双射，则为布尔同构。4.有限布尔代数的结构定义10.19：设L是格，若a是0的覆盖，则称a是L中的原子，即：定理10.13：设 是布尔代数，B中元素a是原子的充要条件是a0，且对，有：,10.4 布尔代数,定理10.14：设L是格，a，b是L中的原子，若ab，则ab=0。定理10.15：设B是有限布尔代数，令 是B中所有x的原子构成的集合()，则：,10.4 布尔代数,10.4 布尔代数,10.4 布尔代数,定理10.16(有限布尔代数的表示定理)：设 是有限布尔代数，A=a|aB且a是原子，则,10.4 布尔代数,10.4 布尔代数,推论1：任何有限布尔代数的基数为推论2：任何具有 个元素的布尔代数互相同构(对无限布尔代数不成立),10.4 布尔代数,5.布尔表达式定义10.20：设 是一个布尔代数，B中的元素称为布尔常元，取值于B中元素的变元称为布尔变元。定义10.21：设 是一个布尔代数，在B上的布尔表达式定义如下：(1).B中任何一个常元是布尔表达式；(2).B中任何一个布尔变元是布尔表达式；(3).如果 是布尔表达式，则 也是布尔表达式；(4).有限次使用(1)，(2)，(3)所构造的符号串是布尔表达式。,10.4 布尔代数,定义10.22：设 是一个布尔代数，B的一个含有n个相异布尔变元的布尔表达式称为n元布尔表达式，记为，其中 是布尔变元。定义10.23：设 和 是布尔代数 上的两个布尔表达式，如果对n个布尔变元的任意指派，和 的值均相等，则称 与 是等价的或相等的，记作：(1).如果能有限次应用布尔代数的公式，将一个布尔表达式化成另一个布尔表达式，就可判定两式是等价的；,10.4 布尔代数,(2).等价关系将n元布尔表达式集合划分成等价类，同一等价类中的布尔表达式等价，等价类数目有限。定义10.24：设 是布尔代数，给定n个布尔变元，表达式：()，称为极小项。(1).n个布尔变元就有 个不同的极小项，分别记为，下标是二进制数 的十进制表示，其中,10.4 布尔代数,(2).(3).定义10.25：设 是布尔代数，如 的布尔表达式称为主析取范式，其中 是布尔常元，是极小项().(1).每个 有|B|种取法，故有n个布尔变元的不同的主析取范式有 个，当B=0,1时有 个;(2).个极小项，最多能构造出 个主析取范式，所以一个n元布尔表达式必等价于这 个主析取范式之一；(3).可用数理逻辑中的方法，用德摩根律等将一,10.4 布尔代数,个n元布尔表达式转化为等价的主析取范式；(4).相应的：极大项：主合取范式为：是布尔常元，是极大项，同样有 个不同的主合取范式，个极大项最多能构造 个不同的主合取范式。例：将布尔代数 上的布尔表达式 化为主析取范式和主合取范式,10.4 布尔代数,10.4 布尔代数,定义10.26：设 是一个格，一个从 到B的函数，如果能够用该布尔代数上的布尔表达式来表达，则称这个函数为布尔函数。(1).每一个n元布尔表达式可以看作是一个n个布尔变元的函数；(2).n个变元的主析取范式最多有 个，只能代表 个不同的函数，到|B|的函数共有 个；当B=0,1时，函数有 个，主析取范式 个，每个函数均可用布尔表达式表示，当B0,1时，如B=0,1,a,b时，函数有 个，主析取范式有 个，即当|B|2时，有些 到B的函数不能用布尔表达式表示。,10.4 布尔代数,(3).命题逻辑可以用布尔代数 来描述，开关代数可以用布尔代数来描述。,