离散数学基础(洪帆)

4星(超过85%的资源)
所需积分/C币:50 2012-10-28 23:54:35 8.81MB PDF
92
收藏 收藏
举报

离散数学基础(洪帆著) 本书为计算机专业的基础教科书,由华中科技大学洪帆老师编著。
576都尔代数的子衰示 …*210 §7,7布尔代数W2 ■中■■■中鲁 Fi §7,8布尔表式和有抓数 …………217 ……………………-……………………223 八章论………………………………227 §8?基4麒念 ………………-…227 82时阵 236 §8,3欧图利哈识长 …"an;"4"……"""243 8,4树 …"……………………z48 8,5有 253 §8,6 259 冬 26 §88有河饜……∵……… 271 ·;b"■■b‘T号■}下·· L山 山■■■dh■bP■;■山 276 √九靠效逕誓…… ……………282 (→)命题演算… ■■d 282 §91命和命题公式……" ■■■■■■■自『■“血■會甲卩中卩聊l■■司冒F血■血 282 92命题公式的等值小系和蕴含关系 28g s9.3范式 299 §9,4命题演算的推期理论… 308 (二)调词演算…………………………………………315 §9。5谓词、个体词利撤词 d■s山■p『■+h甲;■■■p ■卩■ψ■西■■昏■『■■▲ 315 §,6谓词演算公式…+……………… 3I8 89。7谓词演算的永真公式和公式的等 320 §98谓证演算的推理理………… 23 习题………………M…""…""…326 ●考书目 …rr"!328 3 第一章集合 集合的穊念是觋代数学r最基的…-,并深入到各 种科学和技术的领域。对于计算杌科学作老来,集的 念是不可觖少的。在开关理论、有限忘动机、形式语等领域中 集合论有着广泛的应月 这一章我们介轺僳合及其」集幂集、分划等基本概念,集 合的并,交、补运算以及这熙运算的性质;还介绍文氏图和成员 装,它们对集合进行运算和分析的有用工具;最后介绍集合的 标准形式。 §1.1集合 集合是数学的一个最基本的概念,很难再用别的词来定义 我们通常只是价了一种拙述。 把一些确定的、彼此不[的物作为一个整体来考虑时,这 个整体便称为是一个集合,这里所谓“事物”也称“个体”,可以 是在极其广泛的意义上使用,至包括象的事物、例如, 中国人,一本书中的部概念,一羊,所有自然教等年,都分 别可以构成集合。 集合里所含有的个休叫袋集合的元囊,饼如,全休中国人的 集合,它的元素就是每一个国人;一·群羊的集合,它的元素就 是该羊群中的每一只羊;所有自然数的集合,它的元素就是每 个自然数。 今后我们用大写拉丁字母表示集合,用小写拉丁字母表示元 素.如果a是集合A的元素,则记作“a∈A”,读作“a属集 合A”或“a在集合A中”。如果a不是集合A的元素,则记竹 a终A”,读作“a不属于集合A”或“a不在台A中”例如 若用N表示自然数的集合,则2EN,3∈N,但2.3N,-5续N。 关于集合的瓶念,很重要的一点是我们给出…个“个体” 后,应该能够确定它是否是这个集合的元素,例如,百货商店里 好看的花布”就不成为一个集合,因为对每一种布,没有确定的 标准说它是“好看”还是“不好看”。“这个班里的高个子学生” 也不构成一个集合。因为在“岛个子”与“不是高个子”之阁没 有明确的界限。但悬,如果我们给出“个完全确定的标准(如身 高h≥17米),合乎这个标准的算是“高个子”,否则不算,那么 对于这个班里的每一个学生,总可以明确地断定是否合乎这个标 准,不会发生两可的情形,这村“这个班里的高个子学生”就构 威一个集合 下面介绍儿个常见的集合的表示符号。 N:正鑫数或自然数集合(1,2,3,…) z:非负整数集合(0,12,3,)。 :整数集合(0,-1,1,-2,2y) P:素数集合(只能被1和它本身整除,不能被其他正整数整 除的大于1的正整数称作素数) :有理数集合〈有理数是可以表示成订形式的数,这里i 和j都是整数,且j≠0) R:实数集合(包括全部有理数和无理数)。 C:复数集合(包括所有形如4+的数,其中a、b是实数 ′-1) Nn(m≥1):介于1和m之的正整数集合;计入1和m(1 2。·,) zm(m≥1):介于0和m-1之间的非负整数集合,计人和 →1(0,1.2,“,71~1) 对于集合,有下面两种常用的表小方法。 把集合的元素孩任意癫序逐…在一个花括弧里,并用话号 分开,这称为列举法。例如,设“1,a2…,是集合A的元素,此 外A无其它元素,则焦合A可表示为A=i01,a2,…,Qn}。又如 绝对值不超过3的所有整数的集合,可记作S={-3,-2,-1, 0,】,2,3},列举法必须把元素的全体尽列出来,丽不熊遗漏低何 个,因此,如果…-个集合含有许多元素时,用列举法是极其麻 烦的。当集合含有元穷多个元素时,列举法更是无能为力,但 这情形,有时起列些出集合的一部分元素,而麟掉的元素应 能列器出的元素以及它们前后的关系所确冠,使得人们一看就 明白.例外,N={1,2,3…}【={…-2,-1,0,1,2…}。但这种 写注有时是很困难,可采用另一种表示方法。 集合的另一种表示法称为描述法,它是利用详细说明元素 a∈A的义条件作出来的。即给定一个条件P(x),当且仅当a使 茶件:P(q成立时,a∈A.其一般形式为A={a!P(a)},读成“A 是使P()成所有元素a集合”。实际上,P()描述了一个 郑则或公式,它使得我们有可能确定a是否在A中。例如,绝对 值不超过3的所有整数的集合用描述法可表示为Ss{a∈I且 3≤≤3又如,B=《a是中国的省j 用描述法来丧示个集合,其方式并不是唯一的,因为对 个集合玓兀素往往可以用多种不同的方式来确定。例如;集合 1,2,34:的元募可定义为不大于4的自然数,也可定义为小于 6而能整除!F然数,因此集合:1,2,3,4}可装示为{aia∈N, ≤4,电时校小为{4(N,a≤<6,a}12 关}集合的概念,还有点需要提起岩意的是,好作为集合的 元索的个纭,并没有纷它们施加什么限制。常常有一些集合其元 本身也是来合,例划·4=:5,{1,2;,,{},B={},{2,3}, {1,3}}。对于这情形,重要的是把集合{a}与元素a区别开 来。例如含是集合A的元素;q}∈A,前q是集合、q∶的 素 i,但q不是A的元素,即qA 而,对“钍罗…切的集合”或“由…切集合组成的集台”等 类似的犬W,我们必须避免使用,圆为它们会导致集俭论中的悼 论。例如,我们米不蔣名的罗素悖论 我们把不包自身作为元素的集合称为寻常集,而把包含自 身作为元素的柒合称为不箔集。于是可知一个集合或者是哥 常集,或者不是惮集,长必居其…,且只居其一。今设T是 由所句常集纠成的策合,即 了={A|A是集合,A¢A} 现在我佾老虑,T是等常集还是不寻常集?若T是等常集, 则哇T的定义,T必包含自身为元糸,因此T是不寻常集。这与 俊设矛眉。收T不是过出集,即T是不寻常集。然而由不寻常粜 釣定义。就烂须有'<T,與此T包含一个不寻常集为元素,这 又与T的定义矛盾。这就是说.由于慑定T的存在,无论T是寻 常集或不寻常集都将出矛适 又契,斫究下述情:某理发师跟只跟城里所有不能给自 羱发鲋人理发定义A为城里所有由该理发师理发的人的集 合,稍加考就会明臼,A一·定是这样的集合,该理发师∈A,而 又有该浬发师¢A,显然这是一个予膚。因此集合A不存在。 定义1-1不含亻任何汇素的集合,称为空橥,记作φ 空集冒起来很不然,但却是个有用的概念。例如,我们 两条平行线的交点之集是 集"即是说“两尔卩行线没有 交点”。又如x;X,X≡8=中,即愙呋着方程x2=8没有整数 根。一般说来,如果我们想要证明俞题P(x)对于一切x均不舆, 贴只要:P(x)=凼 集贫A巾不的数曰,泺为集合A的基数,月卡A表小, 当集合A具有有限数目的不同元素,亦即#A为有限时,称A为 有限集,否则称A为无限集。前述的集合N,Z,PQ,R和C都 是无限集;集合N和Zm是春限集,因为Nm=#Zm=m集合的 基数后邮还要软详细地讨沦。 2集合的包含和相等 集合的红含种祀是集合的个基本关系。 定义1-2有台A、B,如果A的每一个元素都是B的 元素(即若a∈A,必有a∈B),则称A是B的子集,或说A被包 含于B中(或B仁含A),记作A三B或B己A。反之,若A不是B 的子e,则记作A实B成BA 例1设A={a,,d,e;B={,,c,x],C={a,b},则有 C=B、但CsA 注总区别从属关系和包含关系,从属关系a∈A是指集合A 的元素与集合A的关系,前包含关系CsA是指集合A与另 个集合C之间的关系。 例2设A={a,b,,d,则有a∈A,而{GA 由从属关系科包含关系的定义订知,并不排斥同时有A∈B 和A=B的可能 例3设A={,b,C},B=:{,b,ea刚延然有A∈B 时A≌B 关于全的含育下重要性质: (1)对于任意的集合A,有中A 2)对于任意献集合A,有AsAy 3)对于任意的集含A、B、Cy 若A实B,BC,则有AC 性质(2)和(3)的成起明亞的。我们仅证明性质(1)。用 P一·一· 反证祛,设空集φ不是某集合A的子集,即φA,则必存在元素 x∈φ而x¢A、这与空集的定义矛盾,因此,φ〓A 定义1-3有集合A、B,如果A的每一个元素都是B的 元素,B的每一个元紫也都是A的元素,則集合A和B称为是相 ,记作A=B 显然,所谓集合A与集合B相等,即意味着A与B具有完全 相同的元素 由定义12和定义1-3可知,当且仅当A三B且B=A时,有 A= B. 定义1·3的实质是一个集合出它的全部元素所确定 下面给出一些相等集合积不等集合的例子 例4:1,2,4 这就是说,在集合的第一种表示法扌,某个元素的符号重复出现, 不会改变这个集合。然打为了叙述的方便,今后我们不使用这种 表示方法,要求死举的元素各不相同 例5{1,生,2=:1,2,4: 这说明在集合的第一种表示法中,若将元素的次序任意改变,集 合不变。 例6设P={{1,2},4},Q={3,2,4},则PQ。 又{{1}子{1} 如果A={Xx(x-1)=0},B={0,1},则A=B。 定义14设有集合A、B,若AB,且A≠B,奶称集合A 是集合B的真子集,用AB示 例如,集合1,2,节是集合!xxJ,-3≤X≤3的真子集 因为空集是每个集合子集,所以导出如下定理。 定魂t-1空集合是唯一的 证明假设有两个空集合中和中,因为空集被包含于每一个 集合中,因此有中三中,中2三=中1,这意味着中=中2。证完 6 ·■气 1.3幂集 任铃一集合A,我1知空集和集合A都是A的子集。对任 何元素a∈A,集合c;也是A的子集。类钣地,我们可以举出 A的其它子集。下面税打来讨论关于集合A的全部子集的集合 定叉1-5设有集合A,由A的所有子集组成的集合,称为 集合A的都集,记作2“,即 2={S」SsA} 例如,设A={a},则24={中{a}} B={a,b},则2={中,{a},{b},{ab CEa 2{,{a},{b};{c},{a,b},{a,C},也 b,cLi 乎5 集中的幂集,仅含有元素ψ,即2={如} 从上述例子可看出,当集合的基数增加吋,集合的幂集的基 数也随之增加。对于有限集下面的定理给出两者之间的关系。 定1-2设A是具有基数#A的有限集,则#(24x2 证啊设A=1,从个元素中选取个不同元素的方法共 有C种。这里 所以A的不同柔集的数目(包据虫)为 #(24)=c+C1+C+…+CF 由一项式定理可知 (x +3)=cix+ctsy+Cax-2y2+. ma,+Cwy 令x=y=1,便有 2=C十C1+C+·+C票 所以22·,因4里鸦截有#2)R完

...展开详情
试读 127P 离散数学基础(洪帆)
立即下载 身份认证后 购VIP低至7折
一个资源只可评论一次,评论内容不能少于5个字
pianaiwanglei 教材不错,就是不够清晰。
2013-12-01
回复
吃草的虫子 教材还不错,只是纸质不是很好
2013-05-26
回复
zhangbiao30 教材还是很不错,只是太模糊了一点
2013-03-25
回复
Octavian 不是很清楚 但是也很好用
2013-02-26
回复
zzcpp 只有教材,没有配套答案
2012-12-15
回复
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
关注 私信
上传资源赚钱or赚积分
最新推荐
离散数学基础(洪帆) 50积分/C币 立即下载
1/127
离散数学基础(洪帆)第1页
离散数学基础(洪帆)第2页
离散数学基础(洪帆)第3页
离散数学基础(洪帆)第4页
离散数学基础(洪帆)第5页
离散数学基础(洪帆)第6页
离散数学基础(洪帆)第7页
离散数学基础(洪帆)第8页
离散数学基础(洪帆)第9页
离散数学基础(洪帆)第10页
离散数学基础(洪帆)第11页
离散数学基础(洪帆)第12页
离散数学基础(洪帆)第13页
离散数学基础(洪帆)第14页
离散数学基础(洪帆)第15页
离散数学基础(洪帆)第16页
离散数学基础(洪帆)第17页
离散数学基础(洪帆)第18页
离散数学基础(洪帆)第19页
离散数学基础(洪帆)第20页

试读结束, 可继续阅读

50积分/C币 立即下载