《离散数学第八章布尔代数.ppt》由会员分享，可在线阅读，更多相关《离散数学第八章布尔代数.ppt（16页珍藏版）》请在三一办公上搜索。
1、,第八章 布尔代数,离散数学 陈志奎主编人民邮电出版社,英国数学家G.布尔为了研究思维规律（逻辑学、数理逻辑)于1847和1854年提出的数学模型。此后R.戴德金把它作为一种特殊的格。数学家G.布尔由于缺乏物理背景，所以研究缓慢，到了20世纪3040年代才有了新的进展，大约在 1935年，M.H.斯通首先指出布尔代数与环之间有明确的联系，他还得到了现在所谓的斯通表示定理：任意一个布尔代数一定同构于某个集上的一个集域；任意一个布尔代数也一定同构于某个拓扑空间的闭开代数等，这使布尔代数在理论上有了一定的发展。布尔代数在代数学（代数结构）、逻辑演算、集合论、拓扑空间理论、测度论、概率论、泛函分析等数
2、学分支中均有应用；1967年后，在数理逻辑的分支之一的公理化集合论以及模型论的理论研究中，也起着一定的作用。近几十年来，布尔代数在自动化技术、电子计算机的逻辑设计等工程技术领域中有重要的应用。,起源,1835年，20岁的乔治布尔开办了一所私人授课学校。为了给学生们开设必要的数学课程，他兴趣浓厚地读起了当时一些介绍数学知识的教科书。不久，他就感到惊讶，这些东西就是数学吗？实在令人难以置信。于是，这位只受过初步数学训练的青年自学了艰深的天体力学和很抽象的分析力学。由于他对代数关系的对称和美有很强的感觉，在孤独的研究中，他首先发现了不变量，并把这一成果写成论文发表。这篇高质量的论文发表后，布尔仍然留
3、在小学教书，但是他开始和许多第一流的英国数学家交往或通信，其中有数学家、逻辑学家德摩根。摩根在19世纪前半叶卷入了一场著名的争论，布尔知道摩根是对的，于是在1848年出版了一本薄薄的小册子来为朋友辩护。这本书是他6年后更伟大的东西的预告，它一问世，立即激起了摩根的赞扬，肯定他开辟了新的、棘手的研究科目。布尔此时已经在研究逻辑代数，即布尔代数。,起源,布尔代数把逻辑简化成极为容易和简单的一种代数。在这种代数中，适当的材料上的“推理”，成了公式的初等运算的事情，这些公式比过去在中学代数第二年级课程中所运用的大多数公式要简单得多。这样，就使逻辑本身受数学的支配。为了使自己的研究工作趋于完善，布尔在此
4、后6年的漫长时间里，又付出了不同寻常的努力。1854年，他发表了思维规律这部杰作，当时他已39岁，布尔代数问世了，数学史上树起了一座新的里程碑。几乎像所有的新生事物一样，布尔代数发明后没有受到人们的重视。布尔在他的杰作出版后不久就去世了。20世纪初，罗素在数学原理中认为，“纯数学是布尔在一部他称之为思维规律的著作中发现的。”此说一出，立刻引起世人对布尔代数的注意。今天，布尔发明的逻辑代数已经发展成为纯数学的一个主要分支。,起源,格与布尔代数是具有两个二元运算的代数系统，它们与同样具有两个二元运算的代数系统环有着完全不同的性质。格与布尔代数主要应用于逻辑电路设计、数据仓库、软件形式方法等方面。,
5、起源,格的定义与性质,分配格、有补格与布尔代数,应用,内容安排,知识回顾偏序：设R为非空集合A上的关系，如果R是自反的、反对称的和可传递的，则称R为A上的偏序关系，简称偏序，记作。一个集合A和A上的偏序关系R一起叫做偏序集，记作或。,8.1 格的定义与性质,定义8.1 设是偏序集，若a，bL，a，b都有最小上界和最大下界，则称L关于偏序构成格，称是格。由于最小上界和最大下界的唯一性，可以把求x，y的最小上界和最大下界看成x与y的二元运算和，即xy和xy分别表示x与y的最小上界和最大下界。在本章中符号与不再代表逻辑合取和析取，而是格中的运算，若使用其合取与析取的性质将会特别提到。,8.1 格的定
6、义与性质,格的对偶原理 设f是含有格中元素及符号=，等的命题。如果f对于一切格为真，那么f的对偶命题 也对一切格为真。定理8.1 设为格，则运算和满足交换律、结合律、等幂律和吸收率。证明：设x=ab，所以x=ba，所以满足交换律；设x=abc，x=a（bc），所以满足结合律；a=aa，所以满足等幂律；x=abb=ab，所以满足吸收律。同理可证满足交换律、结合律、等幂律、吸收律。,8.1 格的定义与性质,定理8.2 设是具有两个二元运算的代数系统，并且*和运算满足交换律、结合律、等幂律和吸收率。则可以适当的定义S中的偏序关系，使得构成一个格，且a，bS有ab=a*b，ab=ab。定义8.2 设是
7、含有两个二元运算*和的代数系统。如果*和满足交换律、结合律、吸收率，则构成一个格,8.1 格的定义与性质,例8.1 设n是正整数，是n的正因子的集合，D为整除关系，则偏序集构成格。x，y，xy是lcm（x，y），即x与y的最小公倍数。xy是gcd（x，y），即x与y的最大公约数。图8.1给出了个和格中满足四条运算定律（定理8.1），但等幂律可由吸收率推出，故上述定义只需满足三条运算定律即可。,8.1 格的定义与性质,例8.2 判断下列偏序集是否构成格，并说明理由。（1），其中P(B)是集合B的幂集。（2），其中Z是整数集，为小于或等于关系。解：（1）是格，x，yP(B)，xy就是xy，xy就是
8、xy。由于和运算在集合P(B)上是封闭的，所以xy，xyP(B)，称为B的幂集格。（2）是格，x，yZ，xy=max（x，y），xy=min（x，y），他们都是整数。,8.1 格的定义与性质,例8.3 设G是群，L(G)是G的所有子群的集合，即L(G)=H|HG对任意的H1，H2L(G)，H1H2也是G的子群，而是由H1H2生成的子群。在L(G)上定义包含关系，则L(G)关于包含关系构成一个格。称为G的子群格。易见在L(G)中，H1H2就是H1H2，H1H2就是。,8.1 格的定义与性质,定理8.3 设S是格，则a，bS均有：abab=aab=b证明：因为S是格，a，bS，ab，a与b有下界且最大下界为a，所以ab=a。同理可得：ab=b。,8.1 格的定义与性质,定义8.3 设是格，L是S的非空子集，如果L关于格中的运算和仍构成格，那么L是S的子格。,8.1 格的定义与性质,LOGO,大结局,THE END,人生只若如初见,
