第1章集合、映射与运算2015

1、(Discrete Mathematics )祁伟祁伟电话电话Q:826105276 使用教材使用教材书 名：离散数学（第三版） “十一五”国家规划教材主 编：邓辉文出版社：清华大学出版社讲 授：第1章 _ 第6章参考书目参考书目1 1、邵学才、邵学才. . 离散数学（第二版）. . 清清华大学出版社华大学出版社. (. (应用型规划教材应用型规划教材) )2 2、周忠荣、周忠荣. . 离散数学及其应用. . 清华清华大学出版社大学出版社. .3 3、王礼萍、王礼萍. . 离散数学简明教程. . 清华清华大学出版社大学出版社. (. (高职教材高职教材) )4 4、耿

2、素云、耿素云, , 屈婉玲屈婉玲. . 离散数学（修订版）. . 高等教育出版社高等教育出版社. (. (十五规划教材，十五规划教材，北京大学北京大学) )考核方式考核方式期末成绩期末成绩 = 平时成绩平时成绩 + 期末试卷成绩期末试卷成绩 平时成绩平时成绩20分分 平时成绩平时成绩 = 出勤出勤 + 小测验小测验 +作业作业 出勤出勤 = 10 小测验小测验 = 5 作业作业 = 5（独立、自主独立、自主） 期末试卷成绩期末试卷成绩80分。分。研究对象研究对象 离散数学是研究离散量的结构及其相离散数学是研究离散量的结构及其相互之间关系的一互之间关系的一门门学科，学科，它它与当今计算机与当今计

3、算机所处理的对象相一致。所处理的对象相一致。 离散数学是研究计算机科学的离散数学是研究计算机科学的基本数学工具和最合适的理论手段；基本数学工具和最合适的理论手段；是计算机类专业的重要课程。是计算机类专业的重要课程。学习目的学习目的 离散数学是计算机及相关专业的一门核心课程，不是一门纯数学课程，而是计算机学科的专业基础课程。 1、为后继课程提供必要的数学基础 2、培养学生抽象思维能力和严密的逻辑推理能力。基本内容（基本内容（1）一、集合与关系：是离散数学研究的重点内容 1、Chapter 1 集合、映射与运算：集合是现代数学的最基本概念，映射是现代数学的基本概念，是本书的重点。 2、Chapte

4、r 2 关系：是刻画联系的数学模型。二、数理逻辑：研究思维形式及思维规律尤其是推理的学科。 1、Chapter 3 命题逻辑：研究的主要对象是命题。 2、Chapter 4 谓词逻辑：研究原子命题的内部形式结构及其逻辑关系。基本内容（基本内容（2）三、代数结构：研究有一般元素组成的集合上的运算，以及运算满足一些给定的数学结构的性质。 1、Chapter 5 (1) 代数结构：计算机系统本身就是一种代数结构。 2、Chapter 5 (2) 群、环和域：在形式语言与自动机理论学科中发挥作用。 3、Chapter 5 (3) 格与布尔代数：在自动推理和逻辑电路设计的分析和优化等问题中得到应用。四、

5、图论：广泛应用与解决现实问题。 1、Chapter 6 图论：主要研究数据结构中图的相关性质。 2、Chapter 7 几类特殊的图：介绍生活和研究中实际的图论的问题。第第1章章 集合、映射与运算集合、映射与运算 1.1集合的有关概念集合的有关概念 1.2映射的有关概念映射的有关概念 1.3运算的定义及性质运算的定义及性质 1.4集合的运算集合的运算 1.5集合的划分与覆盖集合的划分与覆盖第第1章章 集合、映射与运算集合、映射与运算 集合是现代数学的最基本概念. 映射又称为函数, 它是现代数学的基本概念, 可以借助于集合下定义. 运算本质上是映射, 但有其特殊性.(关系也是集合)集合、映射、运

6、算及关系是贯穿于本书的一条主线.1.1.1 集合集合 集合（set）:是指具有某种特定性质的对象汇集成的一个整体。元素（element）：集合中的每一个对象称为集合的元素。通常用大写字母表示集合，用小写字母表示集合中的元素。 在数学中常用 表示整体.在讨论集合时，为避免出现某些悖论，应指定讨论范围，这个范围也是一个集合，称为全集或论域，记作U。文氏图用矩形框表示。UA隶属关系隶属关系集合与集合中元素的关系隶属关系给定一个集合A， （1）若x是集合A中的元素，记作xA，读作x属于A； （2）若x不是集合A中的元素，则记作xA，读作x不属于A。说明：读作属于；读作不属于例:A=a,b,c,d，则有

7、b A，e A特殊集合表示特殊集合表示几类特殊集合的表示：几类特殊集合的表示：nN 自然数集合自然数集合 , 包括数包括数0；nZ 整数集合；整数集合；nQ 有理数集合；有理数集合；nR 实数集合；实数集合；nC 复数集合复数集合集合的表示集合的表示 列举法列举法 就是把集合中的所有元素一一列举出来，或列出足够多的元素以反映出集合中成员的特征，元素之间用逗号分开，并用花括号括起来。如：A=a1，a2，an B=0，2，4，6，2n，。集合的表示集合的表示 描述法描述法 是指把集合中的元素所满足的条件或具有的性质描述出来，即将条件或性质用文字或符号在花括号内竖线后面表示出来。一般形式为： A=A

8、=x x| |x x 满足的条件或具有的性质满足的条件或具有的性质 如：A=x|x 1 = 0，xR B= x|x是英文字母，x元音集合的表示集合的表示 递归法递归法 是指通过计算规则定义集合中的元素。首先给出该集合的初始元素；然后给出由集合中已知元素构造其他元素的方法；最后强调有限次使用前面的步骤得到的元素是集合中仅有的元素。如：设a0=1,a1=1,an+1=an+an-1, A=a0,a1,a2,=akk0。 集合的表示集合的表示 巴科斯范式巴科斯范式(BNF)表示法表示法 BNF常用来定义高级程序设计语言的标识符或表达式集合。 文氏图法文氏图法(John Venn) 首先画一个大矩形表

9、示全集，然后在矩形内画一些圆，用圆的内部表示集合，集合之间的相互关系和有关的运算可以用文氏图给予形象的描述。集合的特性集合的特性 确定性确定性 确定性是指一旦给定了集合确定性是指一旦给定了集合A A，对于任意元素，对于任意元素a a，我，我们就可以准确地判定们就可以准确地判定a a是否在是否在A A中。中。如：如：A=A=x x| |x x是自然数，且是自然数，且x x100100则必有则必有3030 A A，101101 A A 互异性互异性 互异性是指集合中的元素之间是彼此不同的，即集互异性是指集合中的元素之间是彼此不同的，即集合中不允许出现重复的元素。合中不允许出现重复的元素。如：集合如

10、：集合 A=a,b,c,c,b,d A=a,b,c,c,b,d 应为应为 A=a,b,c,dA=a,b,c,d集合的特性集合的特性 无序性无序性 无序性是指集合中的元素之间没有次序关系。在无序性是指集合中的元素之间没有次序关系。在不特别说明情况下，我们所讨论的集合都不是多重不特别说明情况下，我们所讨论的集合都不是多重集。集。 如：如： A = A = a a, , a a, , b b, , b b, , c c 与与 A=A=a a, , b b, , c c , , a a, , b b 相同相同 抽象性抽象性 抽象性是指集合中元素是抽象的，甚至可以是集合。抽象性是指集合中元素是抽象的，甚

11、至可以是集合。如：如：A = a, a, b, b, c；相关概念相关概念有限集有限集 由有限个元素由有限个元素a1,an组成的集合称为有限集。组成的集合称为有限集。基数（或势）基数（或势） 若集合若集合A是有限集，则集合是有限集，则集合A中的元素个数称为集中的元素个数称为集合合A的基数（或势），通常记作的基数（或势），通常记作|A|。无限集无限集 无限集是指由无限个元素组成的集合。无限集是指由无限个元素组成的集合。空集空集 不含有任何元素的集合是空集。记不含有任何元素的集合是空集。记或或 。1.1.2 子集子集子集子集集合间的包含关系集合间的包含关系 给定两个集合A和B，若A中的任意元素都属

12、于B，则称A是B的子集，或称A包含在B，或称B包含A，通常记作A B，或BA。（若任意aA，必有aB，则A B） 若若A A不是不是B B的子集，则集合的子集，则集合A A中至少有一中至少有一个元素不属于个元素不属于B B。子集定理子集定理1-1 对于任意的集合对于任意的集合A，有，有 A。1-2 设设A、B、C是任意的集合，则有是任意的集合，则有自反性：自反性：A A.（任意集合是其子集）（任意集合是其子集）反对称性：反对称性：A B,B A A = B.传递性：传递性：A B,B C A C.1-3 A = B 的充要条件是的充要条件是A B 且且 B A真子集真子集 若若A A B B，

13、且，且A A B B，则称，则称A A是是B B的真子集，通常记作的真子集，通常记作A A B B。（若。（若A A是是B B的真子集，则的真子集，则B B中至少有一个元素不属中至少有一个元素不属于于A A）注意区别：注意区别： 1.1.3 幂集幂集定理定理 设设A是一个有限集且是一个有限集且|A|=n，则，则|P(A)|=2n|)(XAAXP幂集示例幂集示例X X = = a a, , b b P P( (X X) = ) = , , a a, , b b, , a a, , b b.P P() = ) = , , .习题习题1.1 (7)1.1 (7)1.1.4 n元组元组),(yxO),

14、(xyn=2n=3.,., ,.,),.,(212121nnnxxxxxxxxx),(zyxO序偶序偶.,),.,(),.,(2121iyxyyyxxxiinn1.1.5 笛卡儿积笛卡儿积设设A1，A2，An是集合，称集合是集合，称集合为为A1，A2，An的笛卡儿积（直积，叉积）的笛卡儿积（直积，叉积）.,.,2 , 1,| ),.,(.2121niAxxxxAAAiinn.By,Ax| )y, x(BA笛卡儿积定理笛卡儿积定理.| ,|mnBAnBmA1.2 映射的有关概念映射的有关概念 映射就是函数，研究的是任意两个集映射就是函数，研究的是任意两个集合之间的一种对应关系。合之间的一种对应关

15、系。 映射是现代数学中的基本概念。函数映射是现代数学中的基本概念。函数在信息科学中得到了充分的应用。在信息科学中得到了充分的应用。 与集合一样，映射贯穿本书的所有内与集合一样，映射贯穿本书的所有内容，深刻理解映射的有关内容，对于其他容，深刻理解映射的有关内容，对于其他内容的学习是至关重要的。内容的学习是至关重要的。1.2.1 映射的定义映射的定义 任意给定两个集合任意给定两个集合A和和B，若存在对应法则，若存在对应法则 f ，使得对于，使得对于任意任意x A，均存在，均存在唯一唯一的的y B与它与它对应，则称对应，则称 f 是集合是集合A到到B的一个映射，或称的一个映射，或称A到到B的一个函数

16、，记为的一个函数，记为 f :AB。ABfBAf:映射的两个特点映射的两个特点 假定假定 f :AB, y= f(x) ,通常把通常把x称为自变量，其取值范围称称为自变量，其取值范围称为为定义域记为定义域记为dom f ；将；将y称为因变量，其取值范围称为值域，称为因变量，其取值范围称为值域，记为记为ran f。 映射映射f的定义域是集合的定义域是集合A,记为记为dom f =A； 对于任意对于任意xA,对应于对应于B中唯一的元素中唯一的元素f(x),x为为f的自的自变量变量(也称为原像也称为原像),f(x)称为称为x在映射在映射f下的像下的像,通常记为通常记为y= f(x).映射的表示映射的

17、表示（1）解析表达式）解析表达式（2）图示）图示（3）表格法）表格法B BA A （读作（读作B B上上A A）定义）定义.:|BAffBA定理：定理： 对于集合对于集合A和和B，若，若|A|=m，|B|=n，则，则|BA|=nm。教材教材P7例题例题1-51.2.2 映射的性质映射的性质1、单射、单射 假设假设f :AB,如果对任意如果对任意x1,x2 A,由由f(x1) = f(x2) 可推出可推出x1=x2,则称则称f是是A到到B的单射的单射,或称或称f是是A到到B的一对一映射。的一对一映射。fBA.)()(,212121xxxfxfAxx).()(,212121xfxfxxAxx例：设

18、例：设f f:NN:NN，f f(x)=2x,(x)=2x,则则f f是是N N到到N N的单射，试证明之。的单射，试证明之。1.2.2 映射的性质映射的性质2、满射、满射假设假设f :AB，如果对任意，如果对任意y B,均存在均存在x A，使，使得得y = f(x)，则称，则称f是是A到到B的满射，或称的满射，或称f是是A到到B的映上的映上(onto)的映射。的映射。fBA例：例：设设f:ZN, f(x)=|x|, f:ZN, f(x)=|x|, 则则f f是是Z Z到到N N的满射。的满射。1.2.2 映射的性质映射的性质3、双射、双射假设假设f :AB，f 既是单射又是满射，则称既是单射

19、又是满射，则称f是是A到到B的的双射双射,或称或称f 是是A到到B的一的一 一对应。一对应。fBA例：试建立一个例：试建立一个Z到到N的一的一一对应。一对应。 2x x0f(x) = 2|x| - 1 x0 习题习题1.2 (2)1.2 (2)置换的定义置换的定义例如：写出例如：写出A=1，2，3上的所有置换。上的所有置换。(个数：个数：n!),3213211p,3123212p,1233213p,2313214p,1323215p.2133216p123(1)(2)(3)pppp1.2.3 逆映射逆映射 ，则，则1.2.4 复合映射复合映射xy=f(x)z=g(y)=g(f(x)hfg1.2

20、.4 复合映射复合映射abc123 fg复合映射例题复合映射例题f f( (A A) ) dom(dom(g g) )例例2 2：设设R R到到R R有两个映射有两个映射f f和和g g，定义如下：，定义如下：f(x) = f(x) = x x2 2,g(x) = x + 2,g(x) = x + 2，分别计算复合映射，分别计算复合映射和和 恒等映射恒等映射 设设A A是集合，令是集合，令f f: A: AA, A, f f( (x x) = ) = x x，称称f f为集合为集合A A上的恒等映射上的恒等映射(identity (identity function on A)function

21、 on A)，记为，记为IA 显然恒等映射是唯一存在的。显然恒等映射是唯一存在的。【定理定理1-9】若若f: : A A B B是双射，则有是双射，则有f f-1 = IA，f-1 f = I B. .特别地，若特别地，若f: : A A A A是双射，则是双射，则f f-1= f-1 f = IA 复合映射性质复合映射性质【定理定理1-10】设设f: : A A B B , , g: : B B C C ，(1)若若 f 和和 g 是单射是单射, 则则 f g是单射是单射.(2)若若 f 和和 g 是满射是满射, 则则 f g 是满射是满射.(3)若若 f 和和 g 是双射是双射, 则则 f

22、 g 是双射是双射.【定理定理1-11】设设f: : A A B B , , g: : B B C C ，(1) 若若f g是单射是单射, 则则f是单射是单射, g不一定不一定.(2) 若若f g是满射是满射, 则则g是满射是满射, f 不一定不一定.(3) 若若f g是双射是双射, 则则f是单射且是单射且g是满射是满射.【定理定理1-12】设设f: : A A B B , , g: : B B C C ，h: : C C D D，则则( (f g) h = f (g h)1.3 运算的定义及性质运算的定义及性质 运算是由已知对象得出新对象的一种运算是由已知对象得出新对象的一种方法。运算是讨论

23、对象之间有何联系的一方法。运算是讨论对象之间有何联系的一种方法。种方法。 运算本质上是映射，但运算更侧重于运算本质上是映射，但运算更侧重于研究运算满足的一些运算性质。研究运算满足的一些运算性质。 1.3.1 运算的定义运算的定义 设设A1 , A2 , , An和和B是集合，若是集合，若 f: A1 A2 AnB 则称则称f为为A1 , A2 , , An到到B的的n元运算。在不需元运算。在不需要强调集合要强调集合A1 , A2 , , An和和B时，可以简称时，可以简称f为为运算运算， f: AAAB称称f为为A到到B的的n元运算，或称元运算，或称f f为为A上的上的n元运算。元运算。 如如

24、y = f(xy = f(x1 1,x,x2 2,x,xn n) )中，中， x x1 1,x,x2 2,x,xn n是参加运是参加运算的算的n n个有顺序的对象，个有顺序的对象，f f称为称为n n元运算，元运算，y y是运算结果，是运算结果，由定义知道：由定义知道：运算结果一定是唯一的运算结果一定是唯一的。运算的特征运算的特征1 1、封闭运算封闭运算：若对于：若对于x x1 1 , x , x2 2 , , x , , xn n A A，有有f f(x(x1 1 , x , x2 2 , , x , , xn n) = y) = y A A，则称，则称f f为为A A上的上的n n元封闭运

25、算元封闭运算(closed operation)(closed operation)，或称，或称为为A A上的上的n n元代数运算。元代数运算。习题习题1.3(1)(2)1.3(1)(2)2 2、运算符号的选取运算符号的选取：常用符号和定义符号：常用符号和定义符号3 3、运算符号的位置运算符号的位置：前面、中间和后面：前面、中间和后面4 4、运算表运算表：方便直观：方便直观运算的例题运算的例题例例1 （绝对值运算绝对值运算） f: Z N, f(x) = |x|. （一元运算）（一元运算） 例例2 (模运算模运算) f: Z N, f(x) = x(mod k), 例例3（模（模m加法运算和模

26、加法运算和模m乘法运算）乘法运算）例例4（最大公（最大公因因数数gcd和最小公倍数和最小公倍数lcm）1.3.2 运算的性质运算的性质1、对合性、对合性【定义定义】设设*是是A上的上的1元代数运算，若对于元代数运算，若对于x x A A ，均有均有 *(*x) = x 则称则称*具有对合性，或称具有对合性，或称*满足对合律满足对合律例例1-20实数集上的取反数运算实数集上的取反数运算“”具有对合性，具有对合性，而其上的绝对值运算而其上的绝对值运算|不具有对合性。矩阵的逆运算不具有对合性。矩阵的逆运算及转置运算具有对合性，因为及转置运算具有对合性，因为(A-1)-1 = A并且并且(AT)T =

27、 A1.3.2 运算的性质运算的性质2 2、幂等性、幂等性【定义定义】设设 * * 是是A A上的上的2 2元代数运算，若对于元代数运算，若对于x x A A ，有有 x x * * x = x x = x 则称则称x x为关于为关于* *运算的幂等元；若对于任意的运算的幂等元；若对于任意的x x A A，x x均为幂等元，则称均为幂等元，则称* *具有幂等性，或称具有幂等性，或称* *满足幂等率。满足幂等率。例例1 1：设：设A = 1,2,3A = 1,2,3，A A上的上的* *运算见表，指运算见表，指出出A A中的幂等元，并判断是否满足幂等率？中的幂等元，并判断是否满足幂等率？例例2

28、2：正整数集合：正整数集合N N+ +上上gcdgcd和和lcmlcm是否幂等率？是否幂等率？例例3 3：实数集合：实数集合R R上乘法是否满足幂等率？上乘法是否满足幂等率？1.3.2 运算的性质运算的性质3、交换性、交换性【定义定义】设设*是是A上的上的2元代数运算，若对于任意元代数运算，若对于任意x,yx,y A A，均有均有 x * y = y * x则称则称*具有交换性，或称具有交换性，或称*满足交换律。满足交换律。例例1 1：验证整数集合：验证整数集合Z Z上的加法运算和减法运算是否满足交换上的加法运算和减法运算是否满足交换律律例例2 2：设：设* *是有理数集合是有理数集合Q Q上

29、的上的2 2元运算，定义如下：任意元运算，定义如下：任意x x1 1,x,x2 2 Q Q， x x1 1* *x x2 2 = x = x1 1x2x2。证明。证明* *不具有交换性。不具有交换性。例例3 3：说明复合映射是否具有交换性。：说明复合映射是否具有交换性。1.3.2 运算的性质运算的性质4、结合性、结合性【定义定义】设设 * 是是A上的上的2元代数运算，若对于元代数运算，若对于任意的任意的 x,y,zx,y,z A A ，均有，均有 (x * y) * z = x * (y * z)则称则称*具有结合性，或称具有结合性，或称*满足结合律。满足结合律。 例例1 1：验证整数集合：验

30、证整数集合Z Z上的加法运上的加法运算和减法运算是否满足结合率。算和减法运算是否满足结合率。53145534314421213343142254321154321*例例2 2：判定集合：判定集合A=1,2,3,4,5A=1,2,3,4,5见见表，是否满足交换率和结合率？表，是否满足交换率和结合率？例例3 3：判定映射的复合运算是否：判定映射的复合运算是否满足结合率？满足结合率？1.3.2 运算的性质运算的性质5、单位元素、单位元素【定义定义】设设 * 是是A上的上的2元代数运算，若存在元代数运算，若存在e e A A ，对于任意的对于任意的x x A A ，下列条件均成立：，下列条件均成立：

31、e * x = x x * e = x则称则称e为集合为集合A关于关于*运算的单位元素或幺元素。运算的单位元素或幺元素。 例例1 1：验证整数集合：验证整数集合Z Z关于加法运算关于加法运算+ +的单位元素为的单位元素为0 0，而，而Z Z关于关于乘法运算的单位元素为乘法运算的单位元素为1 1，Z Z关于减法运算没有单位元素。关于减法运算没有单位元素。定理：若定理：若A A关于关于* *运算有单位元素，则单位元素是唯一的。运算有单位元素，则单位元素是唯一的。1.3.2 运算的性质运算的性质6 6、零元素、零元素【定义定义】设设 * * 是是A A上的上的2 2元代数运算，若存在元代数运算，若存

32、在 A A ，对于任意的对于任意的x x A A ，下列条件均成立：，下列条件均成立： * x = x * = 则称为集合则称为集合A A关于关于* *运算的零元素。运算的零元素。例例1 1：验证整数集合：验证整数集合Z Z关于加法运算关于加法运算+ +和减法运算和减法运算- -均没有零元均没有零元素。素。Z Z关于乘法运算的零元素为关于乘法运算的零元素为0 0。1.3.2 运算的性质运算的性质7 7、逆元素、逆元素【定义定义1-211-21】设设 * * 是是A A上的上的2 2元代数运算且有单位元元代数运算且有单位元素素e e，若对于，若对于x x A A，存在，存在y y A A，下列条

33、件均成立：下列条件均成立： y * x = e x * y = e则称则称y y为为x x的逆元素。的逆元素。注意：注意： 1 1、一个方阵关于乘法运算的逆元是其逆矩阵，、一个方阵关于乘法运算的逆元是其逆矩阵，单位元素是单位矩阵；单位元素是单位矩阵； 2 2、一个双射的映射的复合运算的逆元是其逆映、一个双射的映射的复合运算的逆元是其逆映射。单位元素是恒等映射。射。单位元素是恒等映射。1.3.2 运算的性质运算的性质例例1 1：分别考察：实数集合：分别考察：实数集合R R中各元素关于加法运算和中各元素关于加法运算和乘法运算的逆元素。乘法运算的逆元素。例例2 2：设：设A=a, b, c,A=a,

34、 b, c,关于关于* *运算的运算表。分析逆元。运算的运算表。分析逆元。 结论：一个元素的逆元不一定存在，存在也不一结论：一个元素的逆元不一定存在，存在也不一定唯一。定唯一。习题习题1.3(8)1.3(8)caccaabbcbaacba*【定理】设【定理】设A A关于关于* *运算的单位元素为运算的单位元素为e e且且* *运算满足结合律，若运算满足结合律，若x x在在A A中有左逆中有左逆元元y y及右逆元及右逆元z z，则，则y = zy = z。进而，对于。进而，对于一个满足结合律的运算来说，若一个元一个满足结合律的运算来说，若一个元素有逆元则其逆元是唯一的。素有逆元则其逆元是唯一的。

35、 1.3.2 运算的性质运算的性质8 8、消去性、消去性【定义定义1-221-22】设设 * * 是是A A上的上的2 2元代数运算，若元代数运算，若A A关于关于* *运算有零元素，如果对于任意运算有零元素，如果对于任意x,y,zx,y,z A A ，只要，只要xx ，则下列条件均成立：，则下列条件均成立： x x * * y = x y = x * * z y = z z y = z y y * * x = z x = z * * x y = z x y = z则称则称* *具有消去性，或称具有消去性，或称* *满足消去律。满足消去律。例：验证整数集合例：验证整数集合Z Z上的加法运算上的

36、加法运算+ +和乘法运算均满和乘法运算均满足消去律。足消去律。1.3.2 运算的性质运算的性质9 9、分配性、分配性【定义【定义1-231-23】设】设 * *和和 是是A A上的上的2 2元代数运算，若对元代数运算，若对于任意于任意x,y,zx,y,z A A ，下列条件均成立：，下列条件均成立： x x * * (y (y z) = (x ) = (x * * y) y) (x (x * * z) z) (y (y z) ) * * x = (y x = (y * * x) x) (z (z * * x) x)则称则称* *运算对运算对 运算具有分配性，或称满足分配律。运算具有分配性，或称

37、满足分配律。注意：当注意：当* *运算满足交换性时，条件之一成立即可。运算满足交换性时，条件之一成立即可。例：实数集合例：实数集合R上的乘法运算对加法运算可分配。上的乘法运算对加法运算可分配。1.3.2 运算的性质运算的性质1010、吸收性、吸收性【定义【定义1-241-24】设】设 * * 和和 是是A A上的两个上的两个2 2元代数运算，元代数运算，若对于若对于x,yx,y A A ，下列条件均成立：，下列条件均成立： x x * * (x (x y) = x) = x (y (y x) ) * * x = x x = x则称则称* *运算对运算运算对运算 可吸收。可吸收。注意：当注意：当

38、* *和和 运算满足交换性，以上公式之一运算满足交换性，以上公式之一成立即可。成立即可。1.3.2 运算的性质运算的性质1111、德、德摩根（摩根（De MorganDe Morgan）律）律 【定义定义】设设是集合是集合A A上的上的1 1元代数运算，元代数运算， * * 和和 是是A A上的两个上的两个2 2元代数运算，若对于元代数运算，若对于x,yx,y A A ，下列条件，下列条件均成立：均成立： (x * y) = (x) (y) (x y) = (x) *(y)则称这三种运算满足则称这三种运算满足De MorganDe Morgan律律 1.4 集合的运算集合的运算1、并运算、并运

39、算2、交运算、交运算3、补运算、补运算4、差运算、差运算5、对称差运算、对称差运算1.4.1 并运算并运算【定义】设【定义】设A A和和B B是两个任意集合，由所有属于是两个任意集合，由所有属于A A或属或属于于B B的元素组成的集合称为集合的元素组成的集合称为集合A A和和B B的并集，通常记的并集，通常记作作ABAB。即：。即：AB=AB=x x| |x x A A或或x x BB阴影部分为阴影部分为ABABU U B BA A如：设如：设 A=a，b，c，d，B=b，d，e，f，求求ABAB定理：设定理：设A A和和B B是集合，则是集合，则ABAB是包含集合是包含集合A A和和B B的

40、最小集合。的最小集合。并运算的性质并运算的性质设设A A，B B，C C是集合，则是集合，则1 1、幂等律：、幂等律：AA = AAA = A2 2、交换律：、交换律：AB = BAAB = BA3 3、结合律：、结合律：(AB)C=A(BC)(AB)C=A(BC)4 4、A=AA=A= =A(A(空集空集是并运算的单位元素是并运算的单位元素) )5 5、UA=AU=U(UA=AU=U(全集全集U U是并运算的零元素是并运算的零元素) )1.4.2 交运算交运算【定义】设【定义】设A A和和B B是两个任意集合，由所有属于是两个任意集合，由所有属于A A又属又属于于B B的元素组成的集合，称为

41、的元素组成的集合，称为A A和和B B的交集，通常记作的交集，通常记作ABAB。即。即AB=AB=x x| |x x A A且且x x BB阴影部分为阴影部分为ABABU U B BA A如：设如：设 A=a，b，c，d，B=b，d，e，f，求求A AB B定理：设定理：设A A和和B B是集合，则是集合，则A AB B是包含在集合是包含在集合A A和和B B中的最大集合。中的最大集合。交运算的性质交运算的性质设设A A，B B，C C是集合，则是集合，则1 1、幂等律：幂等律：AA=AAA=A2 2、交换律：、交换律：AB= BAAB= BA3 3、结合律：、结合律：(AB)C=A (BC)

42、(AB)C=A (BC)4 4、A=AA=A= =（空集（空集是交运算的零元素是交运算的零元素）5 5、UA=AU=AUA=AU=A（全集（全集U U是交运算的单位元素）是交运算的单位元素）交和并运算的性质交和并运算的性质并、交运算的混合性质并、交运算的混合性质( (吸收律吸收律) )： 设设A A，B B，C C是集合，则是集合，则（1）对对可吸收：可吸收：AA(AB)= A （2）对对可吸收：可吸收：AA(AB)= A （3）对对可分配：可分配：AA(BC)= (AB)(AC) （4）对对可分配：可分配：AA(BC)= (AB)(AC) 1.4.3 补运算补运算【定义定义】设设U U是全集

43、，对于集合是全集，对于集合A A，定义，定义A A的补集如下：的补集如下： =x|x=x|x U U，但，但x x A A 注意：一个集合的补集依赖于全集的选取。注意：一个集合的补集依赖于全集的选取。A阴影部分为阴影部分为A A的补集的补集U UA A例：设集合例：设集合A=a , b , c分别取全集分别取全集U=a , b , c , d和和U=a , b , c , a , b , b , c , c , 求求A的补集。的补集。补运算的性质补运算的性质补运算的性质：补运算的性质： （1）A =U （2）A = De Morgan律律AAABAB BABA1.4.4 差运算差运算【定义】设

44、【定义】设A A和和B B是两个任意集合，是两个任意集合，由所有属于由所有属于A A但不但不属于属于B B的元素组成的集合称为的元素组成的集合称为A A和和B B的差集的差集，通常记作，通常记作A-BA-B。即。即A-B=x|xA-B=x|x A A且且x x BBU UA AB B阴 影 部 分阴 影 部 分为为A-BA-B如：设如：设 A=a，b，c，d，B=b，d，e，f，求求A-BA-B和和B-AB-A差运算的性质差运算的性质（1 1）A-A = A-A = （2 2）A-A- = A = A（3 3）A-U = A-U = 定理：对于集合定理：对于集合A , BA , B，有，有A

45、A B = AB B = AB1.4.5 对称差运算对称差运算【定义】设【定义】设A A和和B B是两个任意集合，是两个任意集合，由所有属于由所有属于A A但不但不属于属于B B或者属于或者属于B B但不属于但不属于A A的元素构成的集合称为对的元素构成的集合称为对称差运算也可称为环和运算称差运算也可称为环和运算 ，通常记作，通常记作A A B B。即。即A A B =B =（A-BA-B） （B-AB-A）A A B =B =（A AB B）- -（BABA）U UA AB B阴影部分为阴影部分为A A B B如：设如：设 A=a，b，c，d，B=b，d，e，f，求求A A B B对称差的性质对称差的性质（1 1）A A B = B B = B A A（2 2）A A = A = A（3 3）A A A = A = （4 4）（）（A A B B） C = A C = A （B B C C）