《大学离散数学.ppt》由会员分享，可在线阅读，更多相关《大学离散数学.ppt（17页珍藏版）》请在三一文库上搜索。
1、离散数学,1. 课程性质 计算机数学基础课程 2. 教学内容 集合 （1）集合论 自然数集 二元关系 （2）组合论：离散函数，计数与生成 （3）图论：图，树 （4）数理逻辑：命题逻辑，谓词逻辑 （5）群论：群、环、域（不讲）,3. 预修课程 （1）高等数学 （2）线性代数 （3）概率论 4. 下列课程的基础课 （1）数据结构 （2）数据库,第一章 集 合, 集合 定义 集合：把一些确定的，彼此不同的对象作为一 个整体考虑，这个整体称为集合。 定义 元素：集合里所含的个体称为集合的元素。,注： 大写英文字母表示集合 小写英文字母（或加数字）表示集合的元素,集合的表示法： .穷举法，例如：， 将集
2、合中的所有的元素罗列出来。 .描述法：把集合内元素的性质、特点概括描述出来， 如上例：是偶数且,元素与集合的关系： .：，表示是集合中的元素 读作属于 .：，表示不是的元素 读作不属于,定义 空集：集合中没有元素，称此集合为空集。 注： .是空集，不是空集，此集合有一个元素 2.，是有二个元素的集合 3. 同一集合里不能有相同的元素，元素之间没有先 后次序（扩充集合除外）,定义 子集：集合的元素均属于集合，称为的 子集，记为。 注：包含在中，不属于的元素也不会属于。,定义 集合相等：与包含相同的元素，记为=。 即，又，得出。,定义 真子集：若是的子集，且中至少有一个元 素不属于，称是的真子集，
3、记为。 注： 1.意为：对a，则a b,但b 2.，即空集是任何集合的子集 非空时，是的真子集，。 3.任何集合是自身的子集，但不是真子集。,定义 平凡子集：的平凡子集只有二个：和。,定义 基数：集合内元素的个数称为此集合的基数。也 称基度、势，记为集合的基数， 或记为Card。 注： 有限集：元素个数是有限个的集合。 无限集：元素个数是无限个的集合。,定义 幂集：集合的所有子集组成的集合称为的幂 集，记为（）。 注： 1.只有一个子集，（） (）20 2.设，有二个子集和， （）， |()| 21 3.若1，2 ，n,|=， 则|()| 2n 即A的不同子集个数为：,集合内元素是无序的，但用
4、计算机进行操作时，只能 对规定了次序的有限集进行操作。 例：31，2，3 （3 ）ii 其中：ii i是二进制数 故有： 0000 10013 20102 30112，3 41001 51011，3 61101，2 71111，2，3,集合的运算及文氏图 常常需要研究集合之间的关系，或用一些集合来构造另一些集合,这就需要讨论集合的运算。 定义 全集：包含当前讨论的所有元素的集合称为全 集，记为。 定义 并集：把所有与的元素并在一起组成新的集 合，称为与的并集，记为 。 or ,注： 1. ， 2. 且，则 3. 。由于与的公共 元素在中只出现一次，故当与无公共元 素且是有限集合时等式成立。,4
5、.当且仅当时。 即要证：若，则有 且若，则有,而要证：若，则有，则需证： （1） （2） 又如何证明：？思路为： 根据定义，对a，证明a,证明：若，则有 （1）对，则或 若，由，得出 故 （2）显然 由集合相等定义得出。证毕。,证明：若，则有 用反证法，若 则，而 故，而 与（）矛盾。,定义 交集：所有既在中又在中的元素组成一个新 的集合，称为与的交集，记为 。 即 and 注： （1）（交换律） （2）， （3）当且仅当且时有 （4）， 当时等号成立。 （5）当且仅当时,定义 差集：所有在中而不在中的元素组成一个新 的集合，称为减的差集，记为。 and 注： （1）只是在中减去了与有公共元素
6、 即（） （2）若 则 （3）有,定义 余集：设是全集，称差集为 关于的余集，记为 注： （1） （2） and and ,定义 对称差：把与的所有元素扣除与的公共 元素组成的集合，称为与的对称差，记为 ，或记为 。 注： （1）（）（） （2）若,文氏图 （英国数学家 ） 直观形象地描绘集合间的关系和运算,由文氏图可知： （）（） （）（）,对于，运算，有以下结论：,结论（6）的证明： 1. 必要性:若P-Q=P,则有= 因为P-Q=P，由（4）得P Q 又=，故结论成立 2. 充分性:若=，则有P-Q=P （1）对 P-Q，根据定义， P，故 P-QP （2）对 P，由于=，故 Q，故有 P-Q，即PP-Q。证毕,