集合映射与运算

《集合映射与运算》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学DiscreteMathematics邓辉文编著清华大学出版社2010.3ISBN978-7-302-21193-8十一五国家级规划教材计算机系列教材离散数学是计算机各专业的专业基础课.(1)程序设计语言(2)离散数学(3)数据结构与算法(4)计算机组成原理(5)计算机网络(6)操作系统(7)数据库(8)软件工程离散数学研究的对象:离散量及其之间的关系.离散量与连续量及其之间的转换.现今计算机的处理对象是非常特殊的离散量:0和1.学习离散数学的目的:1.培养各种能力.2.为后继专业课程的

2、学习作知识上的准备.离散数学的主要内容:1.集合与关系Chapter1集合、映射与运算Chapter2关系2.数理逻辑Chapter3命题逻辑Chapter4谓词逻辑3.代数结构(Chapter5)4.图论Chapter6图论Chapter7几类特殊的图5.组合计数(Chapter8)学习离散数学的方法:1.预习.2.听课.3.复习.4.(分组)作业.参考文献:屈婉玲,耿素云,张立昂,离散数学,高等教育出版社,2007.(108—144学时)傅彦,顾小丰,王庆先,离散数学及其应用,高等教育出版社

3、,2008.(两个学期)Chapter1Sets,MappingsandOperations集合是现代数学的最基本概念(?).映射又称为函数,它是现代数学的基本概念,可以借助于集合下定义.运算本质上是映射,但其研究有其特殊性.(关系也是集合)集合、映射、运算及关系(Chapter2)是贯穿于本书的一条主线.1.1集合的有关概念1.集合在一定范围内,集合(set)是其具有某种特定性质的对象汇集成的一个整体,其中的每一个对象都称为该集合的元素(element).这里所指范围是全集U(见图1-1).(

4、避免悖论!)在数学中常用{}表示整体.若x是集合A中元素,则记xA,否则xA.Fuzzyset?集合通常用大写字母A,B,C,D,…表示.N是自然数集合,包括数0；Z是整数集合；Q是有理数集合；R是实数集合；C是复数集合.P:2,3,5,7,11,13,17,19,23等.(1)m

5、n:n=mq.(2)Dn.(3)素数测试与Mersenne素数:2p-1.表示集合的常用方法:(1)列举法:{0,2,4,6,8},N={0,1,2,3,…}.(2)描述法:{x

6、x满足的条件}.可简记:{直角三

7、角形},{所有人}(3)递归法自然数集合N可递归定义,在后面章节定义命题公式及谓词公式时还会用此法.有限集合A的元素个数

8、A

9、,card(A).Remarks1.集合中的元素可以是集合,例如A={a,{a,b},b,c}.{a,b}A,{a,b}A.2.集合之间的元素原则上是没有次序的,如A={a,{a,b},b,c}就是{a,b,c,{a,b}};3.集合中的元素原则上不重复,如{a,{a,b},b,b,c}还是集合A.不含有任意元素的集合称为空集(emptyset),记为或{}.2.子

10、集AB,特别地是任意集合的子集.A=B.Theorem1-2(P3)(1)AA.(2)AB,BAA=B.(3)AB,BCAC.Theorem1-3A=BAB且BA.注意与的不同.例1-2由AB,BC可否得出AC?Solution不成立,例如A={a,b},B={a,b,c},C={a,{a,b,c}}.课堂练习:4,5.3.幂集(powerset)X={a,b}P(X)={,{a},{b},{a,b}}.P(P())=P({})={,{}}(P5,

11、6(1)).,{},{{}}(P5,2)Theorem1-4Proof(加法原理)由乘法原理证明?4.n元组Def1-4将n个元素(?)x1,x2,…,xn按一定顺序排列就得到一个n元(有序)组(n-tuple).线性代数中的n维向量(?):n=2,n=3(seebelow)n=2:(x,y).n=3:(x,y,z)4元组?显然,一般说来(x,y)(y,x).注意区别(a,b,c),((a,b),c),(a,(b,c))的不同.n维向量是n元组,长度为n的线性表是n元组,抽象数据结构Da

12、ta_Structure=(D,S)本身是一个2元组.2元组常称为有序对(orderedpair)或序偶.5.笛卡儿积(crossproduct)例1-4(P4)设A={a,b},B={1,2},C={},求AB,BA,ABC,BC.SolutionABC={(a,1,),(b,1,),(a,2,),(b,2,)}.BC={(1,),(2,)}RemarkA=B=.P5,10?TheoremHint可推广到更多个集合的笛卡儿积的情形:作业习题1.16,9,