第八章逻辑模型.ppt

《第八章逻辑模型.ppt》由会员分享，可在线阅读，更多相关《第八章逻辑模型.ppt（94页珍藏版）》请在三一办公上搜索。

1、第八章 逻辑模型,数学建模基地,8 逻辑模型,欧几里得在不加证明而被直接采用的一些基本概念和公理的基础上。运用逻辑推理方法得出了一系列的定理、推论，从而建立了完整的欧几里得几何学，这一辉煌成果至今仍然是人类的宝贵财富。本章介绍的一些模型采用的也是类似的方法。建模者从问题应当具有的某些基本属性出发，运用逻辑推理方法或者导出满足这些基本属性的解来，或者证明在原有观念下问题不可能有解，从而从根本上改变人们对这一问题的看法,例1 在每一次人数不少于6人的聚会中必可找出这样的3人，他们或者彼此均认识或者彼此均不认识。,利用图的方法来描述该问题。将人看成顶点，两人彼此都认识用实线连，否则虚线。,证明：,问

2、题转化为在一个6阶图中必存在实线三角形或虚线三角形。,请大家一起画图证明,1,2,3,4,任取一顶点，不妨1,考察23、24和34,23、24和34只能是虚线，否则得证,但这样三角形234的三边均为虚线,拉姆齐问题也可这样叙述：6阶2色完全图中必含有3阶单色完全图。,其他类似可推出的结果：,命题8.1 任一6阶2色完全图中至少含有两个3阶单色完全图。,证明：前面证明必存在3阶单色完全图，不妨设123 为红色完全图,15、25、35中至少有两条黑色、故15与25中至少有一条是黑色,14、24、34至少应有两条黑色，不妨设14、24 黑色,所以存在第二个3阶单色完全图。,命题8.2 7阶2色完全图

3、至少含有4个3阶单色安全图。,命题8.3 18阶2色完全图中必含有4阶单色完全图。,对拉姆齐问题的认识不能仅仅停留在例11.1的水平上。利用逻辑推理方法，实际上还可获得一大批结果。命题11.2和命题11.3的证明留给大家自己去完成。,例2 17位学者中每人都和其他人通信讨论3个方向的课题。任意两人间只讨论其中一个方向的课题，则其中必可找出3位学者，他们之间讨论的是同一方向的课题。,证明：采用反证法，设，其中p、q互素，则有p2=2q2。因为2|p2，故2|p。记p=2p1，可得4p12=2q2，即2p12=q2，故又有2|q，与p、q 互素矛盾。,例3 证明 是无理数。,同样方法可以证明：若m

4、是大于1的素数，n是大于1的整数则 必为无理数。,例4 拟用40块方形瓷砖铺设如下图所示的地面，但商店只有长方形瓷砖，其大小为方形的两块。问购买20块长方形瓷砖后，是否可能不裁开而直接铺好地面？,解 将图11.4中的(a)(b)黑白相间染色。,显然，如长方形瓷砖不裁开，只能用来复盖相邻的两格，故复盖的两格必为一白一黑。下图(a)中共有21个黑格和19个白格，故不可能直接铺好，下图(b)中黑白格各为20个，大家很容易找到直接铺设的方法。,证明:显然有4|mn，故m、n中至少有一个为偶数，不妨 设n为偶数，将棋盘按列黑白相间染色，如下图(a)所示，由于n为偶数，黑、白列的数目相同，故黑白 格数相同

5、，设各为2k个。,板块可以有许多种拼凑法，但容易看出，每一板块放 置的方向（称之为定向）只有八种可能的选择，如下 图(b)所示。,容易看出，不论按什么方向放置板块，每一板块均盖住 奇数个黑格（1格或3格），故盖住棋盘的板块必有偶数 个，从而，mn的棋盘必能被8整除。,例6 拟将一批尺寸为124的的商品装入尺寸为666的正方体包装箱中，问是否存在一种装法，使装入的该商品正好充满包装箱。,解 将正方体剖分成27个222的小正方体，并 按下图所示黑白相间地染色。,再将每一222的小正方体剖分成111的小正方体。易见，27个222的正方体中，有14个是黑的，13个是白的（或13黑14白），故经两次剖分

6、，共计有112个111的黑色小正方体和104个111的白色小正方体。虽然包装箱的体积恰好是商品体积的27倍，但容易看到，不论将商品放置在何处，它都将占据4个黑色和4个白色的111小正方体的位置，故商品不可能充满包装箱。,德国著名的艺术家Albrecht Drer(1471-1521)于1514年曾铸造了一枚名为“Melencotia I”的铜币。令人奇怪的是在这枚铜币的画面上充满了数学符号、数字及几何图形。这里，我们仅研究铜币右上角的数字问题,所谓的魔方是指由1n2这n2个正整数按一定规则排列成的一个n行n列的正方形。n称为此魔方的阶。,Drer魔方：4阶，每一行之和为34，每一列之和为34，

7、对角线（或反对角线）之和是34，每个小方块中的数字之和是34，四个角上的数字加起来也是34,什么是Drer魔方,多么奇妙的魔方！,铜币铸造时间：1514年,构造魔方是一个古老的数学游戏，起初它还和神灵联系在一起，带有深厚的迷信色彩。传说三千二百多年前（公元前2200年），因治水出名皇帝大禹就构造了三阶魔方（被人们称“洛书”），至今还有人把它当作符咒用于某些迷信活动，大约在十五世纪时，魔方传到了西方，著名的科尼利厄斯阿格里帕（1486-1535）先后构造出了39阶的魔方。,如何构造魔方,奇数（不妨n=5）阶的情况,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17

8、,18,19,20,21,22,23,24,25,魔方数量随阶数n增长的速度实在是太惊人了！,同阶魔方的个数,允许构成魔方的数取任意实数,允许取实数,n阶魔方A、B，任意实数、,A+B是n阶魔方,具有指定性质的魔方全体构成一个线性空间,问题已发生了实质性变化,注：刻画一个线性空间只需指出它的维数并求出此线性空间的一组基底,松驰问题的讨论,1在第一行中共有4种取法，为保持上述性质的成立，第二行中的1还有两种取法。当第二行的1也取定后，第三行与第四行的1就完全定位了，故一共可作出8个不同的最简方阵，称之为基本魔方并记之为Q1，Q8,仍以4阶方阵为例。令R为行和，C为列和，D为对角线和，S为小方块和

9、定义0-方：R=C=D=S=0 定义1-方：R=C=D=S=4,R=C=D=S=1的方阵构成的线性空间具有什么样的性质？,类似于构造n维欧氏空间的标准基，利用0和1我们来构造一些R=C=D=S=1的最简单的方阵。,显然，Drer空间（简称D空间）中任何一个元素都可以用Q1，Q2，Q8来线性表示，但它们能否构成D空间的一组基呢？,等号两边对应元素相比较，得r1=r2=r7=0，所以 是线性无关,是D空间的最小生成集。,令D 即解方程组：,=,解得 D=,研究Albrecht Drer铸造的铜币,D空间的子空间和D空间的扩展,（1）要求数字方的所有数都相等 这是集合G=rE,rR，G是以G=E为基

10、的一维向量空间,进一步讨论,（4）仅要求行和与列和相等 得到10维向量空间 基向量B=Q1，Q2，Q7，N1，N2，N3 其中Q1，Q2，Q7是D的基，而,（5）对数字没任何要求 所有44数字方组成16维向量空间M 基向量MB的元素应是标准基（即仅有一个 元素为1，其余元素均为0的阵）。,Botsch（1976年）证明了对于1与16之间的每一个数K，都存在K维的44方的向量空间,由上可知，有下式成立：（向量空间）（维数）0 1 5 7 8 10 16,什么是拼方问题,在H.E.Dudeney所写的Cantebury难题一书中有一个正方形的图案，这个正方形图案是由一个小长方形和若干个边长各异的小

11、正方形组成的。小长方形的长为，宽为，要求求出所有正方形的边长和拼接方法。这种拼接过程称为拼方，而这种类型的问题称为拼方问题。,受上一问题的启示，加拿大数学家W.T.Tutte,A.Stone等人考虑了如下问题：,怎样的长方形可以剖分成若干个边长各异的小正方形？正方形能否剖分成边长各异的小正方形？,称具有上述性质的长方形为完美长方形，正方形为完美正方形。,Z.Moron的完美长方形很接近完美正方形,Tutte等人用来分析Moron给出例子的 奇特方法：,用点表示水平边，用边表示小正方形。边长即小正方形之边长，方向规定由上到下。于是一个剖分好的完美长方形被十分巧妙地转化成了一个有向图网络，见下图,

12、除表示上、下两底边的顶点以外，其余顶点处指入边边长之和应等于指出边边长之和,由上面说明：假如我们把得到的有向图网络看作电网络，则所述性质恰好就是电学中的基尔霍夫定律。,若将每边看成一个单位电阻，在给出正极A与负极F之间的电势差后（相当于给出长方形的高），即可求出每条边上的电流强度（等于两顶点间的电势差），而这些数恰好就是小正方形的边长。,此外还可看出，解应当是唯一的，因为在给定A、F间的电势差后，各边上的电流强度是唯一确定的。,分析Moron给出的完美长方形，取高为32，则相应电网络中的电流强度xi(i=1,9)应满足：其解为：（x1,x2,x3,x4,x5,x6,x7,x8,x9)=(18,

13、15,4,7,8,1,14,10,9)，恰为相应小正方形的边长。此外，由x1+x2=33可知，长方形的宽应为33。,可以不管长方形的剖分，直接根据图的各种情况利用计算机来搜查,前面分析是在对完美长方形作了剖分的前提下作出的，不知道剖分情况怎么办？,有向图只有三条边的图见图1。由x1=x3可知不存在3阶完美长方形。,由四条边组成的有向图可以有两种形式，见图2中的（a）、(b)，它们均不可能对应完美长方形。,逐阶寻查下去可发现，完美长方形对应的电网络必有以下性质,根据这两条性质，可以发现完美长方形的最小阶数为9，进而可作出各种9阶、10阶、11阶完美长方形。,当然，随着阶数增大，计算量将按指数增长

14、，因为相应电网络的数目是按指数增长的。,Tutte等人将他们用人工方法得到的完美长方形列成了一个表，其中包括有二百多个完美长方形。1960年，人们用电子计算机求得了9至15阶的全部完美长方形，可其中没有一个是完美正方形！,是否存在完美正方形？,当求得的完美长方形的长恰好等于宽的十分巧合的情况下，我们才能得到一个正方形的剖分。由于计算量过大，在计算机上寻查并未获得成功，最早作出的正方形的剖分是基于非常复杂的图形并用对称性人工凑出来的，它具有69阶。后来又作出了39阶和38阶的完美正方形。接着Tutte等人利用他们获得的完美长方形表又拼凑出一个26阶的完美正方形，它是由一个边长为231的正方形和两

15、个完美长方形拼合而成的，如图所示。,在此之前，人们对图论还没有多少研究。Tutte等人在引入网络图方法后，十分自然地将兴趣转向了对图论的研究，并因此而获得了许多具有重大意义的开创性结果，直接促进了图论的发展。,对一个完美长方形也可用垂直线代替水平线，用类似方法作出另一个有向图。所以对一个确定的完美长方形，我们可以获得的两个不同的有向图。,添加,添加,前面我们已经看到，由几个完美长方形可以拼出一个新的完美长方形。相应地，新网络图与原有的完美长方形的网络之间存在着十分密切的联系。应当看到这种拼合而成的完美长方形是比较特殊的，它们与那些非拼合而成的（基本）完美长方形有着重大的区别，这些区别必然会在图

16、论中反映出来。例如，考察由两个完美长方形拼接成的完美长方形，可以导出下述定义：,8.2 合作对策模型,在上一章我们已经看到，从事某一活动的各方如能通力合作，常常可以获得更大的总收益（或受到更小的总损失）。本节主要讨论在这种合作中应当如何分配收益（或分摊损失），这一问题如果处理不当，合作显然是无法实现的。先让我们来分析一个具体实例,分析 本问题中三城镇处理污水可以有五种方案：(1)每城镇各建一个处理厂（单干）。(2)城1,城2合建一个,城3单独建一个(1、2城合作建于城2处)。(3)城2,城3合建一个,城1单独建一个(2、3城合作建于城3处)。(4)城3,城1合建一个,城2单独建一个(1、3城合

17、作建于城3处)。(5)三城合建一个污水处理厂（建于城3处）,容易计算：,以三城合作总投资为最少,费用怎么分摊呢？,建厂费用按三城污水量之比5：3：5分摊，管道是为城1、城2建的，应由两城协商分摊。,同意城3意见，由城2城3的管道费用可按污水量之比5：3：5分摊，但城1城2的管道费用应由城1承担。,分摊方案有道理，但得作一番“可行性论证”，,城1的“可行性论证”：,联合建厂费：（万元）城1负担：（万元）城1城2管道费：（万元）全部由城1负担城2城3管道费：（万元）城1负担：（万元）城1的总负担：约为2457万元,城1自己建厂费用：2300万元,合作后城1费用增加！,差点做了冤大头！,怎样找出一个

18、合理的分摊原则，以保证合作的实现呢？,N人合作对策模型,设有一个n人的集合I=1,2,n，其元素是某一合作的可能参加者。,(1)对于每一子集S I，对应地可以确定一个实数V(S)，此数的实际意义为如果S中的人参加此项合作，则此合作的总获利数为V(S)，十分明显，V(S)是定义于I的一切子集上的一个集合函数。根据本问题的实际背景，还应要求V(S)满足以下性质:,(2)定义合作结果V（S）的分配为，其中 表示第i人在这种合作下分配到的获利。显然，不同的合作应有不同的分配，问题归结为找出一个合理的分配原则 来，被称为合作对策,1953年Shapley采用逻辑建模方法研究了这一问题。首先，他归纳出了几

19、条合理分配原则 应当满足的基本性质（用公理形式表示），进而证明满足这些基本性质的合作对策 是唯一存在的，从而妥善地解决了问题。,是否存在合理分配原则,Shapley提出了以下公理：设V是I上的特征函数，是合作对策，则有,公理1,合作获利对每人的分配与此人的标号无关。,公理2,，即每人分配数的总和等于总获利数。,公理3,若对所有包含的i的子集S有：V(S-i)=V(S)，=0。,即若第i人在他参加的任一合作中均不作出任何贡献，则他不应从合作中获利,公理4,若此n个人同时进行两项互不影响的合作，则两项合作的分配也应互不影响，每人的分配额即两项合作单独进行时应分配数的和。,利用上述公理可以证明满足公

20、理14的 是唯一存在的(证明略),存在 的公式吗,Shapley指出，可按下列公式给出：,(8.1)i=1,n,可视为i在合作S中所作的贡献,W(|S|)可看作这种贡献的权因子,合作的获利真的不少于他单干时的获利吗,对每一iI，有,求证:,证明:,|S|=K时，包含i的子集S共有 个,即 个,故=1/n,从而,又根据性质，有,故有,城1究竟应当承担多少费用,首先不难看出：S1=1,1,2,1,3,1,2,3 计算出与(11.1)式有关的数据并列成表,城2和城3应该承担的费用可类似算出,我们应该承担的是2103万元！,8.3 公平选举是可能的吗?,什么是选举,所谓选举，其实质就是在评选人对候选人

21、先后（优劣）次序排队的基础上，根据某一事先规定的选举规则决定出候选人的一个先后次序，即得出选举结果。现用I=1,2,n表示评选人集合，用有限集A=x,y,表示候选人集合，用,=,y)i表示评选人i认为x优于y，用(xy)表示选举结果为x优于y并用pi表示评选人i的排序，p表示选举结果。,A的排序应满足以下性质：,简单多数规则,几种选举规则,它规定当且仅当(xy)i的评选人超过半数时选举结果才为(xy)。,有时要超过2/3多数等,根据选举规划，结果应为 P:xyuv,根据规则，自然应有(xy),(yz)和(zx),违反传递性（2）,简单多数规则的主要优点是简单易行，使用方便。但可惜的是这一规则有

22、时会违反传递性,Borda数规则,记Bi(x)为p1中劣于x的候选人数目，记，称B(x)为x的Borda数，Borda数规则规定按Borda数大小排列候选人的优劣次序，即当B(x)B(y)时有(xy)，两关系式中的等号必须同时成立。,对于例11.9，计算出B(x)=B(y)=B(z)=3 故选举结果为 x=y=z,用Borda数规则得出的结果更合乎常理,例10 I=1,2,3,4,A=x,y,z,u,v，选票情况为 p1p2p3:xyzuv P4:yzuvx,计算得 B(x)=12，B(y)=13 故选举结果为 yx,但有三人认为x优于y,用Borda数规则得出的结果未必合理,能找到一种在任何

23、情况下都“公平”的选举规则吗,什么是“公平”的选举规则,“公平”的选举规则应当满足以下公理,公理1,投票人对候选人排出的所有可能排列都是可以实现的。,公理2,如果对所有的i，有(xy)i，则必须有(xy)。,公理3,如果在两次选举中，对任意i，由 必可得出，则由 必可得出。,公理4,如果两次选举中，每个投票人对x、y的排序都未改变，则对x、y的排序两次结果也应相同。,公理5,不存在这样的投票人i，使得对任意一对候选人x、y，只要有(xy)i,，就必有(xy)。,有满足上述公理的选举规则吗,Arrow不可能性定理使上述想法终结,定理8.1,如果至少有三名候选人，则满足公理1公理5的选举规划 事实

24、上是不可能存在的。,证：,将证明由公理1公理4必可导出存在一个独裁者，从而违反了公理5,首先引入决定性集合的概念。称I的子集Vxy为候选人x、y的决定性集合，如果由所有Vxy中的I 有(xy)i必可导出(xy)。显然决定性集合是必定存在，由公理2或实际一次选举得到。找出所有决定性集合中含元素最少的一个，不妨仍记为Vxy。,证明 Vxy只能含有一个元素某评选人i。反证 假定Vxy至少含有两个元素，则Vxy必可分解为两个非空集合的和 即 与 非空且不相交，且均不可能是任一对候选人的决定性集合 假设,根据公理1，以下选举是允许的：当 时，（xyz）i 当 时，（zxy）i 当 时，（yzx）i 其中

25、z是任一另外的候选人,考察选举结果(xz)是不可能，否则 是x、z的决定性集合，故必有(zx)。又Vxy是x、y的决定性能合，故必有(xy)。由传递性(zx)。得 是y、z的决定性集合，从而导出矛盾。以上证明说明Vxy不能分解，即Vxy=i，i为某一投票人。,考虑另一次选举：(xyz)i，而（yzx）jI 显然，由于全体一致意见，（yz）必成立。又i是x、y的决定性集合，故应有（xy）。于是，由传递性，必有（xz）。再由公理4，y的插入不应影响x、z的排序，故i也是x、z的决定性集合。类似还可证明，如果是异议于x、z的任一候选人，i也是w、z的决定性集合，这就是说，评选人i是选举的独裁者。,A

26、rrow的公理系统隐含矛盾,例11 设I=1,2,A=x,y,z，考察如下的四次选举：（第一次）xyz（第三次）yzx xyz zyx 结果应有 xy 合理结果 y=z（第二次）xzy（第四次）xyz zxy zxy 合理结果 x=z 结果？,由公理1，第四次的选举应当是有效的 由公理2，必须有（xy）(4)再与第二次选举比较并根据公理3，则应有（x=z）(4)与第三次比较并根据公理3，应有（y=z）(4),xy，x=z与y=z 居然同时成立！,8.4 信息的度量与应用,怎么度量信息,首先分析一下问题的认识过程,1.对一问题毫无了解，对它的认识是不确定的,2.通过各种途径获得信息，逐渐消除不确

27、定性,3.对这一问题非常的了解，不确定性很小,对于系统，可以利用守恒关系有 A+I=B，得I=B-A。,可否用消除不确定性的多少来度量信息！,几个例子：,例12 当你要到大会堂去找某一个人时，甲告诉你两条消息：（1）此人不坐在前十排，（2）他也不坐在后十排；乙只告诉你一条消息：此人坐在第十五排。问谁提供的信息量大？,乙虽然只提供了一条消息，但这一条消息对此人在什么位置上这一不确定性消除得更多，所以后者包含的信息量应比前者提供的两条消息所包含的总信息量更大,例13 假如在盛夏季节气象台突然预报“明天无雪”的消息。在明天是否下雪的问题上，根本不存在不确定性，所以这条消息包含的信息量为零。,是否存在

28、信息量的度量公式,基于前面的观点，美国贝尔实验室的学者香农（Shannon）应用概率论知识和逻辑方法推导出了信息量的计算公式,Shannon提出的四条基本性质（不妨称它们为公理）,公理1,信息量是该事件发生概率的连续函数,公理2,如果事件A发生必有事件B发生，则得知事件A发生的信息量大于或等于得知事件B发生的信息量。,公理3,如果事件A和事件B的发生是相互独立的，则获知A、B事件将同时发生的信息量应为单独获知两事件发生的信息量之和。,公理4,任何信息的信息量均是有限的。,将某事件发生的信息记为M，该事件发生的概率记为p，记M的信息量为I（M）。,上述公理怎样推出信息量的计算公式呢,定理8.2,

29、满足公理1公理4的信息量计算公式为I(M)=Clogap，其中C是任意正常数，对数之底a可取任意为不为1的正实数。,证明:,由公理1 I(M)=f(p)，函数f连续。,由公理2 若A发生必有B发生，则pApB，有f(pA)f(PB)，故函数f是单调不增的。,由公理3 若A、B是两个独立事件，则A、B同时发生 的概率为pApB，有f(PAPB)=f(pA)+f(pB)。,先作变量替换 令p=a-q，即q=logaP 记,，又 有：，g亦为连续函数。,g(x+y)=g(x)+g(y)的连续函数有怎样的性质,首先，由g(0)=g(0+0)=2g(0)得出g(0)=0或g(0)=。但由公理4，后式不能

30、成立，故必有g(0)=0。,记g(1)=C，容易求得g(2)=2C,g(3)=3C,一般地，有g(n)=nC。进而，可得。于是对一切正有理数 m/n，g(m/n)=(m/n)C。,由连续性可知：对一切非负实数x，有g(x)=Cx,当x取负实数时，由g(x)+g(x)=g(0)=0，可得出g(x)=g(x)=cx也成立，从而对一切实数x，g(x)=Cx,故g(q)=Cq。,若取a=2,C=1，此时信息量单位称为比特若取a=10,C=1，此时信息量单位称为迪吉特若取a=e,C=1，此时信息量单位称为奈特,例14 设剧院有1280个座位，分为32排，每排40座。现欲从中找出某人，求以下信息的信息量。

31、（i）某人在第十排；（ii）某人在第15座；（iii）某人在第十排第15座。,解：在未知任何信息的情况下，此人在各排的概率可以认为是相等的，他坐在各座号上的概率也可以认为是相等的，故,（i）“某人在第十排”包含的信息量为（比特）,（ii）“某人在第15座”包含的信息量为（比特）,（iii）“某人在第十排第15座”包含的信息量为（比特）,5bit+5.32bit=10.32bit,这一例子反映了对完全独立的几条信息，其总信息量等于各条信息的信息量之和。,对于相应不独立的信息，要计算在已获得某信息后其余信息的信息量时，需要用到条件概率公式，可以参阅信息论书籍。,平均信息量（熵）问题,设某一实验可能

32、有N种结果，它们出现的概率分别为p1,pN,则事先告诉你将出现第i种结果的信息，其信息量为log2pi，而该实验的不确定性则可用这组信息的平均信息量（或熵）来表示,例15 投掷一枚骼子的结果有六种，即出现16点、出现每 种情况的概率均为1/6，故熵 H=log262.585（比特）。投掷一枚硬币的结果为正、反面两种，出现的概率均为1/2，故熵 H=log22=1（比特）。向石块上猛摔一只鸡蛋，其结果必然是将鸡蛋摔破，出现的概率为1，故熵H=log21=0,从例子可以看出，熵实质上反映的是问题的“模糊度”，熵为零时问题是完全清楚的，熵越大则问题的模糊程度也越大,离散型概率分布的随机试验，熵的定义

33、为：（11.5）,连续型概率分布的随机试验，熵的定义为:（11.6）,熵具有哪些有趣的性质,定理11.3,若实验仅有有限结果S1,Sn，其发生的概率分别为 P1,Pn，则当 时，此实验具有最大熵。,此定理既可化为条件极值问题证明之，也可以利用凸函数性质来证明，请大家自己去完成,定理8.4,若实验是连续型随机试验，其概率分布P(x)在a,b区间以外均为零，则当 P(x)平均分布时具有最大熵。,定理8.5,对于一般连续型随机试验，在方差一定的前提下，正态分布具有最大的熵。,定理8.6,最大熵原理，即受到相互独立且均匀而小的随机因素影响的系统，其状态的概率分布将使系统的熵最大。,上述结果并非某种巧合

34、。根据概率论里的中心极限定理，若试验结果受到大量相互独立的随机因素的影响，且每一因素的影响均不突出时，试验结果服从正态分布。最大熵原理则说明，自然现象总是不均匀逐步趋于均匀的，在不加任何限止的情况下，系统将处于熵最大的均匀状态。,例16 有12个外表相同的硬币，已知其中有一个是假的，可能轻些也可能重些。现要求用没有砝码的天平在最少次数中找出假币，问应当怎样称法。,解 假币可轻可重，每枚硬币都可能是假币。故此问题共有 24种情况，每种情况的概率为1/24。所以此问题的熵为log224。,确定最少次数的下界,实验最多可能出现三种结果，根据定理11.3，这种实验在可能出现的各种事件具有相等的概率时，

35、所提供的平均信息量最大，故实验提供的平均信息量不超过log23。,设最少需称k次，则这k次实验提供的总信息量 不超过klog23=log23k，又问题的模糊度（熵）为log224 必要条件:log23klog224，得 k3。,称三次足够了吗？,实验方法：使每次实验提供尽可能大的平均信息量。,第一次：将12枚硬币平分成三堆，取两堆称，出现两中情况,三次是最少次数！,英文的熵是多少呢？,例17 在人类活动中，大量信息是通过文字或语言来表达的，而文学或语言则是一串符号的组合。据此，我们可以计算出每一语种里每一符号的平均信息量。例如，表8-2、表8-3、表8-4分别是英语、德语和俄语中每一符号（字母

36、与空格，标点符号不计）在文章中出现的概率的统计结果（汉语因符号繁多，难以统计）,英文的多余度,信息通道的容量问题,问题背景：,信息的传递是需要时间的。用n个符号S1、Sn来表达信息，各符号传递所需时间是各不相同的，设分别为t1、tn，并设各符号出现的概率分别为p1、pn。这样，就出现了两方面的问题。,一、pi是确定的，如何缩短传递确定信息所需的时间。,二、ti是确定的，如何使单位时间传递的平均信息量最大。,单位时间内信息通道能够传递的最大平均信息量称为此信息通道的容量,如何求信息通道的容量？,每一符号的平均信息量为：,每一符号所需的平均时间为：,故单位时间内传递的平均信息量应为：,问题化为：,

37、（8.7）,利用拉格朗日乘子法，（11.7）式可化为无约束极值问题：,（8.8）,记（11.8）式的目标函数为f(p,)，即求解方程组：,（8.9）,方程组（8.9）的解为：,由于 是与pi有关的量，方程组的解仍无法算出为此，记,例18 为简单起见，设符号只有四种：S1、S2、S3和S4，在利用这些符号传递信息时，这些符号分别需要1、2、3、4单位传递时间，试求出此信息通道的容量及相应的最佳pi值。,而,某地区物价指数图,8.5 物价指数问题,怎样定义和计算物价指数,单种商品的情况,设基准年价格为P0，目前价格为P可如下定义物价指数：,社会中的商品不可能只有一种。多种商品的问题更为复杂,多种商

38、品的情况,假设有两种商品，基准年价格分别为、，目前价格分别 为P1，P2。可采用多种平均方法来定义：,算术平均值之比：,比值的算术平均值：,比值的调和平均值：,比值的几何平均值：,假如存在着n种商品，可以相应地写出类似的公式。,上述方法没有区别不同商品的重要性,事实上各种商品在人们生活中所占地位不尽相同，例如，钢琴降价20%和粮食涨价20%无法对消。,模型的进一步改进,物价指数I(P0,q0,P,q)为 的连续函数。,物价指数函数,前面的公式能否取作物价指数函数,对衡量物价指数方法的一些具体要求：,（1）单调性（2）权系数的不变性（3）齐次性（4）平均性（5）货币单位的独立性（6）商品单位的独

39、立性（7）基准年的独立性（8）物价指数不因某种商品的淘汰而失去意义,(1)若，则,(2)=1,(3),(4),(5),(7),(8),公理（7）的一些说明 若以1972年为基准年（物价指数取为1），则1989年美国物价指数为1.660，而1980年为1.843，若以1973年为基准年，则1979年和1980年美国物价指数分别为1.093和1.209。根据公理（7）的要求，应当有,事实上，此式只近似成立。,请大家自行验证前面给出的公式I1I4是否都能同时满足公理系统的(1)(8)要求,一些常用的物价指数函数是否满足公理系统的要求,此公式是由laspeyres于1871年提出，在将近一个世纪的时间

40、里,被广泛用于计算物价指数,可以用构造法证明上式公理（7)不成立,即不一定成立。,此式是Paasche在1874年提出的，与不同的是计算时采用了现在的权系数。,容易直接看出公理（2）不成立。,其中ai0，且,此式是平均方式（4）的一种自然推广。ai的取法和q0、q有关，实质上是权系数的一种变形。,该式也不能同时满足公理（1）（8）。令某，则I0，而若令某，则又有,所有较自然地导出的平衡公式均不能满足公理系统，是否该公理系统有矛盾？,先证明以下两个引理：,引理11.1 记，D1、D2为任意两个对角元素为正 的对角矩阵，则有：,证明：,引理8.2 记，则有：,证明定理11.7：,先引入下列矩阵,记,对角线上第j个元素为，其余元素为1的对角阵,则有：,令，则有根据P的定义，至少存在一个j，使得,与公理（8）矛盾,上述公理系统隐含矛盾,上述公理间相对独立吗？,证明：取P=P0，由公理（4）可知：,（）,因此：若取=1，即得出（2）成立。,一个严谨的公理系统应当满足公理间的无矛盾性和相对独立性,