布尔代数

nullnull第五章 布尔代数基础 逻辑与代数是计算机科学最重要的基础，布尔代数是数理逻辑早期的雏形，是一种用代数演算的方法来研究思维结构的逻辑系统，同时也为计算机的运算提供重要基础。 null 问：什么是逻辑呢？ 对逻辑来说不存在清规戒律，每个人都可以构造自己的逻辑，即他自己达思想的语言形式，只要他愿意。但如果他想讨论这种逻辑，那么，对他的唯一要求是他必须说清楚他的方法，即给出语法和语义规则，而不是给出哲学论据。 Carnap（卡尔纳普） null 第五章 布尔代数基础 本章主要介绍布尔代数的基本知识，它可以为学生今后学习计算机逻辑代数，数字逻辑，计算机组成原理，二进制运算，以及数理逻辑提供一个基础。 5.1 集合的基本概念与基本运算 由事物或对象组成的集体，无论它们是由其成员通过枚举方式直接表示出来的，还是由其成员所具有的某些本质属性表示出来的，都称为集合。 称两个集合是相等的，如果构成这两个集合的成员完全相同。集合的成员也叫元素。 一个集合A中元素的个数叫做集合A的基数，记为│A│。 请注意，这不是基数的严格的定义。对有穷集合，这样定null义基数勉强可行，但对无穷集合不恰当。有关集合基数的概念和知识将来读者会在离散数学或集合论等课程中系统地学习，目前，我们暂且使用这种不严格的直观上的定义。 5.1.1 从属与包含关系 通常用大写英文字母作为集合的名称。若某事物a是集合A的一个元素，则记为 a∈A 并说“a属于A”，或者说“a在A中”。 若a不是集合A的元素，则记为 aA 当以枚举形式表示一个集合时，我们用一个大括号把这些枚举的元素括起来以表示这个集合。 例1 {麻雀，黄鹂，杜鹃，白鹭，红嘴鸥}是一个由五种鸟组成的集合；null{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中，记为nullA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。null如果从全集合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)，其余的证明留给读者作为练习。null今后，我们也采用这种方式，将一部分证明工作留给读者。 证明 (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， （交换律）null (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。null 所以，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)大家可以自己试着去证明。null 证明 (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是显然的。 □null上面的证明中，仍然采用了论证两个集合相等最基本的方法，即设法先证明等式两边的集合互为子集合。若两个集合互为子集合，那么，显然这两个集合是相等的。 证明一个定理，有时候需要从定义出发推导、论证，有时候需要引用已知的结论来简化证明步骤。事实上，定理4(1)的证明中第一部分可以直接引用定理3的(1)。今后我们应该逐步习惯于简化的证明方式。 定理5（De Morgan 律） 设A、B为任意集合，则 (1) (A∩B)’＝A’∪B’， (2) (A∪B)’＝A’∩B’。 证明 我们只要证明其中的一个就可以了，因为这两个式子中的任何一个是另一个在相补关系下的直接结果。下面，我们证明(1)。 设任意元素x∈(A∩B)’，则x(A∩B)，因此x A或nullx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。 □null 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)。这就证null明了 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。null 定理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，null所以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’；null (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)，null (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)。 □null 定理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。null 6. 幂集合及其性质 前面已经讨论了集合的一些最基本的内容。众所周知，我们到现在为止所讨论的集合的元素都是以现实世界中的个 体作为参照对象的。如果考虑构成集合的元素不必是现实世界中某一类事物中的个体，而允许它是一个集合，那么，就可以研究由集合作为元素构成的集合，这样就产生了幂集合的概念。 定义4 设A为一个集合，称由A的全体子集合构成的集合为A的幂集合，记为P(A)，即 P(A)＝{x│xA } 由定义可知，P()＝{}， P({})＝{，{}}。 如果将幂集合的定义看作是由一个集合到另一个集合的幂集运算，那么集合的幂集运算就具有下列性质：null 定理20 设A、B是任意两个集合，则 (1) AB 当且仅当P(A)P(B)； (2) P(A∩B)＝P(A)∩P(B)； (3) P(A)∪P(B)P(A∪B)； (4) P(A－B)(P(A)－P(B))∪{}。 对任意一个有穷集合A，P(A)的元素个数即它的基数是多少呢？利用大家中学时学过的数学知识，不难证明，│P(A)│＝2│A│ 。 下面我们进入下一节。 null5.2 自对偶的公理系统 5.2.1. 布尔代数公理系统 在上一节中，我们学习了集合代数的一些知识。细心的 读者可能已经发现，按照前面章节中关于布尔代数的简单介绍，好象集合代数与布尔代数之间不是一回事。于是，产生疑问：为什么要引入集合代数？ 1. 布尔代数系统的公理 人们在社会生活中，不仅需要计算，也需要推理，需要在许多情况下根据自己已有的知识对许多事情作出判断和推断，这就产生了逻辑。 古典逻辑是采用自然语言建立概念、断言和推理系统。随着人们对自然现象和社会事物的认识不断深化，用自然语言来描述事物有时就显得既不严格，也不方便，甚至难以理解。哲学中逻辑的发展急需要一种类似于象数学那样的强有力的工具。布尔为了使逻辑中的推理能象数学计算一样地进null行，将代数符号引入逻辑系统，用符号来表示由自然语言描述的各种抽象的断言及其结构，通过对符号的代数演算来反映用自然语言描述推理的过程及其所作的断言。根据这一思 想，布尔建立了一个二值运算的代数系统，可以将人类的一类思维推理方式和过程先从自然语言的表述转化为抽象的数学计算，然后把计算的结果通过解释的方法返回到非形式化的定义和描述中去。这样一来，逻辑推理就有可能化为一种数学计算，优点是显而易见的。 为了叙述布尔代数系统，我们先引入类的概念。 我们讨论的所有对象和事物的全体构成论域，也叫类。不太严格地讲，可以将类看作1，即全集合。布尔代数是将1看成由所有命题构成的一个特殊的类。 所谓命题，是指其含义确定，取值为“真”或“假”值的断言。命题不是真的，就是假的。命题的真、假值统称命题的真值。null 布尔将其建立的这个代数系统描述成一个公理系统，它一共有十条公理，具体如下： 设κ代表类，表示集合的包含关系符号，那么，系统 的公理为： Ⅰ. 如果Aκ且Bκ，则A∩Bκ； Ⅱ. 如果Aκ且Bκ，则A∪Bκ； Ⅲ. 存在ω，ωκ，使得对任意的A，如果Aκ，则A∩ω＝A； Ⅳ. 存在，κ，使得对任意的A，如果Aκ，则A∪＝A； Ⅴ. A∩B＝B∩A，Aκ，Bκ； Ⅵ. A∪B＝B∪A，Aκ，Bκ； Ⅶ. A∩(B∪C)＝(A∩B)∪(A∩C)，Aκ，Bκ；null Ⅷ. A∪(B∩C)＝(A∪B)∩(A∪C)，Aκ，Bκ； Ⅸ. 对任意的A，存在一个A'，使得A∪A'＝κ，A∩A'＝； Ⅹ. 在类κ中至少存在两个不同的元素。 有了公理，我们只要再给出一些从已知的命题出发得到另一个命题的推理规则，就能从布尔代数的公理出发，推导我们需要的命题。注意，这些推理规则有语法推理规则和语义推理规则之分。采用语法推理规则，推导只是形式上的，只关心从怎样的一些已知的形式上的命题（形式前提）推出一些以前未知的形式上的命题（形式结论），而不考虑这些已知的形式上的命题具体是一些什么样的命题，也不考虑它们和推导出的形式上的命题之间在逻辑真值方面是否一致。采用语义的推理规则，推导将是语义上的，必须考虑这些已知的命题为真时与推导出的命题的真值之间在逻辑上是否一致，因为我们不能设想前提为假的条件下推出的结论是可靠的，能够令人信服。由于人类在进行推导时，总是在前提为null真的条件下试图去推出一个命题成立或不成立，因此，我们自然希望语法推理规则与语义推理规则之间保持一致。这就涉及到布尔代数公理系统的系统特征，更具体地说涉及到一 个公理系统的推理的可靠性和完备性。这里所谓的可靠性是指凡形式上的推理所反映的前提与结论之间的关系，在语义上的逻辑推理中都是成立的，形式推理可靠地反映了语义上的逻辑推理；所谓完备性是说凡在语义上的逻辑推理中成立的前提与结论之间的关系，形式上的推理也都能反映，即形式推理在反映语义上的逻辑推理时无一遗漏。 由于读者的基础知识和本是面向一年级大学生的原因，我们暂时还不能深入地介绍数理逻辑的知识，如形式推理与逻辑推理之间的关系。关于这方面更深入的内容，一年级的大学生学习时可能有困难，不过没有关系，待读者系统地学习了数理逻辑课程后，将会接触到这方面的内容，获得深入而又完整的理解。目前，没有必要作深入的探讨。null 当我们注意到在集合代数中任意一个集合A与A’互为补集合，的补集合为1，1的补集合为时，如果我们将这里的每一个集合看成是一个命题，该集合的补集合看成是这个 命题的否命题，特别，1表示一种无论什么情况下都为“真”的恒真命题（也叫永真命题），表示一种无论什么情况下都为“假”的恒假命题（也叫永假命题）的话，那么，集合代数就可以看成是一种建立在命题表示基础之上的代数演算系统，所有命题只取“真”、“假”两个值的逻辑代数。一旦真值的“真”用1表示，“假”用0代表，那么，永真命题和永假命题既可以以其命题符号1参加运算，也可以以其值1参加运算，对永假命题也一样，两者在形式上完全一致。此外，对其它任意命题，它既可以取值为“真”，也可以取值为“假”。一个命题A，如果它取值为“真”，那么它的否命题A’就取值为“假”。 下面，我们采用公理系统演算的方法，将与上一节对应的逻辑代数的一些性质和关系推导出来。剩下的一些性质和null关系，读者不妨自己动手练习一下，试着证明。 2. 代数系统的形式演算 事实上，对于大多数的逻辑代数的性质和关系都可以从 上面给出的公理I-Ⅸ出发推导出来。为了今后使用方便，我们按照上面关于命题取值的说明，先将这几条公理改写成如下形式。 [1] A∩1＝A； [2] A∪0＝A； [3] A∩B＝B∩A； [4] A∪B＝B∪A； [5] A∩(B∪C)＝(A∩B)∪(A∩C)； [6] A∪(B∩C)＝(A∪B)∩(A∪C)； [7] A∩A’＝0； [8] A∪A’＝1；null其中，1表示永真命题，0表示永假命题。 另外，我们需要对“＝”作假定，它满足自反性、对称性和传递性，即满足： (1) 对任意A，A＝A（自反性）； (2) 若A＝B，则B＝A（对称性）； (3) 若A＝B，B＝C，则A＝C（传递性）。 由于只考虑“真”、“假”两个值，所以，如果A＝B，则A’＝B’。这就是说，如果两个命题的值相等，它们否命题的值也相等。 定理21 0和1都是唯一的。任意A，A的补（否命题）A’也是唯一的。 证明 用反证法。设若不然，01和02是两个不同的0，则null 01＝01∪02 （根据[2]） ＝02 （根据[2]，[4]） □ 矛盾。这就证明了01＝02，0是唯一的。 同理，可证1是唯一的，对任意A，A’也是唯一的。 □ 定理22 设A为一个命题，A’为A的补，则A’’＝A。 证明 因为A∩A’＝0，A∪A’＝1（根据[7]，[8]），这说明A是A’的补，但补是唯一的，所以A’’＝A。 □ 定理23 对任意的A和B，有 (1) A∩A＝A， （幂等律） (2) A∪A＝A， （幂等律） (3) A∩0＝0， (4) A∪1＝1。null 证明 (4) 因为 A∪1＝(A∪1)∩1 （根据[1]） ＝1∩(A∪1) （根据[3]） ＝(A∪A’)∩(A∪1) （根据[8]） ＝A∪(A’∩1) （根据[6]） ＝(A∪A’) （根据[1]） ＝1， （根据[8]） 所以，A∪1＝1。 □ 从上面三个定理可以看出，我们在推导中隐含地使用了几条推导规则，它们是 (1) 等式的传递推导。如果已知A＝B，B＝C，那么，就可以推出A＝C； (2) 反证法。如果假定一个命题不成立，由此可以得出矛盾的结论，那么，原命题得证；null (3) 代换推导。如果一个命题A中的某一命题B（也可以就是这个命题本身），用与它相等的命题C代换之后（即用C代换A中的一个或多个的B）得到命题D，那么，A＝D。 这些推导规则也可以用形式化的方式来表示，不过暂时无此必要。至于其它的推导规则，读者可以从今后的定理证明过程中自己试着去总结。需要指出的是，读者如果感到从定理证明过程中总结推导规则有困难时，完全不必担忧，因为大家今后在数理逻辑课程中将会系统地学习这方面的知识。作者所以这样写教材，是希望大家在今后的学习中，特别是在数学基础课程的学习中，努力去掌握读书、思考、体会、探索的读书方式和方法。 思考：什么样的应该和可以作为公理，什么样的规则应该成为推理规则？两者之间有关系吗？null 定理24 对任意的A和B，有 (1) A∩(A∪B)＝A，（吸收律） (2) A∪(A∩B)＝A。（吸收律） 证明 (1) 我们从等式左边出发，推导出右边。 A∩(A∪B)＝(A∪0)∩(A∪B) （根据[2]） ＝A∪(0∩B) （根据[6]） ＝A∪0 （定理23(3)） ＝A。 □ 定理25 若对任意的A、B和C，有A∩B＝A∩C，A∪B＝A∪C，则B＝C。 证明 因为 B＝B∩(B∪A) （由定理24(1)） ＝B∩(C∪A) （由题设） ＝(B∩C)∪(B∩A) （根据[5]） ＝(B∩C)∪(C∩A) （由题设）null ＝C∩(A∪B) （根据[5]） ＝C∩(A∪C) （由题设） ＝C， （定理24(1)） 所以，B＝C。 □ 定理26 若对任意的A、B和C，有A∪B＝A∪C，A’∪B＝A’∪C，则B＝C。 证明 因为 (A∪B)∩(A’∪B)＝B∪(A∩A’) （根据[6]） ＝B∪0 （根据[7]） ＝B； （根据[2]） 又 (A∪B)∩(A’∪B)＝(A∪C)∩(A’∪C) （由题设） ＝C∪(A∩A’) （根据[6]） ＝C∪0 （根据[7]） ＝C， （根据[2]） 所以，B＝C。 □null 定理27 若对任意的A、B和C，有A∩B＝A∩C，A’∩B＝A’∩C，则B＝C。 证明留给读者。 下面我们来给出并证明结合律，同时，请读者自己补上每一步推理的依据。 定理28 对任意的A、B和C，有 (1) A∩(B∩C)＝(A∩B)∩C， (2) A∪(B∪C)＝(A∪B)∪C。 证明 (2) 设L＝A∪(B∪C)，M＝(A∪B)∪C，那么 A∩L＝A∩(A∪(B∪C)) ＝A， 且 A∩M＝A∩((A∪B)∪C) ＝(A∩(A∪B))∪(A∩C) ＝A∪(A∩C) ＝A，null故 A∩L＝A∩M； 又 A’∩L＝A’∩(A∪(B∪C)) ＝(A’∩A)∪(A’∩(B∪C)) ＝0∪(A’∩(B∪C)) ＝(A’∩(B∪C)) ＝(A’∩B)∪(A’∩C)， 且 A’∩M＝A’∩((A∪B)∪C) ＝(A’∩(A∪B))∪(A’∩C) ＝((A’∩A)∪(A’∩B))∪(A’∩C) ＝(0∪(A’∩B))∪(A’∩C) ＝(A’∩B)∪(A’∩C)， 故 A’∩L＝A’∩M＝A。null于是，由定理27，可得L＝M。这就证明了并的结合律。 □ 定理29 若对任意的A和B，有A∩B＝A∪B，则A＝B。 证明 因为 A＝A∩(A∪B) （定理24(1)） ＝A∩(A∩B) （由题设） ＝(A∩A)∩B （结合律） ＝A∩B （定理23(1)） ＝A∩(B∩B) （定理23(1)） ＝(A∩B)∩B （结合律） ＝(A∪B)∩B （由题设） ＝B， （[3]，定理24(1)） 所以，A＝B。 □ 下面证明德·摩根（De Morgan）律，也请读者自己补上每一步推理的依据。null 定理30（De Morgan 律） 设有任意的A、B，则 (1) (A∩B)’＝A’∪B’， (2) (A∪B)’＝A’∩B’。 证明 (1) 因为 (A∩B)∩(A’∪B’)＝(A∩B∩A’)∪(A∩B∩B’) ＝((A∩A’)∩B)∪(A∩(B∩B’)) ＝(0∩B)∪(A∩0) ＝0∪0 ＝0； 而 (A∩B)∪(A’∪B’)＝(A∪A’∪B’)∩(B∪A’∪B’) ＝((A∪A’)∪B’)∩((B∪B’)∪A’) ＝(1∪B’)∩(A’∪1) ＝1∩1 ＝1；null由定理21和定理22知，A’∪B’是A∩B的补，故(1)成立。 □ 在上一节定理4 的证明中，曾经证明了如下三个循环等 价关系，并提到这些关系可用来进一步定义概念。现在，我们就来叙述这些关系的应用。 (1) AB，当且仅当A∩B＝A， (2) A∩B＝A，当且仅当A∪B＝B， (3) A∪B＝B，当且仅当AB。 细心的读者可能已经注意到，[1]-[8]并没有与“”有关的公理，那么，上一节中与“”有关的定理怎么在公理系统中推导出来呢？ 注意，到循环等价关系(1)-(3)中，AB 分别等价于A∩B＝A 和 A∪B＝B，因此，只要任取其一就可以引入AB的定义，另一个可以推导出来。这样，实际上也就引入了符号“”，从而，上一节中与“”有关的定理也可望在公理系null统中获得证明。 下面，我们引入“”关系，并导出有关的定理。推导的依据，全部留给读者。 定义5 设有任意的A、B，定义AB（读作A包含于B中，或B包含A）为A∩B＝A。 定理31 设有任意的A、B，若AB，则A∩B＝A，当且仅当A∪B＝B。 证明 由题设A＝A∩B即AB，知 A∪B＝(A∩B)∪B ＝(A∪B)∩(B∪B) ＝(A∪B)∩B ＝B； 反过来，设A∪B＝B，也有 A∩B＝A∩(A∪B) ＝(A∩A)∪(A∩B)null ＝A∪(A∩B) ＝A。 □ 推论1 对任意的A，0A，A1。 定理32 设有任意的A、B、C，若AB且BC，则AC。 证明 依定义5，我们只要证明：若A＝A∩B且B＝B∩C，则A＝A∩C即可。由题设，因为 A∩C＝(A∩B)∩C ＝A∩(B∩C) ＝A∩B ＝A 所以，A＝A∩C。 □ 定理33 设有任意的A、B，则 (1) AB，当且仅当A∩B’＝0； (2) AB，当且仅当A’∪B＝1。 证明 (1) 由题设AB，知A＝A∩B。因为null A∩B’＝(A∩B)∩B’ ＝A∩(B∩B’) ＝A∩0 ＝0； 反过来，如果A∩B’＝0，则 A＝A∩1 ＝A∩(B∪B’) ＝(A∩B)∪(A∩B’) ＝(A∩B)∪0 ＝A∩B， 此即AB。 □ 定理34 对任意的A、B，有 (1) A∩BA， (2) AA∪B。 证明 (1) 因为null (A∩B)∩A＝(A∩A)∩B ＝A∩B， 所以，由定义5，A∩BA。 □ 定理35 对任意的A、B，若AB且BA，则A＝B。 证明 由题设AB且BA，据定义5和交换律立即可得 A＝A∩B ＝B∩A ＝B。 □ 定理36 对任意的A、B，若AB且AC，则AB∩C。 证明 因为 A∩(B∩C)＝(A∩B)∩C ＝A∩C ＝A， 所以，AB∩C。 □ 下面，我们仿照上一节集合的差和对称差的概念引入差null和对称差的概念，然后继续给出若干定理。至于定理的证明，则留给读者作为练习。 定义6 设有任意的A、B，定义差A－B（读作A与B的差） 为A∩B’。 定理37 对任意的A、B，若AC且BC，则A∪BC。 定理38 对任意的A、B、C，若AB，则A∩CB∩C 且 A∪CB∪C。 定理39 设有任意的A，则 (1) 若对任意的B，都有BA，则A＝1； (2) 若对任意的B，都有AB，则A＝0。 定理40 对任意的A、B、C，下列关系成立： (1) A＝1－A’； (2) A－B＝0，当且仅当AB； (3) (A－B)∪B＝A∪B； (4) 若A∩B＝0，则A－B＝A；null (5) C∩(A－B)＝(C∩A)－(C∩B)。 定义7 设有任意的A、B，定义对称差AB（读作A与B的对称差）为(A－B)∪(B－A)。 定理41 对任意的A、B、C，下列关系成立： (1) AB＝(A∪B)∩(A’∪B’)， (2) AB＝BA， (3) (AB)C＝A(BC)， (4) AB＝(A∪B)－(A∩B)， (5) AB＝A’B’， (6) A∩(BC)＝(A∩B)(A∩C)， （分配律） (7) A∪(BC)≠(A∪B)(A∪C)， （并关于对称差不满足分配律） (8) AA＝0， (9) 若AB＝0，则A＝B。 定义8 设有任意的A、B，定义AB的补A×B（读作A与nullB的叉，）为(A∩B)∪(A’∩B’)。 定理42 对任意的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。 null5.2.2* 标准形式和公理系统的完备性 标准形式 由命题A，B，C，…有限次使用∩、∪、’、－、、×等 所构成的任何式子，都可以简化为下列标准形式： S1∩S2∩S3∩…∩Sn-1∩Sn， 其中，每个Si(1≤i≤n)是一些不再含有∩、∪、’、－、、×的命题或否命题有限次使用∪而成，或者简化为第二标准形式： T1∪T2∪T3∪…∪Tn-1∪Tn， 其中，每个Ti(1≤i≤n)是一些不再含有∩、∪、’、－、、×的命题或否命题有限次使用∩而成。 利用下列等式进行替换，确实能够实现化为标准形式的目标。null (1) A＝(A’)’； (2) (A∩B)’＝(A’∪B’)； (3) (A∪B)’＝(A’∩B’)； (4) A∩B＝B∩A； (5) A∪B＝B∪A； (6) A∩(B∪C)＝(A∩B)∪(A∩C)； (7) A∪(B∩C)＝(A∪B)∩(A∪C)； (8) A∩(B∩C)＝(A∩B)∩C； (9) A∪(B∪C)＝(A∪B)∪C。 事实上，前面所有定理中的关系或等式，均可用于化简。将一个式子化简在实际工作中有着重要的应用。例如，许多数字逻辑系统的，从对系统功能最直观的认识和思想出发，常常能够很快设计出正确的逻辑电路。然而，正确的逻辑电路不一定是最简单的逻辑电路。为了简化电路，降低生null产成本，提高器件运算速度，就需要运用布尔代数的一些关系进行化简。这在表面上看起来好象是一个逻辑电路的问题，而实质上是一个布尔代数中的数学问题。 完备性问题 上面给出的各项定理，都是采用形式推导的方式给出的，我们并没有去关心定理中的那些命题都代表一些什么样的命题，更没有考察它们是“真”是“假”，或有时候为“真”，有时候为“假”，以及前提“真”时，结论是否为“真”。所有这些推导都只是形式上的，即根据公理和推导规则，从这种形式可以推出那种形式。 但是，这样一种推导显然不能令人满意，因为我们所关心的是这样一些推导：当前提为“真”时，结论也为“真”。于是，需要对每一个命题作出解释。这种解释，并不是去关心每一个命题究竟表示一个什么样的具体命题，而只是考察该命题的真值。因为，一旦一个命题A被具体对应到一个实实在null在的命题，如“上海动物园内现生活着20只大熊猫”，那么，A的真值也就被确定了。 设f(A1,A2,…,An)表示任意一个由命题A1，A2，…，An通过 有限次使用’、∩、∪所构成的式子，则用f(A1,A2,…,Ai-1,0,Ai+1,…,An)表示以0代替f(A1,A2,…,An)的Ai而得到的式子。 定理43 任意式子f(A1,A2,…,An)都可以由A1，A2，…，An及其补，连同着仅仅包含0，1的式子而得到。 证明 我们首先证明 (Th) f(A)＝(A∪f(0))∩(A’∪f(1))。 设f(A)＝A，因为 A＝A∩1 ＝(A∪0)∩(A’∪1) ＝(A∪f(0))∩(A’∪f(1)) 所以，当f(A)为只包含一个命题的式子时，结论成立。而且，null当(Th)对f(A)成立时，对f’(A)即f(A)的补也成立，理由是 f’(A)＝(A’∩f’(0))∪(A∩f’(1)) ＝(A’∩1)∪(A∩0) ＝A’∪0 ＝0∪A’ ＝(A∪1)∩(A’∪0) ＝(A∪f’(0))∩(A’∪f’(1))。 其次，设f(A)满足f(A)＝(A∪f(0))∩(A’∪f(1))，g(A)满足g(A)＝(A∪g(0))∩(A’∪g(1))，即(Th)对f(A)，g(A)成立，则 (A∪f(0))∩(A’∪f(1))∩(A∪g(0))∩(A’∪g(1)) ＝(A∪f(0))∩(A∪g(0))∩(A’∪f(1))∩(A’∪g(1)) ＝(A∪(f(0)∩g(0)))∩(A’∪(f(1)∩g(1)))； 类似地，我们有null ((A∪f(0))∩(A’∪f(1)))∪((A∪g(0))∩(A’∪g(1))) ＝((A∪0)∩(A’∪1))∪((A∪0)∩(A’∪1)) ＝((A∪0)∪((A∪0)∩(A’∪1)))∩((A’∪1)∪((A∪0)∩ (A’∪1))) ＝((A∪0)∪(A∪0))∩((A∪0)∪(A’∪1))∩((A’∪1)∪ (A∪0))∩((A’∪1)∪(A’∪1)) ＝(A∪0∪0)∩(A∪0∪A’∪1)∩(A’∪1∪A∪0)∩(A’∪1) ＝(A∪0∪0)∩(A∪A’∪1)∩(A∪A’∪1)∩(A∪A’∪1) ＝(A∪0∪0)∩(A∪A’∪1) ＝(A∪0∪0)∩(A’∪1∪1) ＝(A∪f(0)∪g(0))∩(A’∪f(1)∪g(1))； 这就是说，(Th)对f(A)和g(A)的∩和∪都成立。因为每个式子都是由’、∩、∪构成的，所以(Th)对所有式子f(A)都成立。特别，当f(A)＝I，f(A)是一个不含A的式子时，(Th)对nullf(A)也成立。因为 (A∪I)∩(A’∪I)＝(A∩A’)∪I ＝I 现在，设f(A,A1,A2,…,An)是由A，A1，A2，…，An构成的式子，我们来证明 (Th*) f(A,A1,A2,…,An)＝(A∪f(0,A1,A2,…,An))∩ (A’∪f(1,A1,A2,…,An)) 以下分三种情形证明。 (1) f(A,A1,A2,…,An)中不包含A，令f(A,A1,A2,…,An)＝I 于是由 (A∪f(0,A1,A2,…,An))∩(A’∪f(1,A1,A2,…,An))＝I， 知(Th*)成立； (2) 设f(A,A1,A2,…,An)＝A∩g(A1,A2,…,An)， 因为 g(A1,A2,…,An)中不含A，所以由null f(A,A1,A2,…,An)＝(A∪f(0, A1,A2,…,An))∩ (A’∪f(1, A1,A2,…,An)) ＝(A∪(0∩g(A1,A2,…,An)))∩ (A’∪(1∩g(A1,A2,…,An))) ＝A∩(A’∪g(A1,A2,…,An) ＝(A∩A’)∪(A∩g(A1,A2,…,An)) ＝(A∩g(A1,A2,…,An))， 知(Th*)对f(A, A1,A2,…,An)＝A∩g(A1,A2,…,An)成立； (3) 设f(A, A1,A2,…,An)＝A∪g(A1,A2,…,An)， 因为g(A1,A2,…,An)中不含A，所以由 f(A, A1,A2,…,An)＝(A∪f(0, A1,A2,…,An))∩ (A’∪f(1, A1,A2,…,An)) ＝(A∪(0∪g(A1,A2,…,An)))∩ (A’∪(1∪g(A1,A2,…,An)))null ＝(A∪g(A1,A2,…,An))∩1 ＝(A∪g(A1,A2,…,An))， 知(Th*)对f(A, A1,A2,…,An)＝A∪g(A1,A2,…,An)成立。 综上所述，如果(Th*)对某些式子成立，则对于它们有限次的补、并、交构成的式子也成立。所以，(Th*)对一切由命题有限次使用’、∩、∪构成的式子都成立。 □ 根据定理41，我们已经知道，依照(Th*)，可以逐步将所有式子表成需要的形式。首先，对于f(A,B)，应用(Th)和(Th*)，有 f(A,B)＝(A∪f(0,B))∩(A’∪f(1,B))，但f(0,B)和f(1,B)是至多只含有B的式子，类似地有 f(0,B)＝(B∪f(0,0))∩(B’∪f(0,1))， f(1,B)＝(B∪f(1,0))∩(B’∪f(1,1))， 所以null f(A,B)＝(A∪B∪f(0,0))∩(A∪B’∪f(0,1))∩ (A’∪B∪f(1,0))∩(A’∪B’∪f(1,1))。 同理，对f(A,B,C)，有 f(A,B,C)＝(A∪B∪C∪f(0,0,0))∩(A∪B∪C’∪f(0,0,1)) ∩(A∪B’∪C∪f(0,1,0))∩(A∪B’∪C’∪f(0,1,1)) ∩(A’∪B∪C∪f(1,0,0))∩(A’∪B∪C’∪f(1,0,1)) ∩(A’∪B’∪C∪f(1,1,0))∩(A’∪B’∪C’∪f(1,1,1))， ……。 对上面的每个式子f(I1,I2,……,In)，当Ii＝0或1时， (1≤i≤n)，f(I1,I2,……,In)是等于0或1的。因此，对于 (Th) f(A)＝(A∪f(0))∩(A’∪f(1))， 如果取遍f(0)、f(1)所有可能的值的组合，就可得到所有只 含有A的不同的化简式子： (A∪0)∩(A’∪0)＝A∩A’＝0，null (A∪0)∩(A’∪1)＝A∩1＝A， (A∪1)∩(A’∪0)＝1∩A’＝A’， (A∪1)∩(A’∪1)＝1∩1＝1。 这就是说，每一个只含有A的式子，无论多么复杂，都可以简化为0，1，A，A’中的一个，它们相等。 同理，每个只含有A，B的式子与下列16个式子中的一个相等： (A∪B∪0)∩(A∪B’∪0)∩(A’∪B∪0)∩(A’∪B’∪0)＝0， (A∪B∪0)∩(A∪B’∪0)∩(A’∪B∪0)∩(A’∪B’∪1)＝ A∩B， (A∪B∪0)∩(A∪B’∪0)∩(A’∪B∪1)∩(A’∪B’∪0)＝ A－B， (A∪B∪0)∩(A∪B’∪0)∩(A’∪B∪1)∩(A’∪B’∪1)＝A， (A∪B∪0)∩(A∪B’∪1)∩(A’∪B∪0)∩(A’∪B’∪0)＝ B－A，null (A∪B∪0)∩(A∪B’∪1)∩(A’∪B∪0)∩(A’∪B’∪1)＝B， (A∪B∪0)∩(A∪B’∪1)∩(A’∪B∪1)∩(A’∪B’∪0)＝ A＋B， (A∪B∪0)∩(A∪B’∪1)∩(A’∪B∪1)∩(A’∪B’∪1)＝ A∪B， (A∪B∪1)∩(A∪B’∪0)∩(A’∪B∪0)∩(A’∪B’∪0)＝ A’∪B’， (A∪B∪1)∩(A∪B’∪0)∩(A’∪B∪0)∩(A’∪B’∪1)＝ (A＋B)’， (A∪B∪1)∩(A∪B’∪0)∩(A’∪B∪1)∩(A’∪B’∪0)＝B’， (A∪B∪1)∩(A∪B’∪0)∩(A’∪B∪1)∩(A’∪B’∪1)＝ A∪B’， (A∪B∪1)∩(A∪B’∪1)∩(A’∪B∪0)∩(A’∪B'∪0)＝A’， (A∪B∪1)∩(A∪B’∪1)∩(A’∪B∪0)∩(A’∪B’∪1)＝null A’∪B， (A∪B∪1)∩(A∪B’∪1)∩(A’∪B∪1)∩(A’∪B'