离散数学第三章集合.ppt

《离散数学第三章集合.ppt》由会员分享，可在线阅读，更多相关《离散数学第三章集合.ppt（62页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、离散数学第三章集合1现在学习的是第1页，共62页离散数学 目目 标标 掌握集合论掌握集合论、代数系统、布尔代数、图论的基本、代数系统、布尔代数、图论的基本思想和方法，提高用思想和方法，提高用集合论集合论、代数系统、布尔代数、代数系统、布尔代数、图论的思想和方法分析问题和解决问题的能力。图论的思想和方法分析问题和解决问题的能力。2现在学习的是第2页，共62页离散数学 目目 录录w序言序言w第三章集合第三章集合w第四章关系第四章关系w第五章函数第五章函数w第六章代数系统第六章代数系统w第七章格与布尔系统第七章格与布尔系统w第八章图论第八章图论3现在学习的是第3页，共62页离散数学Discrete

2、Mathematicsw序言：序言：w离散数学是现代数学的一个重要分支，计算机科学基础理论的核心课程。它充分描述了计算机科学的离散性特点，是随着计算机科学的发展而逐步建立起来的新兴的基础性学科。w本课程作为计算机科学的基础性课程，把握离散数学的关键性问题，介绍五大块内容：集合论、代数系统、布尔代数、图论、数理逻辑。w这些和计算机科学密切相关的理论的结构按排，既着重于各部分之间的紧密联系，又深入探讨各部分内容的概念、例子、理论、算法、以及实际应用。4现在学习的是第4页，共62页离散数学w叙述恰当严谨，论证详尽严密，内容新颖丰富是本课程的特点。w离散数学具有抽象性、非线性、非寻绎性、构造性、结构性

3、、整体性等结构性数学特点。w证明方法除了大量的运用常用的（数学）归纳法、演绎法、反证法、归谬法、二难法、二分法、枚举法（穷举法）、相容排斥法等方法之外，特别着重于存在性、结构性、构造性方法，以及各部分内容自己所特有的方法（比如图论的删点增点方法、删边增边方法、伸路蹦圈方法）。5现在学习的是第5页，共62页离散数学w集合论在计算机科学中的应用集合论在计算机科学中的应用 集合论包括集合关系和函数3部分 1)集合集合 集合不仅可以表示数，而且可以像数一样进行运算，还可以用于非数值信息的表示和处理，如数据的增加、删除、排序以及数据间关系的描述，有些很难用传统的数值计算来处理的问题，却可以用集合来处理。

4、因此，集合论在程序语言、数据结构、数据库与知识库、形式语言和人工智能等领域得到了广泛的应用。2)关系关系 关系也广泛地应用于计算机科学技术中，例如计算机程序的输入和输出关系、数据库的数据特性关系和计算机语言的字符关系等，是数据结构、情报检索、数据库、算法分析、计算机理论等计算机领域中的良好数据工具。另外，关系中划分等价类的思想也可用6现在学习的是第6页，共62页离散数学于求网络的最小生成树等图的算法中。3)函数函数 函数可以看成是一种特殊的关系，计算机中把输入、输出间的关系看成是一种函数。类似地，在开关理论、自动机原理和可计算性理论等领域中，函数都有极其广泛的应用，其中双射函数是密码学中的重要

5、工具。7现在学习的是第7页，共62页 集合集合全集全集空集空集单元素集单元素集子集子集幂集幂集交交集集并集并集余集余集差集差集环和集环和集环积环积集集8现在学习的是第8页，共62页离散数学 第三章集合第三章集合 (set)(set).集合理论中的一些基本概念集合理论中的一些基本概念 个体与集合之间的关系个体与集合之间的关系 集合的表示法集合的表示法 集合与集合之间的关系集合与集合之间的关系 幂集幂集 2.集合代数集合的基本运算集合代数集合的基本运算 集合的补运算集合的补运算 集合的交运算和并运算集合的交运算和并运算 集合的宏运算集合的宏运算9现在学习的是第9页，共62页离散数学 第三章集合第三

6、章集合 (set).集合理论中的一些基本概念集合理论中的一些基本概念 集合概念将作为一个不言自明的元概念（基本概念）。它不能用别的术语来精确的定义，只能用别的术语来加以说明。它本身就是用来定义其它概念的概念。我们来看看一些关于什么是集合的各种不同的说法，以便加深对集合这个元概念的理解。1.莫斯科大学的那汤松教授说：凡具有某种特殊性质某种特殊性质的对象对象的汇集汇集称之为集。2.复旦大学的陈建功教授说：凡可供吾人思维的，不论它有形或无形，都叫做物物。具有某种条件某种条件的物，称它们的全部全部谓之一集。3.南开大学的杨宗磐教授说：10现在学习的是第10页，共62页离散数学 集就是“乌合乌合之众众”

7、。不考虑怎样“乌合乌合”起来的，众可以具体可以具体，可以抽象可以抽象。这种乌合性被归纳为集合的一条性质 任意性：任意性：任意性是说组成集合的元素任意；构成的法则任意；什么都可以构成集合，不加任何限制。任意性是集合的四大性质之一。4.集合论之父G.Cantor（1845-1918）说：集合是由总括总括某些个体个体成一个整体而成的。对于每个个体，只设其为可思考的对象，辨别它的异同可思考的对象，辨别它的异同。个体之间并不需要有任何关系。11现在学习的是第11页，共62页离散数学 因此，对于集合，我们接受以下事实：(a)承认集合的存在性。即，接受集合概念；(b)承认集合是由一些个体（对象）组成的。这些

8、个体称为该集合的成员或元素（member,element）；(c )承认个体是可辩认的。即，一个个体要么是一个集合的成员，要么不是；二者必居其一，也只居其一。这种存在性，可辩认性被归纳为集合的一条性质 确定性：确定性：确定性是说集合确定；个体确定；集合与个体之间的关系确定。因此，经典集合的边界是分明的、清晰的。确定性是集合的四大性质之一。12现在学习的是第12页，共62页离散数学 综上所述集合的概念有三要素：1.个体（元素）2.个体的可辨认性 3.集合（动词，汇到一块）w通常用小写拉丁字母表示个体：a、b、c、d、w通常用大写拉丁字母表示集合：A、B、C、D、w有时还用德文花写字母表示集合：,

9、w关于个体的辨认有赖于各方面公认的知识。一一.个体与集合之间的关系：个体与集合之间的关系：个体与集合之间的关系称为属于关系属于关系。对于某个个体 a 和某个集合 A 而言，只有两种可能：(1)a 属于（belong to）A，记为 aA（记号 是希腊字i的第一个字母，意思是“是”。由意大利数学家G.Peano首先采用），同时称 a 是 A 的元素或A13现在学习的是第13页，共62页离散数学的成员。(2)a 不属于 A，记为 aA或aA，称 a 不是 A 的元素或a 不是 A 的成员。w判断个体 a 属于 A 还是不属于 A，必须使用个体的可辨认性，而且个体的可辨认性是无二义性的，即或者 a

10、属于 A 或者 a 不属于 A，二者居其一且只居其一。AaAaAaAa14现在学习的是第14页，共62页离散数学w集合论是一种语言。它可以作为别的学科的描述工具语言。二二.集合的表示法：集合的表示法：我们规定用花括号 表示集合。w(1)文字表示法：用文字表示集合的元素，两端加上花括号。在座的同学；奇数；去年的下雨天；高等数学中的积分公式；闭区间0,1上的连续函数；比较粗放。比较适合在对集合中的元素了解甚少、不详，难以用精确的数学语言来刻划时使用。w(2)元素列举法（罗列法）：15现在学习的是第15页，共62页离散数学将集合中的元素逐一列出，两端加上花括号。1，2，3，4，5；风，马，牛；2，4

11、，6，8，10，；3，7，11，15，19，；比较适合集合中的元素有限（较少或有规律），无限（离散而有规律）的情况。w(3)谓词表示法：x:P(x)或者 xP(x)其中：P表示 x 所满足的性质（一元谓词）。x:x I（且）x8 =，-3，-2，-1，0，1，2，3，4，5，6,7 ；16现在学习的是第16页，共62页离散数学 x:x2=1；y:y 是开区间(a,b)上的连续函数；（混合表示法）使 x2=1 的实数=1，-1=x:x2=1 比较适合在对集合中的元素性质了解甚详，且易于用精确的数学语言来刻划时使用。w外延外延(extension)：集合 x:P(x)称为性质谓词P(x)的外延；w

12、内涵内涵(intension,connotation)：性质谓词P(x)称为集合 x:P(x)的内涵；由此看到，采用谓词法定义集合，关键是要得出内涵P(x)，并且显然有如下的17现在学习的是第17页，共62页离散数学w概括原理：概括原理：集合 x:P(x)恰由那些满足性质谓词P(x)的元素组成。即 x x:P(x)(当且仅当)P(x)真。w悖论悖论(paradox)：所谓悖论是指这样一个所谓的命题P，由P真立即推出P假；由P假立即推出P真；即 P真P假 。w理发师悖论：理发师悖论：某偏远小山村仅有一位理发师。这位理发师规定：他只给那些不给自己刮脸的人刮脸。那么要问：这位理发师的脸由谁来刮？如果

13、他给自己刮脸，那么，按他的规定，他不应该给自己刮脸；如果他不给自己刮脸，那么，按他的规定，他应该给自己刮脸；18现在学习的是第18页，共62页离散数学w罗素悖论罗素悖论(Russell paradox(1902)：罗素1902年在集合论中也发现了如下的悖论。他构造了这样一个集合 S=x:xx 然后他提出问题：SS？如果SS，那么，按罗素给S的定义，则应有 S S；如果S S，那么，按罗素给S的定义，则应有SS；罗素悖论的发现，几乎毁灭集合论，动摇数学的基础，倾危数学的大厦。直接引发了数学的第三次危机。19现在学习的是第19页，共62页离散数学 为了解决集合论中的悖论问题，人们产生了类型论和形式

14、化公理化集合论(ZF和ZFC公理系统)，以求排除集合论中的悖论。近年来，基于ZFC公理系统和一阶逻辑(谓词逻辑)，人们提出了抽象的计算机程序设计语言_Z语言语言。在公理化集合论中，人们引进了类(class)的概念。20现在学习的是第20页，共62页离散数学 本章我们所讲解的集合论是朴素(naive)集合论；所讨论的集合一般也不会产生悖论。三三.集合的名字：集合的名字：(1)大写的拉丁字母：例如A=x:x=1,B=-1,1；(2)小写的希腊字母：例如=a,b,c,=n:nN3n；(3)花写的徳文字母：例如=y:yR0y 1,=u:u I u+30；不够用时可以加下标。同一个集合可以有几个名字。四

15、四.集合的相等集合的相等（equality）：外延性原理：外延性原理：两个集合相等，当且仅当，它们的成员完全相同。即 A=B x(xA xB)；21现在学习的是第21页，共62页离散数学 两个集合不相等，记为AB；根据这个定义，关于集合我们可得下列性质：(1)无序性：无序性：集合中的元素是无序的。例如 a,b,c=b,a,c=b,c,a 因此，为了使用方便，我们可任意书写集合中元素的顺序。但一般情况下，通常采用字母序、字典序；有时，还需要强行命名一种序；无序性是集合的四大性质之一。(2)无重复性：无重复性：集合中元素的重复是无意义的。例如 a,a,a,a,b,b,b,c,c=a,b,c包包(b

16、ag)：若允许元素重复称为包。例如 a,a,a,a,b,b,b,c,c 一般记为4a,3b,2c22现在学习的是第22页，共62页离散数学 无重复性是集合的四大性质之一。五五.空集空集(empty,null,void set)：记为 空集是没有成员的集合。即 x(x)(所谓的空集公理)；所以=；空集是集合（作这点规定是运算封闭性的要求）。空集是唯一的。因为若有两个空集，则它们有完全相同的元素（都没有任何元素），所以它们相等，是同一集合。六六.全集全集（universe of discourse）：记为X 全集是所要研究的问题所需的全部对象（元素）所构成的集合。全集给个体（研究的对象）划定适当的

17、范围。23现在学习的是第23页，共62页离散数学全集一般用一个矩形框来表示：七七.单元素集合单元素集合（singleton set）：只含一个元素的集合称为单元素集。例如 a；张三；w 左边是空集；右边不是空集，而是单元素集合，有一个成员；这说明：差别在于级别差别在于级别。即，右边的集合级别高。w单元素集合是构造复杂集合的原子原子。X24现在学习的是第24页，共62页离散数学八八.子集子集（subset）：对于两个集合A，B，若A中的每个元素x都是B 的一个元素，则称A包含在B中（或者说B包含A），记为AB。同时称A是B的子集（称B是A 的超集(superset)）。即 AB x(xA xB)

18、。w真子集真子集（proper subset）：称A是B的真子集或者说A真包含在B中（或者说B真包含A），记为AB。即ABX例例.X=a,b,c,d,e,f,A=a,c,d,B=a,b,c,d。则。AB。25现在学习的是第25页，共62页离散数学 AB ABAB。w子集的两种特殊情况（平凡子集）：(1)空集（见下面定理2）；(2)每个集合自己（见下面定理1的(1)）；九九.集合与集合之间的关系集合与集合之间的关系:集合与集合之间的关系有四种。列举如下 (1)B包含A，AB x(xA xB)；(2)A包含B，BA x(xB xA)；(3)A等于B，A=B x(xB xA)ABBA；(4)A与B互

19、不包含，(AB)(BA)x(xAxB)y(yByA)；例例.X=a,b,c,d,e,f,A=a,c,d,B=a,c,d,e。则 AB。26现在学习的是第26页，共62页离散数学定理定理1.设A,B,C为任意三个集合。那么 (1)自反性：A A (每个集合是它自己的子集)；(2)反对称性：AB BA A=B；(3)传递性：AB BC AC；这说明包含关系是集合间的半序关系(参见第二章6)。证明.（采用逻辑法）(1)x(xA xA)(同一律：pp)AA xyX例例.X=a,b,c,d,e,f,A=a,c,d,B=c,d,e。则(AB)(BA)。即A与B互不包含27现在学习的是第27页，共62页离散

20、数学 所以包含关系是自反的；(2)ABBA x(xA xB)x(xB xA)x(xA xB)(xB xA)(量词对 的分配律：xA(x)xB(x)x(A(x)B(x)x(xAxB)A=B 所以包含关系是反对称的；(3)ABBC x(xA xB)x(xB xC)x(xA xB)(xB xC)(量词对 的分配律：xA(x)xB(x)x(A(x)B(x)28现在学习的是第28页，共62页离散数学 x(xA xC)(假言)三段论原则：(pq)(q r)p r )AC 所以包含关系是传递的。定理定理2.空集是任一集合的子集。即 A 。证明.(采用逻辑法)x(x）(空集的定义)x(x)x(xxA)(由析取

21、构成式及联结词归约有：p(p q)(pq)A。29现在学习的是第29页，共62页离散数学十十.幂集幂集(power set)：定义定义1.幂集 一个集合A的所有子集构成的集合称为A的幂集。记为 2A(或P(A)或 P(A)，即 2A=B：B A 。显然，A的两个平凡子集 和A 都属于A的幂集。即 2A，A 2A。例例1.若A=1,2,3，则 2A=,1,2,3,1,2,1,3,2,3,1,2,3。注注：(1)包含关系两边必须是集合，并且这两个集合的级别（广义上）相同；(2)属于关系左边是元素（广义上），右边是集合，两边级别差一级。30现在学习的是第30页，共62页离散数学定义定义2.基数 一个

22、有穷集合（有限集合元素个数有限的集合）A中元素的个数称为A的基数。记为|A|(或A，)。显然基数有以下两个性质：(1)齐性：|=0；(2)非负性：|A|0（对任何集合A）；另外，由于2=，所以|2|=1。一般地，关于幂集有以下结果定理定理3.若A是有限集合，则有|2A|=2|A|。这个定理也说明，我们为什么把一切子集构成的集合称为幂集。证明.由于集合A有限，故可设A=a1，a2，an，于是31现在学习的是第31页，共62页离散数学 A=n。A的子集按其基数大小可分为0，1，2，n共n+1类。A的所有k个元素的子集（基数为k的类）为从n个元素中取k个元素的组合数 。另外，因A，故（按加法原理）2

23、A =1+=但由于二项式定理 (x+y)n=xkyn-k 令x=y=1，则有2n=，从而，有 2A=2n=2 A 。32现在学习的是第32页，共62页离散数学定理定理4.若A，B是两个集合，那么，A=B 2A=2B。证明.）：由幂集的定义，显然；)：一方面，AA (自反性)A2A(因为2A=B:B A)A2B (充分性条件：2A=2B)AB (因为2B=A:AB)另一方面，B B(自反性)B2B(因为2B=A:AB)B2A (充分性条件：2A=2B)BA (因为2A=B:BA)因此，由包含关系的反对称性，得到 A=B。33现在学习的是第33页，共62页离散数学 2.集合代数集合的基本运算集合代

24、数集合的基本运算定义定义1.余(补或非)运算(absolute)complment)设X是全集。一元运算 :2X 2X 对任何集合A X，使得A=x:xX x A (当全集明确时，A=x:x A)称为集合的余运算。称A是A关于X的余集。余运算有时也记为，或 ，或A或A。XAA 集合A以外的元素!34现在学习的是第34页，共62页离散数学例例1.X=a,b,c,d,e,f,A=a,c,d。则 A=b,e,f。定理定理1.余运算基本定理 设X是全集，A，B是X的子集。则 (1)反身律(对合律)：(A)=A；(2)换质位律（逆否律）；AB B A；(3)A=B A=B；(4)零壹律：X=，=X。证明

25、.(采用逻辑法)(1)对任何元素xX，x(A)xA xA 所以 (A)=A；35现在学习的是第35页，共62页离散数学(2)对任何元素xX，xB xB xA(条件：AB)xA 所以 B A ；(4)对任何元素x，xX xX x 所以 X=；对任何元素x，x x xX (已证：X=)xX 所以=X。36现在学习的是第36页，共62页离散数学定义定义2.交运算，并运算(intersection,union)设X是全集。(1)二元运算 :2X2X 2X 对任何集合A,BX，使得 AB=x:xAxB 称为集合的交运算。称AB为A与B的交集。英语读作cap（帽子）。若AB=，则称A与B互不相交(pair

26、wise)disjoint)。(2)二元运算:2X2X 2X 对任何集合A,B X，使得 AB=x:xAxB 称为集合的并运算。称AB为A与B的并集。英语读作cup（酒杯）。同时属于集合A和集合B的元素!至少属于集合A和集合B之一的元素!37现在学习的是第37页，共62页离散数学例例2.设X=a,b,c,d,e,f,A=a,c,d,f,B=b,d,f。则 AB=d,f,AB=a,b,c,d,f。定理定理2.交、并、余运算的基本定理 设X是全集，A，B，C是X的三个子集。则 (1)幂等律：AA=A，AA=A；(2)互补律：AA=，AA=X；XXABABABBA38现在学习的是第38页，共62页离

27、散数学 (2)零壹律：AX=A，AX=X；(全集是交的幺元,并的零元)(2”)零壹律：A=，A=A；(空集是交的零元,并的幺元)(3)上界：A AB，B AB；下界：AB A，AB B；(3)上确界：A C B C AB C；(并集AB是同时包含A和B的集合中最小的一个)(3”)下确界：C A C B C AB；(交集AB是同时被A和B所包含的集合中最大的一个)(4)吸收律：A(AB)=A，A(AB)=A；(5)交换律：AB=BA，AB=BA；39现在学习的是第39页，共62页离散数学 (6)结合律：(AB)C=A(BC)，(AB)C=A(BC)；(7)分配律：A(B C)=(AB)(AC)，

28、A(B C)=(AB)(AC)；证明.(3)(采用逻辑法)对任何元素xX，xAB xAxB xCxC (已知条件：AC，BC)xC (幂等律：ppp)所以，ABC。(7)先证：A(BC)(AB)(AC)(采用元素法)对任何元素xX，若xA(BC)，则xA，且xBC。于是x A，且x B或者xC。40现在学习的是第40页，共62页离散数学 若xB，则xA且xB，于是xAB；若xC，则xA且xC，于是xAC；综合xAB或者xAC，因此 x(AB)(AC)；所以，A(BC)(AB)(AC)。次证：(AB)(AC)A(BC)(采用包含法)由(3)有ABA，ABBBC（逐步放大法）。于是根据(3”)可得

29、ABA(BC)同理可得 ACA(BC)于是根据(3)可得 (AB)(AC)A(BC)。最后，根据包含关系的反对称性，就得到 A(BC)=(AB)(AC)。41现在学习的是第41页，共62页离散数学定理定理3.de Morgan律（也叫对偶律）设A，B为两个集合。则 (1)(AB)=AB，(2)(AB)=AB。证明.只证(1)先证：(AB)AB (采用包含法)由定理2(3)有 AAB，BAB于是由定理1(2)可得 (AB)A，(AB)B再用定理2(3”)，就有 (AB)AB；次证：AB(AB)(采用逻辑法)对任何元素x X，xAB42现在学习的是第42页，共62页离散数学 xAxB xAxB x

30、AB (否则 xAB xAxB，这与xAxB矛盾)x(AB)所以AB(AB)最后，根据包含关系的反对称性，就得到 (AB)=AB。定理定理4 设A，B为两个集合。则下面三式等价。(1)A B；(2)AB=B；(3)AB=A。43现在学习的是第43页，共62页离散数学证明.(采用循环论证法)(1)(2)：(采用包含法)首先，根据定理2(3)，我们得到 BAB；其次，由已知条件AB，及自反性BB，根据定理2(3)，我们得到 ABB；最后，根据包含关系的反对称性，我们就得到 AB=B 。(2)(3)：(采用变换法(公式法)AB=A(AB)(根据(2)AB=B)=A (根据定理2(4)吸收律)即 AB

31、=A。(3)(1)：(采用：包含法)A=AB (根据(3)AB=A)B (根据定理2(3)ABB)44现在学习的是第44页，共62页离散数学 即AB。定义定义3.差运算(difference)设X是全集。二元运算 :2X2X 2X 对任何集合A,BX，使得 AB=x:xA xB 称为集合的差运算。称 AB 为 A 和 B 的差集。差集有时也称为相对补(relative complement)。而余运算可看成绝对补。即 A=XA 。ABBAX 属于集合A但不属于集合B的元素!45现在学习的是第45页，共62页离散数学例例3.X=a,b,c,d,e,f,A=a,c,d,f,B=b,d,f。则 AB

32、=a,c,BA=b。由差运算、交运算、余运算的定义知 AB=AB。由于差运算可以由交、并、余运算线性表出，因此称差运算为宏运算。请问：交、并、余三个运算是线性无关的吗？注注：答案是否定的。实际上，根据反身律、de Morgan律，我们有 AB=(AB)；AB=(AB)。46现在学习的是第46页，共62页离散数学定理定理5.差运算基本定理设X是全集，A，B，C是X的三个子集。则 (1)ABA；(2)ABAB=；(3)AA=；(4)XA=A；AX=；(5)A=A；A=；(6)A(BC)=(AB)(AC)(交对差的分配律)；(7)A(BC)=(AB)(AC)；(8)A(BC)=(AB)(AC)(相对

33、补的de Morgan律)；(9)A(BC)=(AB)(AC)(相对补的de Morgan律)。47现在学习的是第47页，共62页离散数学证明.(采用包含法和变换法(公式法)法)(1)AB=AB A (根据定理2(3)ABA)；(2)AB=AB =(AB)B (由已知条件AB根据定理4(3)有AB=A)=A(BB)(结合律)=A (互补律BB=)=(零壹律)；(3)，(4)，(5)：显然；(6)A(BC)=A(BC)=(ABC)(零壹律,结合律)=(B)(ABC)(零壹律)48现在学习的是第48页，共62页离散数学 =(BAA)(ABC)(互补律,结合律)=(ABA)(ABC)(交换律)=(A

34、B)(AC)(分配律)=(AB)(AC)(de Morgan律)=(AB)(AC)；(7)A(BC)=A(BC)=A(BC)=A(BC)(de Morgan律,反身律)=(AB)(AC)(分配律)=(AB)(AC)；(8)A(BC)=A(BC)=A(BC)(de Morgan律)=(AA)(BC)(幂等律)49现在学习的是第49页，共62页离散数学 =(AB)(C)(结合律，交换律)=(AB)(AC)；(9)A(BC)=A(BC)=A(BC)(de Morgan律)=(AB)(C)(分配律)=(AB)(AC)。定义定义4.对称差（环和）运算(symmetric difference)设X是全集

35、。二元运算 :2X2X 2X ，对任何集合A,BX，使得 AB=x:(xA xB)(xB xA)称为集合的对称差运算。称 AB 为 A 和 B 的对称差集。属于集合A和集合B，但不同时属于集合A和集合B的元素!50现在学习的是第50页，共62页离散数学w由环和运算和并、差运算的定义可知 AB=(AB)(BA)w由环和运算和交、并、余运算的定义可知 AB=(AB)(BA)因此环和运算也是宏运算。例例4.设X=a,b,c,d,e,f,A=a,c,d,f,B=b,d,f。则 AB=a,c,BA=b,于是 AB=a,b,c。ABXAB51现在学习的是第51页，共62页离散数学定理定理6.环和运算基本定

36、理 设X是全集，A，B，C是X的三个子集。则(1)AB=(AB)(AB)=(AB)(AB)；(2)A=A（空集是环和的幺元）；AX=A；(3)AA=（自己是自己（环和）的逆元）；AA=X ；(4)AB=AB；(5)(AB)=AB=AB；(6)交换律：AB=BA；(7)结合律：A(BC)=(AB)C；(8)分配律：A(BC)=(AB)(AC)(交对环和的)；(9)消去律：AB=AC B=C。52现在学习的是第52页，共62页离散数学证明.(采用变换法(公式法)只证(5)，(7)，(9)(5)(AB)=(AB)(AB)=(AB)(AB)(de Morgan律)=(AB)(AB)(de Morgan

37、律，反身律)=(AB)A)(AB)B)(分配律)=(AA)(BA)(AB)(BB)(分配律，结合律)=(AA)(AB)(AB)(BB)(交换律)=(AB)(AB)(互补律)=(AB)(AB)(零壹律)AB=(AB)(AB)=(AB)(AB)(反身律)=(AB)(AB)(交换律)53现在学习的是第53页，共62页离散数学 AB=(AB)(AB)=(AB)(AB)(反身律)所以 (AB)=AB=AB=(AB)(AB)；(7)A(BC)=(A(BC)(A(BC)=(A(BC)(BC)(A(BC)(BC)(根据本定理的(5)的证明)=(ABC)(ABC)(ABC)(ABC)(分配律，结合律)(AB)C

38、 =(AB)C)(AB)C)=(AB)(AB)C)(AB)(AB)C)(根据本定理的(5)的证明)(BC)=BC=BC=(BC)(BC)(1,1.1)=7,(1,0,0)=4,(0,1,0)=2,(0,0,1)=1(AB)=AB=AB=(AB)(AB)54现在学习的是第54页，共62页离散数学 =(ABC)(ABC)(ABC)(ABC)(分配律，结合律)=(ABC)(ABC)(ABC)(ABC)(交换律，结合律)所以 A(BC)=(AB)C；(9)B=B (根据本定理的(2)=(AA)B (根据本定理的(3)=A(AB)(根据本定理的(7)结合律)=A(AC)(已知条件AB=AC)=(AA)B

39、 (根据本定理的(7)结合律)=C (根据本定理的(3)=C (根据本定理的(2)。(1,1.1)=7,(1,0,0)=4,(0,1,0)=2,(0,0,1)=155现在学习的是第55页，共62页离散数学定义定义5.环积运算 设X是全集。二元运算 :2X2X 2X 对任何集合A,BX，使得 AB=x:(xAxB)(xBxA)称为集合的环积运算。称 AB 为 A 和 B 的环积集。w由环积运算和交、并、余运算 的定义可知 AB=(AB)(BA)因此环积运算也是宏运算。ABXAB56现在学习的是第56页，共62页离散数学例例5.设X=a,b,c,d,e,f,A=a,c,d,f,B=b,d,f。则

40、AB=a,c,d,e,f,BA=b,d,e,f,于是 AB=d,e,f。定理定理7.环积运算基本定理 设X是全集，A，B，C是X的三个子集。则 (1)AB=(AB)(AB)=(AB)(AB)；(2)AB=(AB)=AB=AB；(3)A=A；AX=A（全集是环积的幺元）；(4)AA=X（自己是自己（环积）的逆元）；AA=；(5)A B=AB；57现在学习的是第57页，共62页离散数学 (6)(AB)=AB=AB；(7)交换律：AB=BA；(8)结合律：A(BC)=(AB)C；(9)分配律：A(BC)=(AB)(AC)(并对环积的)；(10)消去律：A B=A C B=C。证明.(采用变换法(公式

41、法)只证(9)(9)A(BC)=A(AB)(AB)=(ABC)(ABC)(分配律，结合律)=X(ABC)X(ABC)(零壹律)=(AB)(ABC)(AC)(ABC)(互补律，零壹律，交换律，结合律)58现在学习的是第58页，共62页离散数学 =(AB)(C)(AB)(AC)(交换律，结合律，分配律)=(AB)(C)(AB)(AC)(de Morgan律)=(AB)(AC)；定义定义5.(1)初级交：A1 A2 An =x:(kN)(1 kn)(xAk)A1 A2 An =x:(kN)(k1)(xAk)(2)初级并：A1 A2 An =x:(kN)(1 kn)(xAk)A1 A2 An 59现在

42、学习的是第59页，共62页离散数学 =x:(kN)(k1)(xAk)(3)广义交：x:()(xA)(4)广义并：x:()(xA)这里：称为索引，下标，指标；称为索引集，下标集，指标集。例6.=(0,1)，A=(1-,2+)。则 1,2；(0,3)。01-123)(2+60现在学习的是第60页，共62页离散数学定理定理8.(1)分配律：(2)de Morgan律：61现在学习的是第61页，共62页离散数学证明.(采用逻辑法)(1)只证第三式 对任何元素xX，xA()xA x xA()(xA)()(xAxA)(量词前移：pxA(x)x(pA(x)()(xAA)x 所以A()=；62现在学习的是第62页，共62页