扫一扫
关注中图网
官方微博
本类五星书更多>
-
>
中医基础理论
-
>
高校军事课教程
-
>
思想道德与法治(2021年版)
-
>
毛泽东思想和中国特色社会主义理论体系概论(2021年版)
-
>
中医内科学·全国中医药行业高等教育“十四五”规划教材
-
>
中医诊断学--新世纪第五版
-
>
中药学·全国中医药行业高等教育“十四五”规划教材
离散数学/吴秀兰 版权信息
- ISBN：9787302514541
- 条形码：9787302514541 ; 978-7-302-51454-1
- 装帧：一般胶版纸
- 册数：暂无
- 重量：暂无
- 所属分类：>>
离散数学/吴秀兰 内容简介
本书共分8章，分别为命题逻辑、一阶逻辑、集合、二元关系和函数、代数系统、格与布尔代数、图论和树.在结构体系上，本书首先介绍数理逻辑及集合相关内容；其次介绍关系及代数系统；很后介绍图论与树的相关知识及应用.每一章的内容介绍之后都选配了适量的习题，做到少而精，注意突出重点.便于学生理解和掌握抽象理论和方法. 本书不仅可作为高等院校数学、计算机科学与技术及相关专业的教材，也可作为从事计算机工作的相关人员的参考书.
离散数学/吴秀兰 目录
1.1命题与联结词1
1.1.1命题与真值1
1.1.2命题联结词2
1.2命题公式及其解释6
1.2.1命题公式6
1.2.2命题的符号化7
1.2.3公式的赋值及真值表8
1.3命题公式的等值演算10
1.3.1命题公式的等值式10
1.3.2代入规则与替换规则11
1.4范式13
1.4.1合取范式与析取范式13
1.4.2主范式15
1.5联结词完备集18
1.6命题演算的推理理论20
1.7自然推理系统N中的形式证明22
习题127
第2章一阶逻辑30
2.1一阶逻辑基本概念30
2.2一阶逻辑公式及解释33
2.3一阶逻辑等值式与置换规则36
2.4一阶逻辑前束范式39
2.5一阶逻辑的推理理论40
习题246
第3章集合49
3.1集合的基本概念49
3.2集合的基本运算50[3]目录[3][1]目录[3]3.3集合中元素的计数51
习题353
第4章二元关系和函数54
4.1集合的笛卡儿积与二元关系54
4.2关系的运算57
4.3关系的性质63
4.4关系的闭包68
4.5等价关系与偏序关系74
4.6函数的定义和性质79
4.7函数的复合与反函数82
习题485
第5章代数系统88
5.1二元运算及其性质88
5.2代数系统94
5.3代数系统的同态与同构96
习题598
第6章格与布尔代数100
6.1格的定义与性质100
6.2分配格与有补格105
6.3布尔代数111
习题6114
第7章图论116
7.1图的基本概念116
7.2通路、回路和图的连通性123
7.3图的矩阵表示128
7.4欧拉图131
7.5哈密顿图135
7.6应用举例139
习题7142
第8章树144
8.1无向树及生成树144
8.2根树及其应用148
习题8153
1.1.1命题与真值1
1.1.2命题联结词2
1.2命题公式及其解释6
1.2.1命题公式6
1.2.2命题的符号化7
1.2.3公式的赋值及真值表8
1.3命题公式的等值演算10
1.3.1命题公式的等值式10
1.3.2代入规则与替换规则11
1.4范式13
1.4.1合取范式与析取范式13
1.4.2主范式15
1.5联结词完备集18
1.6命题演算的推理理论20
1.7自然推理系统N中的形式证明22
习题127
第2章一阶逻辑30
2.1一阶逻辑基本概念30
2.2一阶逻辑公式及解释33
2.3一阶逻辑等值式与置换规则36
2.4一阶逻辑前束范式39
2.5一阶逻辑的推理理论40
习题246
第3章集合49
3.1集合的基本概念49
3.2集合的基本运算50[3]目录[3][1]目录[3]3.3集合中元素的计数51
习题353
第4章二元关系和函数54
4.1集合的笛卡儿积与二元关系54
4.2关系的运算57
4.3关系的性质63
4.4关系的闭包68
4.5等价关系与偏序关系74
4.6函数的定义和性质79
4.7函数的复合与反函数82
习题485
第5章代数系统88
5.1二元运算及其性质88
5.2代数系统94
5.3代数系统的同态与同构96
习题598
第6章格与布尔代数100
6.1格的定义与性质100
6.2分配格与有补格105
6.3布尔代数111
习题6114
第7章图论116
7.1图的基本概念116
7.2通路、回路和图的连通性123
7.3图的矩阵表示128
7.4欧拉图131
7.5哈密顿图135
7.6应用举例139
习题7142
第8章树144
8.1无向树及生成树144
8.2根树及其应用148
习题8153
展开全部
离散数学/吴秀兰 节选
第3章集合集合论是现代数学的基础，它的起源可以追溯到16世纪末期.为了追寻微积分的坚实的基础，人们只进行了有关数集的研究.直到1876—1883年，康托发表了一系列有关集合论的文章，对任意元素的集合进行了深入的探讨，提出了关于基数、序数和良序集等理论，奠定了集合论的深厚基础.但是，随着集合论的发展，以及它与数学哲学密切联系所作的讨论，在1900年前后出现了各种悖论，使集合论的发展一度陷入僵滞的局面.1904—1908年，策墨罗列出了**个集合论的公理系统，他的公理，使数学哲学中产生的一些矛盾基本上得到统一，在此基础上逐步形成了公理化集合论和抽象集合论，使该学科成为数学中发展*为迅速的一个分支.本章介绍集合的一些基本知识. 3.1集合的基本概念 在研究问题时，通常把具有某种性质的事物作为一个整体来研究，这个整体称为集合，其中的每个事物称为集合的元素.常用英文大写字母A,B,C等表示集合，以英文小写字母a,b,c等表示集合的元素.a∈A表示a是A的元素，aA表示a不是A的元素. 定义3.1.1一个集合若由有限个元素组成，则称为有限集，否则称为无限集.特别地，元素个数为零的集合称为空集，记作“”.用符号“|A|”表示有限集A的元素个数. 常见的集合表示法分为枚举法和特性描述法.枚举法是将集合的元素一一列出.如集合A由元素a,b,c,d组成，可记为A={a,b,c,d}.特性描述法是用集合的元素所具有的共同性质来刻画集合.如A={x|x是正偶数}.一般集合可用A={x|P(x)}表示，其中P(x)表示事物x满足性质P，集合A由满足性质P的所有元素组成. 注（1） 集合的元素具有确定性，即元素a∈A或aA二者必居且仅居其一. （2） 集合的确定不应引起悖论.如A={x|xA}不能定义成为一个集合. （3） 集合中的元素具有无序性.如{a,b}={b,a}. 定义3.1.2集合间的关系有如下定义： （1） 设A，B为集合，AB表示A是B的子集，即如果a∈A，则a∈B. （2） 设A，B为集合，AB表示A是B的真子集，即AB且存在b∈B使bA. （3） 设A，B为集合，A=B表示AB且BA，即A和B元素相同，称作A与B相等. （4） 称P(X)={A|AX}为X的幂集，即X的所有子集组成的集合，有时也记为2X. 根据讨论问题的需要，常设一个充分大的集合为全集，也称为基本集，所讨论的集合均为这个集合的子集.[3]第3章集合[3][1]3.2集合的基本运算[3]注（1） X含有n个元素，则X有2n个子集，即P(X)含有2n个元素. （2） 空集是任一集合的子集. （3） 包含关系满足以下性质： ① AA；（自反性） ② 若AB,BA，则A=B； （反对称性） ③ 若AB,BC，则AC. （传递性） 例3.1.1设A={a,b},求P(A). 解P(A)={,{a},{b},{a,b}}. 注2={}，要区分与{}，其中表示空集，其中没有任何元素，而{}则表示以空集为元素的一个集族，即∈{}. 一般用N,Z,Q,R,C分别表示自然数集、整数集、有理数集、实数集、复数集，它们满足NZQRC. 3.2集合的基本运算 集合有并、交、差、补、对称差等运算. 定义3.2.1设A,B为集合，A与B的并集记作A∪B，其定义式为 A∪B={x|x∈A或x∈B}. 定义3.2.2设A,B为集合，A与B的交集记作A∩B，其定义式为 A∩B={x|x∈A且x∈B}. 定义3.2.3设A,B为集合，A与B的差集记作A－B或A\\B，其定义式为 A－B={x|x∈A且xB}. 定义3.2.4设X为基本集，集合A的补集记作Ac或，其定义式为 Ac=X－A={x|xA且x∈X}. 定义3.2.5设A，B为集合，A与B的对称差记作AB，其定义式为 AB=(A－B)∪(B－A). 对称差也称为布尔和. 以上定义的并和交运算称为初级并和初级交.下面考虑推广的并和交运算，即广义并和广义交. 定义3.2.6设A为集合，A的元素的元素构成的集合称作A的广义并，记作∪A，符号化表示为 ∪A=x|zz∈A∧x∈z. 例3.2.1设A=a,b,c,a,c,d,a,e,f，B=a，C=a,c,d.则 ∪A={a,b,c,d,e,f}，∪B=a， ∪C=a∪c,d，∪= 根据广义并定义，我们有，若A=A1,A2,…,An，则∪A=A1∪A2∪…∪An. 定义3.2.7设A为集合，A的元素的元素构成的集合称作A的广义交,记作∩A，符号化表示为 ∩A=x|zz∈A→x∈z. 考虑例3.2.1中的集合，有 ∩A=a,∩B=a,∩C=a∩c,d. 但空集不可以进行广义交，因为∩不是集合，在集合论中是没有意义的.和广义并类似，若A=A1,A2,…,An，则∩A=A1∩A2∩…∩An. 例3.2.2设A={{a},a,b},计算∪∪A,∩∩A和∩∪A∪∪∪A－∪∩A. 解∪A={a,b},∩A=a,∪∪A=a∪b, ∩∪A∪∪∪A－∪∩A=a∩b∪a∪b－a =a∩b∪b－a =b. 所以∪∪A=a∪b，∩∩A=a, ∩∪A∪∪∪A－∪∩A=b. [3][1]3.3集合中元素的计数[3]3.3集合中元素的计数 集合的运算可以用文氏图表示.文氏图的构造方法如下： E是全集，圆A,B的内部为集合A,B，如果没有关于集合不交的说明，任何两圆应彼此相交.图中的阴影区域表示集合A,B在相应运算下组成的集合.具体见图3.3.1. 图3.3.1 X为集合，A,B,C为X的子集，∪,∩,c为集合的并、交、补运算，有以下性质： （1） A∪B=B∪A,A∩B=B∩A；（交换律） （2） (A∪B)∪C=A∪(B∪C), (A∩B)∩C=A∩(B∩C)； （结合律） （3） A∪=A,A∩X=A； （同一律） （4） A∪Ac=X,A∩Ac=； （互补律） （5） A∪(A∩B)=A,A∩(A∪B)=A； （吸收律） （6） A∪(B∩C)=(A∪B)∩(A∪C)， A∩(B∪C)=(A∩B)∪(A∩C)； （分配律） （7） A∪A=A,A∩A=A； （幂等律） （8） A∪X=X,A∩=； （零律） （9） (Ac)c=A； （双重否定律） （10） A∪Bc=Ac∩Bc,(A∩B)c=Ac∪Bc. （德摩根律） 由以上性质知，在任何集合运算的公式中，将∪与∩互换，公式仍然成立.这就是集合论的对偶原则. 定理3.3.1（包含排斥原理）设S为有限集合，P1,P2,…,Pm是m个性质. S中的任何元素x或者具有性质Pi或者不具有性质Pi(i=1,2,…,m)两种情况必居其一.令Ai表示具有性质Pi的元素构成的子集，则S中不具有性质P1,P2,…,Pm的元素个数为 |A1∩A2∩…∩Am|=|S|－∑mi=1|Ai|+∑1≤i－∑1≤i+…+(－1)m|A1∩A2∩…∩Am|. 推论S中至少具有一条性质的元素数为 |A1∪A2∪…∪Am| =∑mi=1|Ai|－∑1≤i－…+(－1)m－1|A1∩A2∩…∩Am|. 当m=2时，有 |A1∪A2|=|A1|+|A2|－|A1∩A2|. 当m=3时，有 |A1∪A2∪A3|=|A1|+|A2|+|A3|－|A1∩A2|－|A1∩A3| －|A2∩A3|+|A1∩A2∩A3|. 一般包含排斥原理又称为容斥原理. 例3.3.1有120个学生参加考试，这次考试有3道题A,B,C，考试结果如下： 12个学生3道题都做对了，20个学生做对A,B两道题，16个学生做对A,C两道题，28个学生做对B,C两道题，做对A题的有48个学生，做对B题的有56个学生，还有16个学生一道题也没做对.求做对C题的学生有多少个？ 解设做对A题的学生为P1,做对B题的学生为P2,做对C题的学生为P3,由题意，根据容斥原理可知 |P1∩P2∩P3|=12,|P1∩P2|=20,|P1∩P3|=16,|P2∩P3|=28， |P1|=48,|P2|=56,|P1∪P2∪P3|=16,所以|P1∪P2∪P3|=120－16=104， 而 |P1∪P2∪P3|=|P1|+|P2|+|P3|－|P1∩P2|－|P1∩P3| －|P2∩P3|+|P1∩P2∩P3|， 因此|P3|=52，所以做对了C题的学生有52人. [3][1]习题3[3]习题3 1. 设A,B为集合，试确定下列各式成立的充分必要条件： (直接写结论就可以) (1) A－B=B; (2) A－B=B－A; (3) A∩B=B∪A; (4) AB=A. 2. 证明(A∪B=A∪C)∧(A∩B=A∩C)B=C. 3. 求下列集合的幂集: (1) A={a,b,c}，则P(A)=; (2) B={1,{2,3}}，则P(B)=; (3) C={}，则P(C)=; (4) D={,{}}，则P(D)=. 4. 设E=1,2,3,4,5,6,A=1,4,B=1,2,5,C=2,4，求下列集合(用枚举法写出集合的具体元素): （1） A∩BC； （2） (A∩B)∪CC； （3） (A∩B)C； （4） P(A)∩P(B)； （5） P(A)－P(B). 5. 用枚举法表示下面的集合： （1） S1=x|x=2∨x=5； （2） S2=x|x∈Z∧3（3） S3=x|x∈R∧x2－1=0∧x>3; （4） S4=〈x,y〉|x,y∈Z∧0≤x≤2∧－1≤y≤0. 6.设A=2,a,3,4,B=,4,a,3,C=1,2,1.求:(1) AB=; (2) P(C)=. 7. 设S={2,a,{3},4}，R={{a},3,4,1},指出下面的写法哪些是对的，哪些是错的. （1） {a}∈S;（2） {a}∈R;（3） {a,4{3}}S; （4） {{a},1,3,4}R;（5） S=R;（6） {a}S; （7） {a}R;（8） R;（9） {{a}}R; （10） {}S;（11） ∈R;（12） {{3},4}.第4章二元关系和函数第3章讨论了集合及集合的运算，本章研究集合内元素的关系以及集合间元素的关系，这就是关系和函数.关系和函数是很重要的数学概念，它在计算机科学技术中的许多方面有着重要的应用，如数据结构、数据库、情报检索、算法分析等.本章主要讨论二元关系理论. 4.1集合的笛卡儿积与二元关系 定义4.1.1由两个元素x和y(允许x=y)按一定顺序排列成的二元组，称为一个有序对或序偶，记作〈x,y〉，其中x是它的**元素，y是它的第二元素. 有序对〈x,y〉具有如下性质： 1. 当x≠y时，〈x,y〉≠〈y,x〉. 2. 〈x1,y1〉=〈x2,y2〉 的充要条件是x1=x2 且 y1=y2. 上述两条性质是二元集x,y所不具备的.例如，当x≠y时，有x,y=y,x.原因在于集合中的元素是无序的，而有序对中的元素是有序的. 例4.1.1已知〈x+2,3〉=〈3,2x+y〉，求x和y. 解由有序对相等的充要条件，有x+2=3, 2x+y=3.解得x=1，y=1. 定义4.1.2设A，B为两个集合，所有**元素属于A,第二元素属于B的序偶所组成的集合,称为集合A和集合B的笛卡儿乘积.记作A×B,即 A×B={〈x,y〉|x∈A∧y∈B}. 例4.1.2设A={a,b},B=0,1,C=,试求A×B,B×A,A×A,B×B,C×C,A×B×C和A×B×C. 解A×B=〈a,0〉,〈a,1〉,〈b,0〉,〈b,1〉,B×A=〈0,a〉,〈1,a〉,〈0,b〉,〈1,b〉, A×A=〈a,a〉,〈a,b〉,〈b,b〉,〈b,a〉, B×B=〈0,0〉,〈0,1〉,〈1,0〉,〈1,1〉, C×C=〈,〉, A×B×C=〈〈a,0〉,〉,〈〈a,1〉,〉,〈〈b,0〉,〉,〈〈b,1〉,〉, B×C=〈0,〉,〈1,〉, A×(B×C)={〈a,〈0,〉〉,〈a,〈1,〉〉,〈b,〈0,〉〉,〈b,〈1,〉〉}.[3]第4章二元关系和函数[3][1]4.1集合的笛卡儿积与二元关系[3]如果A=m，B=n，则A×B=mn.从例4.1.2不难看出笛卡儿积具有如下性质: 性质1对任意集合A，根据定义有 A×=，×A=. 性质2一般地说，笛卡儿积元素不满足交换律，即 A×B≠B×A(当A≠∧B≠∧A≠B时). 性质3笛卡儿积运算不满足结合律，即 A×B×C≠A×B×C(当A≠∧B≠∧C≠时). 性质4笛卡儿积运算对并和交运算满足分配律，即 A×(B∪C)=A×B∪A×C， (B∪C)×A=B×A∪C×A， A×(B∩C)=A×B∩A×C， (B∩C)×A=B×A∩C×A. 证明我们只证明**个等式.任取〈x,y〉∈A×B∪C，则有 〈x,y〉∈A×B∪Cx∈A∧y∈B∪C x∈A∧(y∈B∨y∈C) (x∈A∧y∈B)∨(x∈A∧y∈C) 〈x,y〉∈A×B∨〈x,y〉∈A×C 〈x,y〉∈A×B∪A×C, 所以有A×(B∪C)=A×B∪A×C. 类似地可以证明其他情形. 性质5AC∧BDA×BC×D. 采用命题演算的方法，可以证明性质5.该证明留给读者考虑. 值得注意的是,性质5的逆命题不成立,分以下几种情况讨论: (1) 当A=B=时,显然有AC且BD成立. (2) 当A≠且B≠时,也有AC且BD成立.具体证明如下: 任取x∈A,由于B≠,则存在y∈B.所以有〈x,y〉∈A×BC×D.由笛卡儿积的定义有x∈C且y∈D. (3) 当A=但B≠时,有AC成立,但不一定有BD成立.例如,取A=,B={1},C={2},D={3}. (4) 当A≠但B=时，有BD成立，不一定有AC成立.例如，A={1}，B=，C={2}，D={3}. 例4.1.3设A=1,2，求PA×A. 解P(A)={,1,{2},{1,2}},P(A)×A={〈,1〉,〈,2〉,〈{1},1〉,〈{1},2〉,〈{2},1〉,〈{2},2〉,〈{1,2},1〉,〈{1,2},2〉}. 例4.1.4设A，B，C，D为任意集合，判断以下命题是否为真，并说明理由. (1) A×B=A×CB=C; (2) A－B×C=(A－B)×(A－C); (3) A=B∧C=DA×C=B×D; (4) 存在集合A，使得AA×A. 解(1) 不一定为真，当A=,B={1},C={2}时,有A×B==A×C，但是B≠C. (2) 不一定为真，当A=B={2}，C={3}时,有 A－(B×C)=2－〈2,3〉={2}， A－B×(A－C)=×{2}=. (3) 为真. (4) 为真.取集合A=时，有AA×A. 定义4.1.3如果一个集合满足下列条件之一：
书友推荐
- >
人文阅读与收藏·良友文学丛书:一天的工作
人文阅读与收藏·良友文学丛书:一天的工作
¥14.7¥45.8 - >
【精装绘本】画给孩子的中国神话
【精装绘本】画给孩子的中国神话
¥17.6¥55.0 - >
伯纳黛特,你要去哪(2021新版)
伯纳黛特,你要去哪(2021新版)
¥25.4¥49.8 - >
姑妈的宝刀
姑妈的宝刀
¥13.5¥30.0 - >
有舍有得是人生
有舍有得是人生
¥14.4¥45.0 - >
新文学天穹两巨星--鲁迅与胡适/红烛学术丛书(红烛学术丛书)
新文学天穹两巨星--鲁迅与胡适/红烛学术丛书(红烛学术丛书)
¥9.9¥23.0 - >
巴金－再思录
巴金－再思录
¥14.7¥46.0 - >
月亮与六便士
月亮与六便士
¥18.1¥42.0
本类畅销
-
初等数论-(I)
¥15.6¥18 -
流体力学(第二版)
¥68.2¥96 -
模糊数学
¥47.5¥56 -
4.23文创礼盒A款--“作家言我精神状态”
¥42.3¥206 -
4.23文创礼盒B款--“作家言我精神状态”
¥42.3¥206 -
一句顶一万句 (印签版)
¥40.4¥68
