离散数学课件 第三章 集合论-2nd.pdf

1 43 第三章 集合论 大连理工大学软件学院 陈志奎 教授 办公室 综合楼411 Tel 87571525 实验室 教学楼A318 323 Tel 87571620 24 MobileEmail zkchen zkchen00 2 43 3 2集合的运算 定义 由集合A和B的所有公共元素所组成的集 合 称为集合A和B的交集 记作ABI ABx xAxB I AB ABI 一 相交运算 例如 设A a b c d B d f a C e f g 则 ABa d I BCf I AC I 可以看出 ABA ABB II 3 43 一 相交运算 证明 若 则 对任一 则 且 即 且 故 因 此 ABACBC II设 求证 xA xB xAC IxA xC xB xC xBC I ACBC II 集合的交运算具有如下性质 a AAA b A c AEA d ABBA eABCABC I I I II IIII AB ABI 4 43 一 相交运算 类推至多个集合的情况 集合的交运算仍满足结 合律 ABCABC IIII试证明 ABCx xABxC x xAxBxC x xAxBxC x xAxBC x xAxBC III I I 证明 12 1 n n i i PAAA A III I 假设有n个集合A1 A2 An 那么这些集合的交集可表 示为 5 43 二 联合运算 集合的并 定义 由集合A和B的所有元素组成的集合称为A和 B的并集 记作A BU ABx xAxB U A B ABU 例如 例如 设设A a b c B c d f C b e 那么 ABa b c d f ACa b c e BCb c d e f U U U 可以看出 AAB BAB UU 6 43 二 集合的并 集合的并运算具有如下性质 a AAA b AEE c AA d ABBA eABCABC U U U UU UUUU 注意 假设有n个集合A1 A2 An 那么这些集合 的并集可表示为 12 1 n n i i WAAA A UUK U U 7 43 二 集合的并 AB CDACBD UU例1 假设则 xACxAxC xAABxBxBD xCCDxDxBD ACBD U U U UU 证明 对任意 有 若 由可得 故 若 由可得 故 因此 8 43 二 集合的并 证明 对于任意的x 若 由x的任意性可知 a 成立 同理可以证明 b 3 2 1 A B C a ABCABAC b ABCABAC IUIUI UIUIU 定理 设为三个集合 那么 xABC xAxBC xAxBxC xAxBxAxC xABxAC xABAC IU U II IUI 9 43 二 集合的并 3 22 A B a AABA b AABA UI IU 定理 设为任意两个集合 那么 a AABAEAB AEB AE A UIIUI IU I 证明 b AABAAAB AAB A IUUIU UI 证明 10 43 二 集合的并 3 23ABABBABA UI定理 当且仅当或 ABxAxB xABxAxBxB ABB BABABB ABBAABAB ABABA U U UU UU I 证明 1 若 对任意 必有 对任意 则或 即 所以 又 故得到 2 若因为故 同理可证明当且仅当 11 43 关于交集 并集的例子 老师讲完交集 并集的概念之后 提问学生 1 设A x x是参加百米赛跑的同学 B x x是参加跳高比赛的同学 求A B 2 设A x x是红星农场的汽车 B x x是 红星农场的拖拉机 求A B 一学生答道 1 中A B x x是参加百米障碍赛的同学 2 中A B x x是红星农场的联合收割机 12 43 三 差分运算 集合的补 定义 设A B是两个集合 所有属于A而不属于B的 元素组成的集合 称为A和B的差集差集或B对A的相相 对补集对补集 记作A B 绝对补集 B对E的相对补集叫做绝对补集 简称 补集 记作 B ABx xAxB A B A B A A A 13 43 三 差分运算 集合的补 例 设A是小于10的素数集和 B是奇数集合 求 A B 解 A 1 2 3 5 7 B 1 3 5 7 9 A B 2 例 设U I I是整数集合 0 Ai iI i 解 0 UAi iI i A U 14 43 三 差分运算 集合的补 集合的差分运算还具有如下性质 aAA bE c AAE d AA U I A A A 15 43 三 差分运算 集合的补 定理3 2 4 设A B为任意两个集合 则下列关系式 成立 aABAB bABAB U I I U ABx xAB x xAB xxAB xxAxB xxAxB x xAxB x xAB AB U U U U I I 证明 a 16 43 三 差分运算 集合的补 定理3 2 5 设A B为任意两个集合 则下列关系式 成立 a ABAB b ABAAB I I 证明 b 设 即且 因为 则必有 故有 即为 设 则且 即 且 或者 显然只能 与 成立 即 xAB xA xB xB xAB I xAAB I ABAAB I xAAB IxA xAB I xA xA xB xA xB xAB AABAB I 17 43 三 差分运算 集合的补 定理3 2 6 设A B C为任意三个集合 则下列关系 式成立 ABCABAC III 证 ABCABC III ABC II ABAC II又 ABAC ABAC ABAABC ABC II I II U II UII II 因此 ABCABAC III 18 43 三 差分运算 集合的补 3 27 A BAB aBA bBAAB U 定理 设 是任意两个集合 若 则 xAxBxBxA xBxABA 证 a 若 则 因此 若 必有 即若 则 即 bBAA BAA BAAA BAE BA ABBAB b U IU UIU UI U U 证 因为 所以 得证 19 43 四 对称差分运算 定义 设A B为任意两个集合 属于A但不属于B 的所有元素和属于B 但不属于A的所有元素的并 集 称为A和B的对称差集 记作 例如 A 1 2 3 B 3 2 4 则 1 4 ABABBA ABBA ABAB U IUI UI AB AB E AB 20 43 四 对称差分运算 集合的对称差分运算满足如下性质 a ABBA b AA c AA d ABABBA eABCABC IUI AB E 21 43 四 对称差分运算 ABCABC 求证 ABCABCABC ABABCABABC ABCABCABABC I U I I U II U I U II I I U II U UIU I 证 ABABC ABAABBC AAABABBBC ABABC ABCABC UIU I UIUUII IUIUIUII UIUIUI IIUII 由于 22 43 四 对称差分运算 ABC ABCABCABC ABC IIUIIUII U I I 所以 ABC ABCABC ABCBCABCBC ABCBCABCABC ABBABCABCACCA BCABC ABCABCABCABC IUI IIUIUIIUI IUIUUIIUII IIU IIUIIUIIUI IUII IIUIIUIIUII 又因为 ABCABC 得证 23 43 四 对称差分运算 上述证明结果可以通过以下文氏图清楚看出 E A B C B A C E AB ABCABC BC 24 43 3 3集合定律 1 2 3 4 5 6 7 8 9 10 11 12 SABA SABB SAAB SBAB SABA SABAB SABBA SABBA SABBA SABCABC SABCABC SABCABC I I U U U UU II UUUU IIII 交换律 结合律 25 43 3 3集合定律 13 14 15 16 17 18 19 20 21 22 23 SABCABAC SABCABAC SAA SABAB SABAB SAAA SAAA SAA SAAE SAEA SAA S IUIUI UIUIU I U U I I U I U I U 分配律 双重否定律 德 摩根律 等幂律 补余律 24 25 AA SAA 同一律 26 43 3 3集合定律 26 27 28 29 30 31 32 33 34 35 SA SAEE SAABA SAABA SE SE SAA SABA SABAAB SABCABAC I U UI IU I UU UI 吸收律 零律 27 43 3 3集合定律 证明 39 转化为假设 为假 证明 为假 由 为假可知 和 均 为假 即 并且 为真 也就是 为真 使得 为假 36 37 38 39 40 SABCABAC SABAB SABABAB SABAB SABAB IU I I U I U I AB AB U AB A B A B AB U AB U 28 43 3 4包含排斥原理 集合的运算 可用于有限个元素的技术问题 设A1 A2是有限集合 用 A1 A2 分别表示它们的基 数 那么可以推出 1212 1212 1212 121212 min 2 AAAA AAAA AAAA AAAAAA U I I 29 43 3 4包含排斥原理 定理3 4 1 设A1 A2是有限集合 A1 A2 为其基 数 则 121212 AAAAAA UI 1212 1212 1212 1 AAAA AAAA AAAA I U I 证 当 和不相交 即时 12 11212 21212 12121212 12121212 121212 2 2 AA AAAAA AAAAA AAAAAAAA AAAAAAAA AAAAAA I I I II I II I II UI U 当 那么 所以 由于 因此 30 43 3 4包含排斥原理 例 假设在10名青年中有5名是工人 7名是学 生 其中兼具有工人与学生双重身份的青年有三 名 问既不是工人又不是学生的青年有几名 解 设工人的集合为W 学生的集合为S 则根据 题设应有 5 7 3 10 WSWSWSWS I IU又因为则 10 10 10 573 1 WSWS WSWS IU I 因此既不是工人又不是学生的青年有1人 31 43 3 4包含排斥原理 包含排斥原理在三个有限集和上的推广 123123121323 123 AAAAAAAAAAAA AAA UUIII II 32 43 3 4包含排斥原理 例 某工厂装配30辆汽车 可供选择的设备是收音机 空气调节器和对讲机 已知其中15辆 汽车有收音 机 8辆有空气调节器 6辆有对讲机 而且其中有3 辆这三种设备都有 我们希望知道有几辆汽车没有 提供任何设备 解 设A1 A2和A3分别表示配有收音机 空气调节器和对 讲机的汽车集合 因此由题设知 123123 15 8 6 3AAAAAA II 因为12123 13123 23123 3 3 3 AAAAA AAAAA AAAAA III III III 得 123121323 1586 3 3233323 AAAAAAAAA UUIII 33 43 3 4包含排斥原理 把包含排斥原理推广到n个集合 定理3 4 2 设A1 A2 An 为n个有限集合 它们 的基数分别为 A1 A2 An 可得 12 11 1 12 1 1 n niij iij n n ijkn ij k n AAAAAA AAAAAA UUK UI IIIII 34 43 3 4包含排斥原理 例 求1到250之间能被2 3 5和7中任何一个整 除的整数个数 解 设A1表示1到250之间能被2整除的整数集合 A2表示能被3整除的整数集合 A3表示能被5整除 的整数集合 A4表示能被7整除的整数集合 x 表示小于或等于x的最大整数 1 250 125 2 A 3 250 50 5 A 2 250 83 3 A 4 250 35 7 A 12 250 41 2 3 AA I 13 250 25 2 5 AA I 14 250 17 2 7 AA I 35 43 3 4包含排斥原理 23 250 16 3 5 AA I 24 250 11 3 7 AA I 34 250 7 5 7 AA I 123 250 8 2 3 5 AAA II 134 250 3 2 5 7 AAA II 234 250 2 3 5 7 AAA II 1234 250 1 2 3 5 7 AAAA III 于是有 1234 1258350354125 17 16 11 78532 1193 AAAA UUU 36 43 3 5多重序元与迪卡尔乘积 定义 由两个具有固定次序的客体组成的序列 称序偶 记作 一 序偶 2 3 3 2 2 33 2 37 43 一 序偶 序偶的相等 x ya bxayb 序偶中 a称为第一元素 b称为第二 元素 两个元素不一定来自同一个集合 他 们可以代表不同类型的事务 38 43 二 多重序元 定义 n重序元是一个序偶 它的第一元素是 n 1 重序元 3重序元 z 简单记作 n重序元 xn n重序元的相等 121121 1122 nnnn nn x xxxa aaa xaxaxa KK 39 43 三 迪卡尔乘积 定义 设A和B是任意两个集合 若序偶的第一个 元素是A的一个元素 第二个元素是B的一个元