《离散数学及其应用（原书第5版）》章节试读

《离散数学及其应用（原书第5版）》的笔记-第692页

2.3节习题25，二分插入排序的分析中，最坏比较次数的复杂度答案给的是O(logn)，翻了下英文版，也是O(logn)。但是这应该是不对的。
T(N) = sigma(i=2, n-1) logi = log2 + log3 + ... + logn-1 = log(n-1)! = O(nlogn)
而且在实际中，logi应该是ceil(logi)

《离散数学及其应用（原书第5版）》的笔记-第4页 - 1.1.3 蕴含

看到“p仅当q”=“p->q”，不理解，第一反应是怀疑书打错了，应该是“q->p”吧，吃午饭时想着想着就突然顿悟了。。。
举个例子：
p：放假
q：周末
p仅当q：放假仅当周末
分析：如果放假，只有周末才有可能放假，不是周末就不可能放假，那么肯定是周末，p推出q，p是q的充分条件，q是p的必要条件，即“p->q”，而反之未必，如果周末，未必放假，周末可以放假，也可以不放假，也可以这周末放假下周末不放假，换句话说，放假肯定周末，周末不一定放假，p推得出q，q推不出p，所以“q->p”错误。
再想想如果没放假，那跟是否周末没关系，是不是周末都可以不放假，符合“p->q”。
如果还是没明白可以举个自己熟悉的例子仔细体会，我就是通过这个例子慢慢体会出来的。。。
转自：http://www.cnblogs.com/LYLtim/archive/2012/08/04/2623009.html

《离散数学及其应用（原书第5版）》的笔记-第253页

勘误：习题17：由5个ASCII码构成且至少(在符号位)包含一个@字符的串有多少个？
“在符号位” 是一个严重的翻译错误。原文是
@('at' sign)
已经完全吐槽不能了，我用不同的方法算了N次和答案都对不上。结果居然是这样。

《离散数学及其应用（原书第5版）》的笔记-第75页

习题2.d.书上是 学校及不再二年级的也不上离散的学生的集合。这里的也翻译是错误的。（除非也具有or的效果）
原文是：the set of students at your school who either are not sophomores or are not taking ds
可以在这里查看：http://www.docin.com/p-283223025.html&endPro=true#documentinfo
我知道这是第六版的，但是表述一般不会变。而且solution manual里的答案也是从‘或’给出的
最后说一句：翻译的时候认真点好么？亲！

《离散数学及其应用（原书第5版）》的笔记-第141页 - 第3章

第6版第3章例8（141页）的解答有点奇怪啊，($(n^2+3)*logn$)这部分，前面($n^2+3$)是($O(n^2)$)这个没问题，但($logn$)应该是($O(n)$)啊（见139页例7），那么($(n^2+3)logn$)应该是($O(n^2*n)=O(n^3)$)，为什么书中是($O(n^2*logn)$)呢，不解~

《离散数学及其应用（原书第5版）》的笔记-第11页

13.
假设两条路分别为a、b。问村民：你是否想告诉我路a通向遗址？
分析：
如果村民回答“是”。两种情况：村民说的是真话，那么路a通向遗址；村民说的是假话，意味着他想告诉我路b通向遗址，村民总说谎，说明路b通向遗址是假的，即路a通向遗址。
如果村民回答“不”。两种情况：村民说的是真话，那么路b通向遗址；村民说的是假话，意味着他想告诉我路a通向遗址，村民总说谎，说明路a通向遗址是假的，即路b通向遗址。
逻辑表达式：
p：村民回答是，q：村民总说真话，r：村民想告诉我路a通向遗址，s：路a通向遗址。则：
p∧q→r，r∧q→s；p∧¬q→¬r，¬r∧¬q→s；即p→s。
¬p∧q→¬r，¬r∧q→¬s；¬p∧¬q→r，r∧¬q→¬s；即¬p→¬s。

《离散数学及其应用（原书第5版）》的笔记-第99页

各种算法有若干共有的性质。在描述算法时记住他们是有用的。这些性质是：
* 输入 算法从一个指令的集合得到输入值
* 输出 对每个输入值集合，算法都要从每个指令的集合中产生输出值。输出值就是问题的解。
* 确定性 算法的步骤必须是准确定义的。
* 正确性 对每一组输入值，算法都产生正确的输出值。
* 有限性 对集合中的任何输入，算法都应在有限（可能很多）步之后产生所求的输出。
* 有效性 算法的每一步必须能够准确地执行，并在有限时间内完成。
* 通用性 算法过程应适用于要求形式的所有问题，而不只是用于一组特定的输出值。

《离散数学及其应用（原书第5版）》的笔记-第15页

卧槽，看的我都傻了，这逻辑。
附题一道，大家娱乐娱乐。
边远山区的每个人要么说真话，要么说假话。对旅行者的问题，村民要么回答是，要么回答不是，假定你再此旅游，到一个岔路口，一条路通向想去的遗迹，另一条路通向丛林深处，此时恰有一村民站在岔路口，问村民一个什么问题就能决定走那条路？

《离散数学及其应用（原书第5版）》的笔记-第190页

证明实数集不可数的构造式写错了，应该是
($$ d_{i} \begin{cases}
4 & \text{ if } d_{ii}\neq 4 \\
5 & \text{ if } d_{ii}= 4
\end{cases} $$)

《离散数学及其应用（原书第5版）》的笔记-第703页

11题的答案中，于是 ($$ a_{n} < n+k $$) 是错误的，应该是 ($$ a_{n} = n+k $$) 否则推不出结果

《离散数学及其应用（原书第5版）》的笔记-第112页

常用于估计特定计算机过程或算法需要的操作数的函数有：
($1$)<($logn$)<($n$)<($nlogn$)<($n^2$)<($2^n$)<($n!$)

《离散数学及其应用（原书第5版）》的笔记-第11页

14.
a) 问：你说谎吗？
分析：
p：指定的吃人者回答是，q：指定的吃人者总是说谎的。
p∧q→ ┐q，矛盾，该情况不存在；p∧┐q→ q，矛盾，该情况不存在。
┐p∧q→ q；┐p∧┐q→ ┐q。
综上，吃人者只可能回答“不”，且不论他是否说谎，这种回答都成立，因此探险者不能做出判断。
b)问：如果我问你是否说谎你将回答不，对吗？
p：指定的吃人者回答是，q：如果我问吃人者是否说谎他将回答不，r：指定的吃人者永不说谎。
p∧r→q，q∧r→r；
p∧┐r→ ┐q，┐q∧┐r→r，矛盾，该情况不存在；
┐p∧r→ ┐q，┐q∧r→ ┐r，矛盾，该情况不存在；
┐p∧┐r→ q，q∧┐r→ ┐r。
综上：针对这个问题，永不说谎的吃人者将回答“是”，总是说谎的吃人者将回答“不”，由此，探险者可以准确做出判断。

《离散数学及其应用（原书第5版）》的笔记-第175页

勘误：例3
证明：如果n是不能被2或3整除的整数，则n^2 - 1能被24整除
应该是不能被2[和]3整除。

《离散数学及其应用（原书第5版）》的笔记-第119页 - 函数

如果 f 是 从 A 到 B的函数, 则 A是 f 的定义域（domain），B 是 f 的陪域（codomain）。
如果 f(a) = b, 则说 b 是 a 的像（image），a 是 b 的原像（preimage）。f 的值域（range） 是A中所有元素的结合。还可以说 f 把 A 映射（map） 到 B。
我真不记得自己还学过这些Θ_Θ

《离散数学及其应用（原书第5版）》的笔记-第62页 - 1.5 证明方法

练习77题目翻译有误，原文he is neither impotent nor malevolent.应该翻译成：他既不无能也无恶意，小学生都会的翻译，结果中译版居然翻译反了。。。

《离散数学及其应用（原书第5版）》的笔记-第134页

习题勘误：23题的提示应该是
2^ab -1 = (2^a - 1)(2^a(b-1) + 2^a(b-2)+...+2^a +1)
中译版的态度令人发指

《离散数学及其应用（原书第5版）》的笔记-第126页 - 2.4.3 素数

素数无穷性的证明
素数有无穷多个。现在已知最早的证明方法是欧几里得在他的《几何原本》中提出的，该证明方法如下：
假设只有有限个素数。令。那么，N+1是素数或者不是素数。
如果N+1为素数，则N+1要大于，所以它不在那些假设的素数集合中。
如果N+1为合数，因为任何一个合数都可以分解为几个素数的积；而N和N+1的最大公约数是1，所以N+1不可能被整除，所以该合数分解得到的素因数肯定不在假设的素数集合中。
因此无论该数是素数还是合数，都意味着在假设的有限个素数之外还存在着其他素数。
对任何有限个素数的集合来说，用上述的方法永远可以得到有一个素数不在假设的素数集合中的结论。
所以原先的假设不成立。也就是说，素数有无穷多个。

　　但是，千万不可认为，形如p1·p2·...·pn+1（其中p1,p2,...,pn均为素数）的数就一定是素数！第八届全国青少年信息学奥林匹克联赛（NOIP2002)提高组初赛试题第三题第2小题，写程序运行结果，程序要找的就是形如p1·p2·...·pn+1（其中p1,p2,...,pn均为素数）的数中第一个是合数的整数。
2*3+1=7 是素数
2*3*5+1=31 是素数
2*3*5*7+1=211 是素数
2*3*5*7*11+1=2311 是素数
2*3*5*7*11*13+1=30031 不是素数，因为30031=59*509

　　但是例子中的13并不是假设中的最大的素数。如果13是最大的素数，那么例子中的“30031可以被59整除”中的59必然是合数，既然是合数，那么必然可以分解（这个可以证明），也就是说能被小于13的素数整除，很明显的矛盾了，这个例子的问题在于13不是最大的素数，本来就没有最大的素数的，所以根本不可能找到一个最大的素数反驳。这个例子说明的问题是：p1,p2,...,pn的乘积+1未必是素数，但首先得明确pn不是假设中的最大的素数，而是我们找到的其中一个素数。证明理论里是说所有的素数，而上面例子的59根本就没有出现在等式的左边。
　　详见：http://www.cnblogs.com/LYLtim/articles/2686973.html

《离散数学及其应用（原书第5版）》的笔记-第61页

48题的翻译应该是不对的。
根据答案：The number 1 has this property, since the only positive integer not exceeding 1 is 1 itself, and therefore the
sum is 1. This is a constructive proof.
猜测原题大意应该是：证明存在某个正整数等于不大于它的正整数的和

《离散数学及其应用（原书第5版）》的笔记-第463页

勘误：
有向图的邻接矩阵定义中，aij=1，若{vi,vj}是G的一条边
{vi,vj}改成(vi,vj)
由于没找到第五版的原书，只翻了第六版。第六版是正确的写法，所以推测是中译本译者的疏忽

《离散数学及其应用（原书第5版）》的笔记-第5页 - 第一章 基础: 逻辑证明,集合,函数 1.1 逻辑

p仅当q的理解略难,虽然文中尝试阐述,但还是很绕有木有
由于两者在自然语言不能通顺转化,所以会带来一定的理解难度
举个例子,
例子1
p = 群众革命
q = 政府倒台
套在 p->q 是很好理解: 如果群众革命,那么政府倒台
套在 p仅当q就别扭多了:群众革命仅当政府倒台
上面两个例子是混淆的根源,是容易误入的歧途
要理解他们的关系一定要在真值层面进行,试图在语言直觉层面理解只会自取其惑.
下面从真值关系入手
p仅当q:
p = 老鼠活着
q = 猫死了
p=true,q=true : true; 因为猫死了,老鼠也活着.
p=true,q=false : false; 猫没死,老鼠还活着,这不合理,因为老鼠只有在猫死了的情况下才活着.
p=false,q=false : true; 同上,猫没死,所以老鼠必然不能活,所以是真的.
p=false,q=true : true; 即时猫死了,老鼠也并不保证能够或存活啊,虽然很贱,却是合理
可以看出他的真值情况和p->q是一样的, 所以认为他们两是等价的.
另外文绉绉的仅当还可以换成"只有在...的情况下", 英文叫 "only if"

《离散数学及其应用（原书第5版）》的笔记-第155页

13题的答案看着不对啊
令 ($m' = \frac{m}{\gcd(c,m)}$)怎么就得出m'和c互素了？？

《离散数学及其应用（原书第5版）》的笔记-第87页

应该是三次方……

《离散数学及其应用（原书第5版）》的笔记-第50页

谬误中 否定假设谬误的命题给错了，应该是
p->q 析取 非P -> 非q

《离散数学及其应用（原书第5版）》的笔记-第11页

12.在古西西里的传说中有一个住在边远小镇上的剃头匠，只有穿过一条危险的山路才能找到他。这个剃头匠只给那些不自己剃须的人刮胡子。这样的剃头匠能存在吗？
网络上的答案普遍是：不存在。证明如下：
根据这句话“这个剃头匠只给那些不自己剃头的人刮胡子”，可以推出“剃头匠给人刮胡子当且仅当这些人不给自己刮胡子。”设命题 p：剃头匠给自己刮胡子。﹁q：剃头匠不给自己刮胡子。p↔﹁q：显然这个逻辑表达式是为假的。所以这样的剃头匠是不存在的。
不同观点：应是p→﹁q，而非p↔﹁q。即这些人不给自己刮胡子是必要条件，但题目中说“剃头匠只给那些不自己剃须的人刮胡子”，并非是剃头匠要给所有不自己剃须的人刮胡子，因此，他只要不给自己刮胡子就可以了。

《离散数学及其应用（原书第5版）》的笔记-第116页

习题勘误：
第37题，最后应该是：若 f_{1} \left( x \right) , \f_{2} \left( x \right 均可取负值，结论是否还成立。
即使是这样，我怎么还是觉得可以的。。。而且也得出了证明。渐进上界应该是没问题的，下界那块做了一个绝对值不等式的放缩，感觉也应该是对的。。。
可惜答案只说有可能不成立，没给出证明或者反例。。

《离散数学及其应用（原书第5版）》的笔记-第11页

15.
a) 如果吹北风，那么就会下雪。
b) 如果暖天持续一周，那么苹果树就会开花。
c) 如果活塞队打败了湖人队，那么他们就赢得了冠军。
d) 如果到了朗斯峰的顶峰，那么就走了有8英里。
e) 如果能够世界闻名，那么就可以得到教授职位。
f ) 如果你驾车超过400英里，那么你需要买汽油。
g) 如果你的保修单有效，那么你购买的CD机尚未超过90天。

《离散数学及其应用（原书第5版）》的笔记-第61页

第52题中的任意两个数之积改成 存在....
答案用的是鸽巢原理来说明必有两个数成绩为非负
如果按照任意来做的话，估计要估算了

《离散数学及其应用（原书第5版）》的笔记-第489页

习题46：但是删除顶点v和所有与v关联的边..这里的v应该是内部五角星上的顶点（根据答案推测的结果）
习题47：小题(a)是存在Hamilton Circuit的。答案有误。翻了下原书，正确，应该是中译版的问题。

《离散数学及其应用（原书第5版）》的笔记-第147页

时间复杂度，搞不懂啊