数学建模逻辑模型

第八章

逻辑模型

欧几里得是古希腊著名数学家、欧氏几何学的开创者。欧几里得生于雅典，当时雅典就是古希腊文明中心。浓郁的文化气氛深深地感染了欧几里得，当他还是个十几岁的少年时，就迫不及待地想进入“柏拉图学园”学习。§8

逻辑模型

欧几里得在不加证明而被直接采用的一些基本概念和公理的基础上。运用逻辑推理方法得出了一系列的定理、推论，从而建立了完整的欧几里得几何学，这一辉煌成果至今仍然是人类的宝贵财富。本章介绍的一些模型采用的也是类似的方法。建模者从问题应当具有的某些基本属性出发，运用逻辑推理方法或者导出满足这些基本属性的解来，或者证明在原有观念下问题不可能有解，从而从根本上改变人们对这一问题的看法。所谓的魔方是指由1~n2这n2个正整数按一定规则排列成的一个n行n列的正方形。n称为此魔方的阶。Dürer魔方：4阶，每一行之和为34，每一列之和为34，对角线（或反对角线）之和是34，每个小方块中的数字之和是34，四个角上的数字加起来也是34

8.1什么是Dürer魔方多么奇妙的魔方！铜币铸造时间：1514年

构造魔方是一个古老的数学游戏，起初它还和神灵联系在一起，带有深厚的迷信色彩。传说三千二百多年前（公元前2200年），因治水出名皇帝大禹就构造了三阶魔方（被人们称“洛书”），至今还有人把它当作符咒用于某些迷信活动，大约在十五世纪时，魔方传到了西方，著名的科尼利厄斯·阿格里帕（1486-1535）先后构造出了3~9阶的魔方。如何构造魔方奇数（不妨n=3）阶的情况Step1:在第一行中间写1Step2:每次向右上方移一格依次填按由小到大排列的下一个数，向上移出界时填下一列最后一行的小方格；向右移出界时填第一列上一行的小方格。若下面想填的格已填过数或已达到魔方的右上角时，改填刚才填的格子正下方的小方格，继续Step2直到填完偶数阶的情况

偶数阶的魔方可以利用奇数阶魔方拼接而成，拉尔夫·斯特雷奇给出了一种拼接的方法，这里不作详细介绍。645972831如何构造魔方奇数（不妨n=5）阶的情况Step1:在第一行中间写1Step2:每次向右上方移一格依次填按由小到大排列的下一个数，向上移出界时填下一列最后一行的小方格；向右移出界时填第一列上一行的小方格。若下面想填的格已填过数或已达到魔方的右上角时，改填刚才填的格子正下方的小方格，继续Step2直到填完12345678910111213141516171819202122232425

§

8.2公平选举是可能的吗?

什么是选举

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

A的排序应满足以下性质：(1)择一性

关系式(x>y)、(x=y)、(x<y)有且仅有一个成立(2)传递性

若x≥y,y≥z,则必有x≥z

简单多数规则

几种选举规则它规定当且仅当(x>y)i的评选人超过半数时选举结果才为(x>y)。

有时要超过2/3多数等

例

设I={1,2,3},A={x,y,u,v}，三位评选人的选票为

p1:x>y>u=vp2:y>x>u>vp3:x=u>v>y

根据选举规划，结果应为

P:x>y>u>v

例

设I={1,2,3},A={x,y,z}p1:x>y>zp2:y>z>xp3:z>x>y根据规则，自然应有

(x>y),(y>z)和(z>x)违反传递性（2）简单多数规则的主要优点是简单易行，使用方便。但可惜的是这一规则有时会违反传递性

Borda数规则

记Bi(x)为p1中劣于x的候选人数目，记，称B(x)为x的Borda数，Borda数规则规定按Borda数大小排列候选人的优劣次序，即当B(x)≥B(y)时有(x≥y)，两关系式中的等号必须同时成立。计算出B(x)=B(y)=B(z)=3

故选举结果为x=y=z用Borda数规则得出的结果更合乎常理

I={1,2,3},A={x,y,z}p1:x>y>zp2:y>z>xp3:z>x>y根据规则，自然应有

(x>y),(y>z)和(z>x)

Borda数规则

记Bi(x)为p1中劣于x的候选人数目，记，称B(x)为x的Borda数，Borda数规则规定按Borda数大小排列候选人的优劣次序，即当B(x)≥B(y)时有(x≥y)，两关系式中的等号必须同时成立。用Borda数规则得出的结果更合乎常理

例

I={1,2,3,4},A={x,y,z,u,v}，选票情况为p1p2p3:x>y>z>u>vP4:y>z>u>v>x

计算得B(x)=12，B(y)=13

故选举结果为

y>x但有三人认为x优于y

用Borda数规则得出的结果未必合理

能找到一种在任何情况下都“公平”的选举规则吗

什么是“公平”的选举规则“公平”的选举规则应当满足以下公理公理1投票人对候选人排出的所有可能排列都是可以实现的。公理2

如果对所有的i，有(x≥y)i，则必须有(x≥y)。公理3如果在两次选举中，对任意i，由必可得出，则由必可得出

。公理4如果两次选举中，每个投票人对x、y的排序都未改变，则对x、y的排序两次结果也应相同。公理5不存在这样的投票人i，使得对任意一对候选人x、y，只要有(x≥y)i,，就必有(x≥y)。有满足上述公理的选举规则吗Arrow不可能性定理使上述想法终结定理8.1

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

将证明由公理1~公理4必可导出存在一个独裁者，从而违反了公理5

首先引入决定性集合的概念。

进一步说明：对于任意另外的候选人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的决定性集合。评选人i是选举的独裁者。Arrow的公理系统隐含矛盾

例

设I={1,2},A={x,y,z}，考察如下的四次选举：

（第一次）

x＞y＞z（第三次）

y＞z＞x

x＞y＞zz＞y＞x

结果应有

x＞y合理结果

y=z

（第二次）

x＞z＞y（第四次）

x＞y＞z

z＞x＞yz＞x＞y

合理结果

x=z结果？？？由公理1，第四次的选举应当是有效的由公理2，必须有（x＞y）(4)

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

与第三次比较并根据公理3，应有（y=z）(4)

x＞y，x=z与y=z居然同时成立！改进方案解决这一问题的另一途径是事先适当限制评选人的排序方式，使得可能出现的情况数减少，以便保证一个合理的选举规则的存在。

§

8.3信息的度量与应用

怎么度量信息首先分析一下问题的认识过程1.对一问题毫无了解，对它的认识是不确定的2.通过各种途径获得信息，逐渐消除不确定性

3.对这一问题非常的了解，不确定性很小黑箱不确定度A灰箱不确定度B白箱不确定度C信息I信息II对于系统，可以利用守恒关系有A+I=B，得I=B-A。可否用消除不确定性的多少来度量信息！几个例子：例

当你要到大会堂去找某一个人时，甲告诉你两条消息：（1）此人不坐在前十排，（2）他也不坐在后十排；乙只告诉你一条消息：此人坐在第十五排。问谁提供的信息量大？

乙虽然只提供了一条消息，但这一条消息对此人在什么位置上这一不确定性消除得更多，所以后者包含的信息量应比前者提供的两条消息所包含的总信息量更大例

假如在盛夏季节气象台突然预报“明天无雪”的消息。在明天是否下雪的问题上，根本不存在不确定性，所以这条消息包含的信息量为零。是否存在信息量的度量公式基于前面的观点，美国贝尔实验室的学者香农（Shannon）应用概率论知识和逻辑方法推导出了信息量的计算公式Inhiswords"Ijustwonderedhowthingswereputtogether."ClaudeElwoodShannon(April30,1916-February24,2001)hasbeencalled"thefatherofinformationtheory".Shannon提出的四条基本性质（不妨称它们为公理）公理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的正实数。各种信息量单位若取a=2,C=1，此时信息量单位称为比特若取a=10,C=1，此时信息量单位称为迪吉特若取a=e,C=1，此时信息量单位称为奈特例

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

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

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

（比特）

（ii）“某人在第15座”包含的信息量为

（比特）

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

（比特）5bit+5.32bit=10.32bit这一例子反映了对完全独立的几条信息，其总信息量等于各条信息的信息量之和。对于相应不独立的信息，要计算在已获得某信息后其余信息的信息量时，需要用到条件概率公式，可以参阅信息论书籍。I(M)=－Clogap，a=2,C=1，

至此，我们已经引入了信息度量的定量公式。如前所述，它是信息对消除问题的不确定性的度量。这种讲法似乎有点难以为人们所接受，其实，这只是人们的习惯在起作用。这里，我们不妨来作一比较。在人们搞清热的奥秘以前，温度也是一个较为抽象的概念，因它实质上是物体分子运动平均速度的一种

反映。人们天生就知道冷和热，但如何来度量它却曾经是一个难题。只有在解决了这一问题以后，以定量分析为主的热力学才能得到飞速的发展。信息问题也是这样，人们对各种信息包含的实质“内容”究竟有多少往往也有一个直观的感觉，但用什么方法来度量它，却比“今天15度”这样的讲法更不易理解，因为它是通过较为抽象的概率来计算的。平均信息量（熵）问题

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

来表示例

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

投掷一枚硬币的结果为正、反面两种，出现的概率均为1/2，故熵H=log22=1（比特）。向石块上猛摔一只鸡蛋，其结果必然是将鸡蛋摔破，出现的概率为1，故熵H=log21=0从例子可以看出，熵实质上反映的是问题的“模糊度”，熵为零时问题是完全清楚的，熵越大则问题的模糊程度也越大离散型概率分布的随机试验，熵的定义为：

连续型概率分布的随机试验，熵的定义为:

熵具有哪些有趣的性质定理8.3

若实验仅有有限结果S1,…,Sn，其发生的概率分别为P1,…,Pn，则当时，此实验具有最大熵。此定理既可化为条件极值问题证明之，也可以利用凸函数性质来证明，请大家自己去完成定理8.4

若实验是连续型随机试验，其概率分布P(x)在[a,b]区间以外均为零，则当P(x)平均分布时具有最大熵。定理8.5

对于一般连续型随机试验，在方差一定的前提下，正态分布具有最大的熵。

定理8.6

最大熵原理，即受到相互独立且均匀而小的随机因素影响的系统，其状态的概率分布将使系统的熵最大。上述结果并非某种巧合。根据概率论里的中心极限定理，若试验结果受到大量相互独立的随机因素的影响，且每一因素的影响均不突出时，试验结果服从正态分布。最大熵原理则说明，自然现象总是不均匀逐步趋于均匀的，在不加任何限止的情况下，系统将处于熵最大的均匀状态。例

有12个外表相同的硬币，已知其中有一个是假的，可能轻些也可能重些。现要求用没有砝码的天平在最少