(a∧b)∨(a∧c)a∧(b∨c).pptVIP

计算机学院 计算机科学与工程学院 冯伟森 Email：fws365@scu.edu.cn * * 计算机学院 * 格与布尔代数 下面讨论两个重要的代数系统——格与布尔代数。布尔代数是人们利用数学方法研究人类思想规律的一项重要成果。布尔代数在逻辑电路设计和开关网络研究中有着广泛的应用，是计算机科学必需的基础知识。 布尔代数是一类特殊的格代数，在格与布尔代数中，偏序关系具有重要意义。本章将从格的偏序定义出发，研究格系统的各种性质，建立布尔代数的基本理论。 * 计算机学院 * 本章的主要内容 格的概念和基本性质 子格的定义 保序定理 特殊的格及性质 布尔代数的概念和基本性质 布尔表达式 * 计算机学院 * 格的定义 定义17.1（代数格） 设L，∨，∧是一个代数系统，如果∨，∧满足： 交换律：a∨b=b∨a，a∧b=b∧a, 结合律：a∨(b∨c)=(a∨b)∨c, a∧(b∧c)=(a∧b)∧c 吸收律：a∨(a∧b)=a，a∧(a∨b)=a 则称L，∨，∧是一个代数格。 这样的代数系统满足幂等律、交换律、结合律、吸收律、和分配律 集合代数系统2A，∪，∩ 命题逻辑系统?，∨，∧ 对这样的代数系统，从运算性质进行抽象，提取共性，得到下述“格”的概念 * 计算机学院 * 定理17.1(幂等律)： 设L，∨，∧是一个代数格,a ∈L, 则 a∨a=a，a∧a=a。 定义17.2　设L，?是一个偏序集，对?a，b?L，集合{a，b}都有最大下界(glb)和最小上界(lub)，则称L，?是一个偏序格，简称L是一个格，若L是一个有限集，则称L，?为有限格。 从定义知道：有限偏序集要成为格，必须有一个最大元和最小元。 * 计算机学院 * 偏序集2A，?中，任何两个元素X、Y?2A， 都有lub（X，Y）=X∪Y， glb（X，Y）=X∩Y 因此2A，?是一个偏序格，称为幂集格。 定理17.2 设L，∨，∧是一个代数格，定义“?”： a?b当且仅当a∧b=a（a∨b=b），则L，?是一个偏序格。 * 计算机学院 * 定理17.3 设L，?是一个偏序格，在格上定义“∨”、“∧”： a∧b=glb（a，b）， a∨b= lub（a，b）， 则 L，∨，∧是一个代数格。 定理17.2和定理17.3表明： 格的两种定义是完全等价的。 * 计算机学院 * 例17-1.1 如图所示的八个偏序集都是格； * 计算机学院 * 图17.1 * 计算机学院 * 如图所示的五个偏序集都不是格。 图17.2 * 计算机学院 * 子格与格同态 定义17.3　设代数系统L,∨,∧是一个格，S?L，若S满足： S≠Φ； 运算∨和∧对子集S都是封闭的； 则称S,∨,∧是L,∨,∧的子格。 注意：即使S,∨,∧构成一个格，但它不一定 是L,∨,∧的一个子格。 例17-2.1 设下图是格L,∨，∧对应的Hasse图，S1={a,b,c,f},S2={a,c,d,f},那么S1,∨，∧不是L,∨，∧的子格。因为b和c的最大下界是e,不在S1中，即S1不是封闭的，所以S1,∨，∧不是子格。同时b和c的最大下界在S中是f，而在L中是e,这也说明定义在L上的运算与定义在S1上的运算并不相同。 而S2,∨，∧是L,∨，∧ 的子格，因为它满足子格的条 件。 * 计算机学院 * * 计算机学院 * 定义1.13：设A和A*是两个包含?、∨、∧的命题公式。如果把A中的联结词∨换成∧，把∧换成∨，把Ｔ换成Ｆ，把Ｆ换成Ｔ后得到的正是A* ，则称A*是A的对偶公式。 如公式（P∨Q）∧R的对偶式为（P∧Q）∨R ～P∨（Q∧R）的对偶式为～P∧（Q∨R） 对偶原理（定理1.5） 设A和B是两个命题公式，若A ? B， 则 A* ? B* 复习 * 计算机学院 * 对偶原理 定义17.4 设L，?和L，?’是二个偏序格，如果?’是?的逆关系,则称这两个偏序格是互为对偶的格。 定义17.5 设L，?是一个格，格中的最大元用1表示，最小元用0表示。 E是格中的一个公式。将E中的0和1互换，∨和∧互换后得到的新公式E*称为E的对偶公式。 * 计算机学院 * 对偶原理 设X和Y是格L，?上的两个公式，X*和Y*是相对应的对偶公式。如果X=Y，那么X*=Y*。 * 计算机学院 * 例17-2.2 设L是由18的正因子组成的集合，则L关于整除关系构成格L,|。整除关系的逆关系是倍数关系。设倍数关系用“‖”表示，那么L,‖是格，并和L,|互为对偶。