离散数学第三章课件.ppt

离 散 数 学 第二篇集合论 集合与关系 函数 离 散 数 学 第三章 集合与关系 目录 3-1 集合的概念与表示法 3-2 集合的运算 3-3 包含排斥原理 3-4 序偶与笛卡尔积 3-5 关系及其表示 3-6 关系的性质 3-7 复合关系和逆关系 3-8 关系的闭包运算 3-9 集合的划分与覆盖 3-10 等价关系与等价类 3-11 相容关系 3-12 次序关系 小结 集合初步知识 基本概念及集合的表示方法 集合间的关系 特殊集合 集合的运算 ＊包含排斥原理 3-1 集合的概念和表示法 1.集合与元素集合是个最基本的概念。 集合：是由确定的对象(客体)构成的集体。用大写的英文字母表示。 这里所谓“确定”是指：论域内任何客体，要么属于这个集合，要么不属于这个集合，是唯一确定的。元素：集合中的对象，称之为元素。∈：表示元素与集合的属于关系。 例如，N表示自然数集合，2∈N，而1.5不属于N 写成?(1.5∈N), 或写成 1.5?N。 3-1 集合的概念和表示法 2. 有限集合与无限集合这里对有限集合与无限集合只给出朴素的定义，以后再给出严格的形式定义。 有限集合：元素是有限个的集合。如果A是有限集合，用|A|表示A中元素个数。例如，A={1,2,3}, 则|A|=3。 无限集合：元素是无限个的集合。 对无限集合的所谓”大小”的讨论，以后再进行。 3-1 集合的概念和表示法 3.集合的表示方法 列举法：将集合中的元素一一列出，写在大括号内。 例如，N={1,2,3,4,……} A={a,b,c,d} 描述法：用句子(或谓词公式)描述元素 的属性。例如，B={x| x是偶数}C={x|x是实数且2≤x≤5} 一般地，A={x|P(x)}, 其中P(x)是谓词公式，如果论域内客体a使得P(a)为真，则a∈A，否则a?A。 3-1 集合的概念和表示法 4. 说明 ⑴集合中的元素间次序是无关紧要的，但是必须是可以区分的，即是不同的。例如A={a,b,c,a}，B={c,b,a,}，则A与B是一样的。 ⑵对集合中的元素无任何限制，例如令A={人，石头，1，Ｂ}, B={Φ,{Φ}} ⑶本书中常用的几个集合符号的约定：自然数集合N= {1,2,3,……}整数集合I，实数集合R，有理数集合Q 3-1 集合的概念和表示法 ⑷集合中的元素也可以是集合，下面的集合的含义不同： 如a：张书记{a}:党支部(只有一个书记){{a}}：分党委(只有一个支部){{{a}}}：党委 (只有一个分党委){{{{a}}}}：市党委(只有一个党委) 3-1 集合的概念和表示法 5.集合间的关系 (1).被包含关系(子集) ? ① . 定义3-1.1 ：A、B是集合，如果A中元素都是B中元素，则称B包含A，A包含于B，也称A是B的子集。记作A?B。文氏图表示如右下图。例如，N是自然数集合，R是实数集合，则N?R 谓词定义： A?B??x(x∈A?x∈B) 3-1 集合的概念和表示法 ②. 性质： 有自反性，对任何集合A有A?A。 有传递性，对任何集合A、B、C，有A?B且 B?C ，则A?C。 有反对称性，对任何集合A、B，有A?B且 B?A ，则A=B。 3-1 集合的概念和表示法 (2)相等关系 ① . 定义3-1.2 ：A、B是集合，如果它们的元素完全相同，则称A与B相等。记作A=B。 定理3-1.1：A=B，当且仅当A?B且 B?A。 证明：充分性(反证法)，已知A?B且 B?A，假设A≠B，则至少有一个元素a,使得a∈A而a?B；或者a∈B而a?A。如果a∈A而 a?B，则与A?B矛盾。如果a∈B而a?A，则与 B?A矛盾。所以A=B。 必要性显然成立，因为如果A=B，则必有A?B且 B?A。 3-1 集合的概念和表示法 谓词定义：A=B?A?B?B?A ??x(x∈A?x∈B)??x(x∈B?x∈A) ??x((x∈A?x∈B)?(x∈B?x∈A)) ??x(x∈A?x∈B) ② . 性质 有自反性，对任何集合A，有A=A。 有传递性，对任何集合A、B、C，如果有A=B且 B=C ，则A=C。 有对称性，对任何集合A、B，如果有A=B，则B=A。 3-1 集合的概念和表示法 (3)真被包含关系(真子集) ? ① . 定义3-1.3：A、B是集合，如果A?B且A≠B，则称B真包含A，A真包含于B，也称A是B的真子集。记作A?B。 谓词定义：A?B?A? B?A≠B ??x(x∈A?x∈B)???x(x∈A?x∈B) ??x(x∈A?x∈B)(??x(x∈A?x∈B)???x(x∈B?x∈A)) ?(?x(x∈A?x∈B)???x(x∈A?x∈B))(?x(x∈A?x∈B)? ??x(x∈