第八章逻辑模型

敏锐的观察能力与严密的逻辑推理能力是科学研究必须具备的两项基本素质。爱因斯坦说过：“真正宝贵的因素是直觉。”大数学家庞加莱则认为，面对大千世界的复杂事实，研究者要做的事情首先是从所要研究的事实中作一选择。在他看来，作为这种选择的能力是由研究者的直觉能力决定的。

直觉是极其宝贵的，可仅凭直觉并不能令人信服。再伟大的科学家也会犯错误，包括犯直觉上的错误。直觉是数学发明的工具，而逻辑则是证明直觉的工具，直觉只有在经过逻辑上完全严禁的证明才会被人们普遍地接受。自从欧儿里得依据公理系统及严格的逻辑推理建立起他的几何学以来，数学的严格性、精确性至少已经经历了两千多年的考验，数学以公理化为标志所达到的高度是其他任何学科都不可比拟的。

§ 8.1 逻辑与数学

数学研究的是现实世界里数量关系中存在的共性，这些共性的发现自然起源于一个个的实例，但数学所涵盖的知识是前人从这些实例中总结、抽象出来的普遍规律，而不是这些实例本身。从某种意义上讲，数学的发展就可以看成是一个不断建模、不断完善的过程.。本节将举出一些浅显的例子来说明数学中的一些概念是怎样产生和发展的，人们又是怎样通过逻辑推理的办法来加深对客观世界的认识的。

一个刚开始接触数学的孩子会问妈妈这样的问题：“妈妈，为什么1+2 = 3？”。也许，孩子的妈妈会回答他说：“傻孩子，你看，这是一个手指头，那是两个手指头，合在一起，不是三个手指头吗？”这回，孩子似乎明白了一点，但他多半并没有真懂。说不定下次他还会去问妈妈什么是2，什么是3？为什么2+3= 5?……等等问题。

小学算术老师让孩子们背加法口诀表、乘法口诀表，为什么不教他们一个手指头加两个手指头等于三个手指头这样的算术呢。因为1+2=3讲的是一种共性，一个指头加两个指头是3个指头固然不错，可1个苹果加两个苹果不也是3个苹果、一匹马加两匹马不也是3匹马吗？当你真正理解了什么是1+2=3时，你能处理的是一般性的问题，而不只是几个手指头的加减。当然，为了掌握这些普遍的规律，你得先付出一定的代价，例如，你得先理解一个抽象的概念“1”，它既不是一个指头，也不是一个苹果，它代表的是物品的一个单位。为了将来计算得快些，不至于老像孩子那样数着手指头做加减乘除，你还应当背誦一些口诀表。这就使得某些人感到数学太抽象、太枯燥乏味，甚至会有人怀疑学这些抽象的东西究竟有没有用，抽象可以让人们去掌握更一般的规律，但与此同时，抽象也失去了原有的实际背景，使人们在初学时感到费解。

抽象过程会产生数学中的“概念”、“公式”（运算规律）及“定理”，你既需要像搞清“什么是1”那样去正确理解数学中的每一个新概念，像背九九表那样通过各种途径来熟练掌握每一个公式与运算规律（例如，你要背出求导公式和求导的运算法则等），也要懂得如何运用逻辑推理去得出新的结果（即定理），包括记住这些定理本身。懂得了这一点，你也就大致知道了学习数学和开展数学研究的基本方法。

例8.1（无理数的发现）

人们曾经在长达近2000年的时间里无法理解无理数，并因此而引发出所谓的第一次数学危机。古希腊在公元前五世纪时是世界上数学最先进的地区之一，当时，统治古希腊政治、

1

科学、宗教的是一个被称为“友谊联盟”的集团，该集团的领袖人物是赫赫有名的大数学家毕达哥拉斯（注：中学数学中有被称为毕达哥拉斯定理的勾股弦定理，三角形三内角之和等于180度也是毕达哥拉斯最先证明的，他还最先提出黄金分割等，对古代数学的发展作出过卓越的贡献）。古希腊数学家认为，最基本的数是整数，分数不过是两个整数的商（即当时的人们只承认有理数）。可是这种对数的认识却导出了重大的矛盾。据说毕达哥拉斯有一个叫希帕斯的学生，他在公元前470年左右时向老师提了一个问题：边长为1的正方形的对角线的长度是多少？我们都知道，该正方形的边长为2，可是，在当时2并不是一个数。因为如果2是“数”（即今天我么说的有理数），则应存在两个互素的正整数p和q，使得

2p，故又可得出p22q2，由于2是素数，2必整除p，即存在p1，使得p2p1，q2因而又可得2p1q2，同样因为2是素数，此式又说明2整除q，从而导出p与q有公因

子2的矛盾。正方形的对角线不可能没有长度，上面的证明又说明没有一个当时知道的数是该正方形的长度。毕达哥拉斯无法回答这一问题，为了维护学术理论的权威性，毕达哥拉斯竟指挥其学生们将希帕斯扔进了爱琴海，制造了数学史上的一起特大冤案。

以至于被人们误认为是数学2究竟是什么？这一问题困扰了人们长达1800多年之久，

的一大危机（数学史上称之为第一次数学危机。其实，所谓的数学危机只是原有的数学所表

现出来的一些缺陷，而每次“数学危机”的解决都会带来数学上的重大突破）。今天，大家都知道21.414213562373095048801688724097.......，它是一个无限不循环小数，不论写到哪一位，得到的都不是2。产生所谓数学危机的根本原因是由于人们对数的认识（即什么是数的定义）太狭隘了，不承认无理数我们连开方运算也无法实现。可承认无理数又必须具有极限概念。2是1.4，1.41，1.414，……，这样一个无穷有理数列的极限，没有极限概念就无法理解无理数。在很长的一段时期里，人们无法理解无理数，故而把它们称为“无理数”，所以，可以这么说，无理数是逻辑推理生出来的一个“怪蛋”。无理数的引入（随之而来的是极限概念的引入），引起了数学本身突飞猛进的发展。

数学是严格的科学，其严格性有时甚至达到了近乎苛刻的地步。有些人可能会认为没有必要这样做，从而对某些严格的证明产生厌倦情绪，殊不知，数学之美，就在于其简洁性与严格性。前面已经讲过，数学不相信猜测，只相信经过严格证明过的东西。从这一意义上讲，数学中每一新成果的诞生都是人们以逻辑为武器所取得的胜利

例8.2（导数是什么）

求导运算是微积分中的一种重要运算（就像初等数学中的加减乘除一样重要），以求即时速度为例

SS(tt)S(t) tt只是 ttt时间段内的平均速度，不论t是多么地小，它都不是t时刻的即时速度。

S但随着t0，将趋于t时刻的即时速度，这意味着即时速度应当用极限来定义。

t

2

在今日的微积分教材里是这样来定义导数的：

dyylim dxx0x然而，牛顿在创建微积分时使用的却是所谓“流数”x（相当于x）。例如，利用流数法求x的导数时是这样进行的：

n(xx)nxnx= nxn1nxn1nn(n1)n22xxx...xn1n(n1)n12xn2x...x = nx2x

上述写法虽然很简单，既运算方便又能解决实际问题（求导运算简便），理所当然地受到了数学界与物理学界的欢迎，但应当指出的是这种写法在逻辑上是不够严密的，有悖于数学的严密性，并引发了所谓第二次数学危机。不难看出，在前几个式子中，我们认为x是不等于0的（否则怎么可以做除数），但要得出最后一式，我们又认为x是等于0的，这不是自相矛盾吗？大主教、哲学家贝克莱曾讥讽地称这个一会儿不等于0一会儿又等于0的东西为“鬼魂”，数学史上则称此矛盾为“贝克莱悖论”。牛顿的流数法虽然看起来已引起了悖论，但由于它在解决实际问题时十分有效，在长达两个世纪的时间段里，仍一直被人们广泛地应用于各个领域。直到19世纪，康托、柯西等人建立了严格的极限理论，才最终解决了这一问题。原来，我们要求的是变化的趋势（即极限），x并不等于0，但x趋向于0，而导数则是在x0时变量

y的变化趋势。 x 极限和导数概念的出现为高等数学的产生和发展奠定了基础，引领人们走进了一个全新的数学境地。

例8.3（实数域概念的产生）

牛顿、莱布尼兹虽然建立了微积分，但当时的微积分还包含着另一个严重的问题。极限的引入使人们认识了无理数，从而产生了实数的概念。可是实数列的极限是否必定也是实数呢，会不会产生像有理数那样的情况（例如2不是可以写成有理数列的极限吗，但2却不是有理数）。这一问题直到20世纪初才被解决，人们证明了实数的完备性，即任意实数列的极限必定仍是实数，这才使我们完全放下心来，微积分才真正成为了一门严格的数学学科。

全体实数组成的集和不同于全体有理数组成的集合，在全体实数组成的集合中，你除了可以放心地进行加减乘除以外、也可以大胆地乘方、开方，不必担心运算的结果是否会出界。具有这种性质的数集被称为“数域”，故全体实数组成的集合被人们称为实数域。实数域的完备性则进一步说明在实数域中你甚至还可以大胆地进行极限运算，不必担心计算结果是否会出界。

例8.4（在实数集中到底是有理数多还是无理数多）

人们在接受无理数并搞清了实数集的完备性（即实数集中只有有理数与无理数）后，自然会想：究竟是有理数多还是无理数多？让我们再一次运用逻辑推理的方法来简要地讨论一下这一问题。

3

为了简单起见，我们仅比较0,1区间中的有理数和无理数。

不难看出，0,1区间中有无穷多个有理数，也有无穷多个无理数，也就是说，0,1区间内的有理数全体和无理数全体是两个无限集（即包含有无穷多个元素的集合）。两个无限集合是否能比较大小（即包含元素的多少）呢？没有学过高等数学的人会认为无限集有无穷多个元素，怎么进行比较，或者认为无限集中有数不完个数的元素，因而，无限集有同样多的元素。然而，一个训练有素的人却不会这样想，他们不会仅凭感觉做出判断，而会以逻辑推理为工具，去推导出这一问题的答案。 显然，我们不能再靠数元素个数的方法来比较集合的大小了（有限集比较大小是这样进行的），因为无限集中有数不完的元素。那么，怎样比较集合的大小呢？看来只好采用1-1对应的办法。如果两个集合中的元素可以1个对1个地对应起来，我们就应当认为这两个集合中的元素是一样多的。但假如我们这样来看问题，那么，整体大于部分就不一定成立了（只学过初等数学的人常常以为这总是对的），例如，自然数全体和偶数全体应当看成有同样多的元素个数，尽管自然数集合中还有大量的奇数。为什么呢？因为只要你让n2n，自然数与偶数之间不就1-1对应了吗？请看：

1 2 3 4 5 6 7 8 9 10 11 12 ·········· 2 4 6 8 10 12 14 16 18 20 22 24 ··········

难道将自然数集中的每一个数都乘以2，集合中的元素个数也会减少吗？

由了比较集合大小的方法，我们就可以开始进行比较了。考察由区间0,1中的全体有理数构成的集合，为叙述方便我们把它记成R，R中有无穷多个元素，rR，显然有

0r1，我们可以将它们按如下规则排成一列：每一有理数均可写成既约分数

先排q较小的，在q相同的时候则先排p较小的，即排成： 1，1/2，1/3，2/3，1/4，3/4，1/5，2/5，3/5，4/5，……… 将此数列记为

r1,r2,r3,.........rn,.........

这种可以按先后顺序排成一列的无限集合被称为可列集。

现取一个充分小的正数ε ，作一个长度为

p，pq，q的小区间把rn包围起来，（注意：一个数n2即为一个点，数学认为点是没有长度的，故任何长度大于零的区间均可将一个数包在里面）。这样的小区间有无穷多个，它们已将R中的所有元素包围起来，这些小区间的长度之和为：

n12n

由于ε可以任意小，故0,1中的有理数全体可以用总长度任意小的区间列包起来。（注意：我们事实上已证明任意可列集均可用总长度任意小的区间列包起来）

记0,1中的全体无理数构成的集合为Q，则Q不可能是可列集（称为非可列集），否则，我们将得出以下矛盾：0,1区间中的所有数均可被两个总长度任意小的区间列包起来，但

4

这是不可能的，因为0,1区间的长度为1且有理数和无理数充满了整个区间。

经过以上分析，我们已不难比较有理数集R和无理数集Q谁大谁小了。原来，在0,1区间中到处都有有理数，但与无理数相比，在0,1区间里有理数稀少到了可以忽略不计的地步，就像房间里到处都有空气，但空气并未沾满房间，其所占的总“体积”其实是0（当然，我们要重新考虑什么叫体积，这就导出了数学中所谓“测度”的概念，我们不在这里继续深究了）。

实数域的完备性证明和无限集合的分类已超出了理工科大学微积分课程的范畴，它们属于微积分的基础理论，是别的高等数学课程的教学内容。我们举出这两个例子是为了说明一个道理，数学不相信直觉，数学只相信是经得起逻辑推理检验的东西，就连我们对什么是“数”的理解也毫不例外。

§8.2 对数字的某些研究

科学家们在对数字本身的研究中表现出了惊人的观察力与想象力，正是这种观察、想象能力与严密的逻辑推理能力的结合，推动着数论学科的发展。在本节中，我们将举一些实例，说明在科学研究中猜测与验证是如何巧妙地结合在一起的。

例8.5（何时n为素数）

众所周知，只能被1和自身整除的正整数被称为素数，否则被称为合数。1770年，威尔逊（Wilson）提出了一个猜测：当且仅当(n1)！+1可被n整除时n才是素数。例如，5整除25（即4！+1），7整除721（即6！+1），5和7均为素数：9不整除40321（即8！+1），9不是素数。此猜测于1773年被拉格朗日证明，这就是数论中的威尔逊定理。威尔逊定理其实只有理论上的意义并无多大的实用价值，因为当n很大时，验证 (n-1)！+1能否被n整除事实上要比直接验证n是否为素数更加困难。

xx41，1772年，欧拉在其著作中给出了一个二次多项式：假如你取x = 0，1，……，

39，由多项式求得的竟然全部是素数，但如果令x取40，得到的则是41。多么奇妙的现象。

类似地还有：

22x2x11在x = 0，……，9时均为素数，但当x = 10时得到的是112

更有意思的是，xx72491在x =0，1，……,10000时得到的均为素数，但这一次，我们已不会再认为它总能给出素数了，不难看出，只要令x = 72490，则得到的并非素数，

27249172491 事实上，7249072491上述关系式是否暗示着素数分布的某种规律呢？可惜，人们至今仍未从中发现任何规律。1967年，斯塔克证明：当a > 41时，xxa不可能具有上述性质（指x取0~a1均为素数）。

222 5

猜测虽然并非总是正确的，但没有猜测，科学研究常常会停滞不前，从这一意义上讲，猜测为科学研究提供了动力，应当被看成科学研究中的重要一步，

例8.6（有多少素数）

人们很早就在猜测，自然数中有无穷多个素数。早在公元前，欧几里得就已经用反证法证明了这一猜测（这是人们所知道的关于素数有无穷多个的最早证明）。其证明大意如下：

设只有有限多个素数，它们是：P1,......,Pn 令PPPn1 1P2.......显然，P比所有的Pi,(i1,......,n)都大，P是正整数，但不能被任一Pi(i1,......,n)整除，故P必为素数，从而导出矛盾，证毕。

素数有无穷多个的猜测也可用正面方法来证明，有人曾作过仔细观察，发现直到6000000为止，在n于2n之间必存在素数，于是他大胆地提出了一个猜测：对任一自然数n，在n与2n之间至少存在一个素数。9年后，这一猜测被一位数学家证实。据此不难证明，在自然数中存在着无穷多个素数。

既然自然数中有无穷多个素数，那么，素数在自然数中所占的比例究竟有多大呢？设x为任一自然数，记不超过x的素数个数为(x)，例如，(10)4，因为不超过10的素数有2、3、5、7（1不算素数），共有4个。有人又作了如下的观察：

X x/(x) Ln(x) 据此，1800年，一位德国数学家和一位法国数学家又猜测当x趋向于无穷时有

2.5 2.3 10 100 4 4.6 1000 5.95 6.9 10000 8.14 9.2 100000 10.42 11.5 500000 12.05 13.1 lnx1，

x/(x)此猜测在96年后被两位法国数学家同时地证明了。从此，人们知道了以下事实： 当x非常大时，不超过x的素数大约有ln(x)个。

例8.7（默森数）

默森在其14年出版的著作“物理学与数学的深思”中曾作出过如下的猜测： 当p ≤ 257时，在形如21的数中只有11个素数，他们对应的p分别为2、3、5、7、13、17、19、31、67、127和257。 默森的猜测中包含了五个错误： （1）1883年，佩尔佛森证明了2（2）1903年，科尔指出26761p1是素数。

11937077217618382357287，故2671是合数。

6

（3）1911年，波尔斯证明了21是素数。

107（4）1914年，波尔斯又证明了21是素数。

257（5）1922年，克拉伊切克证明了21是合数而不是素数。

事实上，直到1952年，人们已知的最大素数是1877年吕卡斯用自己创立的方法证明的

21271，（这是一个39位数）。

1931年，雷默改进了吕卡斯的方法，他指出：21（ p ＞ 2 ）是素数当且仅当它

2能整除vp1，这里，v14，vk1vk2。

p根据递推关系式可求得：v214，v3194，v437634，„„。

7整除14，故7是素数。15（即21）不能整除194（即v3），故15不是素数而是合数。31（即21）整除37634（即v4），故31是素数，„„。从上面的计算不难发现，雷默的方法在验证21是否为素数时仍较麻烦，但利用计算机迭代求出vk，再检查2是否整除vk以检查2k1pk111是否为素数显然要比将其因式分解方便得多，故雷默的方法不失

为是一种非常好的方法，人们已经利用这类方法一一检查了所有p ＜ 20000的默森数

2p1，发现其中只有24个素数，最大的是p = 19937，是由塔克曼于1971年发现的。

例8.8（完全数）

一个数如果恰好是其全部真因子的总和，则此数被称为完全数，例如，6是完全数，因为6 = 1+2+3，28也是完全数，因为28 = 1+2+4+7+14。

完全数与雷默数有着密切的联系，2000多年前，欧几里得就已经知道：若21是素数，则Cp2p1(2p1)必为完全数。事实上，由于21是素数，故2p1(2p1)的全部真因子为：

1，2，„，2其总和为：

p1ppp2p及（21），„„，2(21)

p12......2p1(12......2p2)(2p1) = 2p(12.......2p2)2p1

= 2p1(12......2p1) = 2p1(2p1),此即需证。

完全数似乎都应该是偶数，但人们至今仍不知道这一猜测是否正确。1968年，塔克曼证明了在小于10的奇数中不存在完全数，但是在更大的奇数中是否存在完全数的问题，

36 7

答案至今仍然未知。

欧拉曾证明：欧几里得的公式包含了所有偶的完全数。1911年，迪克森又给出了此结果的一个简单证明。

设某偶完全数为2nq，其中n ≥ 1,q 为奇数。令q 的全部因子为

q1,q2,......,qm，其中q11，qmq，记Sq1q2......qm

由2nq是完全数及12......22 2n1q2(2nq)(2n11)S 故 Sqnn11可得

q2n11

有由于qS2n1及S、q 均为正整数可知q2n11及Sq1。由最后一个式子及S的定义又可知q2n11必为素数，证毕。

根据欧几里德的公式可得出前8个完全数是：C26,C328，C5496，

28，C78128，C1333550336，C1785869056，C191374386913。 C312305843008139952128 关于完全数，曾发生过一个令人啼笑皆非的笑话。1936年，“纽约先驱论坛报”曾作过如下报道：S.I.Kireger博士发现了一个155位的完全数—2256(22571)，为了证明此数为

257完全数，他整整花费了五年时间。事实上，正如例2中所说，1922年已有人证明了2是合数而非默森素数，从而，根据欧拉证明的结果，22561(22571)不可能是完全数，这位

学者白白浪费了宝贵的五年时间，可见，研究者在开始自己的研究之前，应当尽可能全面地了解现有的研究结果，否则，你的研究完全有可能是徒劳。 根据经欧拉证明的欧几里得公式，寻找完全数的难点在于寻找默森素数。现已由计算机证明，在n ＜ 20000的默森数21中只有24个是素数，由此可以看出，要寻找下一个完全数并不是一件容易的事情。

例8.9（费马数）

费马是世界公认的一流数学大师。他治学极为严谨，凡是他宣称证明过的定理（尽管证明有些已经失传），后人没人能指出其中的哪一个是错误的。所有他不能证明的猜测，在著作中他都会明确作出声明

费马在数论方面也有极丰富的研究成果。他曾作出过大量猜测，这些猜测经后人不懈地努力，几乎都被证明是正确的。唯一的一次例外,就是本例中介绍的费马数。 10年费马曾猜测：2

2nnn1均为素数。

8

记Fn221，称Fn为费马数。易见，F03，F15，F217，F3257，

nF465537，它们均为素数。

欧拉第一个否定了这一猜测，1732年他指出，F54294967297=1*6700417是合数而不是素数。借助于高斯创建的二次同余理论，兰德里于1880年指出F6也不是素数。1909年，墨尔里得和维斯顿又证明了F7和F8均不是素数，但他们无法分解它们的因式（这两个数的因式分解直到60多年后的1970年才找到）。

关于费马数，迄今为止人们已作过大量的研究，得到的结果都不是素数。因此，人们正在试图证明相反的结果：当n ＞ 4 时，Fn均为合数。

F1945是迄今为止人们研究过的最大数字之一，它大到根本无法书写出来的地步，其位

数已超过宇宙中的基本粒子数，据说有51*2

例8.10（费马大定理）

学过平面几何的同学都知道勾股弦定理，也牢记了345。

费马在其晚年著作中宣称：若n为大于2的整数，则xnynzn,(xyz0)没有整数解。这就是极为著名的费马大定理或费马最后定理。他还宣称，他已找到了一个完美的论证。

费马大定理难住了世人长达350多年。现存资料只留下了费马对n = 4时的证明，其余部分的证明均已丢失。其后，欧拉给出了n3时的类似证明，上述情况的证明方法均无法推广到一般情况中去。1823年，勒让得证明n = 5 时定理成立；1832年，狄里克里证明 n = 14时定理成立；1840年，拉梅与勒贝格证明 n = 7时定理成立，„„。350年中，数学家们一直在努力攻击这一难题，直到1994年，这一定理才被最终证明，攻克这一难题的是英国数学家怀尔斯，其论文发表在数学年刊（Annals of Mathematics）142卷第3期（1995年5月号）上。

在欧拉证明了xyz不存在正整数解后不久，有人猜测，可能：

44455555nnn， x1，„„,x1x14x2x3x4x2x3x4x5......xn1xn

333222260位。

均无正整数解。这一猜测长达近200年无人能加以证明。1966年，有人指出： 2784110133144

否定了以上猜测之一（中间一个）。接着，又有人指出： 2682440153656391879676020615673

95800217519414560422481（注：这是最小的一组解，可见举出这样的

4444444455555 9

nnn反例并非易事）此后，人们又证明了不定方程x1......xn1xn有无穷多组正整数解，

最后的结果竟与原先猜测的相差如此之远，这是人们始料所不及的。

例8.11（哥德猜想）

1742年，哥德在给欧拉的信中提出了一个猜想：看起来，至少每个大于1的数是3个素数的和，大于等于6的偶数都是两个素数的和，大于等于9的奇数都是3个素数的和。欧拉在回信中说：虽然我不能证明，但我肯定每个素数都是两个素数之和，这是一条正确的定理。这就是著名的哥德猜想，至今仍未得到最终解决。160多年来，许多功名卓著的数学家都在奋力攻击这一难题。1900年，当时的数学界领袖人物希尔伯特在世界数学家大会上提出了20世纪数学家要解决的23个著名问题，其中就包括了哥德猜想（第八问题）。 哥德猜想听起来似乎非常简单。一些数学功底不够扎实的年轻人误以为它应当不难证明，想碰碰自己的“运气”，轻率地“立志”要攻克这一难题，殊不知这样做其实是没有成功希望的，真想研究这一问题的人首先应当明白这样一个道理，连欧拉都说不会证明的题目绝不可能是一个简单的课题。下面让我们来看一下，数学家们为了攻克这一难题，100多年来走过的道路是多么地艰难：

1912年，数学家郎道将哥德猜想减弱为以下猜测：存在一个正整数M,使每一个自然数均可表示为M个素数之和。此猜测于1930年被证实。

1937年，哥德猜想的后半句，即大于等于9的素数可写成3个素数之和，被前苏联数学家维诺格拉多夫证实，这是哥德猜想的一个重大突破，在当时曾引起不小的轰动。 1920年挪威数学家郎道用古老的筛选法证明了（9+9），即每个充分大的偶数都可表示为两个殆素数之和，所谓殆素数是指素因子不超过9的数。

1924年，德国数学家拉德玛哈尔证明了（7+7） 1932年，英国数学家麦斯特曼证明了（6+6） 1938年，前苏联数学家布赫斯塔布证明了（5+5）。同年，我国数学家华罗庚证明对几乎所有的偶数都成立者（1+1）

1940年，布赫斯塔布又证明了（4+4）

以上结果（p,q）中p、q均未达到1，1947年，雷尼证明了（1+6）

1955年，我国数学家王元（华罗庚的学生，中国科学院院士）证明了（3+4） 1957年，前苏联数学家小维诺格拉多夫证明了（3+3），同年，王元又证明了（2+3） 1962年，我国数学家（中国科学院院士）潘承洞证明了（1+5）。同年，潘承洞与王元一起又证明了（1+4）。

1965年，布赫斯塔布、小维诺格拉多夫和邦比尼证明了（1+3） 1966年，我国数学家（中国科学院院士）陈景润证明了（1+2），因原因，文章发表于1973年。这是迄今为止关于歌德猜想的最好成果，虽然离哥德猜想的最终证明只剩下了最后一步，即直接证明（1+1），30多年过去了，但人们始终未能跨越这一步。

数论是一门历史悠久而又富有挑战性的数学分支，自从数字出现以来，人们可以说从未停止过对数字本身及其内在关系的研究。本节介绍的只是数论中极为普通的几个例子，但从这些例子中已经可以看出，没有敏锐的观察力与丰富的想象力，科学研究常常会失去方向和动力；而没有严密的逻辑推理和灵活的技巧（包括创造力），又不可能将观察到的现象转化为普遍规律，使之成为人类掌握的知识财富。两者相辅相成（很难区分谁更重要），推动着人类社会的文明与进步。

10

§8.3 几个数学游戏

本节将采用逻辑推理方法讨论几个颇为有趣的问题。 一．

例8.12 在每一次人数不少于6人的聚会中必可找出这样的3人，他们或者彼此均认识或者彼此均不认识。在这里，认识是指双方面的。即只要有一方讲不认识对方，这两人就应算成不认识。

证明 采用图来描述这一问题，将人看成顶点，对n人的聚会构造一个n个顶点的图。对任意两点，如它们对应的两人是认识的，用一实线相连，否则用一虚线相连。

任取一顶点，例如υ1。它与其余五个顶点的连线中实线和虚线的条数至少有一个不小于3，不妨设实线的条数至少为3，例如υ1υ2、υ1υ3和υ1υ4为实线。如图8.1所示。

图8-1 现考察边υ2υ3、υ2υ

4

相识问题（拉姆塞定理）

和υ3υ4。若它们中至少有一条是实线，则已存在三边均为实

4

线的三角形，从而存在三个彼此均认识的人；否则，三角形υ2υ3υ

的三边均为虚线，相

应的三人均不认识，与υ1相关联的边中至少有三条虚边的情况可类似证明。

拉姆塞问题也可如下叙述：用两种颜色对6阶（即6个顶点）完全图的边染色（称为6阶2色完全图），则必可从中找出一个单色边组成的一角形，即6阶2色完全图中必含有3阶单色完全图。具有这一性质的双色完全图至少应为六阶，我们记这一结果为r(3,3)6，并称之为拉姆塞数。括号内有两个分量，表示双色图，括号内的两个3，表示要求存在两种颜色的3阶单色完全图之一，6表示具有上述性质的双色完全图的最小阶数为6。此结果最初是由英国数学家拉姆塞于1928年在伦敦数学会上提出的，故被称为拉姆塞定理。

事实上，我们还可推出许多其他的结果。

命题8.1 任一6阶2色完全图中至少含有两个3阶单色完全图。

证明 我们已经证明，必存在3阶单色完全图，不妨设为υ1υ2υ3，其边用实线表示，见图8-2。

11

图8-2

若υ4υ5υ6也是单色完全图（即单色三角形），则命题已得证。从而可设其中至少有一边与υ1υ2υ3的边异色，不妨设为边υ4υ5，用虚线表示之。

易见υ1υ4、υ2υ4、υ3υ4至少应有两条与υ1υ2υ3的边异色（虚线），否则已存在另一个3阶单色完全图，不妨设它们为υ1υ4和υ2υ4。

同理，υ1υ5、υ2υ5、υ3υ5中至少有两条与υ1υ2υ3的边异色（虚线），故υ1υ5与υ2υ5中至少有一条是虚线，从而存在第二个3阶单色完全图。

图8.3表明，确实存在着只含2个3阶单色完全图的6阶双色完全图

（图8.3）

例8.13 在平面上给定6点，设其中任意3点均构成边长全不相等的三角形，证明在这6点构成的完全图中必存在两个三角形，其中一个三角形的最长边在另一个三角形中却是的最短边。

证明 现用红蓝两种颜色对由此6点组成的完全图的边按如下方式染色：将每一三角形中的最短边染成红色，将其余边染成蓝色。根据r(3,3)6，从此6阶双色完全图中必可找出一个同阶单色完全图，由于此三角形中必有最短边，按染色规则，该最短边必被染成红色，故此单色三角形应为红色三角形。该三角形的最长边被染成了红色，同样根据染色规则，必存在某一个三角形，该最长边在那里却是最短边，此即需证。

命题8.2 7阶2色完全图至少含有4个3阶单色安全图。

证明 根据命题8.1，在由v1,......,v6构成的6阶2色完全图中必包含至少2个3阶单色完全图。

（情况1）如这两个3阶单色完全图（即三角形）有公共的顶点，去除这个公共顶点及

12

与其相关联的边并加入v7和与v7相关联的边，我们又得到了一个6阶2色完全图，其中至少也含有2个3阶单色完全图。显然这两个3阶单色完全图均非原先的那两个，命题得证。

（情况2）若两个3阶单色完全图没有公共顶点，去除任一顶点及相关边（其中的一个单色三角形将不复存在），加入顶点v7及相关边，由命题8.1，我们必可找出一个新的3阶单色完全图。这就是说，7阶2色完全图中至少含有3个3阶单色完全图。由于总共只有7个顶点，从这3个3阶单色完全图中必可找出两个共顶点的，从而可以像情况1那样加以证明。

拉姆塞指出r(3,3)6以后，引起了全世界数学家与计算机科学家的关注。你用两种颜色去给6阶完全图（即图论中所讲的团）的边染色，不论你如何染法，其中必可找出3阶的单色完全图来。多么奇妙的现象，在随意性中也包含着必然性。这不会是孤立的现象，应当还有大量类似的结果。经数十年的不懈努力，人们终于又发现并证明了： r(3,4)=9, r(3,5)=14, r(3,6)=18, r(3,7)=23, r(3,8)=28, r(3,9)=36 r(4,4)=18, r(4,5)=25, r(3,3,3)=17

迄今为止，人们发现的拉姆塞数总共只有上面的十个，要找到新的拉姆塞数已经极为困难。例如，1993年，英国曼彻斯特理工大学的S.P.Radziszowski和澳大利亚国立大学的B.D.Mckay用计算机求出了r(4,5)=25，其计算量达到了惊人的地步，即使用计算机求解，也得耗费11年的时间。如果采用类似的方法，我们几乎没有希望求得r(5,5), r(5,6),…。

例8.14 17位学者中每人都和其他人通信讨论3个方向的课题。任意两人间只讨论其中一个方向的课题，则其中必可找出3位学者，他们之间讨论的是同一方向的课题.

证明 将每一学者看成一个顶点，作一个17阶完全图。按讨论课题的方向对边染色，相同方向染成同一颜色，得到一个17阶3色完全图。

任取一顶点A，与它相关联的有16条边，其中必能找出6条相同颜色的边，不妨设A与υ1，„，υ6的连线有相同颜色。连接A和6个顶点υ1，„，υ6。如果这6个顶点间也有这种颜色的边，则已找到讨论同一方向课题的三位学者；否则，υ1，„，υ6及连接它们的边构成一个6阶2色完全图，由例1，必可从中找到一个3阶单色完全图，即找出三位讨论同一方向课题的学者。

（例13说明r(3,3,3)≤17，只需再作出一个16阶三色完全图，其中不含3阶单色完全图，我们就完成了r(3,3,3)=17的证明。要作出这样的16阶完全图并非难事，读者可自行给出一个）。

二、奇偶数校验及相关问题

有些结果常可利用奇偶数的差异或类似的性质加以证明，下面我们来考察几个十分简单的实例。

例8.15 拟用40块方形瓷砖铺设如图8.4所示的地面，但商店只有长方形瓷砖，其大

13

小为方形的两块。问购买20块长方形瓷砖后，是否可能不裁开而直接铺好图8.4（（a）、（b））中的地面？

(a) (b) （图8.4）

解 将图8.4中的(a) (b)黑白相间染色。显然，如长方形瓷砖不裁开，只能用来复盖相邻的两格，故复盖的两格必为一白一黑。图11.4(a)有21个黑格和19个白格，故不可能直接铺好，图11.4(b)中黑白格各为20个，读者很容易找到直接铺设的方法。

例8.16 设一块m×n的棋盘被若干个形如 的板块恰好盖满，试证明m×n必能被8整除。

证明 显然有4|m×n，故m、n中至少有一个为偶数，不妨设n为偶数，将棋盘按列黑白相间染色，见图8.5（a）由于n为偶数，黑、白列的数目相同，故黑白格数相同，设各为2k个。板块可以有许多种拼凑法，但容易看出，每一板块放置的方向（称之为定向）只有八种可能的选择，如图8.5(b)所示。

(a) (b)

图8-5

容易看出，不论按什么方向放置板块，每一板块均盖住奇数个黑格（1格或3格），故盖住棋盘的板块必有偶数个，从而，m×n的棋盘必能被8整除。

例8.17 拟将一批尺寸为1×2×4的商品装入尺寸为6×6×6的正方体包装箱中，问是否存在一种装法，使装入的该商品正好充满包装箱。

解 将正方体剖分成27个2×2×2的小正方体，并按图8.6所示黑白相间地染色。 再将每一2×2×2的小正方体剖分成1×1×1的小正方体。

14

图8-6

易见，27个2×2×2的正方体中，有14个是黑的，13个是白的（或13黑14白），故经两次剖分，共计有112个1×1×1的黑色小正方体和104个1×1×1的白色小正方体。

虽然包装箱的体积恰好是商品体积的27倍，但容易看到，不论将商品放置在何处，它都将占据4个黑色和4个白色的1×1×1小正方体的位置，故商品不可能充满包装箱。

§8.4 平面地图染色的四色问题

1853年，英国伦敦的一位大学毕业生格斯里（F. Guthrie，1831—19）在绘制英格兰地图时发现，只需要用四种颜色就可以将所有的郡都一一区分开来。他猜测有可能这是一个普遍规律，于是就和他的兄弟弗里德里克（Frederick）商讨起这一问题。他的兄弟带着这一问题去请教了德莫根（De Mogen）教授，德莫根教授对这一问题很有兴趣，但他也无法证明，就在给哈密顿爵士的信中讲述了这一问题。可是此时后来不了了之，慢慢被人遗忘了。

1878年，凯利认为四色问题非同寻常，但他自己又不会证明，就将此问题提到了伦敦数学会上，并指出了该问题证明中的若干困难，自此，四色问题才引起了数学界的广泛重视。

究竟什么是四色问题呢？四色问题是说：任何平面地图至多用四种颜色即可将其染色，使相邻的国家或地区均被染成不同的颜色。当然，这里对相邻要有一定的要求，否则结果可以不成立：（1）两个国家或地区相邻必须要有一条公共的边，只有一个公共的顶点不能算相邻 （2）国家必须是连通的（数学上称为单联通区域）。

1879年，肯普（ A. B. Kempe，1849—1922 ）宣称证明了四色问题并发表了他的论文。当时人们没有从文章中发现毛病，一度认为四色问题已被证明。

10年，希伍德（ P. J. Heawood，1861—1955 ）指出了肯普文章中的一个错误，他申明自己未能证明四色问题，并指出了证明时遇到的一些困难，但他证明了五色定理（即证明五种颜色总是足够的）。自此，四色问题再度引起了人们的注意。

肯普的文章中虽然有错误，但其思想方法还是很有价值的，此后的证明基本上都沿用了他的方法。

四色问题的主要困难在于：平面地图可以这样画，也可以那样画，在给定一张地图后，你会发现总可以用四种颜色来染色，在你染好颜色后，只要稍稍改动一下地图，又可改得非要用第五种颜色不可，但假如你对此地图从头开始染色，你又会发现还是可以做到只用四种颜色染色，你似乎进入了一个怪圈。

让我们来看看肯普是怎样分析这一问题的。肯普首先对问题作了一定程度的简化，提出了一种标准形式，证明只要能对标准形式的地图染色就可对任意地图染色。在他的标准图中，

15

排除了一些不必考虑的情况，例如，可以做出如下假设：

（1） 任意国家的顶点是三条和其他国家交界的边界线的交点。 （2） 任意国家都有五个邻国

（3） 不存在“环形”区域的国家（即将平面划分为内部与外部的国家） （读者可自行证明：只要会用4种颜色对标准地图染色，就会对任何地图染色）。

在上述假定下平面地图的染色被等价地转化为多面体的面的染色问题。到了20世纪，人们采用了肯普的上述思想，但避免了他所出的差错，得到了一系列的结果。1939年，弗兰克林（Franklin）证明在国家数不超过22个时用4种颜色来染色总是足够的：1950年，威恩（Winn）将可用4种颜色染色的国家数提高到35：1968年，此数又被增大到39；1975年被提高到52。

解决四色问题的另一技巧是将地图的染色转化为图的顶点的染色。地图的染色其实只和国家间的邻接关系有关，但相同的邻接关系可以被画成无数张不同的地图。将问题转化成图的顶点染色恰恰是抓住了问题的本质，抓住了内在的拓扑结构。例如，下面的图8.7（a）中的地图染色问题可被等价地转化为（b）中的图的顶点染色问题：

图8-7

在转化过程中，国家被变化成了图的顶点，两个国家如果相邻，则对应的顶点间用边相连。 容易看出，可以用同一颜色染色的顶点间不能有边相连，这样的顶点集在图论中被称为图中的集。由于我们希望使用尽可能少的颜色，故总希望在使用一种颜色时能够染尽可能多的国家，即我们希望能求出图中的极大集（即再增加任何国家得到的都将不是集），任一极大集中的顶点（国家）均可用一种颜色来染色，问题转变为在求出所有极大集后，还应求出最少需要几个集才能够把图中的所有顶点都包含住（这一问题被称为最小覆盖问题）。非常可惜的是无论是求图的所有极大集还是求最小覆盖都非常困难，他们都是NP难的，至今仍未发现任何求解它们的多项式时间算法。

例8.18 用最少种数的颜料将图8.8（a）中的地图染色.

16

(a) (b) （图8-8）

解：将图中国家编号，并作出相应的图G，如图8-8（b）所示。

步1 求G的所有极大集，解得：{1，4}，{1，5}，{2，5}，{2，6}，{3}，{4，6}。 步2 构造复盖问题，求出一个最小复盖。解得最小复盖：{{1，4}，{2，5}，{3}，{4，6}}。

于是，图8.8（a）可用四种颜料染色：用第一种颜料染1、4，用第二种颜料染2、5，用第三种颜料3最后，用第四种颜料染6。

§ 8.5 公平选举是可能的吗?

应用逻辑推理方法建立数学模型的一般步骤是：根据实际问题的特点，总结出几条不加证明就采用的性质，称之为公理体系；由公理体系出发，运用逻辑推理方法，推出一系列有用的结果，并最终解决想要解决的实际问题。自从欧几里得采用这种方法建立起以其名字命名的几何学以来，这种建模方法已经至少被使用了2000多年。本节以对选举问题的讨论为例，简要地说明应当如何来建立逻辑模型。

选举是人类社会生活中经常会遇到的一项活动。人们有时会参加竞选、选美，有时会参加评选优秀演员、优秀运动员、名牌产品等等。出于习惯想法或人们的良好愿望，也许有人会认为选举当然应该是绝对公平的，否则选举还有什么意义。然而下面的Arrow不可能性定理却雄辩地证明了以下事实：如果至少存在着三名候选人，那么所谓绝对公平的选举规则根本不可能存在。

在介绍Arrow定理以前，让我们先来分析一下几种常见的选举规则。

所谓选举，其实质就是在评选人对候选人先后（优劣）次序排队的基础上，根据某一事先规定的选举规则决定出候选人的一个先后次序，即得出选举的结果。现用I={1,2,„,n}表示评选人集合，用A={x,y,„}表示候选人集合，用 > , = , < 分别表示优于、等于、劣于，用(x>y)i表示评选人i认为x优于y，用（x>y）表示选举结果为x优于y并用pi表示评选人i的排序，p表示选举结果。 根据一般常识，A的排序应满足以下性质：

（1）x,yA，关系式(x>y)、(x=y)、(x17

（2）x,y,zA，若x≥y, y≥z,则必有x≥z；等号当且仅当前两个关系式均为等式时才成立。（传递性）

简单多数规则 该规则规定当且仅当(xy)i的评选人i超过半数时（有时为等）选举结果才为（x>y）。

例8.19 设I={1,2,3},A={x,y,u,v}，三位评选人的选票为 p1: x>y>u=v p2: y>x>u>v p3: x=u>v>y

根据选举规划，结果应为 p: x>y>u>v

简单多数规则的主要优点是简单易行，使用方便。但十分可惜的是这一规则有时会违反传递性（2）。

例8.20 设I= {1,2,3}, A={x,y,z} p1: x>y>z p2: y>z>x p3: z>x>y

根据规则，自然应有（x>y）, (y>z)和(z>x)，违反传递性。

简单多数规则虽然比较了候选人之间的优劣，但并未体现出在选举人心目中候选人之间的优劣程度。为了能体现出优劣程度，有人设计了以下的Borda数规则。

Borda数规则 记Bi(x)为p1中劣于x的候选人数目，记B(x)2多数3B(x)，称B（x）

ii1n为x的Borda数，Borda数规则规定按Borda数大小排列候选人的优劣次序，即当B(x)≥B(y)时有（x≥y），两关系式中的等号必须同时成立。

对于例18，可计算出B(x)=B(y)=B(z)=3，故选举结果为（x=y=z）。在这个例子中，使用Borda数规则得出的结果似乎更合乎常理。

Borda数规则有时也会得出不符合常理的结果： 例8.21 I={1,2,3,4}, A={x,y,z,u,v}，选票情况为 p1p2p3: x>y>z>u>v p4: y>z>u>v>x

计算得B(x)=12, B(y)=13，因此选举结果为（y>x）。但这里有三人认为x优于y，只有一个认为y优于x，然而结果却是y优于x，这样的结果是否合理还是很值得怀疑的。

我们希望能找出一种“公平”的选举规则来，以便能在一切情况下给出一个“合理”的选举结果。

那么，什么是“公平”的选举规则呢？我们应当给出一个“公平”的评判标准，即指出所谓公平的选举应当满足一些什么性质（公理）。也许你还会增加些其他条件，但根据常识，

18

以下五条似乎是必须具备的：

公理1 投票人对候选人排出的所有可能排列都是可以实现的。

公理2 如果对所有的i，有(x≥y)i，则必须有(x≥y)，而且在这种情况下当且仅当对一切i均有(x=y)i时，才有(x=y)。这表示选举尊重投票人的一致愿望。

公理3 如果在两次选举中，对任意i，由(xy)i(1)必可得出(xy)i(2)，则由(xy)(1)必可得出(xy)(2)。右上角的(1)，(2)分别表示第一次选举和第二次选举。这就是说，如果第一次选举中认为x≥y的评选人在第二次选举中均未改变对两人的评价，那么，若第一次选举结果为x≥y，则第二次结果必须也是x≥y。

公理4 如果在两次选举中，每个投票人对x、y的排序都未改变，则对x、y的两次排序结果也应当相同。这表示其他候选人（如z）的位置变动，不应影响到x、y之间的排序。

公理5 不存在这样的投票人i，使得对任意一对候选人x、y，只要有(x≥y)i就必有(x≥y)。这表示选举中不存在垄断选举的者。

现在我们来证明著名的Arrow不可能性定理。

定理8.1 如果至少有三名候选人，则满足公理1~公理5的选举规划事实上是不可能存在的。

证：我们将证明由公理1~公理4必可导出存在一个者，从而违反了公理5 。 为了叙述方便，先引入决定性集合的概念。称I的子集Vxy为候选人x、y的决定性集合，如果由所有Vxy中的I有(x≥y)i必可导出(x≥y)。显然，对于任一对候选人x、y，这样的决定性集合是必定存在的，例如根据公理2，全体评选人集合I就是一个决定性集合。此外，由公理4，可根据这样一次选举来判定集合Vxy是x、y的决定性集合：iVxy有(x≥y)i，iVxy，则有(x>y)i，而选举结果则为(x≥y)。

根据公理2，对任意一对候选人 x、y，均存在着他们的决定性集合Vxy，例如选举人全体所成的集合I就是他们的决定性集合。现在找出所有决定性集合中含元素最少的一个，不妨仍记为Vxy，我们来证明Vxy只能含有一个元素——某评选人i。假设不然，Vxy至少含有两个元素，则Vxy必可分解为两个非空集合的和，即

(1)(2) VxyVxyVxy子集Vxy与Vxy均非空且不相交。它们均不可能是任一对候选人的决定性集合，因为Vxy是最小的决定性集合。在这里，我们不妨假设IVxy，因为不然的话，将导出对任一对候选人x、y其决定性集合均为I，显然，这样的选举规则一般是得不出结果的。

根据公理1，以下选举是允许的： 当iVxy时，（x≥y≥z）i

19

(1)(1)(2)(2)当iVxy时，（z≥x≥y）i

当iVxy时，（y＞z＞x）i

其中z是任一另外的候选人（根据条件，至少有三名候选人）。现在考察选举结果，显

(1)然（x≥z）是不可能的，因为不然的话，Vxy就成了x、z的决定性集合，故必有（z＞x）。(2)又Vxy是x、y的决定性能合，故必有（x≥y）。于是由传递性，应有（x＞y），但这又说明Vxy是y、z的决定性集合，从而导出矛盾。以上证明说明Vxy不能分解，即Vxy={i}，i为某一投票人。

现在进一步说明，对于任意另外的候选人z，V={i}也是x、z的决定性集合。为此，考虑另一次选举：

(x＞y≥z)i，而（y≥z≥x）j≠i

显然，由于全体一致意见，（y≥z）必须成立。又由于{i}是x、y的决定性集合，故应有（x＞y）。于是，由传递性，必有（x＞z）。再由公理4，y的插入不应影响x、z的排序，故{i}也是x、z的决定性集合。类似还可证明，如果w是异于x、z的任一候选人，{i}也是w、z的决定性集合，这就是说，评选人i是选举的者。

容易看出，定理的证明是在至少有三名候选人的前提下完成的。若只有一名候选人，则此时已不构成选举问题；若只有两名候选人，则容易证明简单多数规则就符合Arrow提出的五条公理。此外，定理的证明并非说明任何选举中均存在着者，而是说明公理系统中存在着矛盾。

在一般情况下，利用公理化方法常常是希望得出一个肯定的结果，但在本节中，Arrow却对选举问题得出了一个否定的结果，这多少有点令人感到惊讶。证明过程是正确的（虽然还不够严格），而且这一定理还有其他的证明方法。

事实上，Arrow提出的公理系统中确实隐含着矛盾，下面举一实例说明之。 例8.22 设I={1,2}, A={x,y,z}，考察如下的四次选举：

(1)(1)（第一次）p1、p2 x＞y＞z

选举结果中自然应有x＞y。 （第二次）p1 x＞z＞y

(2) z＞x＞y p2(2)合理的结果应有x=z。 （第三次）p1 y＞z＞x

(3)p1(3) z＞y＞x

合理的结果应有y=z。

20

(4)（第四次）p1 x＞y＞z (4) z＞x＞y p2现在不难发现，如果要求选举规则满足Arrow公理体系，那么关于如何对第四次选举给出结果，我们就会感到左右为难了。事实上，不论第四次结果怎样，必然会和前三次的结果发生矛盾。首先，由公理1，第四次的选举应当是有效的。由公理2，必须有（x＞y）(4)，

(4)

再与第二次选举比较并根据公理3，则应有（x=z），与第三次比较并根据公理3，应有（y=z）(4)

。但关系式x＞y，x=z与y=z显然不能同时成立，从而导出矛盾。

一个可以考虑的改进方案为要求评选人给出他对每一候选人优劣程度的评价，然后按定

量方式决定候选人的顺序，但矛盾仍然不能避免，总可以构造出类似于Borda数规则中所举反例那样的例子来。

解决这一问题的另一途径是事先适当评选人的排序方式，使得可能出现的情况数减少，以便保证一个合理的选举规则的存在。由于本节的主要目的是介绍利用逻辑方法讨论实际问题的Arrow不可能性定理，关于选举问题我们就不再继续讨论下去了。

§8.6 信息量应当如何度量

我们生活在信息社会里，每天都要通过各种途径接受大量的信息。可是什么叫信息，信息对我们有什么用，信息量的大小又应当如何来度量呢？

让我们先来分析一下认识问题的过程。当我们对问题毫不了解时，对它的认识是不确定的。在了解过程中，通过各种途径获得了信息，逐渐消除了不确定性，获得的信息越多，消除的不确定性就越多。因此，我们可用消除问题不确定性的多少来度量信息量的大小。事实上，用这种方法来度量信息量的大小要比仅仅比较消息的条数更为科学。例如：

例8.23 假如在盛夏季节气象台突然预报“明天无雪”的消息，你一定会感到荒唐可笑，因为这是人所共知的事。在明天是否下雪的问题上，根本不存在不确定性，这条消息包含的信息量为零。

基于这样一种观点，美国贝尔实验室的学者香农（Shannon）应用概率论知识和逻辑方法推导出了信息量的计算公式。

21

In his words

\"I just wondered how things were put together.\"

Claude

Elwood

Shannon

(April 30, 1916 - February 24, 2001) has been called \"the

首先，香农提出了几条最为基本的性质，和前几节一样，我们不妨称它们为公理。根据常识，以下公理是信息度量时应当满足的：

公理1 信息量是该事件发生概率的连续函数。

公理2 如果事件A发生必有事件B发生，则得知事件A发生的信息量大于或等于得知事件B发生的信息量。

公理3 如果事件A和事件B的发生是相互的，则获知A、B事件将同时发生的信息量应为单独获知两事件发生的信息量之和。

公理4 任何信息的信息量均是有限的。

记某事件为M，该事件发生的概率为p，将获知M即将发生的信息量记为I（M）。 定理8.2 满足公理1—公理4的信息量计算公式为I(M)Clogap，其中C是任意正常数，对数之底a可取任意为不1的正实数。

证明：首先，由公理1，I(M)f(p)，其中f是函数符号，f连续。

若A发生必有B发生，则pA≤pB，由公理2，有f(pA)≥f(PB) ，故函数f是单调不增的。 若A、B是两个事件，则A、B同时发生的概率为pApB，根据公理3，又有f(PAPB)=f(pA)+f(pB)。为了证明方便，先作一变量替换。令p=a-q，即q=－logaP于是

pApBe(qAqB)，记f(p)(eq)g(q)，则上式化为：

g(qAqB)g(qA)g(qB)，g亦为连续函数。

现在来求具有性质g(x+y)=g(x)+g(y)的函数。首先，由g(0)=g(0+0)=2g(0)得出g(0)=0或g(0)=∞。但由公理4，后式不能成立，故必有g(0)=0。

记g(1)=C，容易求得g(2)=2C,g(3)=3C,„,一般地，有g(n)=nC。进而，由

m11111g(1)gng，可得gg(1)。于是对一切正有理数，可得到

nnnnnn

22

mmgC。这样，由连续性可知：对一切非负实数x，有g(x)=Cx。 nn当x取负实数时，由g(x)+g(－x)=g(0)=0，可得出g(x)=―g(―x)=cx也成立，从而对一切实数x，g(x)=Cx,故g(q)=Cq。

现作逆变换q=－logap，得

I(M)f(p)Clogap （8.1）

证毕。

若取a=2,C=1，此时信息量单位称为比特（bit, binary unit的缩写）；若取a=10,C=1，此时信息量单位称为迪吉特，（或哈特，Hartley的缩写）；若取a=e,C=1，此时信息量单位称为奈特（mat, nature unit的缩写）。

例8.24 设剧院有1280个座位，分为32排，每排40座。现欲从中找出某人，求以下信息的信息量。（i）某人在第十排；（ii）某人在第15座；（iii）某人在第十排第15座。

解 在未知任何信息的情况下， 此人在各排的概率可以认为是相等的，他坐在各座号上的概率也可以认为是相等的，故

（i）“某人在第十排”包含的信息量为

log215（比特） 3215.32（比特） 40110.32（比特） 1280（ii）“某人在第15座”包含的信息量为

log2（iii）“某人在第十排第15座”包含的信息量为

log2这一例子反映了对完全的几条信息，其总信息量等于各条信息的信息量之和，即公理3成立。对于相应不的信息，要计算在已获得某信息后其余信息的信息量时，需要用到条件概率公式，本节不再作介绍，有兴趣的读者可以参阅信息论书籍。

至此，我们已经引入了信息度量的定量公式。如前所述，它是信息对消除问题的不确定性的度量。这种似乎有点难以为人们所接受，其实，这只是人们的习惯在起作用。这里，我们不妨来作一次比较。在人们搞清楚热的奥秘以前，温度也是一个较为抽象的概念，因它实质上是物体分子运动平均速度的一种反映。人们天生就知道冷和热，但如何来度量它却曾经是一个难题。只有在解决了这一问题以后，以定量分析为主的热力学才能得到飞速的发展。信息问题也是这样，人们对各种信息包含的实质“内容”究竟有多少往往也有一个直观的感觉，但用什么方法来度量它，却比“今天15度”这样的更不易理解，因为它是通过更为抽象的概率来计算的。

作为一种特殊情况，当我们面临的是N个等概率的事件时，得知其中某一个将会发生的信息，其信息量应为

23

log2（平均信息量一熵）

1log2N（比特） （8.2） N设某一实验可能有N种结果，它们出现的概率分别为p1,„,pN,则事先告诉你将出现第i种结果的信息，其信息量为－log2pi，而该实验的不确定性则可用这组信息的平均信息量

Hpilog2pi （8.3）

i1N来表示。

由于（8.3）式与物理学中的熵只相差一个负号，因此也把平均信息量H（即期望值）称为熵，或称为负熵。

例8.25 投掷一枚骰子的结果有六种，即出现1—6点、出现每种情况的概率均为故熵H=log26≈2.585（比特）。

投掷一枚硬币的结果为正、反面两种，出现的概率均为

1，61，故熵H=log22=1（比特） 2向石块上猛摔一只鸡蛋，其结果必然是将鸡蛋摔破，出现的概率为1，故熵H=log21=0（比特）。

从例8.25可以看出，熵实质上反映的是问题的“模糊度”，熵为零时问题是完全清楚的，熵越大则问题的模糊程度也越大。

对于具有连续型概率分布的随机试验，熵的定义则为

H(p)p(x)log2p(x)dx （8.4）

熵具有一些十分有趣而又重要的性质，我们将以定理的形式列出，不加证明地对它们作一简单的介绍。

定理8.3 若实验仅有有限结果S1,„,Sn，其发生的概率分别为p1,„,pn，则当

p1pn1时，此实验具有最大熵。 n此定理既可化为条件极值问题证明之，也可以利用凸函数性质来证明，留给读者自己去完成。

定理8.4 若实验是连续型随机试验，其概率分布P(x)在[a,b]区间以外均为零，则当

p(x)1(x[a,b])时，实验具有最大熵（平均分布具有最大熵）。 ba定理8.5 对于一般连续型随机试验，在方差一定的前提下，正态分布具有最大的熵。 定理11.4和定理11.5均可化为条件极值问题加以证明。

定理8.6（最大熵原理）受到相互且均匀而小的随机因素影响的系统，其状态的概率分布将使系统的熵最大。（证明从略）

上述结果并非某种巧合。例如，根据概率论里的中心极限定理，若试验结果受到大量相互的随机因素的影响，且每一因素的影响均不突出时，试验结果服从正态分布。最大熵

24

原理则说明，自然现象总是不均匀逐步趋于均匀的，在不加任何限止的情况下，系统将处于熵最大的均匀状态。

例8.26 有12个外表相同的硬币，已知其中有一个是假的，可能轻些也可能重些。现要求用没有砝码的天平在最少次数中找出假币，问应当怎样称法。

解：由于每枚硬币均可能是真的，也可能是假的，且假币既可能轻些也可能重些，故总共有24种可能情况，每种情况发生的概率均为

1，因而问题的熵为log224。 24又由于每次实验（秤）最多可能出现三种结果，例如可将假币分成三部分，取其中两部分分放在天平两边，假币可能出现在任一部分中。根据定理11.3，这种实验在可能出现的各种事件具有相等的概率时，所提供的平均信息量最大，故实验提供的平均信息量不超过log23。

设最少需称k次，则这k次实验提供的总信息量不超过klog23=log23k，而问题的模糊度（熵）为log224，要使得在最不顺利时也能区分假币，必须log23k≥log224，故必须有k≥3（这只是必要条件，由于估计中作了放大，还不能得出三次必能找出假币的结论）。

根据上述分析，第一次称前应将12枚硬币分成三堆，每堆4枚，这样可提供最大的平均信息量。将两堆分放于天平的两边。此时可能出现两种情况：

（情况1）两边相等，故假币在未秤的4枚中。任取其中的3枚，从已秤过的8枚中任取1枚加入（共得4枚），将此4枚钱币分成数量相等的两堆分放到天平的两边。如仍相等，则最后剩下的一枚是假币由于其余均为真币，再称一次即可知其比真币轻还是重。如两边不等，不妨设右重左轻，且不妨设加入的1枚（注意，它是真币）在左边。此时，我们知道的不光是假币在第2次称的3枚中，还知道如果它在天平右边，则应比真币重，如果在天平左边，则应比真币轻。这样，只需将天平右边的2枚钱币分放到天平两边称一次，结果就可得知了。

（情况2） 两边不等，不妨设右边较重。第二次按以下方法秤：先从左边取出两枚，再将右边的取两枚放到左边，将原来左边的两枚中取出一枚放于右边（每边三个），

（i）若两边相等，则假币在取出的两枚中，再称一次即可找出假币，（注意，轻的是假币）。

（ii）两边不等。若仍为右边较重，则假币在右边原来的两枚及左边未动过的一枚中（若为前者，则假币偏重；若为后者，则假币偏轻），于是再称一次即可找出假币。若第二次称时左边较重，则假币必在交换位置的三枚中，可类似区分真伪。

根据以上分析，称三次必能找出假币，且这是最少次数的称法。

可以看出，第二次称法的设计是求解的关键，读者可以自己分析一下为什么要这样设计。

习 题 8

1．某单位有50名工作人员，其中有15名已购置私家车，有12名已购置商品房，设有3名工作人员既购买了私家车又购买了商品房，问该单位还有多少名工作人员既未卖私家

25

车也未买商品房？

2．某招待所有100间客房，其中有50间是带有空调的，有40间是带有卫生间的，有30间是双人房（其余为单人房），已知该招待所带空调和卫生间的双人房共有20间，问既无空调又无卫生间的单人房至少有几间？

3．（梵塔问题）据说在印度北方的某庙宇里有一个巨大的黄铜板，板上竖立着3根石柱，其中的一根上套着下面大上面小的只两两大小不同的中间有孔的铜盘。传说这是佛祖用来考验人类智慧的，要求人们每天移动其中的一只铜盘，将其从原先的石柱上拿出，套到另外的石柱上，但必须遵守一个规则，不许任一较大的铜盘被套在较小的铜盘之上。那里的人普遍相信，只要将这只铜盘移到另一根石柱上，希玛拉雅山就会变成一座金山。僧侣们每天在移动着铜盘，可谁也没能完成任务。请你计算一下，要完成上述任务至少需要多少天。

4．证明：若xnynzn没有正整数解，则对任意的正整数k，xknyknzkn也没有正整数解。

5．证明区间1,1和区间,中具有同样多的点。

6．作一个五阶双色完全图，其中不含有任何三阶单色完全图（即单色三角形）。 7．求拉姆赛数是相当困难的事，作为一个尝试，你不妨可以试求一下r(3,4)

8．如果只有两名候选人，证明简单多数规则就满足Arrow的公理系统（即公理1~5。 9．如果国家可以不联通，则四色问题可以不成立，请举例加以说明之

10．证明：只要会用4种颜色对肯普提出的标准地图染色，就会对任意地图染色。 （提示：考察一下情况转换： 游戏p232）

26