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

《逻辑与代数是计算机科学最重要的基础,布尔代数是数理逻辑早期》由会员分享，可在线阅读，更多相关《逻辑与代数是计算机科学最重要的基础,布尔代数是数理逻辑早期（62页珍藏版）》请在金锄头文库上搜索。

1、第五章 布尔代数基础逻辑与代数是计算机科学最重要的基础，布尔代数是 数理逻辑早期的雏形，是一种用代数演算的方法来研究思 维结构的逻辑系统，同时也为计算机的运算提供重要基础 。问题：什么是逻辑呢？对逻辑来说不存在清规戒律，每个人都可以构造自己 的逻辑，即他自己表达思想的语言形式，只要他愿意。但 如果他想讨论这种逻辑，那么，对他的唯一要求是他必须 说清楚他的方法，即给出语法和语义规则，而不是给出哲 学论据。Carnap（卡尔纳普）第五章 布尔代数基础本章主要介绍布尔代数的基本知识，它可以为学生今 后学习计算机逻辑代数，数字逻辑，计算机组成原理，二 进制运算，以及数理逻辑提供一个基础。 5.1 集合

2、的基本概念与基本运算由事物或对象组成的集体，无论它们是由其成员通过 枚举方式直接表示出来的，还是由其成员所具有的某些本 质属性表示出来的，都称为集合。称两个集合是相等的，如果构成这两个集合的成员完 全相同。集合的成员也叫元素。一个集合A中元素的个数叫做集合A的基数，记为A 。 请注意，这不是基数的严格的定义。对有穷集合，这样定义基数勉强可行，但对无穷集合不恰当。有关集合基数的 概念和知识将来读者会在离散数学或集合论等课程中系统 地学习，目前，我们暂且使用这种不严格的直观上的定义 。5.1.1 从属与包含关系通常用大写英文字母作为集合的名称。若某事物a是集 合A的一个元素，则记为 aA 并说“a

3、属于A”，或者说“a在A中”。若a不是集合A的元素，则记为 aA当以枚举形式表示一个集合时，我们用一个大括号把 这些枚举的元素括起来以表示这个集合。例1 麻雀，黄鹂，杜鹃，白鹭，红嘴鸥是一个由五 种鸟组成的集合；a,b,c,d,x,y,z是由英语的26个小写字母组成的集合。例2 Axax2+bx+c0 且 a,b,cR，R是实数集。例3 Ba,b,aa,ab,bb,aaa,aab,abb,bbb,aaaa,这种带省略的表示形式实际上可表示一些集合元素有某 种出现规律的无穷集合。集合的表示应当注意以下两点：(1) 同一个集合中的元素是互不相同的。(2) 集合中的元素之间不规定次序。与空集合相对应

4、的一个大的集合是所谓的全集合，即一 切事物构成的集合。这是一个虚构的集合，但它在布尔代数 的运算中是有用的。我们用1来表示这个虚设的全集合。考虑两个集合A和B。若集合A的每一个元素也是集合B的 一个元素，则称集合B包含集合A，也称集合A包含在集合B中 ，记为AB若AB，则称A是B的子集合，B是A的母集合。显然，对 任何集合A，有AA。若集合A、B之间存在AB且AB，则称A是B的真子集合，记为AB。若AB，又有BA，则可 以得出结论AB。这是因为A的元素都是B的元素，而B的元 素也是A的元素，说明A，B中拥有相同的元素，所以A和B相 同，故相等。显然，对任何集合A，A1。特别地，1。5.1.2

5、集合的基本运算和基本关系1. 集合的交与并设A、B是两个集合，定义A和B的公共元素构成的集合C 为A和B的交集，简称A和B的交，记为CAB；将集合A的 元素和集合B的元素合并在一起，组成一个新的集合C，那 么，这样得到的集合C就定义为集合A和集合B的并集，简称 A和B的并，记为CAB。如果从全集合1中取出部分元素构成集合A，剩下的元素构成 集合B，那么，集合A与集合B就形成互补关系。我们称集合B 为集合A的补集合，记为AB。显然，也有BA。而且此时下列定理1的一系列等式成立。定理1 设A为一个集合，B为A的补集合，则(1) AB，(2) AB1，(3) 1，(4) 1，(5) (A)A，(6)

6、 (1)1，(7) ()。 我们选择证明其中的(1)，其余的证明留给读者作为练习。今后，我们也采用这种方式，将一部分证明工作留给读者 。证明 (1) 用反证法。设AB，则必存在非空元素 xAB，故xA且xB，此与B为A的补集合矛盾。所以，AB。 例4 设Aa,b,c,d，Bc,d,e,f，Ce,f,g,h ，则 ABc,d，ABa,b,c,d,e,f，AC，ACa,b,c,d,e,f,g,h。根据定义，不难证明定理2。定理2 对任意集合A和集合B，有(1) ABBA， （交换律）(2) ABBA， （交换律）(3) AAA，(4) AAA， （幂等律）(5) AA，(6) AA1，(7) A，

7、(8) AA。我们选择证明其中的(2)，其余的(1)、(3)-(8)大家可 以自己试着去证明。证明 (2) 我们分两部分来证明。首先证明左边的集合 是右边集合的子集合，然后再证明右边的集合是左边集合的 子集合。这样，若两个集合互为子集合时，必然相等。 设任意元素xAB，则xA或者xB，也可表述为 xB或者xA，故ABBA； 同理可证，BAAB。所以，ABBA。 定理2(2)的上述证明方法是证明两个集合相等时最常用 的方法，也是最基本的方法。2. 集合上的一些基本关系下面我们在集合相补、包含、交与并的基础上，首先来 建立一些基本关系。定理3 设A，B为任意集合，则(1) ABA，(2) ABB，

8、(3) AAB，(4) BAB。我们选择证明其中的(1)，其余的(2)-(4)大家可以自己 试着去证明。证明 (1) 设任意元素xAB，由交的定义知，xA ，故ABA。 定理4 设A、B为任意集合，则(1) AB，当且仅当ABA，(2) ABA，当且仅当ABB，(3) ABB，当且仅当AB。这个定理说明了一个循环等价关系。象这样的等价关系 ，今后可用来作等价的概念定义。证明 (1) 我们分两部分来证明定理的充分性。 设任意元素xAB，故xA且xB，可得ABA ； 又设任意元素xA，由AB知xB，故xAB，可 得AAB。综合、，知ABA。由ABA导出AB是显然的。 上面的证明中，仍然采用了论证两

9、个集合相等最基本的方 法，即设法先证明等式两边的集合互为子集合。若两个集 合互为子集合，那么，显然这两个集合是相等的。证明一个定理，有时候需要从定义出发推导、论证， 有时候需要引用已知的结论来简化证明步骤。事实上，定 理4(1)的证明中第一部分可以直接引用定理3的(1)。今后 我们应该逐步习惯于简化的证明方式。定理5（De Morgan 律） 设A、B为任意集合，则(1) (AB)AB，(2) (AB)AB。证明 我们只要证明其中的一个就可以了，因为这两 个式子中的任何一个是另一个在相补关系下的直接结果。 下面，我们证明(1)。设任意元素x(AB)，则x(AB)，因此x A或xB。换言之xA或

10、xB，故xAB。所以， (AB)AB；反之，设任意元素xAB，则xA或xB。 换言之xA或xB，因此x(AB)，故x(AB)。所以， AB(AB)。从而，可知(AB)AB。 定理6 对任意的集合A，A。证明 使用反证法。假设定理不成立，即存在集合A， 使得A不成立。这就是说，存在元素x,但xA，这与 是空集合相矛盾。故定理成立，空集合是一切集合的子集 合。 定理7 空集合是唯一的。证明 设1和2都是空集合，由定理6知11 且 21， 所以12。 3. 集合上的一些运算定律 与中学数学中加法和乘法的结合律、分配律一样，集合的 运算除了满足我们已经看到的幂等律、交换律之外，也满足结合律和分配律。采

11、用类似于定理5的证明方法，容易证 明定理8。定理8 设A、B、C是任意的集合，则(1) A(BC)(AB)C， （结合律）(2) A(BC)(AB)C， （结合律）(3) A(BC)(AB)(AC)， （分配律）(4) A(BC)(AB)(AC)。 （分配律）证明 (3) 设xA(BC)，则xA或xBC。若是 前一种情况，那么xAB且xAC，因而 x(AB)(AC)；若是后一种情况，那么xB且xC， 因此xAB且xAC，也有x(AB)(AC)。这就证明了 A(BC)(AB)(AC)； 反之，设x(AB)(AC)，则xAB且xAC。若xA，那么xA(BC)；若xA，那么必有xB且xC ， 因此x

12、BC，也有xA(BC)。这就证明了(AB)(AC)A(BC)； 所以，A(BC)(AB)(AC)。 4. 集合上的其它一些关系 利用集合上的基本关系和基本运算，可以导出集合上 的其它一些关系。定理9 设A、B、C是任意的集合，那么下列关系成立 ：(1) 若AB且AC，则ABC；(2) 若AC且BC，则ABC。定理10 设A、B、C是任意的集合，若AB，则(1) ACBC，(2) ACBC。由定理3和定理10易证定理11。定理11 设A，B是任意的集合，则有A(AB)A。证明 依定理3有A(AB)A。又AAA，AAB ，因此，由定理10知AAA(AB)，故AA(AB)。 所以，A(AB)A。 定

13、理12 设A、B是任意的集合，则AB，当且仅当 AB。定理13 设A是一个集合，那么下列等式成立：(1) 若对任意的集合B，都有AB，则A；(2) 若对任意的集合B，都有BA，则A1。证明 (1) 由题设，特别当B时，有A，但A，所以A。 定理14 设A、B是两个集合，那么下列等式成立：(1) 若AB，则A且B；(2) 若AB1，则A1且B1。证明 (1) 因AAB，故A；同理可证，B。 5. 集合的差与对称差(同学们在中学已经学习)除了上面介绍的一些运算之外，还有两种重要的集合 运算是大家需要掌握的，它们是集合的差与对称差。定义1 集合A，B的差AB定义为一切属于A但不属于B 的元素构成的集

14、合，即ABAB。对任意集合A，B，不难证明定理15。定理15 设A，B，C都是集合，那么下列等式成立：(1) 1AA；(2) AB，当且仅当AB；(3) (AB)BAB；(4) C(AB)(CA)(CB)。 （分配律）交关于差是可分配的。但是，并关于差却不是可分配 的。大家可以通过思考和举一反例来认识这一点。定义2 集合A，B的对称差AB定义为A与B之差和B与A 之差的并，即AB(AB)(BA)。显然，A与B的对称差也可以写成如下的定义形式：AB(AB)(BA)。由定义2，我们还可以得到对称差的其它几种表示形式 或等价定义。定理16 若A，B是两个集合，则(1) AB(AB)(AB)，(2) AB(AB)(AB)，(3) ABAB。作为一种运算，对称差满足一些定律。定理17 设A，B，C都是集合，那么下列等式成立：(1) ABBA； （交换律）(2) (AB)CA(BC)； （结合律）(3) A(BC)(AB)(AC)； （分配律）(4) A(BC)(AB)(AC)。 （并关于对称差不满足分配律）证明 (3) A(BC)A(BC)(CB)(A(BC)(A(CB)(AB)(AC)(AC)(AB)(AB)(AC)。 定理18 设A，B是两个集合，那么下列等式成立：(1) AA