《离散数学》课程教学资源（教案讲义）第三章 集合与关系

离散数学教案 《离散数学》课程教学教案 内蒙古农业大学计算机与信息工程学院 《离散数学》课程建设组

离散数学教案 1 《离散数学》课程教学教案 内蒙古农业大学计算机与信息工程学院 《离散数学》课程建设组

离散数学教案 集合与关系 一、学习目的与要求 本章目的是介绍集合的基本概念，讲授集合运算的基本理论，关系的定义与运算。 通过本章的学习，使学生了解集合是数学的基本语言，掌握主要的集合运算方法和关 系运算方法，为学习后续章节打下良好基础。 二、知识点 1.集合的基本概念与表示方法； 2.集合的运算： 3.序偶与笛卡尔积： 4.关系及其表示、关系矩阵、关系图： 5.关系的性质，符合关系、逆关系： 6.关系的闭包运算： 7.集合的划分与覆盖、等价关系与等价类：相容关系： 8.序关系、偏序集、哈斯图。 三、要求 1.识记 集合的层次关系、集合与其元素间的关系，自反关系、对称关系、传递关系的识 别，复合关系、逆关系的识别。 2.领会 领会下列概念：两个集合相等的概念几证明方法，关系的闭包运算，关系等价性 证明。 四、主要内容 第3章集合 3.1集合论基础 1.集合与元素 所谓集合，是指某些可辨别的不同对象的全体，将用大写字母A,B,X,Y,···表 示之。组成集合的对象称为集合的元素或成员，将用小写字母a,b,x,y···表 示之。a是A的元素或a属于A,记作aeA:a不属于A或a不是A的元素，记 作agA,或者l(aeA)。 集合的元素一旦给定，这一集合便完全确立。这一事实被形式地叙述为外延公理

离散数学教案 2 集合与关系 一、学习目的与要求 本章目的是介绍集合的基本概念，讲授集合运算的基本理论，关系的定义与运算。 通过本章的学习，使学生了解集合是数学的基本语言，掌握主要的集合运算方法和关 系运算方法，为学习后续章节打下良好基础。 二、知识点 1．集合的基本概念与表示方法； 2．集合的运算； 3．序偶与笛卡尔积； 4．关系及其表示、关系矩阵、关系图； 5．关系的性质，符合关系、逆关系； 6．关系的闭包运算； 7．集合的划分与覆盖、等价 关系与等价类；相容关系； 8．序关系、偏序集、哈斯图。 三、要求 1．识记 集合的层次关系、集合与其元素间的关系，自反关系、对称关系、传递关系的识 别，复合关系、逆关系的识别。 2．领会 领会下列概念：两个集合相等的概念几证明方法，关系的闭包运算，关系等价性 证明。 四、主要内容 第 3 章 集合 3.1 集合论基础 1.集合与元素 所谓集合，是指某些可辨别的不同对象的全体，将用大写字母 A，B，X，Y，··· 表 示之。组成集合的对象称为集合的元素或成员，将用小写字母 a，b，x，y··· 表 示之。a 是 A 的元素或 a 属于 A， 记作 aA；a 不属于 A 或 a 不是 A 的元素，记 作 aA， 或者(aA)。 集合的元素一旦给定，这一集合便完全确立。这一事实被形式地叙述为外延公理

离散数学教案 外延公理：两集合A和B相等，当且仅当它们有相同的元素。 若A与B相等，记为A=B:否则，记为AB。 外延公理可形式表为： A=B白(Vx)(x∈AxeB) 或者 A=B台(Hx)(x∈A→xeB)A(Hx)(xeB→x∈A) 顺便指出，在应用外延公理证明集合A与B相等时，只需考察： 对于任意元素x,应有下式 x∈Ax∈B成立即可。这就是说，证明两集合相等时可按此法行事。 表示一个特定集合，基本上有两种方法： 是枚举法，在可能时列出它的元素，元素之间用逗号分开，再用花括号括起。 如：A={a,e,i,o,u (1) 表明集合A是由字母a,e,I,0和u为元素构成的。 二是谓词法，用谓词公式来确定集合。即个体域中能使谓词公式为真的那些元素， 确定了一个集合，因为这些元素都具有某种特殊性质。若P(x)含有一个自由变元的 谓词公式，则{xP(x)}定义了集合S,并可表为 S=(xIP(x)} 由此可见，P(C)为真当且仅当c∈S。从而有 xESxEP(x) 例如，(1)可表为 A={xx是英文字母表中元音字母到 在用性质来描述集合时，可表述为概括原理或子集合公理。 子集公理： 对于任给集合A和性质P,存在集合B,使得B中元素恰为A中满足P的那些元 素。 子集公理可形式地表为 (臼B)(x)(x∈Bx∈AAp(x) 其中p(x)为不含B自由出现。 子集公理的提出，避免了悖论，使集合论得以存在和发展

离散数学教案 3 外延公理：两集合 A 和 B 相等，当且仅当它们有相同的元素。 若 A 与 B 相等，记为 A=B；否则，记为 AB。 外延公理可形式表为： A=B(x)(xAxB) 或者 A=B(x)(xA→xB)(x)(xB→xA) 顺便指出，在应用外延公理证明集合 A 与 B 相等时，只需考察： 对于任意元素 x，应有下式 xAxB 成立即可。这就是说，证明两集合相等时可按此法行事。 表示一个特定集合，基本上有两种方法： 一是枚举法，在可能时列出它的元素，元素之间用逗号分开，再用花括号括起。 如：A={a,e,i,o,u} (1) 表明集合 A 是由字母 a, e, I ,o 和 u 为元素构成的。 二是谓词法，用谓词公式来确定集合。即个体域中能使谓词公式为真的那些元素， 确定了一个集合，因为这些元素都具有某种特殊性质。若 P(x)含有一个自由变元的 谓词公式，则{x|P(x)}定义了集合 S，并可表为 S={x|P(x)} 由此可见，P(c)为真当且仅当 cS。从而有 xSxP(x) 例如，(1)可表为 A={x|x 是英文字母表中元音字母} 在用性质来描述集合时，可表述为概括原理或子集合公理。 子集公理： 对于任给集合 A 和性质 P，存在集合 B，使得 B 中元素恰为 A 中满足 P 的那些元 素。 子集公理可形式地表为 (B)(x)(xBxA(x)) 其中(x)为不含 B 自由出现。 子集公理的提出，避免了悖论，使集合论得以存在和发展

离散数学教案 应该指出的是： ①集合并不决定于它的元素展示方法。集合的元素被重复或重新排列，集合并不 改变，即{a,a,e,i,o,=【a,u,e,o,i。但有时对重复出现的元素都认为 是集合的元素，这种集合称为多重集。即{a,a,e,i,o,u,u≠{a,e,i,0,u。 本书中集合在不特别指明时，都指前者，即①中的集合。 ②集合的元素可以是具体事物，可以是抽象概念，也可以是集体，不是集合的元 素称为本元。如，一本书，一支笔，集合{1,2,3}可以组成集合={一本书，一支笔， {1,2,3)。特别地，以集合为元素的集合称为集合族或集合类如A={1,2,3引， {8,9,6}。 ③集合中元素之间可以有某种关联，也可以彼此毫无关系。 2.子集、全集与空集 子集是描述一个集合与另一个集合之间的关系，其定义如下。 定义3.1.1设A和B是任意两个集合，如果集合A的每个元素，都是集合B 中的一个元素，则称A是B的子集，或称A被包含于B中，或者说B包含A,并 记为ACB。 本定义也可表成 AcB≌(/x)(x∈A→x∈B) 这表明，要证明AB,只需对任意元素x,有下式 x∈A→x∈B成立即可。 此外，若集合B不包含集合A,记为A生B。 定义3.1.2设A和B是两个集合，若AB且AB,则称A是B的真子集，记为 AcB,也称B真包含A。该定义也可表为 ACB台(ACBAA≠B) 定义3.1.3如果一个集合包含了所要讨论的每一个集合，则称该集合为全集， 记为U或E。它可形式地表为 U={xP(x)vP(x)】 其中P(x)为任何谓词公式。 显然，全集U即是第二章中的全总论域。于是，每个元素x都属于全集U,即命 题（付x)(x∈）为真。由定义易知，对任意集合A,都有ACU。 4

离散数学教案 4 应该指出的是： ①集合并不决定于它的元素展示方法。集合的元素被重复或重新排列，集合并不 改变，即{a, a ,e, i, o, u}= { a, u, e, o, i}。但有时对重复出现的元素都认为 是集合的元素，这种集合称为多重集。即{a, a, e, i, o, u, u}{a, e, i, o, u}。 本书中集合在不特别指明时，都指前者，即①中的集合。 ②集合的元素可以是具体事物，可以是抽象概念，也可以是集体，不是集合的元 素称为本元。如，一本书，一支笔，集合{1,2,3}可以组成集合 B={一本书，一支笔， {1,2,3}} 。特别地，以集合为元素的集合称为集合族或集合类如 A={{1,2,3}, { 8,9,6}}。 ③集合中元素之间可以有某种关联，也可以彼此毫无关系。 2. 子集、全集与空集 子集是描述一个集合与另一个集合之间的关系，其定义如下。 定义 3.1.1 设 A 和 B 是任意两个集合，如果集合 A 的每个元素，都是集合 B 中的一个元素，则称 A 是 B 的子集，或称 A 被包含于 B 中，或者说 B 包含 A， 并 记为 AB。 本定义也可表成 AB(x)(xA→xB) 这表明，要证明 AB，只需对任意元素 x，有下式 xA→xB 成立即可。 此外，若集合 B 不包含集合 A，记为 AB。 定义 3.1.2 设 A 和 B 是两个集合，若 AB 且 AB，则称 A 是 B 的真子集，记为 AB，也称 B 真包含 A。该定义也可表为 AB(ABAB) 定义 3.1.3 如果一个集合包含了所要讨论的每一个集合，则称该集合为全集， 记为 U 或 E。它可形式地表为 U={x|P(x)P(x)} 其中 P(x)为任何谓词公式。 显然，全集 U 即是第二章中的全总论域。于是，每个元素 x 都属于全集 U，即命 题(x)(xU)为真。由定义易知，对任意集合 A，都有 AU

离散数学教案 在实际应用中，常常把某个适当大的集合看成全集U。 定义3.1.4没有任何元素的集合，称为空集，记为②，它可形式地表为： @=(xlP(x)APP(x)} 其中P(x)为任何谓词公式。 由定义可知，对任何集合A,有OcA。这是因为任意元素x,公式x∈O→x∈A总 是为真。 注意，o与{@)是不同的。{@}是以0为元素的集合，而0没有任何元素，能用0 构成集合的无限序列： (1)0,{0),{0},··· 该序列除第一项外，每项均以前一项为元素的集合 (2)a,{a1,{o,{@,··· 该序列除第一项外，每项均以前面各项为元素的集合。它即是冯·诺依曼在1924 年使用空集⑦给出自然数的集合表示： 0:=0,1:={@,2:={0,{a},··· 定理3.1.1空集是唯一的 定理3.1.2（i)对任一集合A,有ACA。 (i)若AcB且BsC,则AcC。 3.集合的基数 表示集合中元素多少或度量集合大小的数，称作集合的基数或势。一个集合A的 基数，记为A。 如果一个集合恰有m个不同的元素，且m是某个非负整数，称该集合是有限的 或有穷的，否则称这个集合为无限的或无穷的。例如，在本书中常用有穷集有： Nme{0,1,2,···,m-10 本书中常见的无穷集合有： ={0,1,2,3,···},即自然数集合。 27={···,-2,-1,0,1,2,3,··},即整数集合。 Z+={1,2,3,···},即正整数集合。 Q=有理数集合。 R=实数集合

离散数学教案 5 在实际应用中，常常把某个适当大的集合看成全集 U。 定义 3.1.4 没有任何元素的集合，称为空集，记为，它可形式地表为： ={x|P(x)P(x)} 其中 P(x)为任何谓词公式。 由定义可知，对任何集合 A，有A。这是因为任意元素 x，公式 x→xA 总 是为真。 注意，与{}是不同的。{}是以为元素的集合，而没有任何元素，能用 构成集合的无限序列： (1)，{}，{{}}，··· 该序列除第一项外，每项均以前一项为元素的集合。 (2)，{}，{，{}}，··· 该序列除第一项外，每项均以前面各项为元素的集合。它即是冯· 诺依曼在 1924 年使用空集 给出自然数的集合表示： 0:= ，1:={} ，2:={ ,{}} ，··· 定理 3.1.1 空集是唯一的 定理 3.1.2 (ⅰ) 对任一集合 A， 有 AA。 (ⅱ) 若 AB 且 BC， 则 AC。 3．集合的基数 表示集合中元素多少或度量集合大小的数，称作集合的基数或势。一个集合 A 的 基数，记为|A|。 如果一个集合恰有 m 个不同的元素，且 m 是某个非负整数，称该集合是有限的 或有穷的，否则称这个集合为无限的或无穷的。例如，在本书中常用有穷集有： Nm={0,1,2,···,m-1} 本书中常见的无穷集合有： N={0,1,2,3,···}，即自然数集合。 Z={···,-2,-1,0,1,2,3,···}，即整数集合。 Z+={1,2,3,···}，即正整数集合。 Q=有理数集合。 R=实数集合

离散数学教案 C=复数集合 4.集合的幂集 一个集合的幂集是指该集合所有子集的集合，即是由这些子集所组成的集合族。 定义3.1.5设A为一集合，A的幂集是一集合族，记为P(A) P(A)=(BIBCA} 由定义可知，OeP(A),AeP(A). 5.文氏图 文氏(Wenn)图是一种利用平面上的点构成的图形来形象展示集合的一种方法。 全集U用一个矩形的内部表示，其他集合用矩形内的园面或一封闭曲线圈成的面积 来表示。 如果AcB,则表示A的圆面一般将完全落在表示B的圆面内，如图1中(a)。如 果A与B没有公共元素，那么表示A的圆面将同表示B的圆面分开，如图3-1中(b)。 当A和B是两个任意的集合时，可能会是：有些元素在A中但不在B中，有些元素在 B中却不在A中，有些元素同时在A和B中，有些元素则既不在A中也不在B中，因 此用图1中(c)表示任意两个集合A和B。 最后给出集合的形式定义结束本节。 定义3.1.6A为集合=（臼x)(x∈AvA=☑）。 这里等号“=”表示定义为的意义，是表示“定义为”还是表示“一般相等”的 意义，由上下文来区分 3.2集合运算及其性质 集合运算是指用已知的集合去生成新的集合。假设所有集合都是全集U的子集， 即这些集合是利用子集公理得到的。下面依次介绍常见的集合运算。 1.并、交和差运算 定义3.2.1设A和B是任意两个集合， ①A和B的并是集合，记为AUB, AUB={x|x∈Avx∈B ②A和B的交是集合，记为AnB, AnB={xx∈AAXEB ③A和B的差，或B关于A的相对补是集合，记为A-B, 6

离散数学教案 6 C=复数集合。 4．集合的幂集 一个集合的幂集是指该集合所有子集的集合，即是由这些子集所组成的集合族。 定义 3.1.5 设 A 为一集合，A 的幂集是一集合族，记为 P(A)， P(A)={B|BA} 由定义可知，P(A)，AP(A)。 5．文氏图 文氏(Venn) 图是一种利用平面上的点构成的图形来形象展示集合的一种方法。 全集 U 用一个矩形的内部表示，其他集合用矩形内的园面或一封闭曲线圈成的面积 来表示。 如果 AB，则表示 A 的圆面一般将完全落在表示 B 的圆面内，如图 1 中(a)。如 果 A 与 B 没有公共元素，那么表示 A 的圆面将同表示 B 的圆面分开，如图 3-1 中(b)。 当 A 和 B 是两个任意的集合时，可能会是：有些元素在 A 中但不在 B 中，有些元素在 B 中却不在 A 中，有些元素同时在 A 和 B 中，有些元素则既不在 A 中也不在 B 中，因 此用图 1 中(c)表示任意两个集合 A 和 B。 最后给出集合的形式定义结束本节。 定义 3.1.6 A 为集合=(x)(xAA=)。 这里等号“=”表示定义为的意义，是表示“定义为”还是表示“一般相等”的 意义，由上下文来区分。 3.2 集合运算及其性质 集合运算是指用已知的集合去生成新的集合。假设所有集合都是全集 U 的子集， 即这些集合是利用子集公理得到的。下面依次介绍常见的集合运算。 1．并、交和差运算 定义 3.2.1 设 A 和 B 是任意两个集合， ① A 和 B 的并是集合，记为 A∪B， A∪B={x|xAxB} ② A 和 B 的交是集合，记为 A∩B， A∩B={x|xAxB} ③ A 和 B 的差，或 B 关于 A 的相对补是集合，记为 A-B

离散数学教案 A-B-{x|x∈MAxeB} 定义3.2.2若A和B是集合，且AnB=⑦，则称A和B是不相交的。 如果C是个集合族，且C中任意两个不同元素都不相交，则称C中集合是两个不 相交的，或称C是两两不相交的集合族。 定理3.2.1任给集合A,B和C,则： ①AUB=BUA ②AnB=BnA ③(AUB)UC=AU(BUC ④(AnB)nC=An(BnC) 该定理表明，集合并和交运算满足交换律和结合律。 定理3.2.2任给集合A、B和C,则 DAU(Bnc)=(AUB)n(AUC) 2An (BUC)=(AnB)U(AnC) 该定理表明，集合运算并对交、交对并都是可分配的。 定理3.2.3任给集合A,B,C和D,则 ①若ACB,则AUB=B,AnB=A ②若ACB和CcD,则AUCCBUD,AnCEBnD 推论3.2.3①AUU-U,②AnU=A 定理3.2.4任给集合A,B和C,则 DA-(BUC)=(A-B)n(A-C) A-(BnC)=(A-B)U(A-C) 定义3.2.3设A是含有元素为集合的集合，或者集合族。 ①A的并是集合，记为UA, UA={x|(GB)(B∈AAx∈B)}=UB ②A的交是集合，记为nA, nA={x|(B)(BeA→x∈B)}=nB 定义3.2.4集合A的补是集合，记为A', A'=U-A={xIxEUAXEA)=(xlxgA} 定理3.2.5任给集合A,则

离散数学教案 7 A-B={x|xAxB} 定义 3.2.2 若 A 和 B 是集合，且 A∩B=，则称 A 和 B 是不相交的。 如果 C 是个集合族，且 C 中任意两个不同元素都不相交，则称 C 中集合是两个不 相交的，或称 C 是两两不相交的集合族。 定理 3.2.1 任给集合 A，B 和 C，则： ① A∪B=B∪A ② A∩B=B∩A ③ (A∪B)∪C=A∪(B∪C) ④ (A∩B)∩C=A∩(B∩C) 该定理表明，集合并和交运算满足交换律和结合律。 定理 3.2.2 任给集合 A、B 和 C，则 ① A∪(B∩C)=(A∪B)∩(A∪C) ② A∩(B∪C)=(A∩B)∪(A∩C) 该定理表明，集合运算并对交、交对并都是可分配的。 定理 3.2.3 任给集合 A，B，C 和 D，则 ① 若 AB，则 A∪B=B，A∩B=A ② 若 AB 和 CD，则 A∪CB∪D，A∩CB∩D 推论 3.2.3 ①A∪U=U，②A∩U=A 定理 3.2.4 任给集合 A，B 和 C，则 ① A-(B∪C)=(A-B)∩(A-C) ② A-(B∩C)=(A-B)∪(A-C) 定义 3.2.3 设 A 是含有元素为集合的集合，或者集合族。 ① A 的并是集合，记为∪A， ∪A={x|(B)(BAxB)}= ∪B ② A 的交是集合，记为∩A， ∩A={x|(B)(BA→xB)}= ∩B 定义 3.2.4 集合 A 的补是集合，记为 A’， A’=U-A={x|xUxA}={x|xA} 定理 3.2.5 任给集合 A，则

离散数学教案 ①AUA'=U, ②AnA'=O. 定理3.2.6任给集合A和B,则 B=A'iff AUB=U且AnB=O 该定理表明了①若A的补是B,则B的补是A,即A和B互补。②补的唯一性。 推论3.2.5①0'=0，②☑'=U 定理3.2.7任给集合A,则A”=A。 该定理表明了，A的补的补是A。 定理3.2.8任给集合A和B,则 ①(AUB)'=A'nB', ②(AnB)'=A'UB'。 定义3.2.5任给集合A和B,A和B的对称差是集合，记为A⊕B, A©B=(A-B)U(B-A)={x|(x∈AAXEB)V(x∈BAXEA)} 定理3.2.9任给集合A和B,则 AOB=(AUB)n(A'UB')=(AUB)-(AnB) 推论3.2.9①A'⊕B'=A⊕B ②AEB=BEA ③A⊕A=O 2.集合代数与对偶原理 本小节将形式地讨论由集合、集合变元、集合运算和圆括号所构成的集合代数 以及集合代数中的对偶原理。 与命题逻辑相似，对于给定集合实行集合运算，可以生成新的集合。同用大写英 文字母表示确定集合一样，也用大写字母表示不确定的集合，前者称为集合常元，后 者称为集合变元。集合变元用以集合常元代替后，才表示确定的集合。下面将给出集 合的合式公式定义。 定义3.2.6可按下列规则生成集合合式公式： ①单个集合变元是集合合式公式。 ②若A是集合合式公式，则A'也是集合合式公式。 ③若A和B是集合合式公式，则(AUB),(AnB),(A-B)和(A⊕B)也都是集合合 8

离散数学教案 8 ① A∪A’=U， ② A∩A’=。 定理 3.2.6 任给集合 A 和 B，则 B=A’ iff A∪B=U 且 A∩B= 该定理表明了①若 A 的补是 B，则 B 的补是 A，即 A 和 B 互补。②补的唯一性。 推论 3.2.5 ①U’=，②’=U 定理 3.2.7 任给集合 A，则 A”=A。 该定理表明了，A 的补的补是 A。 定理 3.2.8 任给集合 A 和 B，则 ① (A∪B)’=A’∩B’， ② (A∩B)’=A’∪B’。 定义 3.2.5 任给集合 A 和 B，A 和 B 的对称差是集合，记为 AB， AB =(A-B)∪(B-A)={x|(xAxB)(xBxA)} 定理 3.2.9 任给集合 A 和 B，则 AB=(A∪B)∩(A’∪B’)=(A∪B) - (A∩B) 推论 3.2.9 ① A’B’=AB ② AB=BA ③ AA= 2．集合代数与对偶原理 本小节将形式地讨论由集合、集合变元、集合运算和 圆括号所构成的集合代数 以及集合代数中的对偶原理。 与命题逻辑相似，对于给定集合实行集合运算，可以生成新的集合。同用大写英 文字母表示确定集合一样，也用大写字母表示不确定的集合，前者称为集合常元，后 者称为集合变元。集合变元用以集合常元代替后，才表示确定的集合。下面将给出集 合的合式公式定义。 定义 3.2.6 可按下列规则生成集合合式公式： ① 单个集合变元是集合合式公式。 ② 若 A 是集合合式公式，则 A’也是集合合式公式。 ③ 若 A 和 B 是集合合式公式，则(A∪B)，(A∩B)，(A-B)和(AB)也都是集合合

离散数学教案 式公式。 ④只有有限次使用①、②和③构成的符号串才是集合合式公式。 为方便计，简称集合合式公式为公式。 定义3.2.7用任意集合常元取代两个集合公式中的各个集合变元，若所得集合 是相等的，则称该二集合公式是相等的，简称等式。 因为集合公式相等，不依赖于取代集合变元的集合，故常称这些等式为集合恒等 式，或集合定律。它们刻划了集合运算的某些性质，这些性质描述一个代数，称为集 合代数。下面列出常用集合定律： (1)等幂律AUA=A AnA=A (2)结合律(AUB)UC=AU(BUC) (AnB)nC=An (Bnc) (3)交换律AUB=BUA AOB=BOA (4)分配律AU(BnC)=(AUB)n(AUC)An(BUC)=(AnB)U(AnC) (5)么律AUO=A AnU=A (6)零律AUU=U An0=0 (7)补律AUA'=U AnA'=☑ (8)吸收律AU(AnB)=A An(AUB)=A (9)德·摩根律(AUB)'=A'nB'(AnB)'=A'UB' (10)对合律 (A')=A 下面介绍集合代数中的对偶原理，它与命题逻辑中对偶原理也很相似。 对偶原理设E是集合代数中等式，将E中的U,∩，U和©的每一个出现分别 代以∩，U,⑦和U后得到一等式E*,称E*为E的对偶式。 显然，E也是*的对偶式，即E与E*互为对偶。 如果E是一集合恒等式，则*也是一集合恒等式。 可见，上述的集合定律中，凡成对的定律都是为对偶的。 3.3集合的笛卡尔积与无序积 笛卡尔积与无序积在后面讨论关系和图论时，都有重要应用。 首先引入有序对和无序对的概念。 定义3.3.1两个元素a,b组成二元组，若它们有次序之别，称为二元有序组， 或有序对，记为,称a为第一分量，b为第一分量：若它们无次序区分，称为

离散数学教案 9 式公式。 ④ 只有有限次使用①、②和③构成的符号串才是集合合式公式。 为方便计，简称集合合式公式为公式。 定义 3.2.7 用任意集合常元取代两个集合公式中的各个集合变元，若所得集合 是相等的，则称该二集合公式是相等的，简称等式。 因为集合公式相等，不依赖于取代集合变元的集合，故常称这些等式为集合恒等 式，或集合定律。它们刻划了集合运算的某些性质，这些性质描述一个代数，称为集 合代数。下面列出常用集合定律： （1）等幂律 A∪A=A A∩A=A （2）结合律 (A∪B)∪C=A∪(B∪C) (A∩B)∩C=A∩(B∩C) （3）交换律 A∪B=B∪A A∩B=B∩A （4）分配律 A∪(B∩C)=(A∪B)∩(A∪C) A∩(B∪C)=(A∩B)∪(A∩C) （5）幺律 A∪=A A∩U=A （6）零律 A∪U=U A∩= （7）补律 A∪A’=U A∩A’= （8）吸收律 A∪(A∩B)=A A∩(A∪B)=A （9）德·摩根律 (A∪B)’=A’∩B’ (A∩B)’=A’∪B’ （10）对合律 (A’)’=A 下面介绍集合代数中的对偶原理，它与命题逻辑中对偶原理也很相似。 对偶原理 设 E 是集合代数中等式，将 E 中的∪，∩，U 和的每一个出现分别 代以∩，∪，和 U 后得到一等式 E*，称 E*为 E 的对偶式。 显然，E 也是 E*的对偶式，即 E 与 E*互为对偶。 如果 E 是一集合恒等式，则 E*也是一集合恒等式。 可见，上述的集合定律中，凡成对的定律都是为对偶的。 3.3 集合的笛卡尔积与无序积 笛卡尔积与无序积在后面讨论关系和图论时，都有重要应用。 首先引入有序对和无序对的概念。 定义 3.3.1 两个元素 a,b 组成二元组，若它们有次序之别，称为二元有序组， 或有序对，记为，称 a 为第一分量，b 为第一分量；若它们无次序区分，称为

离散数学教案 二元无序组，或无序对，记为(a,b)。 若ab时，≠b,a>。但(a,b)=(6,a)。 定义3.3.2给定两个有序对x,y>和。当且仅当x和yV时，有序对 和相等，亦即 =iff (x=u)A(y=v) 可将有序对推广到n元有序组，它的第一分量是(-1)元有序组，并记为 ,或记为。类似地定义两个n元 有序组相等： x,x2,···,xn-l,xn>= iff (x1=y1)A(x2=y2)A···A(xn-1=yn-1)A(xn=yn） 下面将使用有序对和无序对分别定义笛卡儿积和无序积。 定义3.3.3给定集合A和B,若有序对的第一分量是A的元素，第二分量是B 的元素，所有这些有序对的集合，称为A和B的笛卡尔积，记为AxB, AxB={Kx,y>lx∈AAyEB} 定义3.3.4给定集合A和B,若无序对是由A中元素和B中元素组成，所有这 些无序对的集合，称为A和B的无序积，记为A&B。 A&B={(x,y)|xEAAyEB) 定理3.3.1任给集合A,B和C,则 ①A×(BUC)=(AxB)U(AxC) 2 Ax(BnC)=(AxB)(AxC) 3(AUB)xC=(AxC)U(BxC) ④(AnB)xC=(A×C)n(BxC) 笛卡尔积的概念可以推广到n个集合AL,A2,···,A如的笛卡尔积，它可表成： Ai=(A1xA2×···×An-1)×An,n≥2。 用归纳法不难证明，若Ai(1≤i≤)是有穷集合， 则|A1xA2x···xAn=A1|·|A2l·.·|An

离散数学教案 10 二元无序组，或无序对, 记为(a, b)。 若 ab 时，。但(a, b)=(b, a)。 定义 3.3.2 给定两个有序对和。当且仅当 x=u 和 y=v 时，有序对 和相等，亦即 = iff (x=u)(y=v) 可将有序对推广到 n 元有序组，它的第一分量是(n-1)元有序组，并记为 ,xn>，或记为。类似地定义两个 n 元 有序组相等： = iff (x1=y1)(x2=y2)···(xn-1=yn-1)(xn=yn) 下面将使用有序对和无序对分别定义笛卡儿积和无序积。 定义 3.3.3 给定集合 A 和 B，若有序对的第一分量是 A 的元素，第二分量是 B 的元素，所有这些有序对的集合，称为 A 和 B 的笛卡尔积，记为 AB， AB={|xAyB} 定义 3.3.4 给定集合 A 和 B，若无序对是由 A 中元素和 B 中元素组成，所有这 些无序对的集合，称为 A 和 B 的无序积，记为 A&B。 A&B={(x,y)|xAyB} 定理 3.3.1 任给集合 A，B 和 C，则 ① A(B∪C)=(AB)∪(AC) ② A(B∩C)=(AB)∩(AC) ③ (A∪B)C=(AC)∪(BC) ④ (A∩B)C=(AC)∩(BC) 笛卡尔积的概念可以推广到 n 个集合 A1,A2,···,An 的笛卡尔积，它可表成： Ai=(A1A2···An-1)An，n≥2。 用归纳法不难证明，若 Ai(1≤i≤n)是有穷集合， 则|A1A2···An|=|A1|·|A2|·.·|An|