正版新书]离散数学吴秀兰9787302514541

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

第3章集合集合论是现代数学的基础，它的起源可以追溯到16世纪末期.为了追寻微积分的坚实的基础，人们只进行了有关数集的研究.直到1876—1883年，康托发表了一系列有关集合论的文章，对任意元素的集合进行了深入的探讨，提出了关于基数、序数和良序集等理论，奠定了集合论的深厚基础.但是，随着集合论的发展，以及它与数学哲学密切联系所作的讨论，在1900年前后出现了各种悖论，使集合论的发展一度陷入僵滞的局面.1904—1908年，策墨罗列出了第一个集合论的公理系统，他的公理，使数学哲学中产生的一些矛盾基本上得到统一，在此基础上逐步形成了公理化集合论和抽象集合论，使该学科成为数学中发展最为迅速的一个分支.本章介绍集合的一些基本知识.3.1集合的基本概念在研究问题时，通常把具有某种性质的事物作为一个整体来研究，这个整体称为集合，其中的每个事物称为集合的元素.常用英文大写字母A,B,C等表示集合，以英文小写字母a,b,c等表示集合的元素.a∈A表示a是A的元素，aA表示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或aA二者必居且仅居其一.（2）集合的确定不应引起悖论.如A={x|xA}不能定义成为一个集合.（3）集合中的元素具有无序性.如{a,b}={b,a}.定义3.1.2集合间的关系有如下定义：（1）设A，B为集合，AB表示A是B的子集，即如果a∈A，则a∈B.（2）设A，B为集合，AB表示A是B的真子集，即AB且存在b∈B使bA.（3）设A，B为集合，A=B表示AB且BA，即A和B元素相同，称作A与B相等.（4）称P(X)={A|AX}为X的幂集，即X的所有子集组成的集合，有时也记为2X.根据讨论问题的需要，常设一个充分大的集合为全集，也称为基本集，所讨论的集合均为这个集合的子集.[3]第3章集合[3][1]3.2集合的基本运算[3]注（1）X含有n个元素，则X有2n个子集，即P(X)含有2n个元素.（2）空集是任一集合的子集.（3）包含关系满足以下性质：①AA；（自反性）②若AB,BA，则A=B；（反对称性）③若AB,BC，则AC.（传递性）例3.1.1设A={a,b},求P(A).解P(A)={,{a},{b},{a,b}}.注2={}，要区分与{}，其中表示空集，其中没有任何元素，而{}则表示以空集为元素的一个集族，即∈{}.一般用N,Z,Q,R,C分别表示自然数集、整数集、有理数集、实数集、复数集，它们满足NZQRC.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且xB}.定义3.2.4设X为基本集，集合A的补集记作Ac或，其定义式为Ac=X－A={x|xA且x∈X}.定义3.2.5设A，B为集合，A与B的对称差记作AB，其定义式为AB=(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.1X为集合，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.（德摩根律）