數(shù)學建模邏輯模型

第八章

邏輯模型

歐幾里得是古希臘著名數(shù)學家、歐氏幾何學的開創(chuàng)者。歐幾里得生于雅典，當時雅典就是古希臘文明中心。濃郁的文化氣氛深深地感染了歐幾里得，當他還是個十幾歲的少年時，就迫不及待地想進入“柏拉圖學園”學習?！?

邏輯模型

歐幾里得在不加證明而被直接采用的一些基本概念和公理的基礎上。運用邏輯推理方法得出了一系列的定理、推論，從而建立了完整的歐幾里得幾何學，這一輝煌成果至今仍然是人類的寶貴財富。本章介紹的一些模型采用的也是類似的方法。建模者從問題應當具有的某些基本屬性出發(fā)，運用邏輯推理方法或者導出滿足這些基本屬性的解來，或者證明在原有觀念下問題不可能有解，從而從根本上改變人們對這一問題的看法。所謂的魔方是指由1~n2這n2個正整數(shù)按一定規(guī)則排列成的一個n行n列的正方形。n稱為此魔方的階。Dürer魔方：4階，每一行之和為34，每一列之和為34，對角線（或反對角線）之和是34，每個小方塊中的數(shù)字之和是34，四個角上的數(shù)字加起來也是34

8.1什么是Dürer魔方多么奇妙的魔方！銅幣鑄造時間：1514年

構造魔方是一個古老的數(shù)學游戲，起初它還和神靈聯(lián)系在一起，帶有深厚的迷信色彩。傳說三千二百多年前（公元前2200年），因治水出名皇帝大禹就構造了三階魔方（被人們稱“洛書”），至今還有人把它當作符咒用于某些迷信活動，大約在十五世紀時，魔方傳到了西方，著名的科尼利厄斯·阿格里帕（1486-1535）先后構造出了3~9階的魔方。如何構造魔方奇數(shù)（不妨n=3）階的情況Step1:在第一行中間寫1Step2:每次向右上方移一格依次填按由小到大排列的下一個數(shù)，向上移出界時填下一列最后一行的小方格；向右移出界時填第一列上一行的小方格。若下面想填的格已填過數(shù)或已達到魔方的右上角時，改填剛才填的格子正下方的小方格，繼續(xù)Step2直到填完偶數(shù)階的情況

偶數(shù)階的魔方可以利用奇數(shù)階魔方拼接而成，拉爾夫·斯特雷奇給出了一種拼接的方法，這里不作詳細介紹。645972831如何構造魔方奇數(shù)（不妨n=5）階的情況Step1:在第一行中間寫1Step2:每次向右上方移一格依次填按由小到大排列的下一個數(shù)，向上移出界時填下一列最后一行的小方格；向右移出界時填第一列上一行的小方格。若下面想填的格已填過數(shù)或已達到魔方的右上角時，改填剛才填的格子正下方的小方格，繼續(xù)Step2直到填完12345678910111213141516171819202122232425

§

8.2公平選舉是可能的嗎?

什么是選舉

所謂選舉，其實質就是在評選人對候選人先后（優(yōu)劣）次序排隊的基礎上，根據某一事先規(guī)定的選舉規(guī)則決定出候選人的一個先后次序，即得出選舉結果。現(xiàn)用I={1,2,…,n}表示評選人集合，用有限集A={x,y,…}表示候選人集合，用>,=,<分別表示優(yōu)于、等于、劣于，用(x>y)i表示評選人i認為x優(yōu)于y，用(x>y)表示選舉結果為x優(yōu)于y并用pi表示評選人i的排序，p表示選舉結果。

A的排序應滿足以下性質：(1)擇一性

關系式(x>y)、(x=y)、(x<y)有且僅有一個成立(2)傳遞性

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

簡單多數(shù)規(guī)則

幾種選舉規(guī)則它規(guī)定當且僅當(x>y)i的評選人超過半數(shù)時選舉結果才為(x>y)。

有時要超過2/3多數(shù)等

例

設I={1,2,3},A={x,y,u,v}，三位評選人的選票為

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

根據選舉規(guī)劃，結果應為

P:x>y>u>v

例

設I={1,2,3},A={x,y,z}p1:x>y>zp2:y>z>xp3:z>x>y根據規(guī)則，自然應有

(x>y),(y>z)和(z>x)違反傳遞性（2）簡單多數(shù)規(guī)則的主要優(yōu)點是簡單易行，使用方便。但可惜的是這一規(guī)則有時會違反傳遞性

Borda數(shù)規(guī)則

記Bi(x)為p1中劣于x的候選人數(shù)目，記，稱B(x)為x的Borda數(shù)，Borda數(shù)規(guī)則規(guī)定按Borda數(shù)大小排列候選人的優(yōu)劣次序，即當B(x)≥B(y)時有(x≥y)，兩關系式中的等號必須同時成立。計算出B(x)=B(y)=B(z)=3

故選舉結果為x=y=z用Borda數(shù)規(guī)則得出的結果更合乎常理

I={1,2,3},A={x,y,z}p1:x>y>zp2:y>z>xp3:z>x>y根據規(guī)則，自然應有

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

Borda數(shù)規(guī)則

記Bi(x)為p1中劣于x的候選人數(shù)目，記，稱B(x)為x的Borda數(shù)，Borda數(shù)規(guī)則規(guī)定按Borda數(shù)大小排列候選人的優(yōu)劣次序，即當B(x)≥B(y)時有(x≥y)，兩關系式中的等號必須同時成立。用Borda數(shù)規(guī)則得出的結果更合乎常理

例

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ōu)于y

用Borda數(shù)規(guī)則得出的結果未必合理

能找到一種在任何情況下都“公平”的選舉規(guī)則嗎

什么是“公平”的選舉規(guī)則“公平”的選舉規(guī)則應當滿足以下公理公理1投票人對候選人排出的所有可能排列都是可以實現(xiàn)的。公理2

如果對所有的i，有(x≥y)i，則必須有(x≥y)。公理3如果在兩次選舉中，對任意i，由必可得出，則由必可得出

。公理4如果兩次選舉中，每個投票人對x、y的排序都未改變，則對x、y的排序兩次結果也應相同。公理5不存在這樣的投票人i，使得對任意一對候選人x、y，只要有(x≥y)i,，就必有(x≥y)。有滿足上述公理的選舉規(guī)則嗎Arrow不可能性定理使上述想法終結定理8.1

如果至少有三名候選人，則滿足公理1~公理5的選舉規(guī)劃事實上是不可能存在的。證：

將證明由公理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的公理系統(tǒng)隱含矛盾

例

設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居然同時成立！改進方案解決這一問題的另一途徑是事先適當限制評選人的排序方式，使得可能出現(xiàn)的情況數(shù)減少，以便保證一個合理的選舉規(guī)則的存在。

§

8.3信息的度量與應用

怎么度量信息首先分析一下問題的認識過程1.對一問題毫無了解，對它的認識是不確定的2.通過各種途徑獲得信息，逐漸消除不確定性

3.對這一問題非常的了解，不確定性很小黑箱不確定度A灰箱不確定度B白箱不確定度C信息I信息II對于系統(tǒng)，可以利用守恒關系有A+I=B，得I=B-A。可否用消除不確定性的多少來度量信息！幾個例子：例

當你要到大會堂去找某一個人時，甲告訴你兩條消息：（1）此人不坐在前十排，（2）他也不坐在后十排；乙只告訴你一條消息：此人坐在第十五排。問誰提供的信息量大？

乙雖然只提供了一條消息，但這一條消息對此人在什么位置上這一不確定性消除得更多，所以后者包含的信息量應比前者提供的兩條消息所包含的總信息量更大例

假如在盛夏季節(jié)氣象臺突然預報“明天無雪”的消息。在明天是否下雪的問題上，根本不存在不確定性，所以這條消息包含的信息量為零。是否存在信息量的度量公式基于前面的觀點，美國貝爾實驗室的學者香農（Shannon）應用概率論知識和邏輯方法推導出了信息量的計算公式Inhiswords"Ijustwonderedhowthingswereputtogether."ClaudeElwoodShannon(April30,1916-February24,2001)hasbeencalled"thefatherofinformationtheory".Shannon提出的四條基本性質（不妨稱它們?yōu)楣恚┕?信息量是該事件發(fā)生概率的連續(xù)函數(shù)公理2如果事件A發(fā)生必有事件B發(fā)生，則得知事件A發(fā)生的信息量大于或等于得知事件B發(fā)生的信息量。公理3如果事件A和事件B的發(fā)生是相互獨立的，則獲知A、B事件將同時發(fā)生的信息量應為單獨獲知兩事件發(fā)生的信息量之和。公理4任何信息的信息量均是有限的。將某事件發(fā)生的信息記為M，該事件發(fā)生的概率記為p，記M的信息量為I（M）。上述公理怎樣推出信息量的計算公式呢定理8.2

滿足公理1—公理4的信息量計算公式為I(M)=－Clogap，其中C是任意正常數(shù)，對數(shù)之底a可取任意為不為1的正實數(shù)。各種信息量單位若取a=2,C=1，此時信息量單位稱為比特若取a=10,C=1，此時信息量單位稱為迪吉特若取a=e,C=1，此時信息量單位稱為奈特例

設劇院有1280個座位，分為32排，每排40座。現(xiàn)欲從中找出某人，求以下信息的信息量。（i）某人在第十排；（ii）某人在第15座；（iii）某人在第十排第15座。解：

在未知任何信息的情況下，此人在各排的概率可以認為是相等的，他坐在各座號上的概率也可以認為是相等的，故

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

（比特）

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

（比特）

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

（比特）5bit+5.32bit=10.32bit這一例子反映了對完全獨立的幾條信息，其總信息量等于各條信息的信息量之和。對于相應不獨立的信息，要計算在已獲得某信息后其余信息的信息量時，需要用到條件概率公式，可以參閱信息論書籍。I(M)=－Clogap，a=2,C=1，

至此，我們已經引入了信息度量的定量公式。如前所述，它是信息對消除問題的不確定性的度量。這種講法似乎有點難以為人們所接受，其實，這只是人們的習慣在起作用。這里，我們不妨來作一比較。在人們搞清熱的奧秘以前，溫度也是一個較為抽象的概念，因它實質上是物體分子運動平均速度的一種

反映。人們天生就知道冷和熱，但如何來度量它卻曾經是一個難題。只有在解決了這一問題以后，以定量分析為主的熱力學才能得到飛速的發(fā)展。信息問題也是這樣，人們對各種信息包含的實質“內容”究竟有多少往往也有一個直觀的感覺，但用什么方法來度量它，卻比“今天15度”這樣的講法更不易理解，因為它是通過較為抽象的概率來計算的。平均信息量（熵）問題

設某一實驗可能有N種結果，它們出現(xiàn)的概率分別為p1,…,pN,則事先告訴你將出現(xiàn)第i種結果的信息，其信息量為－log2pi，而該實驗的不確定性則可用這組信息的平均信息量（或熵）

來表示例

投擲一枚骼子的結果有六種，即出現(xiàn)1—6點、出現(xiàn)每種情況的概率均為1/6，故熵H=log26≈2.585（比特）。

投擲一枚硬幣的結果為正、反面兩種，出現(xiàn)的概率均為1/2，故熵H=log22=1（比特）。向石塊上猛摔一只雞蛋，其結果必然是將雞蛋摔破，出現(xiàn)的概率為1，故熵H=log21=0從例子可以看出，熵實質上反映的是問題的“模糊度”，熵為零時問題是完全清楚的，熵越大則問題的模糊程度也越大離散型概率分布的隨機試驗，熵的定義為：

連續(xù)型概率分布的隨機試驗，熵的定義為:

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

若實驗僅有有限結果S1,…,Sn，其發(fā)生的概率分別為P1,…,Pn，則當時，此實驗具有最大熵。此定理既可化為條件極值問題證明之，也可以利用凸函數(shù)性質來證明，請大家自己去完成定理8.4

若實驗是連續(xù)型隨機試驗，其概率分布P(x)在[a,b]區(qū)間以外均為零，則當P(x)平均分布時具有最大熵。定理8.5

對于一般連續(xù)型隨機試驗，在方差一定的前提下，正態(tài)分布具有最大的熵。

定理8.6

最大熵原理，即受到相互獨立且均勻而小的隨機因素影響的系統(tǒng)，其狀態(tài)的概率分布將使系統(tǒng)的熵最大。上述結果并非某種巧合。根據概率論里的中心極限定理，若試驗結果受到大量相互獨立的隨機因素的影響，且每一因素的影響均不突出時，試驗結果服從正態(tài)分布。最大熵原理則說明，自然現(xiàn)象總是不均勻逐步趨于均勻的，在不加任何限止的情況下，系統(tǒng)將處于熵最大的均勻狀態(tài)。例

有12個外表相同的硬幣，已知其中有一個是假的，可能輕些也可能重些?，F(xiàn)要求用沒有砝碼的天平在最少