逻辑与代数是计算机科学最重要的基础,布尔代数是数理逻辑早期

第五章布尔代数基础逻辑与代数是计算机科学最重要的基础，布尔代数是数理逻辑早期的雏形，是一种用代数演算的方法来研究思维结构的逻辑系统，同时也为计算机的运算提供重要基础。问题：什么是逻辑呢？对逻辑来说不存在清规戒律，每个人都可以构造自己的逻辑，即他自己表达思想的语言形式，只要他愿意。但如果他想讨论这种逻辑，那么，对他的唯一要求是他必须说清楚他的方法，即给出语法和语义规则，而不是给出哲学论据。Carnap（卡尔纳普）第五章布尔代数基础本章主要介绍布尔代数的基本知识，它可以为学生今后学习计算机逻辑代数，数字逻辑，计算机组成原理，二进制运算，以及数理逻辑提供一个基础。5.1集合的基本概念与基本运算由事物或对象组成的集体，无论它们是由其成员通过枚举方式直接表示出来的，还是由其成员所具有的某些本质属性表示出来的，都称为集合。称两个集合是相等的，如果构成这两个集合的成员完全相同。集合的成员也叫元素。一个集合A中元素的个数叫做集合A的基数，记为│A│。请注意，这不是基数的严格的定义。对有穷集合，这样定义基数勉强可行，但对无穷集合不恰当。有关集合基数的概念和知识将来读者会在离散数学或集合论等课程中系统地学习，目前，我们暂且使用这种不严格的直观上的定义。5.1.1从属与包含关系通常用大写英文字母作为集合的名称。若某事物a是集合A的一个元素，则记为a∈A并说“a属于A”，或者说“a在A中”。若a不是集合A的元素，则记为aA当以枚举形式表示一个集合时，我们用一个大括号把这些枚举的元素括起来以表示这个集合。例1{麻雀，黄鹂，杜鹃，白鹭，红嘴鸥}是一个由五种鸟组成的集合；{a,b,c,d,…,x,y,z}是由英语的26个小写字母组成的集合。例2A＝{x│ax2+bx+c＝0且a,b,c∈R}，R是实数集。例3B＝{a,b,aa,ab,bb,aaa,aab,abb,bbb,aaaa,…}这种带省略的表示形式实际上可表示一些集合元素有某种出现规律的无穷集合。集合的表示应当注意以下两点：(1)同一个集合中的元素是互不相同的。(2)集合中的元素之间不规定次序。与空集合相对应的一个大的集合是所谓的全集合，即一切事物构成的集合。这是一个虚构的集合，但它在布尔代数的运算中是有用的。我们用1来表示这个虚设的全集合。考虑两个集合A和B。若集合A的每一个元素也是集合B的一个元素，则称集合B包含集合A，也称集合A包含在集合B中，记为AB若AB，则称A是B的子集合，B是A的母集合。显然，对任何集合A，有AA。若集合A、B之间存在AB且A≠B，则称A是B的真子集合，记为AB。若AB，又有BA，则可以得出结论A＝B。这是因为A的元素都是B的元素，而B的元素也是A的元素，说明A，B中拥有相同的元素，所以A和B相同，故相等。显然，对任何集合A，A1。特别地，1。5.1.2集合的基本运算和基本关系1.集合的交与并设A、B是两个集合，定义A和B的公共元素构成的集合C为A和B的交集，简称A和B的交，记为C＝A∩B；将集合A的元素和集合B的元素合并在一起，组成一个新的集合C，那么，这样得到的集合C就定义为集合A和集合B的并集，简称A和B的并，记为C＝A∪B。如果从全集合1中取出部分元素构成集合A，剩下的元素构成集合B，那么，集合A与集合B就形成互补关系。我们称集合B为集合A的补集合，记为A’＝B。显然，也有B’＝A。而且此时下列定理1的一系列等式成立。定理1设A为一个集合，B为A的补集合，则(1)A∩B＝，(2)A∪B＝1，(3)’＝1，(4)1’＝，(5)(A’)’＝A，(6)(1’)’＝1，(7)(’)’＝。我们选择证明其中的(1)，其余的证明留给读者作为练习。今后，我们也采用这种方式，将一部分证明工作留给读者。证明(1)用反证法。设A∩B≠，则必存在非空元素x∈A∩B，故x∈A且x∈B，此与B为A的补集合矛盾。所以，A∩B＝。□例4设A＝{a,b,c,d}，B＝{c,d,e,f}，C＝{e,f,g,h}，则A∩B＝{c,d}，A∪B＝{a,b,c,d,e,f}，A∩C＝，A∪C＝{a,b,c,d,e,f,g,h}。根据定义，不难证明定理2。定理2对任意集合A和集合B，有(1)A∩B＝B∩A，（交换律）(2)A∪B＝B∪A，（交换律）(3)A∩A＝A，(4)A∪A＝A，（幂等律）(5)A∩A’＝，(6)A∪A’＝1，(7)A∩＝，(8)A∪＝A。我们选择证明其中的(2)，其余的(1)、(3)-(8)大家可以自己试着去证明。证明(2)我们分两部分来证明。首先证明左边的集合是右边集合的子集合，然后再证明右边的集合是左边集合的子集合。这样，若两个集合互为子集合时，必然相等。①设任意元素x∈A∪B，则x∈A或者x∈B，也可表述为x∈B或者x∈A，故A∪BB∪A；②同理可证，B∪AA∪B。所以，A∪B＝B∪A。□定理2(2)的上述证明方法是证明两个集合相等时最常用的方法，也是最基本的方法。2.集合上的一些基本关系下面我们在集合相补、包含、交与并的基础上，首先来建立一些基本关系。定理3设A，B为任意集合，则(1)A∩BA，(2)A∩BB，(3)AA∪B，(4)BA∪B。我们选择证明其中的(1)，其余的(2)-(4)大家可以自己试着去证明。证明(1)设任意元素x∈A∩B，由交的定义知，x∈A，故A∩BA。□定理4设A、B为任意集合，则(1)AB，当且仅当A∩B＝A，(2)A∩B＝A，当且仅当A∪B＝B，(3)A∪B＝B，当且仅当AB。这个定理说明了一个循环等价关系。象这样的等价关系，今后可用来作等价的概念定义。证明(1)我们分两部分来证明定理的充分性。①设任意元素x∈A∩B，故x∈A且x∈B，可得A∩BA；②又设任意元素x∈A，由AB知x∈B，故x∈A∩B，可得AA∩B。综合①、②，知A∩B＝A。由A∩B＝A导出AB是显然的。□上面的证明中，仍然采用了论证两个集合相等最基本的方法，即设法先证明等式两边的集合互为子集合。若两个集合互为子集合，那么，显然这两个集合是相等的。证明一个定理，有时候需要从定义出发推导、论证，有时候需要引用已知的结论来简化证明步骤。事实上，定理4(1)的证明中第一部分可以直接引用定理3的(1)。今后我们应该逐步习惯于简化的证明方式。定理5（DeMorgan律）设A、B为任意集合，则(1)(A∩B)’＝A’∪B’，(2)(A∪B)’＝A’∩B’。证明我们只要证明其中的一个就可以了，因为这两个式子中的任何一个是另一个在相补关系下的直接结果。下面，我们证明(1)。设任意元素x∈(A∩B)’，则x(A∩B)，因此xA或xB。换言之x∈A’或x∈B’，故x∈A’∪B’。所以，(A∩B)’A’∪B’；反之，设任意元素x∈A’∪B’，则x∈A’或x∈B’。换言之xA或xB，因此x(A∩B)，故x∈(A∩B)’。所以，A’∪B’(A∩B)’。从而，可知(A∩B)’＝A’∪B’。□定理6对任意的集合A，A。证明使用反证法。假设定理不成立，即存在集合A，使得A不成立。这就是说，存在元素x∈,但xA，这与是空集合相矛盾。故定理成立，空集合是一切集合的子集合。□定理7空集合是唯一的。证明设1和2都是空集合，由定理6知11且21，所以1＝2。□3.集合上的一些运算定律与中学数学中加法和乘法的结合律、分配律一样，集合的运算除了满足我们已经看到的幂等律、交换律之外，也满足结合律和分配律。采用类似于定理5的证明方法，容易证明定理8。定理8设A、B、C是任意的集合，则(1)A∪(B∪C)＝(A∪B)∪C，（结合律）(2)A∩(B∩C)＝(A∩B)∩C，（结合律）(3)A∪(B∩C)＝(A∪B)∩(A∪C)，（分配律）(4)A∩(B∪C)＝(A∩B)∪(A∩C)。（分配律）证明(3)设x∈A∪(B∩C)，则x∈A或x∈B∩C。若是前一种情况，那么x∈A∪B且x∈A∪C，因而x∈(A∪B)∩(A∪C)；若是后一种情况，那么x∈B且x∈C，因此x∈A∪B且x∈A∪C，也有x∈(A∪B)∩(A∪C)。这就证明了A∪(B∩C)(A∪B)∩(A∪C)；反之，设x∈(A∪B)∩(A∪C)，则x∈A∪B且x∈A∪C。若x∈A，那么x∈A∪(B∩C)；若xA，那么必有x∈B且x∈C，因此x∈B∩C，也有x∈A∪(B∩C)。这就证明了(A∪B)∩(A∪C)A∪(B∩C)；所以，A∪(B∩C)＝(A∪B)∩(A∪C)。□4.集合上的其它一些关系利用集合上的基本关系和基本运算，可以导出集合上的其它一些关系。定理9设A、B、C是任意的集合，那么下列关系成立：(1)若AB且AC，则AB∩C；(2)若AC且BC，则A∪BC。定理10设A、B、C是任意的集合，若AB，则(1)A∩CB∩C，(2)A∪CB∪C。由定理3和定理10易证定理11。定理11设A，B是任意的集合，则有A∩(A∪B)＝A。证明依定理3有A∩(A∪B)A。又A＝A∩A，AA∪B，因此，由定理10知A∩AA∩(A∪B)，故AA∩(A∪B)。所以，A∩(A∪B)＝A。□定理12设A、B是任意的集合，则AB，当且仅当A∩B'＝。定理13设A是一个集合，那么下列等式成立：(1)若对任意的集合B，都有AB，则A＝；(2)若对任意的集合B，都有BA，则A＝1。证明(1)由题设，特别当B＝时，有A，但A，所以A＝。□定理14设A、B是两个集合，那么下列等式成立：(1)若A∪B＝，则A＝且B＝；(2)若A∩B＝1，则A＝1且B＝1。证明(1)因AA∪B＝，故A＝；同理可证，B＝。□5.集合的差与对称差(同学们在中学已经学习)除了上面介绍的一些运算之外，还有两种重要的集合运算是大家需要掌握的，它们是集合的差与对称差。定义1集合A，B的差A－B定义为一切属于A但不属于B的元素构成的集合，即A－B＝A∩B’。对任意集合A，B，不难证明定理15。定理15设A，B，C都是集合，那么下列等式成立：(1)1－A＝A’；(2)A－B＝，当且仅当AB；(3)(A－B)∪B＝A∪B；(4)C∩(A－B)＝(C∩A)－(C∩B)。（分配律）交关于差是可分配的。但是，并关于差却不是可分配的。大家可以通过思考和举一反例来认识这一点。定义2集合A，B的对称差AB定义为A与B之差和B与A之差的并，即AB＝(A－B)∪(B－A)。显然，A与B的对称差也可以写成如下的定义形式：AB＝(A∩B’)∪(B∩A’)。由定义2，我们还可以得到对称差的其它几种表示形式或等价定义。定理16若A，B是两个集合，则(1)AB＝(A∪B)∩(A’∪B’)，(2)AB＝(A∪B)－(A∩B)，(3)AB＝A’B’。作为一种运算，对称差满足一些定律。定理17设A，B，C都是集合，那么下列等式成立：(1)AB＝BA；（交换律）(2)(AB)C＝A(BC)；（结合律）(3)A∩(BC)＝(A∩B)(A∩C)；（分配律）(4)A∪(BC)≠(A∪B)(A∪C)。（并关于对称差不满足分配律）证明(3)A∩(BC)＝A∩((B－C)∪(C－B))＝(A∩(B－C))∪(A∩(C－B))＝(A∩B)－(A∩C))∪(A∩C)－(A∩B))＝(A∩B)(A∩C)。□定理18设A，B是两个集合，那么下列等式成立：(1)AA＝，(2)若AB＝φ，则A＝B。定义3设A，B为集合，AB的补定义为A与B的叉，记为A×B，即A×B＝(A∩B)∪(A’∩B’)。类似于对称差的性质，易证定理19。定理19设A，B，C都是集合，那么下列等式成立：(1)A×B＝A’×B’，(2)A×B＝B×A，（交换律）(3)(A×B)×C＝A×(B×C)，（结合律）(4)A×A＝1，(5)A×B＝A’B＝AB’，(6)A×B’＝A’×B＝AB。6.幂集合及其性质前面已经讨论了集合的一些最基本的内容。众所周知，我们到现在为止所讨论的集