版块导航: 正在加载中...

登录注册

应《网络安全法》要求，自2017年10月1日起，未进行实名认证将不得使用互联网跟帖服务。为保障您的帐号能够正常使用，请尽快对帐号进行手机号验证，感谢您的理解与支持！

24小时热门版块排行榜

>论坛更新日志 (4801)
>基金申请 (763)
>文献求助 (367)
>导师招生 (287)
>论文投稿 (233)
>休闲灌水 (233)
>虫友互识 (167)
>考博 (145)
>硕博家园 (114)
>考研 (54)
>教师之家 (44)
>公派出国 (39)
>博后之家 (34)
>找工作 (34)
>绿色求助(高悬赏) (28)
>外文书籍求助 (26)

返回列表

【奖励】本帖被评价44次，作者pkusiyuan增加金币 35 个

当前只显示满足指定条件的回帖，点击这里查看本话题的所有回帖

pkusiyuan

银虫 (正式写手)

应助: 0 (幼儿园)
金币: 15212.1
帖子: 773
在线: 130小时
虫号: 3451204

[资源] Discrete Mathematics and Its Applications 7th Edition 2011

Contents
About the Author vi
Preface vii
The CompanionWebsite xvi
To the Student xvii
1 The Foundations: Logic and Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Propositional Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Applications of Propositional Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .16
1.3 Propositional Equivalences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.4 Predicates and Quantifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
1.5 Nested Quantifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
1.6 Rules of Inference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
1.7 Introduction to Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
1.8 Proof Methods and Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .92
End-of-Chapter Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
2 Basic Structures: Sets, Functions, Sequences, Sums, and Matrices . 115
2.1 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
2.2 Set Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .127
2.3 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
2.4 Sequences and Summations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .156
2.5 Cardinality of Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
2.6 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
End-of-Chapter Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
3 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
3.1 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .191
3.2 The Growth of Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
3.3 Complexity of Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
End-of-Chapter Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232
4 Number Theory and Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .237
4.1 Divisibility and Modular Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237
4.2 Integer Representations and Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
4.3 Primes and Greatest Common Divisors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
4.4 Solving Congruences. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .274
4.5 Applications of Congruences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .287
4.6 Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294
End-of-Chapter Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306
iii
iv Contents
5 Induction and Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311
5.1 Mathematical Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311
5.2 Strong Induction andWell-Ordering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333
5.3 Recursive Definitions and Structural Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .344
5.4 Recursive Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 360
5.5 Program Correctness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372
End-of-Chapter Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377
6 Counting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385
6.1 The Basics of Counting. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .385
6.2 The Pigeonhole Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 399
6.3 Permutations and Combinations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407
6.4 Binomial Coefficients and Identities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415
6.5 Generalized Permutations and Combinations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423
6.6 Generating Permutations and Combinations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434
End-of-Chapter Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 439
7 Discrete Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445
7.1 An Introduction to Discrete Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445
7.2 Probability Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .452
7.3 Bayes’ Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 468
7.4 Expected Value and Variance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .477
End-of-Chapter Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494
8 Advanced Counting Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .501
8.1 Applications of Recurrence Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 501
8.2 Solving Linear Recurrence Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 514
8.3 Divide-and-Conquer Algorithms and Recurrence Relations . . . . . . . . . . . . . . . . . . . . . . .527
8.4 Generating Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 537
8.5 Inclusion–Exclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 552
8.6 Applications of Inclusion–Exclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .558
End-of-Chapter Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 565
9 Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 573
9.1 Relations and Their Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 573
9.2 n-ary Relations and Their Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .583
9.3 Representing Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 591
9.4 Closures of Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 597
9.5 Equivalence Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .607
9.6 Partial Orderings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 618
End-of-Chapter Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 633
Contents v
10 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 641
10.1 Graphs and Graph Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 641
10.2 Graph Terminology and Special Types of Graphs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .651
10.3 Representing Graphs and Graph Isomorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 668
10.4 Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 678
10.5 Euler and Hamilton Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .693
10.6 Shortest-Path Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .707
10.7 Planar Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 718
10.8 Graph Coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .727
End-of-Chapter Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 735
11 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .745
11.1 Introduction to Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 745
11.2 Applications of Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .757
11.3 Tree Traversal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 772
11.4 Spanning Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 785
11.5 Minimum Spanning Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 797
End-of-Chapter Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 803
12 Boolean Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .811
12.1 Boolean Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 811
12.2 Representing Boolean Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 819
12.3 Logic Gates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 822
12.4 Minimization of Circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 828
End-of-Chapter Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 843
13 Modeling Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 847
13.1 Languages and Grammars . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 847
13.2 Finite-State Machines with Output. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .858
13.3 Finite-State Machines with No Output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 865
13.4 Language Recognition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 878
13.5 Turing Machines. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .888
End-of-Chapter Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 899
Appendixes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A-1
1 Axioms for the Real Numbers and the Positive Integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2 Exponential and Logarithmic Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3 Pseudocode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
Suggested Readings B-1
Answers to Odd-Numbered Exercises S-1
Photo Credits C-1
Index of Biographies I-1
Index I-2

回复此楼

» 本帖附件资源列表

欢迎监督和反馈：小木虫仅提供交流平台，不对该内容负责。
本内容由用户自主发布，如果其内容涉及到知识产权问题，其责任在于用户本人，如对版权有异议，请联系邮箱：xiaomuchong@tal.com
附件 1 : 离散数学及其应用（英文第七版）Discrete_Mathematics_and_Its_Applications_7th_Edition_2011.pdf

2015-03-12 11:51:47, 9.66 M

» 收录本帖的淘帖专辑推荐

Allen的英文原版+百科

计算数学与经济统计

Allen的数学

» 本帖已获得的红花（最新10朵）

vindichp

» 猜你喜欢

有多少人是今天查系统知道结果的？已经有17人回复
为什么资助数各大高校都创新高，自己申请怎么就这么难已经有8人回复
导师吐槽：我怎么摊上了这么个极品研究生！已经有7人回复
青基如何破局已经有7人回复
基金不中，共勉已经有10人回复
国自然面上复盘~欢迎讨论已经有11人回复
基金未中，这种答复是模板吗？已经有6人回复
看板上这么多中的，有点像50人群里49个人都是骗子的那种感觉…… 已经有6人回复
怎么看青基中了没有啊已经有5人回复
梦想已经有3人回复

» 本主题相关价值贴推荐，对您同样有帮助:

Journal of mathematics and its applications (JMA) 已经有3人回复
求助投稿期刊杂志已经有6人回复
【分享】Discrete Mathematics: Elementary and Beyond. 2003【已搜无重复】已经有3人回复

1楼 2015-03-12 11:52:17

已阅回复此楼关注TA 给TA发消息送TA红花 TA的回帖

regedit666

新虫 (初入文坛)

应助: 0 (幼儿园)
金币: 1.5
帖子: 3
在线: 3.7小时
虫号: 3139341

★★★★★ 五星级,优秀推荐

Thanks a lot!

回复此楼

18楼2015-07-29 19:41:37

已阅回复此楼关注TA 给TA发消息送TA红花 TA的回帖

相关版块跳转我要订阅楼主 pkusiyuan 的主题更新

返回列表

☆ 无星级 ★ 一星级 ★★★ 三星级 ★★★★★ 五星级

普通表情龙兔虎猫高级回复 (可上传附件)

最具人气热帖推荐 [查看全部]		作者	回/看	最后发表

[基金申请] 为什么资助数各大高校都创新高，自己申请怎么就这么难 +8	Kittylucky 2026-08-27	8/400	2026-08-27 18:33 by raiy123
[教师之家] 导师吐槽：我怎么摊上了这么个极品研究生！ +7	苏东坡二世 2026-08-23	7/350	2026-08-27 18:14 by 瞬息宇宙
[基金申请] 基金不中，共勉 +10	eulota 2026-08-26	10/500	2026-08-27 17:23 by lqllinqiaoli
[基金申请] 国自然面上复盘~欢迎讨论 (金币+5) +10	晴天加油 2026-08-26	11/550	2026-08-27 16:35 by msuhlx
[基金申请] 怎么看青基中了没有啊 +5	叶九微 2026-08-26	5/250	2026-08-27 10:35 by l_zh2008
[基金申请] 面上合作单位盖章 +3	ssyjh 2026-08-27	3/150	2026-08-27 09:59 by 阿拉贡aragon
[硕博家园] 售SCI一区T0P文章，我:8.O.55.1.O.54,科目齐全,可+急 +3	LIbGuocjEEYw 2026-08-26	4/200	2026-08-27 02:01 by Ie9AyIAvGbvs
[基金申请] 2026年的国家社科基金项目通讯评审的新规则与新动向、新挑战 +7	process2012 2026-08-23	10/500	2026-08-26 19:23 by hmhminy
[基金申请] 系统查不到 +10	董八千 2026-08-26	10/500	2026-08-26 16:30 by Equinoxhua
[基金申请] 怎么查啊 +5	huang1991js 2026-08-26	5/250	2026-08-26 16:09 by Equinoxhua
[基金申请] 2026国自然函评费到账 +22	羊腰板 2026-08-21	25/1250	2026-08-26 15:00 by zuocuiping
[基金申请] 哪位高人中了，把查询到的截图贴出来让我看看，让我长长见识 +4	yuleib84 2026-08-26	5/250	2026-08-26 13:40 by yuleib84
[基金申请] 为什么国自然不能直接公布 +4	bjdxyxy 2026-08-26	4/200	2026-08-26 13:12 by qingmu1201
[基金申请] 国合里面能看到了 +7	一怀馨秋 2026-08-26	7/350	2026-08-26 11:23 by zhaosm1982
[职场人生] 学生撞见辅导员送外卖，第二天全班都沉默了 +3	鲸鱼融金_浙江_� 2026-08-22	3/150	2026-08-26 09:01 by zzuzxg
[基金申请] 在坚冰还盖着北海的时候，我看到了怒放的梅花。 (金币+10) +6	ziyangfang 2026-08-25	9/450	2026-08-25 20:26 by huagongfeihu
[基金申请] 明天应该可查了！？ +6	chengyan1220 2026-08-23	6/300	2026-08-25 19:45 by zfd97
[基金申请] 某些机构，以效率低为荣，以效率低作为存在感 +9	yuleib84 2026-08-25	10/500	2026-08-25 17:14 by alexon
[基金申请] 时间戳今天，20号变了 +5	archvillain 2026-08-20	5/250	2026-08-22 06:12 by hui_daxiao
[基金申请] 看来今天不会放榜了？ +8	chengyan1220 2026-08-21	11/550	2026-08-21 17:52 by dcqxinyang