1、第五章 布尔代数基础逻辑与代数是计算机科学最重要的基础，布尔代数是数理逻辑早期的雏形，是一种用代数演算的方法来研究思维结构的逻辑系统，同时也为计算机的运算提供重要基础。问题：什么是逻辑呢？对逻辑来说不存在清规戒律，每个人都可以构造自己的逻辑，即他自己表达思想的语言形式，只要他愿意。但如果他想讨论这种逻辑，那么，对他的唯一要求是他必须说清楚他的方法，即给出语法和语义规则，而不是给出哲学论据。Carnap（ 卡尔纳普）第五章 布尔代数基础本章主要介绍布尔代数的基本知识，它可以为学生今后学习计算机逻辑代数，数字逻辑，计算机组成原理，二进制运算，以及数理逻辑提供一个基础。5.1 集合的基本概念与基本运
2、算由事物或对象组成的集体，无论它们是由其成员通过枚举方式直接表示出来的，还是由其成员所具有的某些本质属性表示出来的，都称为 集合 。称两个集合是相等的，如果构成这两个集合的成员完全相同。集合的成员也叫 元素 。一个集合 A中元素的个数叫做集合 A的 基数 ，记为 A。请 注意 ， 这不是基数的严格的定义。对有穷集合，这样定义基数勉强可行，但对无穷集合不恰当。有关集合基数的概念和知识将来读者会在离散数学或集合论等课程中系统地学习，目前，我们暂且使用这种不严格的直观上的定义。5.1.1 从属与包含关系通常用大写英文字母作为集合的名称。若某事物 a是集合 A的一个元素，则记为aA并说 “ a属于 A
3、” ， 或者说 “ a在 A中 ” 。若 a不是集合 A的元素，则记为aA当以枚举形式表示一个集合时，我们用一个大括号把这些枚举的元素括起来以表示这个集合。例 1 麻雀，黄鹂，杜鹃，白鹭，红嘴鸥 是一个由五种鸟组成的集合；a,b,c,d,x,y,z 是由英语的 26个小写字母组成的集合。例 2 A xax 2+bx+c 0 且 a,b,cR ， R是实数集。例 3 B a,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， 则可以得出结论 A B。 这是因为 A的元素都是 B的元素，而 B的元素也是 A的元素
5、，说明 A， B中拥有相同的元素，所以 A和 B相同，故相等。显然，对任何集合 A， A1。 特别地， 1。5.1.2 集合的基本运算和基本关系1. 集合的交与并设 A、 B是两个集合，定义 A和 B的公共元素构成的集合 C为 A和 B的交集，简称 A和 B的交，记为 C AB ； 将集合 A的元素和集合 B的元素合并在一起，组成一个新的集合 C， 那么，这样得到的集合 C就定义为集合 A和集合 B的并集，简称A和 B的并，记为 C AB 。如果从全集合 1中取出部分元素构成集合 A， 剩下的元素构成集合 B， 那么，集合 A与集合 B就形成互补关系。我们称集合 B为集合 A的补集合，记为 A
6、 B。 显然，也有 B A。 而且 此时下列定理 1的一系列等式成立。定理 1 设 A为一个集合， B为 A的补集合，则(1) AB ，(2) AB 1，(3) 1，(4) 1 ，(5) (A) A，(6) (1) 1，(7) () 。我们选择证明其中的 (1)，其余的证明留给读者作为练习。今后，我们也采用这种方式，将一部分证明工作留给读者。证明 (1) 用反证法。设 AB ， 则必存在非空元素xAB ， 故 xA 且 xB ， 此与 B为 A的补集合矛盾。所以，AB 。 例 4 设 A a,b,c,d， B c,d,e,f， C e,f,g,h， 则 AB c,d，AB a,b,c,d,e,
7、f，AC ，AC a,b,c,d,e,f,g,h。根据定义，不难证明定理 2。定理 2 对任意集合 A和集合 B， 有(1) AB BA ， （ 交换律）(2) AB BA ， （ 交换律）(3) AA A，(4) AA A， （ 幂等律）(5) AA ，(6) AA 1，(7) A ，(8) A A。我们选择证明其中的 (2)，其余的 (1)、 (3)-(8)大家可以自己试着去证明。证明 (2) 我们分两部分来证明。首先证明左边的集合是右边集合的子集合，然后再证明右边的集合是左边集合的子集合。这样，若两个集合互为子集合时，必然相等。 设任意元素 xAB ， 则 xA 或者 xB ， 也可表述为xB 或者 xA ， 故 AB BA ； 同理可证， BA AB 。所以， AB BA 。 定理 2(2)的上述证明方法是证明两个集合相等时最常用的方法，也是最基本的方法。2. 集合上的一些基本关系下面我们在集合相补、包含、交与并的基础上，首先来建立一些基本关系。定理 3 设 A， B为任意集合，则(1) AB A，(2) AB B，(3) AAB ，(4) BAB 。我们选择证明其中的 (1)，其余的 (2)-(4)大家可以自己试着去证明。
