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

第五章 布尔代数基础 逻辑与代数是计算机科学最重要的基础，布尔代数是数理逻辑早期的雏形，是一种用代数演算的方法来研究思维结构的逻辑系统，同时也为计算机的运算提供重要基础。 ; 问题：什么是逻辑呢？ 对逻辑来说不存在清规戒律，每个人都可以构造自己的逻辑，即他自己表达思想的语言形式，只要他愿意。但如果他想讨论这种逻辑，那么，对他的唯一要求是他必须说清楚他的方法，即给出语法和语义规则，而不是给出哲学论据。 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个小写字母组成的集合。 例2 A＝{x│ax2+bx+c＝0 且 a,b,c∈R}，R是实数集。 例3 B＝{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}，