离散数学教案 《离散数学》课程教学教案 内蒙古农业大学计算机与信息工程学院 《离散数学》课程建设组
离散数学教案 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， 记作 aA；a 不属于 A 或 a 不是 A 的元素，记 作 aA， 或者(aA)。 集合的元素一旦给定，这一集合便完全确立。这一事实被形式地叙述为外延公理
离散数学教案 外延公理：两集合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；否则，记为 AB。 外延公理可形式表为： A=B(x)(xAxB) 或者 A=B(x)(xA→xB)(x)(xB→xA) 顺便指出，在应用外延公理证明集合 A 与 B 相等时，只需考察： 对于任意元素 x，应有下式 xAxB 成立即可。这就是说，证明两集合相等时可按此法行事。 表示一个特定集合，基本上有两种方法： 一是枚举法，在可能时列出它的元素，元素之间用逗号分开，再用花括号括起。 如：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)为真当且仅当 cS。从而有 xSxP(x) 例如，(1)可表为 A={x|x 是英文字母表中元音字母} 在用性质来描述集合时，可表述为概括原理或子集合公理。 子集公理： 对于任给集合 A 和性质 P，存在集合 B，使得 B 中元素恰为 A 中满足 P 的那些元 素。 子集公理可形式地表为 (B)(x)(xBxA(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， 并 记为 AB。 本定义也可表成 AB(x)(xA→xB) 这表明，要证明 AB，只需对任意元素 x，有下式 xA→xB 成立即可。 此外，若集合 B 不包含集合 A，记为 AB。 定义 3.1.2 设 A 和 B 是两个集合，若 AB 且 AB，则称 A 是 B 的真子集，记为 AB，也称 B 真包含 A。该定义也可表为 AB(ABAB) 定义 3.1.3 如果一个集合包含了所要讨论的每一个集合，则称该集合为全集， 记为 U 或 E。它可形式地表为 U={x|P(x)P(x)} 其中 P(x)为任何谓词公式。 显然，全集 U 即是第二章中的全总论域。于是，每个元素 x 都属于全集 U，即命 题(x)(xU)为真。由定义易知，对任意集合 A，都有 AU
离散数学教案 在实际应用中，常常把某个适当大的集合看成全集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→xA 总 是为真。 注意，与{}是不同的。{}是以为元素的集合，而没有任何元素，能用 构成集合的无限序列： (1)，{}，{{}}，··· 该序列除第一项外，每项均以前一项为元素的集合。 (2)，{}，{，{}}，··· 该序列除第一项外，每项均以前面各项为元素的集合。它即是冯· 诺依曼在 1924 年使用空集 给出自然数的集合表示： 0:= ，1:={} ，2:={ ,{}} ，··· 定理 3.1.1 空集是唯一的 定理 3.1.2 (ⅰ) 对任一集合 A， 有 AA。 (ⅱ) 若 AB 且 BC， 则 AC。 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=实数集合