南京大学《离散数学》课件-第1周.pdfVIP

集合及其运算 离散数学 第1讲 陈道蓄 cdx@nju.edu.cn 集合及其运算 集合与元素 集合的表示 集合相等 空集与 （相对）全集 幂集 罗素悖论 基本的集合运算 连续 vs. 离散 现代数字计算机 离散的数据 离散的状态 离散数学模型 – 一个例子 9根火柴的双人游戏 每次取走 1,2 或3 根，不能与对方刚刚取的数相同。 如果每个人都尽量选择对自己有利的取法，先取者必胜。 问题的推广：保证先取者胜的开始火柴根数 • （1）“格局” ，三元组 （X, m, k ），X 为下一个动作者，非负整 数m是尚未取走的火柴根数 （m初始根数），k 是对方最近一次 取的根数。注意: 输格局是 （X, 0, k ）和 （X, 1, 1） 1 2 3 i • （2 ）“动作”，定义为三个函数 f , f , f ， f ( （X, m, k ）) （X 的 i 对方, m-i, i ），f 在 （X, m, i ）无定义。 （X, 4, k ）和 （X, 8, k ）对于 X都是输格局。 你能提出并证明更一般性的结论吗? 集合的概念 没有定义 a variety of different obj ects as being bound together by some common property, the property may be nothing more than the ability to think of these obj ects (as being) together Description by Cantor ：A set is a collection into a whole of definite, distinct obj ects of our intuition or our thought. The obj ects are called elements (member) of the set. 集合的表示 {x | P(x)}, P 必须是 “数学可定义”的性质 “There exists no Y X” is a well-defined property about X “For every U, U Z iff . U X and U Y” is a well- defined property about X, Y and Z 。 一个集合可以有多种表示 {2, 3, 5} All prime numbers in [1, 7) 3 2 All real roots of the equation x -10x +31x-30 0 。 子集 “子集”(包含)关系是两个集合之间的关 系，其中一个称为另一个的子集: AB 定义为: 对所有的 x A, x B 因此，AB 的意思是: 至少存在一个 x, 满 足 x A, 但是x B 集合的相等 如果两个集合 A,B的元素完全相同，则称