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

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

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

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

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

5、(3) 格与布尔代数：在自动推理和逻辑电 路设计的分析和优化等问题中得到应用。 四、图论：广泛应用与解决现实问题。 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。文氏图用矩形框 表示。 U A 隶属关系隶属关系 集合与集合中元素的关系隶属关系 给定一个集合A， （1）若x是集合A中的元素，记作xA，读作 x

7、属于A； （2）若x不是集合A中的元素，则记作xA， 读作x不属于A。 说明：读作属于；读作不属于 例:A=a,b,c,d，则有b A，e A 特殊集合表示特殊集合表示 几类特殊集合的表示：几类特殊集合的表示： nN 自然数集合自然数集合 , 包括数包括数0； nZ 整数集合；整数集合； nQ 有理数集合；有理数集合； nR 实数集合；实数集合； nC 复数集合复数集合 集合的表示集合的表示 列举法列举法 就是把集合中的所有元素一一列举出 来，或列出足够多的元素以反映出集合中 成员的特征，元素之间用逗号分开，并用 花括号括起来。 如：A=a1，a2，an B=0，2，4，6，2n，。 集合的表

8、示集合的表示 描述法描述法 是指把集合中的元素所满足的条件或具有 的性质描述出来，即将条件或性质用文字或 符号在花括号内竖线后面表示出来。 一般形式为： A=A=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。 集合的表

9、示集合的表示 巴科斯范式巴科斯范式(BNF)表示法表示法 BNF常用来定义高级程序设计语言的标识符 或表达式集合。 文氏图法文氏图法(John Venn) 首先画一个大矩形表示全集，然后在矩形内 画一些圆，用圆的内部表示集合，集合之间 的相互关系和有关的运算可以用文氏图给予 形象的描述。 集合的特性集合的特性 确定性确定性 确定性是指一旦给定了集合确定性是指一旦给定了集合A A，对于任意元素，对于任意元素a a，我，我 们就可以准确地判定们就可以准确地判定a a是否在是否在A A中。中。 如：如：A=A=x x| |x x是自然数，且是自然数，且x x100100则必有则必有3030 A A，

10、101101 A A 互异性互异性 互异性是指集合中的元素之间是彼此不同的，即集互异性是指集合中的元素之间是彼此不同的，即集 合中不允许出现重复的元素。合中不允许出现重复的元素。 如：集合如：集合 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,

11、 , c c 与与 A=A=a a, , b b, , c c , , a a, , b b 相同相同 抽象性抽象性 抽象性是指集合中元素是抽象的，甚至可以是集合。抽象性是指集合中元素是抽象的，甚至可以是集合。 如：如：A = a, a, b, b, c； 相关概念相关概念 有限集有限集 由有限个元素由有限个元素a1,an组成的集合称为有限集。组成的集合称为有限集。 基数（或势）基数（或势） 若集合若集合A是有限集，则集合是有限集，则集合A中的元素个数称为集中的元素个数称为集 合合A的基数（或势），通常记作的基数（或势），通常记作|A|。 无限集无限集 无限集是指由无限个元素组成的集合。无限集

12、是指由无限个元素组成的集合。 空集空集 不含有任何元素的集合是空集。记不含有任何元素的集合是空集。记或或 。 1.1.2 子集子集 子集子集集合间的包含关系集合间的包含关系 给定两个集合A和B，若A中的任意元素 都属于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

13、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，且，且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 幂集

14、示例幂集示例 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元组元组 ),(yx O ),(xy n=2n=3 .,., ,.,),.,( 212121nnn xxxxxxxxx ),(zyx O 序偶序偶 .,),.,(),.,( 2121 iyxyyyxxx iinn 1.1.5 笛卡儿积笛卡儿积 设设A1，A2，An是集合，称集合是集合，称集合 为为A1，A2，An的笛卡儿积（直积，叉积）的笛卡儿积（直积，叉积） .

15、,.,2 , 1,| ),.,(. 2121 niAxxxxAAA iinn .By,Ax| )y, x(BA 笛卡儿积定理笛卡儿积定理 .| ,|mnBAnBmA 1.2 映射的有关概念映射的有关概念 映射就是函数，研究的是任意两个集映射就是函数，研究的是任意两个集 合之间的一种对应关系。合之间的一种对应关系。 映射是现代数学中的基本概念。函数映射是现代数学中的基本概念。函数 在信息科学中得到了充分的应用。在信息科学中得到了充分的应用。 与集合一样，映射贯穿本书的所有内与集合一样，映射贯穿本书的所有内 容，深刻理解映射的有关内容，对于其他容，深刻理解映射的有关内容，对于其他 内容的学习是至关

16、重要的。内容的学习是至关重要的。 1.2.1 映射的定义映射的定义 任意给定两个集合任意给定两个集合A和和B，若存在对应法则，若存在对应法则 f ，使得对于，使得对于任意任意x A，均存在，均存在唯一唯一的的y B与它与它 对应，则称对应，则称 f 是集合是集合A到到B的一个映射，或称的一个映射，或称A 到到B的一个函数，记为的一个函数，记为 f :AB。 A B f BAf: 映射的两个特点映射的两个特点 假定假定 f :AB, y= f(x) ,通常把通常把x称为自变量，其取值范围称称为自变量，其取值范围称 为为定义域记为定义域记为dom f ；将；将y称为因变量，其取值范围称为值域，称为

17、因变量，其取值范围称为值域， 记为记为ran f。 映射映射f的定义域是集合的定义域是集合A,记为记为dom f =A； 对于任意对于任意xA,对应于对应于B中唯一的元素中唯一的元素f(x),x为为f的自的自 变量变量(也称为原像也称为原像),f(x)称为称为x在映射在映射f下的像下的像,通常记为通常记为 y= f(x). 映射的表示映射的表示 （1）解析表达式）解析表达式 （2）图示）图示 （3）表格法）表格法 B BA A （读作（读作B B上上A A）定义）定义 .:|BAffB A 定理：定理： 对于集合对于集合A和和B，若，若|A|=m，|B|=n，则，则|BA|=nm。 教材教材P

18、7例题例题1-5 1.2.2 映射的性质映射的性质 1、单射、单射 假设假设f :AB,如果对任意如果对任意x1,x2 A,由由f(x1) = f(x2) 可推出可推出x1=x2,则称则称f是是A到到B的单射的单射,或称或称f是是 A到到B的一对一映射。的一对一映射。 f BA .)()(, 212121 xxxfxfAxx ).()(, 212121 xfxfxxAxx 例：设例：设f f:NN:NN，f f(x)=2x,(x)=2x,则则f f是是N N到到N N的单射，试证明之。的单射，试证明之。 1.2.2 映射的性质映射的性质 2、满射、满射 假设假设f :AB，如果对任意，如果对任

19、意y B,均存在均存在x A，使，使 得得y = f(x)，则称，则称f是是A到到B的满射，或称的满射，或称f是是A到到B 的映上的映上(onto)的映射。的映射。 f BA 例：例： 设设f:ZN, f(x)=|x|, f:ZN, f(x)=|x|, 则则f f是是Z Z到到N N的满射。的满射。 1.2.2 映射的性质映射的性质 3、双射、双射 假设假设f :AB，f 既是单射又是满射，则称既是单射又是满射，则称f是是A到到B的的 双射双射,或称或称f 是是A到到B的一的一 一对应。一对应。 f BA 例：试建立一个例：试建立一个Z到到N的一的一 一对应。一对应。 2x x0 f(x) =

20、 2|x| - 1 x0 习题习题1.2 (2)1.2 (2) 置换的定义置换的定义 例如：写出例如：写出A=1，2，3上的所有置换。上的所有置换。(个数：个数：n!) , 321 321 1 p , 312 321 2 p, 123 321 3 p , 231 321 4 p, 132 321 5 p . 213 321 6 p 123 (1)(2)(3) p ppp 1.2.3 逆映射逆映射 ，则，则 1.2.4 复合映射复合映射 x y=f(x)z=g(y)= g(f(x) h f g 1.2.4 复合映射复合映射 a b c 1 2 3 f g 复合映射例题复合映射例题 f f( (A

21、 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 on A)，记为，记为IA 显然恒等映射是唯一存在的。显然恒等映射是唯一

22、存在的。 【定理定理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 g 是双射是双射. 【定理定理1-11】设设f: : A

23、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 运算的定义及性质运算的定义及性质 运算是由已知对象得出新对象的一种运算是由已知对象得出新对象的一种 方法。运算是讨论对象之间有何联系的一方法。运算是讨论对象之间

24、有何联系的一 种方法。种方法。 运算本质上是映射，但运算更侧重于运算本质上是映射，但运算更侧重于 研究运算满足的一些运算性质。研究运算满足的一些运算性质。 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元运算。元运算。 如如y = f(xy = f(x1 1,

25、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元封闭运算元封闭运算(clo

26、sed 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加法运算和模加法运算

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

28、)T = A 1.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中的幂等元，并判断是否满足幂等率？中的幂等元，并判断是

29、否满足幂等率？ 例例2 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：设：

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

31、*满足结合律。满足结合律。 例例1 1：验证整数集合：验证整数集合Z Z上的加法运上的加法运 算和减法运算是否满足结合率。算和减法运算是否满足结合率。 531455 343144 212133 431422 543211 54321* 例例2 2：判定集合：判定集合A=1,2,3,4,5A=1,2,3,4,5见见 表，是否满足交换率和结合率？表，是否满足交换率和结合率？ 例例3 3：判定映射的复合运算是否：判定映射的复合运算是否 满足结合率？满足结合率？ 1.3.2 运算的性质运算的性质 5、单位元素、单位元素 【定义定义】设设 * 是是A上的上的2元代数运算，若存在元代数运算，若存在e e

32、A A ， 对于任意的对于任意的x x A A ，下列条件均成立：，下列条件均成立： 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、零

33、元素、零元素 【定义定义】设设 * * 是是A A上的上的2 2元代数运算，若存在元代数运算，若存在 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元代

34、数运算且有单位元元代数运算且有单位元 素素e e，若对于，若对于x x A A，存在，存在y y A A，下列条件均成立：下列条件均成立： y * x = e x * y = e 则称则称y y为为x x的逆元素。的逆元素。 注意：注意： 1 1、一个方阵关于乘法运算的逆元是其逆矩阵，、一个方阵关于乘法运算的逆元是其逆矩阵， 单位元素是单位矩阵；单位元素是单位矩阵； 2 2、一个双射的映射的复合运算的逆元是其逆映、一个双射的映射的复合运算的逆元是其逆映 射。单位元素是恒等映射。射。单位元素是恒等映射。 1.3.2 运算的性质运算的性质 例例1 1：分别考察：实数集合：分别考察：实数集合R R中

35、各元素关于加法运算和中各元素关于加法运算和 乘法运算的逆元素。乘法运算的逆元素。 例例2 2：设：设A=a, b, c,A=a, b, c,关于关于* *运算的运算表。分析逆元。运算的运算表。分析逆元。 结论：一个元素的逆元不一定存在，存在也不一结论：一个元素的逆元不一定存在，存在也不一 定唯一。定唯一。习题习题1.3(8)1.3(8) cacc aabb cbaa cba* 【定理】设【定理】设A A关于关于* *运算的单位元素为运算的单位元素为e e 且且* *运算满足结合律，若运算满足结合律，若x x在在A A中有左逆中有左逆 元元y y及右逆元及右逆元z z，则，则y = zy = z

36、。进而，对于。进而，对于 一个满足结合律的运算来说，若一个元一个满足结合律的运算来说，若一个元 素有逆元则其逆元是唯一的。素有逆元则其逆元是唯一的。 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

37、y = z x y = z 则称则称* *具有消去性，或称具有消去性，或称* *满足消去律。满足消去律。 例：验证整数集合例：验证整数集合Z Z上的加法运算上的加法运算+ +和乘法运算均满和乘法运算均满 足消去律。足消去律。 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)

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

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

40、成立： (x * y) = (x) (y) (x y) = (x) *(y) 则称这三种运算满足则称这三种运算满足De MorganDe Morgan律律 1.4 集合的运算集合的运算 1、并运算、并运算 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

41、x BB 阴影部分为阴影部分为 ABAB U U B B A A 如：设如：设 A=a，b， c，d，B=b，d， e，f，求求ABAB 定理：设定理：设A A和和B B是集合，则是集合，则ABAB是包含集合是包含集合A A和和B B的最小集合。的最小集合。 并运算的性质并运算的性质 设设A A，B B，C C是集合，则是集合，则 1 1、幂等律：、幂等律：AA = AAA = A 2 2、交换律：、交换律：AB = BAAB = BA 3 3、结合律：、结合律：(AB)C=A(BC)(AB)C=A(BC) 4 4、A=AA=A= =A(A(空集空集是并运算的单位元素是并运算的单位元素) )

42、5 5、UA=AU=U(UA=AU=U(全集全集U U是并运算的零元素是并运算的零元素) ) 1.4.2 交运算交运算 【定义】设【定义】设A A和和B B是两个任意集合，由所有属于是两个任意集合，由所有属于A A又属又属 于于B B的元素组成的集合，称为的元素组成的集合，称为A A和和B B的交集，通常记作的交集，通常记作 ABAB。即。即 AB=AB=x x| |x x A A且且x x BB 阴影部分为阴影部分为 ABAB U U B B A A 如：设如：设 A=a，b， c，d，B=b，d， e，f，求求A AB B 定理：设定理：设A A和和B B是集合，则是集合，则A AB B是

43、包含在集合是包含在集合A A和和B B中的最大集合。中的最大集合。 交运算的性质交运算的性质 设设A A，B B，C C是集合，则是集合，则 1 1、幂等律：幂等律：AA=AAA=A 2 2、交换律：、交换律：AB= BAAB= BA 3 3、结合律：、结合律：(AB)C=A (BC)(AB)C=A (BC) 4 4、A=AA=A= =（空集（空集是交运算的零元素是交运算的零元素） 5 5、UA=AU=AUA=AU=A（全集（全集U U是交运算的单位元素）是交运算的单位元素） 交和并运算的性质交和并运算的性质 并、交运算的混合性质并、交运算的混合性质( (吸收律吸收律) )： 设设A A，B

44、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是全集，对于集合是全集，对于集合A A，定义，定义A A的补集如下：的补集如下： =x|x=x|x U U，但，但x x A A 注意：一个集合的补集依赖于全集的选取。注意：一个集合的补集依赖于全集的选取。 A 阴影部分为阴影部分为A A 的补集的补集 U U A A 例：设集合例：设集合A=a , b ,

45、 c 分别取全集分别取全集U=a , b , c , d 和和U=a , b , c , a , b , b , c , c , 求求A的补集。的补集。 补运算的性质补运算的性质 补运算的性质：补运算的性质： （1）A =U （2）A = De Morgan律律 A A ABAB BABA 1.4.4 差运算差运算 【定义】设【定义】设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 BB

46、 U U A 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 B = ABA B = AB 1.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 U A 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）