《集合与关系》PPT课件.ppt

第三章集合与关系 为什么要研究集合 3 1集合的概念和表示方法 定义 集合set 把具有共同性质的一些对象汇集成一个整体 就构成一个集合 这些对象称为元素 element 或成员 member 用大写英文字母A B C 表示集合用小写英文字母a b c 表示元素a A 表示a是A的元素 读作 a属于A a A 表示a不是A的元素 读作 a不属于A 3 1 1有关集合的概念 n元集 n set 有n个元素的集合称为n元集 A 表示集合A中的元素个数 A是n元集 A n0元集 记作 1元集 或单元集 如 a b 有限集 finiteset A 是有限数 A 也叫有穷集 否则为无限集 3 1 2集合的表示方法 通常使用 列举法 和 叙述法 两种方法来给出一个集合 1 列举法 roster 列出集合中的全体元素 元素之间用逗号分开 然后用花括号括起来 例如A a b c d x y z B 0 1 2 3 4 5 6 7 8 9 集合中的元素不规定顺序C 2 1 1 2 集合中的元素各不相同C 2 1 1 2 2 1 3 1 2集合的表示方法 2 叙述法 definingpredicate 用谓词P x 表示 x具有性质P 用A x P x 表示元素具有性质P的集合A 如果P b 为真 那么b A 否则b A 例如P1 x x是英文字母A x P1 x x x是英文字母 a b c d x y z P2 x x是十进制数字B x P2 x x x是十进制数字 0 1 2 3 4 5 6 7 8 9 两种表示法可以互相转化 例如 E 2 4 6 8 x x 0且x是偶数 x x 2 k 1 k为非负整数 2 k 1 k为非负整数 两个集合相等的外延性原理 两个集合A B是相等的 当且仅当它们有相同的成员 记作A B 否则记作A B 集合的元素还可以是一个集合 例如 S a 1 2 p q 3 1 3数的集合 N 自然数 naturalnumbers 集合N 0 1 2 3 Z 整数 integers 集合Z 0 1 2 2 1 0 1 2 Q 有理数 rationalnumbers 集合R 实数 realnumbers 集合C 复数 complexnumbers 集合 3 1 4集合之间的关系 子集 相等 真子集 空集 全集 幂集 n元集 有限集 1 子集 定义 子集 subset 设A B是任意两个集合 如果A的每一个元素是B的成员 则称A为B的子集 或说A包含于B 或说B包含A 记作A B 或B A A B x x A x B 若A不是B的子集 则记作A BA B x x A x B 证明A B x x A x B 成立 证明 根据定义A B x x A x B 则A B x x A x B x x A x B x x A x B x x A x B 子集 举例 设A a b c B a b c d C a b 则A B C A C B 定理3 1 1集合A和集合B相等的充分必要条件是这两个集合互为子集 A B A B B AA B x x Ax B 证明 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 Ax B 等价式 包含 的性质 1 A A 自反性 证明 A A x x A x A T2 若A B 且A B 则B A 反对称性 3 若A B 且B C 则A C 传递性 证明 A B x x A x B x x A x B A B x C B C x x A x C 即A C 2 真子集 定义 真子集 propersubset 如果集合A的每一个元素都属于B 但集合B至少有一个元素不属于A 则称A为B的真子集 记作A B A B A B A BA B x x A x B x x B x A A B的含义 A B A B A B 定义 A B A B 德摩根律 x x A x B A B 定义 A B A B 含义 A不是B的子集或者A和B相等 真包含 的性质 1 A A 反自反性 证明 A A A A A A T F F 2 若A B 则B A 反对称性 证明 反证 设B A 则A B A B A B A B 化简 B A B A B A B A所以A B B A A B 定义 但是A B A B A B A B 化简 矛盾 3 若A B 且B C 则A C 传递性 证明 A B A B A B A B 化简 同理B C B C 所以A C 假设A C 则B C B A 又A B 故A B 此与A B矛盾 所以A C 所以 A C 3 空集 定义 空集 emptyset 没有任何元素的集合是空集 记作 例如 x R x2 1 0 定理 对任意集合A空集是它的子集也就是对任意集合A A证明 A x x x A x F x A T 对于每一个非空集合A 至少有两个不同的子集 A和 称为A的平凡子集 推论 空集是唯一的 可作为讨论 证明 设 1与 2都是空集 则 1 2 2 1 1 2 4 全集 定义 全集 在一定范围内 如果所有集合均为某一集合的子集 则称这个集合是全集 记作E E x P x P x P x 为任何谓词全集是相对的 视情况而定 因此不唯一 例如 讨论 a b 区间里的实数性质时 可以选E a b E a b E a b E a b E a E 等 5 幂集 定义 幂集 powerset 给定集合A 由集合A的所有子集为元素组成的集合 称为A的幂集 记作P A P A x x A 注意 x P A x A例如 A a b P A a b a b 定理 如果有限集合A有n个元素 则幂集P A 有2n个元素 证明 见课本第85页 利用二项式展开定理 3 2集合的运算 2 1 1 定义 集合的交 intersection 设任意两个集合A和B 由集合A和B的所有共同元素组成的集合S 称为A和B的交集 记作A B S A B x x A x B x A B x A x B 例2 设An x R 0 x 1 n n 1 2 则A1 A2 An 2 1 2交集 举例 例1 设An x R n 1 x n n 1 2 10 则A1 A2 An 0 2 1 3不相交 disjoint 不相交 A B 互不相交 设A1 A2 是可数多个集合 若对于任意的i j 都有Ai Aj 则说它们互不相交 例 设An x R n 1 x n n 1 2 10 则A1 A2 是不相交的 2 1 4集合交运算的性质 a A A A 幂等律 b A 零律 c A E A 同一律 d A B B A 交换律 e A B C A B C 结合律 因为集合交运算满足结合律 故n个集合的交记为 nP A1 A2 An Aii 1 2 2集合的并 2 2 1 定义 并集 union 设任意两个集合A和B 由所有集合A和B的元素组成的集合S 称为A和B的并集 记作A B S A B x x A x B x A B x A x B 例2 设An x R 0 x 1 n n 1 2 则A1 A2 An 2 2 2并集 举例 例1 设An x R n 1 x n n 1 2 10 则A1 A2 An 0 10 0 1 2 2 3集合并运算的性质 a A A A 幂等律 b A A 同一律 c A E E 零律 d A B B A 交换律 e A B C A B C 结合律 因为集合并运算满足结合律 故n个集合的并记为 nP A1 A2 An Aii 1 2 3集合的补 相对补 2 3 1 定义 补集 相对补集 relativecomplement differenceset 属于A而不属于B的全体元素组成的集合S 称为B对于A的补集 相对补集 记作A BS A B x x A x B 2 3 2 定义 绝对补 complement 设E为全集 对任一集合A关于E的补E A 称为集合A的绝对补 记作 A A x x E x A 2 4集合的对称差 2 4 1 定义 对称差 symmetricdifference 属于A而不属于B 或属于B而不属于A的全体元素组成的集合S 称为A与B的对称差 记作A B A B x x A x B x A x B A B A B B A A B A B 2 5相对补 对称差 举例 例 设A x R 0 x 2 B x R 1 x 3 则A B x R 0 x 1 0 1 B A x R 2 x 3 2 3 A B x R 0 x 1 2 x 3 0 1 2 3 2 6集合运算的性质 集合恒等式 1 幂等律 idempotentlaws A A AA A A 2 结合律 associativelaws A B C A B C A B C A B C 3 交换律 commutativelaws A B B AA B B A 4 分配律 distributivelaws A B C A B A C A B C A B A C 5 对合律 doublecomplementlaw A A 6 零律 dominancelaws A E EA 7 同一律 identitylaws A AA E A 8 排中律 excludedmiddle A A E 9 矛盾律 contradiction A A 10 全补律 E E 11 吸收律 absorptionlaws A A B AA A B A 12 德 摩根律 DeMorgan slaws A B A B A B A B 13 补交转换律 differenceasintersection A B A B 2 7集合恒等式证明 方法 1 逻辑演算法 利用逻辑等价式和逻辑推理规则 2 集合演算法 利用集合恒等式和已知的集合结论 1 逻辑演算法 格式 题型 A B 证明 x x A x B A B证毕 或证明 x x A x B 另 x x B x A A B证毕 题型 A B 证明 x x A x B A B证毕 例1 分配律 证明 A B C A B A C 证明 x x A B C x A x B C 定义 x A x B x C 定义 x A x B x A x C 命题逻辑分配律 x A B x A C 定义 x A B A C 定义 A B C A B A C 成立 例2 零律 证明 A 证明 x x A x A x 定义 x A F 定义 F 命题逻辑零律 A 成立 例3 排中律 证明 A A E证明 x x A A x A x A 定义 x A x A 定义 x A x A 定义 T 命题逻辑排中律 A A E成立 2 集合演算法 格式 题型 A B 题型 A B 证明 A证明 A B B A B A B 例1 吸收律 一式证明 A A B A证明 A A B A E A B 同一律 A E B 逆用分配律 A E 零律 A 同一律 A A B A 例2 吸收律 二式证明 A A B A证明 A A B A A A B 分配律 A A B 幂等律 A 吸收律第一式 A A B A 2 集合演算法 格式 续 题型 A B证明 A B 或A B A 或B A B 说明 化 成 题型 A B证明 A B A B A B 说明 把 分成 与 A B A A BA B B A B 2 8集合恒等式证明 举例 1 基本集合恒等式例如 补交转换律A B A B证明 x x A B x A x B x A x B x A BA B A B 德 摩根律的相对形式A B C A B A C A B C A B A C 证明 A B C A B C 补交转换律 A B C 德 摩根律 A A B C 幂等律 A B A C 交换律 结合律 A B B A 补交转换律 2 对称差 的性质 1 交换律 A B B A 2 结合律 A B C A B C 3 分配律 A B C A B A C 4 同一律 A A 5 排中律 A A E 6 A A 7 A E A 作业 3 1 3 2 P85 1 a c 6 b c P94 5 a 思考题 8 9 11 b 提示 举例说明即可 3 3包含排斥原理 集合的运算 可用于有限个元素的计数问题 设A1 A2为有限集合 其元素个数分别记为 A1 A2 根据集合运算的定义 显然以下各式成立 A1 A2 A1 A2 A1 A2 min A1 A2 A1 A2 A1 A2 A1 A2 A1 A2 2 A1 A2 3 3包含排斥原理 定理3 3 1设A1 A2为有限集合 其元素个数分别为 A1 A2 则 A1 A2 A1 A2 A1 A2 证明 见P96推理 对于任意三个有限集合A1 A2和A3 则 A1 A2 A3 A1 A2 A3 A1 A2 A1 A3 A2 A3 A1 A2 A3 3 3包含排斥原理 定理3 3 2见P97例题1 P96例题2 P97 作业 3 3 P100 4 3 4序偶与笛卡尔积 3 4 1序偶 二元组 定义 序偶orderedpair 由两个固定次序的客体a b组成的序列称为序偶 记作 其中a b称为序偶的分量 其中 a是第一元素 b是第二元素 记作也记作 a b 定理 序偶和相等 当且仅当a c且b d 即 a c b d 推论 a b 3 4 2三元组 orderedtriple 定义 三元组 c 定义 n 2 元组 an 定理 ai bi i 1 2 n 3 4 3笛卡尔积 Cartesianproduct 及其性质 定义 笛卡尔积 A和B为任意两个集合 若序偶的第一个成员是A的元素 第二个成员是B的元素 所有这样序偶的集合 称为A和B的笛卡尔积或直积 记为 A B x A y B 例1 A a B 1 2 3 A B B A A A B B 3 4 4笛卡尔积的性质 当 A m B n时 A B 是多少 A B m n 3 4 4笛卡尔积的性质 1 非交换 A B B A 除非A B A B 反例 A 1 B 2 A B B A 2 非结合 A B C A B C 除非A B C 反例 A B C 1 A B C 1 A B C 3 笛卡尔积分配律 对 或 运算满足 1 A B C A B A C 2 A B C A B A C 3 B C A B A C A 4 B C A B A C A 3 笛卡尔积分配律 证明 1 A B C A B A C 证明 A B C x A y B C x A y B y C x A y B x A y C A B A C A B A C A B C A B A C 4 其他性质 设A B C D是任意集合 1 若A 则A B A C B A C A B C 即书上的定理3 4 2 2 A C B D A B C D 即书上的定理3 4 3 3 A B A B 证明 1 若A 则A B A C B C 证明 若B 则B C 设B 由A 设x A y y B A B A C x A y C y C B C 若B 则A B A C 设B A B x A y B x A y C A C A B A C 3 4 5推广 n维笛卡尔积 定义 n维笛卡尔积 A1 A2 An x1 A1 x2 A2 xn An A A A An Ai ni i 1 2 n A1 A2 An n1 n2 nn n维笛卡尔积性质与2维笛卡尔积类似 作业 P104 1 b 2 5 3 5关系及其表示 3 5 1关系的概念及记号兄弟关系 长幼关系 同学关系 邻居关系 上下级关系等 在数学上有大于关系 小于关系 整除关系 例如 3小于5 x大于y 点a在b与c之间 我们又知道序偶可以表达两个客体 三个客体或n个客体之间的联系 因此用序偶表达这个概念是非常自然的 例如 火车票与座位之间有对号关系 设X表示火车票的集合 Y表示座位的集合 则对于任意的x X和y Y 必定有x与y有 对号 关系x与y没有 对号 关系 二者之一令R表示 对号 关系 则上述问题可以表示为xRy或xRy 亦可表示为 R或 R 因此我们看到对号关系是序偶的集合 定义 关系 二元关系 binaryrelation 简称关系 任一序偶的集合即确定了一个二元关系R R中任一序偶可记为 R或xRy 不在R中的任一序偶可记为 R或xRy 例1 在实数中关系 可记作 x y是实数且x y 例2 R1 R1是二元关系 例3 A a 1 A不是关系 二元关系的记号 设R是二元关系 则 R x与y具有R关系 xRy 对比 xRy 中缀 infix 记号 R 后缀 suffix 记号 R x y 前缀 prefix 记号 例如 2 R 1R2 R 5R4 A到B的二元关系 也可定义 关系 为 设有任意两个集合A和B 直积A B的子集R称为A到B的二元关系 R是A到B的二元关系 R A B R P A B 幂集 若 A m B n 则 A B mn 故 P A B 2mn 即A到B不同的二元关系共有2mn个 A到B的二元关系 举例 例 设A a1 a2 B b 则A到B的二元关系共有22 1 4个 R1 R2 R3 R4 B到A的二元关系也有4个 R5 R6 R7 R8 A上的二元关系 定义 A上的二元关系 是A A的任意子集 R是A上的二元关系 R A A R P A A 若 A m 则 A A m2 故 P A A 2m2 即A上不同的二元关系共有2m2个 A上的二元关系 举例 例1 设A a1 a2 则A上的二元关系共有16个 R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 R11 R12 R13 R14 R15 R16 例2 设B b 则B上的二元关系共有2个 R1 R2 例3 设C a b c 则C上的二元关系共有29 512个 3 5 2与二元关系有关的概念 对任意集合R 可以定义 前域 定义域 domain domR x y xRy 值域 range ranR y x xRy 域 field FLDR domR ranR前域 定义域 值域 域图示见书106页例题1 定义域 值域 域 举例 例 R1 a b R2 R3 当a b不是序偶时 R1不是关系 domR1 ranR1 FLDR1 domR2 c e ranR2 d f FLDR2 c d e f domR3 1 3 5 ranR3 2 4 6 FLDR3 1 2 3 4 5 6 3 5 3一些特殊关系 设A是任意集合 则可以定义A上的 空关系 emptyrelation 恒等关系 identityrelation IA a A 全域关系 universalrelation UA A A x A y A 此外 设A I 则可以定义A上的 整除关系 DA x A y A x y 例 A 1 2 3 4 5 6 则DA 设A R 则可以定义A上的 小于等于 lessthanorequalto 关系 LEA x A y A x y 小于 lessthan 关系 LA x A y A x y 大于等于 greaterthanorequalto 关系 大于 greatthan 关系 设A为任意集合 则可以定义P A 上的 包含关系 A x A y A x y 真包含关系 A x A y A x y 见P107例2和例3 3 5 4关系的运算 定理 若Z和S是从集合X到集合Y的两个关系 则Z和S的并 交 补 差仍是X到Y的关系 证明见书108页 3 5 5二元关系的表示 1 序偶集合的形式表达 2 关系矩阵 设A a1 a2 an B b1 b2 bm R A B 则R的关系矩阵MR rij n m 其中rij 1 aiRbj或 R0 aiRbj或 R 例题 P103例题5例如 A a b c R1 R2 则110011MR1 101MR2 001000000 3 关系图 A a1 a2 an B b1 b2 bn R A B 首先在平面上做结点a1 a2 an b1 b2 bn以 表示 称为顶点 若aiRbj 则从结点ai向结点bj画有向边 箭头指向bj 若aiRbj 则ai与bj之间没有线段连接 这样得到的图称为R的关系图GR P109例题7 定义在集合A上的关系图有所不同例如 上例 A a b c R1 R2 则关系图如下 关系矩阵 关系图 讨论 当A中元素标定次序后 R A A的关系图GR与R的序偶集合表达式可以唯一互相确定 R的序偶集合表达式 关系矩阵 关系图三者均可以唯一互相确定 作业 3 5 P109 1 5 c 给出关系图和关系矩阵 8 选做