《01-集合及其运算-1》由会员分享，可在线阅读，更多相关《01-集合及其运算-1（24页珍藏版）》请在金锄头文库上搜索。
1、集合及其运算离散数学 第1讲陈道蓄 集合及其运算l集合与元素l集合的表示l集合相等l空集与（相对）全集l幂集l罗素悖论l基本的集合运算连续 vs. 离散 l现代数字计算机离散的数据离散的状态离散数学模型 一个例子l9根火柴的双人游戏每次取走 1,2 或3 根，不能与对方刚刚取的数相同。 如果每个人都尽量选择对自己有利的取法，先取者必胜。 问题的推广：保证先取者胜的开始火柴根数l（1）“格局”，三元组（X, m, k），X 为下一个动作者，非负整数 m是尚未取走的火柴根数（m初始根数），k 是对方最近一次取的 根数。注意: 输格局是（X, 0, k）和（X, 1, 1）l（2）“动作”，定义为三
2、个函数 f 1, f 2, f 3， f i(（X, m, k）)=（X的 对方, m-i, i），f i 在（X, m, i）无定义。 （X, 4, k）和（X, 8, k）对于 X都是输格局。你能提出并证明更一般性的结论吗? 集合的概念l没有定义被认为“具有某种共同性质”的若干不同的对象合在一 起构成集合，而所谓“共同性质”也只不过是让你能将 它们想到一起罢了。Georg Cantor的描述：A set is a collection into a whole of definite, distinct objects of our intuition or our thought. Th
3、e objects are called elements (member) of the set. 集合的表示lx | P(x), P 必须是“数学可定义”的性质“不存在任何 YX” 是关于X的有效性质“对任意的 U, UZ iff. UX 且 UY” 是关于X, Y 和 Z 的有效性质。 l一个集合可以有多种表示2, 3, 5 1, 7)区间内的所有质数 方程 x3-10x2+31x-30=0 的所有实根 子集l“子集”关系是两个集合之间的关系，其中一个称 为另一个的子集:AB 定义为: 对所有的 xA, xB因此，AB 的意思是: 至少存在一个 x, 满足 xA, 但 是xB集合的相等l
4、如果两个集合 A,B的元素完全相同，则称这两个 集合相等 (A=B)l对任意集合 A,B, A=B 当且仅当:AB, 且BA 空集l空集是没有元素的集合例. A=x|x 是整数且 xxl空集是任何集合的子集。假设 A 是空集, B 是任给的一个集合。命题 “存在某 个元素x, 满足xA, 但 xB” 总是假。l空集是唯一的，可以用 表示如果 1, 2都是空集，则 12 和 21 均为真。幂集l(A)=x|xA, 其中A 是任意集合。l(a,b) = ,a,b,a,bl() = l如果 |A|=n, 则 |(A)|=2n幂集的另一种记法: 2A集合悖论lRussell 悖论：定义 R=x | x
5、x, 则 RR iff. RR。理发师悖论：一个小镇上的理发师在广告上写到：“我给所有不 给自己理发的人理发”lA=x|P(x), 实际上不能保证对任意的性质 P，这样的定 义都有意义。 （注意：A=x|x是实数，x20有意义，即空集）lUnfortunately, no way how to determine the properties which do define set is known, and some results in logic(especially the so-called Incompleteness Theorems discovered by Kurt Gde
6、l) seem to indicate that a complete answer is not even possible.塞万提斯版的“罗素”悖论l唐吉柯德第2卷第51章中的一段故事：一个小岛国(桑科潘查不小心成了它的统治者)有一条 奇怪的法律：任何来此的游客必须回答“你来这里做 什么？”这个问题。答对了一切好说，答错了立即被 绞死。如果你是那个游客，你该如何回答。(假设你还不想死)另类悖论这句话 有8个字没基本运算的定义l运算定义的基本方式：将结果定义为一个新的集 合（这也可以看做是一种集合表示方法）并与交：AB=x|xA 或者xBAB=x|xA 并且xB相对补：A-B=x|xA并且x
7、Bl相对于全集的绝对补对称差: AB=(AB)-(AB)=(A-B)(B-A)文氏图（Venns Digram）: 例1l A B 文氏图（Venns Digram）：例2l (A-(BC)(BC)-A) 运算的重要性质 （1）l包含关系下两个集合的最小上界和最大下界 AAB, BAB对任意X，若A X , B X ,则AB XABA, ABB 对任意X，若X A , X B ,则X AB运算的重要性质 （2）l子集与运算的关系 AB=B AB AB=A A-B= 运算的重要性质 （3）l并与交的重要算律等幂律结合律交换律分配律同一律和零律排中律和矛盾律吸收律de Morgan律双重否定律运算
8、的重要性质 （4）l相对补运算的重要性质A-BAA-B=AB运算的重要性质 （5）l对称差的重要性质交换律与结合律同一律AA= (逆元素)消去律常规集合模型的局限性l假如象5位潜在顾客了解对一种新式样手机的反 应，得到如下答复：小赵：“还可以吧，我想。”小钱：“太好了，什么时候能上市？”小孙：“我不相信会有人买。”小李：“我觉得不错。”小周：“看上去真好。”lA=x| x喜欢这种手机应该是什么样的集合呢？模糊集合l令集合S=小赵，小钱，小孙，小李，小周，定义S上 的一个度量mS(x), 对任意xS, 0mS(x)1:小赵：“还可以吧，我想。” (0.4)小钱：“太好了，什么时候能上市？” (1.0)小孙：“我不相信会有人买。” (0.0)小李：“我觉得不错。” (0.7)小周：“看上去真好。” (0.8)lA=x| x喜欢这种手机 = (x, mS(x) | xS, 0mS(x)1= (小赵, 0.4), (小钱, 1.0), (小孙, 0.0), (小李, 0.7), (小周, 0.8) 作业lpp.103-5-812-13
