布尔代数基础

1、第五章布尔代数基本逻辑和代数是计算机科学最重要的基础，布尔代数是数学逻辑的早期原型，是用代数美学研究思维结构的逻辑体系，为计算机运算提供了重要的基础。问题：什么是逻辑？逻辑中不存在清溪率。每个人都可以构成自己的逻辑，即自己表达思想的语言形式。只要他愿意。但如果他想讨论这样的逻辑，对他的唯一要求是他必须明确自己提出语法和语义规则的方法，而不是哲学论据。Carnap，第5章布尔代数的基本章节以布尔代数的基本知识为中心，为学生提供计算机逻辑代数、数字逻辑、计算机构造原理、二进制运算和数学逻辑的基础。5.1集合的基本概念和基本运算是由事物或对象组成的集合，无论该成员是以枚举方式直接表示，还是以成员具有

2、的某些必需属性表示。如果构成两个收藏的成员相同，则这两个收藏是相同的。集合的成员也称为元素。集合a中的元素数称为集合a的基数，用a表示。请注意，这不是基数的严格定义。有穷合这样定的话，意气用事只能勉强，但对无限集合不合适。集合基本的概念和知识以后读者将在离散数学和集合论等过程中系统地学习。现在我们暂时使用这个不严格的直观定义。5.1.1从属关系和包含关系通常使用大写字母作为集合的名称。如果a是a集中的元素，则将其记录为aA，称为“a属于a”或“a位于a”。如果a不是集合a的元素，请记住，当aA以枚举形式表示集合时，此枚举元素用大括号括住以表示。例1麻雀、林莺、杜鹃、白鹭、红嘴鸥是由5种鸟类组成

3、的集合体；a、b、c、d、x、y和z是英语的26个小写字母的集合。示例2ax2xc0和a、b、cR、r是实数集。示例3 ba、b、aa、ab、bb、AAA、aab、abb、BBA，这种省略的表示法实际上可以表示某些集合元素具有一定的无限集合。集合的表示法需要注意以下两个方面：(1)同一集合中的元素徐璐不同。(2)集合中的元素之间没有顺序。对应空元音的大元音是所谓的全集合集，即所有事物的集合。这是虚构的集合，但在布尔代数的运算中很有用。我们用1表示这个破全集。考虑两个集合a和b。如果集a中的每个元素都是集b中的元素，则集b称为包含集a。请记住，集a包含在集b中。如果是AB，则a是b的子集，b是a

4、的超集。显然，所有集合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集合的基本运算和基本关系1。集合的交集和设置a，b是由a和b的公共元素组成的集合c是a和b的交集，简单地是a和b的交集，CAB记录为。通过组合集合a中的元素和集合b中的元素来构建新集合c，结果集合c被定义为集合a和集合b的并集(简单地说，即a和b的并集)，并被记录为CAB。如果集a构成集a，其馀元素构成集b，则集a与

5、集b形成互补关系。我们把集合b称为集合a的补充集合，我记得是AB。很明显还有BA。此时，下一个定理1的一系列方程成立。清理1将A设置为一个集合，b设置为A的补充集合，则(1) AB，(2) AB1，(3) 1，(4) 1，(5) (A)A，(6) (1)1我们证明其中的(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按照定义，证明定理2并不难。清理2包含

6、(1) ABBA，(交换规则)(2) ABBA，(交换规则)，(3) AAA，(4) AAA，(幂等规则)(5) AA，我们决定证明其中的(2)，剩下的(1)，(3)-(8)。证明(2)我们分成两部分证明。首先证明左元音是右元音的子集，然后证明右元音是左元音的子集。如果这两个集合是徐璐子集合，则必须相同。XAB元素，xA或xB，xB或xA，因此为ABBA设置。同样可以证明，BAAB。所以，ABBA。定理2(2)的上述证明方法是证明两个元音相同时最常用的方法和最基本的方法。2.集合的一些基本关系下面是基于集合的补充、包含、交叉和求和建立一些基本关系。清理3设置a，b为任意集合(1) ABA，(2

7、) ABB，(3) AAB，(4) BAB。我们可以试图证明他们中的(1)，其馀的(2)-(4)。证明(1)设置所有元素xAB。相交的定义已知，xA，因此ABA。如果清理4将a，b设置为随机集合(1)，则ab仅用作ABB (2) ABb，abb (3) ABB和AB。这个定理说明了循环等价关系。这种平等的关系今后可以用于平等的概念定义。证明(1)我们分为两部分，证明定理的适当性。设置XAB、xA和xB元素。ABA中选择所需的构件。因为AB知道xB，所以xAB可以有AAB。集成，我知道ABA。从ABA导出AB很明显。在上述证明中，证明两个元音相同的最基本的方法是先证明等式两边的元音是徐璐子集。如

8、果两个集合是徐璐子集合，很明显这两个集合是相同的。要证明一个定理，有时需要从定义中推导，论证，有时需要引用已知的结论来简化证明步骤。实际上，在定理4(1)的证明中，第一部分可以直接引用定理3的(1)。今后我们必须逐渐熟悉简化的证明方法。清理5(De Morgan规则)将a，b设定为任意集合时，如果(1) (AB)AB，(2) (AB)AB。证明我们只需要证明其中一个。因为这两个公式都是商业界的另一个直接结果。接下来，我们证明(1)。如果设置了任何元素x(AB)，则它是x(AB)，因此它是x A或，xB。也就是xA或xB，因此xAB。所以，(ab)ab；相反，如果设置xAB元素，则为xA或xB。

9、因为是XA或xB，所以是x(AB)，所以是x(AB)。所以AB(AB)是。通过这种方式，您可以知道(AB)AB。定理6证明随机集a，a .反证法的使用。假设的定理不成立，即集合a存在，a不成立。也就是说，元素x存在，但xA与空集合矛盾。因此，已设定清理，空集合是所有集合的子集。清理7空集合是唯一的。证明1和2都是空集合，定理6是12，因为我们知道11和21。3 .集合上的一些运算法则在中学数学中与加法和乘法的和，分配法一样，集合运算除了我们已经看到的幂等定律，交换定律外，还充分地填充了求和和纠纷。使用类似于定理5的证明方法，可以很容易地确认定理8。如果清理8集A、b、C是任意集合，则(1) A

10、(BC)(AB)C，(连接规则)(2) A(BC)(AB)C，(连接规则)(3)(分配法)证明(3) xA或xBC(如果您已设置xA(BC)。在以前的情况下为xAB和xAC，因此x(ab)(AC)；在后一种情况下，xAB和xAC也有x(AB)(AC)，因为它是xB和xC。这显示a (BC) (ab) (AC)。相反，设置x(AB)(AC)将使用xAB和xAC。如果是XA，则为XA(BC)；对于XA，必须有xB和xC，因此也有xBC。这证明(ab) (AC) a (BC)。也就是A(BC)(AB)(AC)。4.集合中的其他关系可使用集合中的主关系和主运算来衍生集合中的其他关系。如果定理9将a、b

11、、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是AA(AB)，因为清理10知道AAA(AB)。所以，如果a (ab) a .定理12是a，b是任意集，那么只有当a，b是ab，AB时。如果定理13集a是一个集合，以下等式成立：(1)任意集b有AB的话，a；(2)任意集b有BA的话，A1。证明(1)由问题设定，特别是b有a，但a，因此有a。如

12、果定理14将a和b设置为两个集合，则以下等式成立：(1)如果是AB，则为a和b；(2)如果是AB1，则为A1和B1。证明(1)由于AAB，a；同样可以证明，B. 5。除了以上所述的几种计算外，集合的差异和对称差异(学生在中学学过)，两种重要的集合运算都是大家必须掌握的，集合的差异和对称差异。定义1集合a，b的车AB定义为包含属于a但不属于b的所有元素的集合，即ABAB。对于随机集a，b，证明定理15不难。定理15把a，b，c都集合起来，以下等式成立：(1)1aa；(2)如果是AB、AB；(3)(ab)Bab；(4) C(AB)(CA)(CB)。(分配法)差异是可分配的。但是不能对差异进行分配。

13、大家想了想，举个反例就知道这一点。定义集a 2，b的对称差AB定义为a和b的差、b和a的差以及ab (ba)。显然，a和b的对称差也可以用定义形式(例如ab (ba)记录。在定义2中，还可以获得对称差或等效定义的多个不同表达。清理16 a，b是两个集合：(1) 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(B

14、C)a(CB)(a(CB)(ab)(AC)(AC)(ab)(ab)(AC)，如果定理18集a，b是两组，则以下等式成立：(1) AA，(2)如果是AB，则为AB。将3组a、b定义为集合，将AB定义为a和b的叉，将它们定义为AB (ab) (ab)。和对称差的性质一样，容易的定理19。如果定理19岁的a，b，c都是集合体，那么以下等式成立：(1) abb，(2) ABBA，(交换规则)(3) (AB)CA(BC)，(接合规则)(4) AA1，(5) ababb，6 .在幂集及其性质之前，我们已经讨论了集合的一些最基本的内容。据悉，我们到目前为止讨论的收藏的要素都以现实世界的一个身体作为参考对象。

15、如果构成组件的元素不必是现实世界中任何种类事物中的对象，并允许它成为集合，那么通过研究集合由元素构成的集合，可以生成幂集合的概念。定义4是由A的整个子集组成的集合，称为A的幂集，被记录为P(A)。也就是说，p (a) XGA可以由定义知道，p () p()，如果将幂集的定义视为从一个集合合并到另一个集合的幂集运算，则集合的幂集运算使用(定理20集a，b为任意两个集合时为1) AB，并且仅使用p (a) p (b)。(2)p(ab)p(a)p(b)；(3)p(a)p(b)p(ab)；(4) P(AB)(P(A)P(B)。穷集A，P(A)所在元素的个数，即其基数是多少？运用中学时学的数学知识不难证

16、明。P(A)2A。继续下一节。5.2磁双巩俐系统5.2.1。在布尔代数巩俐系统之前的部分中，我们学习了有关集合代数的一些知识。细心的读者可能已经根据上一章对布尔代数的简单介绍发现了，就像在集合代数和布尔代数之间不是问题一样。问题：为什么要引入集合代数？1.布尔代数系统的公理人不仅在社会生活中需要计算，还需要推理，很多时候，要根据自己已经拥有的知识判断和推断很多事情，才会产生逻辑。古典逻辑构建使用自然语言的概念、语言、推理体系。随着人们对自然现象和社会事物的认识的加深，用自然语言描述事物有时显得不严格、不舒服，甚至难以理解。在哲学中，逻辑的发展迫切需要数学等强大的工具。布尔将行、代数符号引入逻辑系统，以使逻辑的推理像数学计算一样进入逻辑系统，用符号表示自然语言中描述的各种抽象断言及其结构，用自然语言描述推理的过程及其断