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

第八章

邏輯模型

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

邏輯模型

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

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

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

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

§

8.2公平選舉是可能的嗎?

什么是選舉

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

A的排序應(yīng)滿足以下性質(zhì)：(1)擇一性

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

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

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

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

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

例

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

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

根據(jù)選舉規(guī)劃，結(jié)果應(yīng)為

P:x>y>u>v

例

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

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

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

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

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

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

(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)劣次序，即當(dāng)B(x)≥B(y)時(shí)有(x≥y)，兩關(guān)系式中的等號必須同時(shí)成立。用Borda數(shù)規(guī)則得出的結(jié)果更合乎常理

例

I={1,2,3,4},A={x,y,z,u,v}，選票情況為p1p2p3:x>y>z>u>vP4:y>z>u>v>x

計(jì)算得B(x)=12，B(y)=13

故選舉結(jié)果為

y>x但有三人認(rèn)為x優(yōu)于y

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

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

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

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

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

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

將證明由公理1~公理4必可導(dǎo)出存在一個(gè)獨(dú)裁者，從而違反了公理5

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

進(jìn)一步說明：對于任意另外的候選人z，V={i}也是x、z的決定性集合?？紤]另一次選舉：(x＞y≥z)i，而（y≥z≥x）j≠I

顯然，由于全體一致意見，（y≥z）必成立。又{i}是x、y的決定性集合，故應(yīng)有（x＞y）。于是，由傳遞性，必有（x＞z）。再由公理4，y的插入不應(yīng)影響x、z的排序，故{i}也是x、z的決定性集合。評選人i是選舉的獨(dú)裁者。Arrow的公理系統(tǒng)隱含矛盾

例

設(shè)I={1,2},A={x,y,z}，考察如下的四次選舉：

（第一次）

x＞y＞z（第三次）

y＞z＞x

x＞y＞zz＞y＞x

結(jié)果應(yīng)有

x＞y合理結(jié)果

y=z

（第二次）

x＞z＞y（第四次）

x＞y＞z

z＞x＞yz＞x＞y

合理結(jié)果

x=z結(jié)果？？？由公理1，第四次的選舉應(yīng)當(dāng)是有效的由公理2，必須有（x＞y）(4)

再與第二次選舉比較并根據(jù)公理3，則應(yīng)有（x=z）(4)

與第三次比較并根據(jù)公理3，應(yīng)有（y=z）(4)

x＞y，x=z與y=z居然同時(shí)成立！改進(jìn)方案解決這一問題的另一途徑是事先適當(dāng)限制評選人的排序方式，使得可能出現(xiàn)的情況數(shù)減少，以便保證一個(gè)合理的選舉規(guī)則的存在。

§

8.3信息的度量與應(yīng)用

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

3.對這一問題非常的了解，不確定性很小黑箱不確定度A灰箱不確定度B白箱不確定度C信息I信息II對于系統(tǒng)，可以利用守恒關(guān)系有A+I=B，得I=B-A?？煞裼孟淮_定性的多少來度量信息！幾個(gè)例子：例

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

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

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

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

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

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

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

（比特）

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

（比特）

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

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

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

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

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

來表示例

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

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

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

熵具有哪些有趣的性質(zhì)定理8.3

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

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

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

定理8.6

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

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