- 相關(guān)推薦
多主體認知系統中的互知推理
在多主體認知系統中，每個(gè)主體都是一個(gè)推理者。多主體之間互知推理的復雜性在于，這種推理的對象中，不僅包括對象世界的知識，而且包含系統中其他的同樣正在進(jìn)行推理的主體；推理者對其他主體的思考及其結果進(jìn)行推理，這些主體同樣對推理者的思考及其結果進(jìn)行推理。這使得推理的素材是彈性的，動(dòng)態(tài)的，隨著(zhù)推理的過(guò)程不斷變化的。這種推理，是對人的日常思維能力的挑戰，也是對邏輯學(xué)的挑戰�！�
本文通過(guò)構造關(guān)于知道的模型，用邏輯語(yǔ)義學(xué)的方法，來(lái)刻劃多主體之間的互知�！�
形式語(yǔ)言K
在形式語(yǔ)言K中：
1,2,…,n分別表示系統中n個(gè)不同的主體�！�
p,q,r,s…分別表示如“舊金山正在下雨”、“冰冰額上有泥巴”這樣一些原子命題，它們的集合Φ構成作為主體認知和推理對象的外部世界的知識�！�
模態(tài)算子K[,i]表示“主體i知道…”。因此，K[,i]p讀作“主體i知道p”�！�
原子命題是公式；如果A是公式，則┐A是公式；如果A和B是公式，則A∧B是公式。如果A是公式，則K[,i]A是公式�！�
A∨B（讀作“A析取B”，表示“A或者B”）定義為┐(┐A∧┐B)；
A→B（讀作“A蘊含B”，表示“如果A，那么B”）定義為┐A∨B；
附圖（讀作“A當且僅當B”）定義為(A→B)∧(B→A)；
T是p∨┐p這樣的永真公式（稱(chēng)為重言式）的縮寫(xiě)，表示“真”；F定義為┐T，表示“假”�！�
現在，我們可以把在自然語(yǔ)言中非常復雜的關(guān)于知道的命題表述得十分簡(jiǎn)明。例如，公式
K[,1]K[,2]p∧┐K[,2]K[,1]K[,2]p
表示“主體1知道主體2知道p，但是主體2不知道主體1知道主體2知道p”�！�
我們可以用“知道”來(lái)定義主觀(guān)模態(tài)“可能”：主體i認為A是可能的，當且僅當主體i不知道┐A，即┐K[,1]┐A。而像“主體i不知道是否p”這樣的斷定，實(shí)際上是說(shuō)“主體i認為P和┐p都是可能的”，也就是說(shuō)“主體i既不知道┐p也不知道p”，即┐K[,i]┐p∧┐K[,i]p�！�
考慮下面這個(gè)有關(guān)水門(mén)事件的斷定：迪恩不知道尼克松是否知道迪恩知道尼克松知道麥卡德偷竊了奧博林在水門(mén)的辦公室。令主體1表示迪恩，主體2表示尼克松，p表示“麥卡德偷竊了奧博林在水門(mén)的辦公室”，則該斷定可表達為
┐K[,1]┐(K[,2]K[,1]K[,2]p)∧┐K[,1](┐K[,2]K[,1]K[,2]p)
形式語(yǔ)言K的語(yǔ)義解釋?zhuān)P(guān)于“知道”的模型
模型M，是一個(gè)克里普克結構(W,V,R[,1],…,R[,n])，其中，W是一可能世界集；V是一個(gè)解釋?zhuān)o任一可能世界，指派以一個(gè)確定的真值賦值，即對任一w[,i]∈W，和任一原子命題p∈Φ，V(p,w[,i])=T或V(p,w[,i])=F，但不能二者。如果p表示“舊金山正在下雨”，則V(p,w[,i])=T表示在可能世界w[,i]中，舊金山正在下雨；R[,i]是W上的二元關(guān)系。如果w[,j]和w[,k]有關(guān)系R[,i]，記為w[,j]R[,i]w[,k]，表示主體i依據在可能世界w[,j]中的信息，認為可能世界w[,k]是可能的。（一個(gè)世界，是一個(gè)事件集，只要其中不包括矛盾事件，就是一個(gè)可能世界；但一個(gè)可能世界，對于某個(gè)主體來(lái)說(shuō)，完全可能是不可能世界，如果這個(gè)主體知道這個(gè)可能世界中某個(gè)事件的矛盾事件。）這里，我們進(jìn)一步規定R[,i]是同時(shí)滿(mǎn)足自返、對稱(chēng)和傳遞關(guān)系的等價(jià)關(guān)系，這樣，如果主體i在可能世界w[,j]中覺(jué)得w[,k]是可能的，這說(shuō)明在可能世界w[,j]和w[,k]中，主體i具有對外部世界同樣的信息，從而對他來(lái)說(shuō)，這兩個(gè)世界是無(wú)法區分的。因此，w[,j]R[,i]w[,k]也表述為“主體i無(wú)法區分w[,j]和w[,k]”�！�
一個(gè)公式A在一個(gè)結構（模型）M的一個(gè)給定的可能世界w[,i]中真，記作附圖
附圖
上述模型所表達的核心意思是：主體i知道p，當且僅當p在主體i認為可能的所有可能世界中都真。我們用一個(gè)實(shí)例的圖示來(lái)描述這一點(diǎn)，克里普克結構的優(yōu)點(diǎn)之一是可圖示的�！�
附圖
上圖所示的模型M=(W,V,R[,1],R)，其中，W=｛w[,1],w[,2],w[,3]｝，p在w[,1]和w[,3]中真，而在w[,2]中假。主體1不能區分w[,1]和w[,2]（即主體1在w[,1]認為w[,2]是可能的，由R的對稱(chēng)性，自然在w[,2]同樣認為w[,1]是可能的，即w[,1]R[,1]w[,2]和w[,2]R[,1]w[,1]成立），主體2不能區分w[,1]和w[,3]。標有1,2的線(xiàn)段在w[,i](i=1,2,3)從自身指向自身，表示R關(guān)系的自返性，即表示w[,i]R[,j]w[,i](i=1,2,3;j=1,2)，例如表示w[,3]R[,1]w[,3]；標有1的線(xiàn)段的兩端指向w[,1]和w[,2]，表示主體1不能區分w[,1]和w[,2]，并表示R關(guān)系的對稱(chēng)性。同樣，標有2的線(xiàn)段表示主體2不能區分w[,1]和w[,3]�！�
令p表示“北京天晴”，則依據上圖，可得出以下結論：
結論1。在可能世界w[,1]，北京天晴，但主體1并不知道這一點(diǎn)，因為他在w[,1]中認為w[,1]和w[,2]都是可能的（或者說(shuō)依據他在w[,1]的知識，他無(wú)法確定w[,1]和w[,2]究竟哪個(gè)是真實(shí)世界，即無(wú)法區分w[,1]和w[,2]），而p在w[,1]中真，但在w[,2]中假�！�
結論2。主體2在可能世界w[,1]知道北京天晴，因為在可能世界w[,1]，主體2認為可能的世界是w[,1]和w[,2]，在這兩個(gè)可能世界中，p都是真的�！�
結論3。主體2在可能世界w[,2]知道并非北京天晴，因為主體2在w[,2]中認為可能的世界只有w[,2]自身，而在w[,2]中，┐p真。同理，主體1在可能世界w[,3]中知道北京天晴�！�
結論4。在可能世界w[,1]，主體1知道主體2知道北京是否天晴，因為在可能世界w[,1]，主體1認為可能的兩個(gè)世界是w[,1]和w[,2]，在這兩個(gè)世界中，主體2都知道北京的天氣（見(jiàn)結論2和結論3）。也就是說(shuō)，雖然在可能世界w[,1]，主體1并不知道北京是否天晴，但是他知道主體2知道這一點(diǎn)�！�
結論5。和結論4成為對比的是，在可能世界w[,1]，雖然主體2知道北京天晴（結論2），但是他不知道主體1不知道這一點(diǎn)。因為在可能世界w[,1]，主體2認為可能的兩個(gè)世界是w[,1]和w[,3]，在w[,1]中，主體1不知道北京天晴（結論1），但在w[,3]中，主體1知道北京天晴（結論3）�！�
以上結論，可以用一個(gè)邏輯表達式概括：
附圖
前面已經(jīng)指出，一個(gè)可能世界是一個(gè)事件集，相應的命題在其中真或假。在以上的討論中，構成w[,1]和w[,3]的事件都是“北京天晴”，因此，似乎是兩個(gè)相同的世界因而可以略去一個(gè)。但事實(shí)上卻不能這樣。因為一個(gè)可能世界的規定，不光基于構成它的事件，而且基于主體認為它是否可能。例如，在可能世界w[,1]，主體1認為可能世界w[,2]是可能的，但在可能世界w[,2]，他卻不這么認為，這樣，他在w[,1]不知道北京天晴，而在w[,3]則知道這一點(diǎn)�！�
多主體系統中的共同知識
在n主體系統中，如果所有的主體都知道所有的主體都知道…（重復≥n遍）A，則稱(chēng)這n個(gè)主體掌握了關(guān)于A(yíng)的共同知識，或稱(chēng)A是這n個(gè)主體的共同知識。這一多主體認知系統中的重要概念，最早是由路易斯在討論“協(xié)約”時(shí)提出的，他認為，某種東西要成為多方的“協(xié)約”，必須成為締約各方的共同知識，也就是說(shuō)，締約各方不但都要知道協(xié)約的內容，而且要知道各方都知道協(xié)約的內容，等等�！�
為了對共同知識進(jìn)行形式刻劃，需要在語(yǔ)言K中增加新的算子E[,G]和C[,G]，滿(mǎn)足：如果A是公式，則E[,G]、C[,G]都是公式�！�
G表示主體集｛1,2,…,n｝。E[,G]A表示“G中每個(gè)主體都知道A”；C[,G]A表示“A是G中所有主體的共同知識”。在不引起歧義的情況下，作為下標的G可以省略，即E[,G]A和C[,G]A分別記為EA和CA�！�
如果｛1,2,…,i｝是G的一個(gè)真子集（即i表示在｛1,2,…,i｝中每個(gè)主體都知道A。這種寫(xiě)法同樣用于C。這樣，附圖就表示主體3知道p不是主體1和主體2的共同知識。
在模型M中作如下定義：
附圖，當且僅當對任一附圖，即在可能世界w[,i]中，EA真，當且僅當每個(gè)主體都知道A�！�
令E[1]A表示EA，E[k+1]A表示EE[k]A，則
附圖，當且僅當附圖，即在可能世界w[,i]中，CA真（A是所有主體的共同知識），當且僅當所有的主體都知道所有的主體都知道…（重復≥n遍）A。（注意，事實(shí)上，對于任意k>1和任意w[,i]∈W，如果附圖，則附圖附圖。）
對共同知識可以作出一種有意思的直觀(guān)圖示，為此，先來(lái)定義何為從一個(gè)可能世界到另一個(gè)可能世界可通達。(1)對任意可能世界w[,j1]和w[,j2]，如果存在主體i，w[,j1]R[,i]w[,j2]，則稱(chēng)從w[,j1]至w[,j2]可通達，并稱(chēng)這種通達為一步可通達；(2)對任意可能世界w[,j1]、w[,j2]和w[,j3]，如果從w[,j1]至w[,j2]可通達，并且從w[,j2]至w[,j3]可通達，可從w[,j1]至w[,j3]可通達。并且，如果從w[,j1]至w[,j2]是k步可通達，從w[,j2]至w[,j3]是1步可通達，則從w[,j1]至w[,j3]是k+1步可通達�！�
雖然一般模態(tài)邏輯都把結構中的R關(guān)系稱(chēng)為可通達關(guān)系，但這里定義的可通達關(guān)系不同于R[,i]關(guān)系。第一，R[,i]關(guān)系是相對于某個(gè)主體i而言的，可通達關(guān)系不是相對于某個(gè)主體i而言的；第二，存在可通達關(guān)系的可能世界之間，不一定有R關(guān)系成立。例如，圖1中從w[,2]至w[,3]可通達，但w[,2]R[,1]w[,3]和w[,2]R[,2]w[,3]都不成立�！�
關(guān)于可通達關(guān)系，有兩條重要推論�！�
推論1。附圖，當且僅當附圖并且對所有w[,j]，如果從w[,i]至w[,j]k步可通達，則附圖
推論2。附圖，當且僅當對所有w[,j]，如果從w[,i]至w[,j]可通達，則附圖
可以設想這樣一個(gè)示圖，其中，每個(gè)可能世界表示為一個(gè)點(diǎn)，任意兩個(gè)一步可通達的可能世界之間用線(xiàn)段聯(lián)接。以上兩個(gè)結論的意義在于，判定A是否為可能世界w[,i]上的共同知識，只須看A是否在從w[,i]可通達的點(diǎn)（可能世界）上都真；判定E[k]A在w[,i]上是否為真，只須看A是否在從w[,i]k步可通達的點(diǎn)上都真�！�
下面，運用以上的模型方法，來(lái)分析一個(gè)很有意思的實(shí)例�！�
“額上沾泥巴的孩子”
一個(gè)教室中有10個(gè)孩子。其中，有7個(gè)孩子額上沾有泥巴。每個(gè)孩子都能看到別的孩子額上是否有泥巴，但無(wú)法看到自己的。這時(shí)老師走進(jìn)教室，對孩子們說(shuō)：“你們之中至少有一人額上有泥巴”。然后，他問(wèn)：“誰(shuí)知道自己額上有泥巴？知道的請舉手。”他如是連續問(wèn)了六遍，無(wú)人舉手，當問(wèn)到第七遍的時(shí)候，所有額上有泥巴的孩子都舉起了手。假設所有的孩子都有理想的邏輯分析能力，那么，他們是如何思考并得出結論的？
現在，嘗試構造語(yǔ)義模型，對“額上沾泥巴的孩子”作形式分析。假設孩子有n個(gè)，要證明的是，沾泥巴的孩子的人數，正好等于他們都舉手時(shí)老師提問(wèn)的次數�！�
自然需要假設題目陳述的條件，例如，所有的孩子都足夠聰明，對所有孩子都是共同知識�！�
令1,2,…,n分別表示n個(gè)不同的孩子。(x[,1],…,x[,n])表示可能世界，其中任一x[,i],x[,i]=1，或者x[,i]=0。如果x[,i]=1，則表示孩子i額上有泥巴，否則表示沒(méi)有。顯然，對于n個(gè)孩子，這樣的不同可能世界共2[n]個(gè)。例如，如果只有3個(gè)孩子，則可能世界｛1,0,1｝表示孩子1和孩子3有泥巴。假設這個(gè)可能世界就是真實(shí)世界。在這個(gè)世界中，在老師說(shuō)話(huà)之前，孩子1能看到孩子2沒(méi)有泥巴而孩子3有泥巴，他惟一不能確定的是自己額上是否有泥巴，因此，他認為(1,0,1)（即真實(shí)世界）和(0,0,1)都是可能的。也就是說(shuō)，孩子i在可能世界(a[,1],…,a[,n])認為可能世界(b[,1],…,b[,n])是可能的，即(a[,1],…,a[,n])R[,i](b[,1],…,b[,n])，當且僅當除了a[,i]≠b[,i]以外，(a[,1],…,a[,n])和(b[,1],…,b[,n])完全相同�！�
令Φ=｛p[,1],…,p[,n],p｝，其中p[,i]表示“孩子i有泥巴”(i=1,…,n)，p表示“至少有一個(gè)孩子有泥巴”。附圖當且僅當x[,i]=1。附圖當且僅當存在x[,j],x[,j]=1�！�
這樣，完成了對模型M=(W,V,R[,1],…,R[,n])的定義�！�
這一模型的優(yōu)點(diǎn)之一是基于之上可以作出清晰直觀(guān)的圖示解析�！�
令2[n]個(gè)點(diǎn)表示上述2[n]個(gè)不同的可能世界，并在任意兩個(gè)一步可通達的點(diǎn)之間用標有數字i的線(xiàn)段聯(lián)接（即如果孩子i在w[,i]認為w[,j]可能，則用標有i的線(xiàn)段聯(lián)接表示這兩個(gè)可能世界的點(diǎn)），這樣，長(cháng)于想象的讀者可以知道，我們因此得到了一個(gè)n維立方體。下圖表示的就是當n=3（即假設只有3個(gè)孩子）時(shí)這樣的一個(gè)三維立方體�！�
附圖
圖2中共有8個(gè)點(diǎn)，表示所有的8個(gè)可能世界。每?jì)蓚�(gè)可能世界之間都有標有數字的線(xiàn)段聯(lián)接，例如，標有1的線(xiàn)段聯(lián)接(1,1,1)和(0,1,1)，表示孩子1在這兩個(gè)世界的任何一個(gè)中都認為另一個(gè)世界是可能的。圖中也說(shuō)明，從任何一個(gè)可能世界出發(fā)，其余的可能世界都是可通達的�！�
從圖2立即可以得出（證明）許多結論，例如：
結論1。每個(gè)孩子都知道除自己外哪個(gè)孩子額上有泥巴。不妨設可能世界(1,0,1)是現實(shí)世界，在這一世界中，孩子1認為可能的世界是(1,0,1)和(0,0,1)，在這兩個(gè)可能世界中，孩子3都有泥巴，因此，孩子1知道孩子3有泥巴；同理，孩子2知道孩子1和孩子3有泥巴；孩子3知道孩子1有泥巴�！�
結論2。“每個(gè)孩子都知道除自己外哪個(gè)孩子額上有泥巴”是所有孩子的共同知識。結論1的證明所選擇的可能世界帶有任意性，因此，“每個(gè)孩子都知道除自己外哪個(gè)孩子額上有泥巴”在所有可能世界中真，即在從任意一個(gè)可能世界可通達的所有可能世界中真，因此，是共同知識�！�
結論3。附圖，即在可能世界(1,0,1)中，所有的孩子都知道至少有一個(gè)孩子額上有泥巴。自(1,0,1)一步可通達的可能世界有(1,1,1)、(1,0,0)和(0,0,1)，在這四個(gè)可能世界中，p即“至少有一個(gè)孩子有泥巴”都真�！�
結論4。附圖，即在可能世界(1,0,1)中，并非所有的孩子都知道所有的孩子都知道至少有一個(gè)孩子額上有泥巴。因為存在自(1,0,1)兩步可通達的可能世界(0,0,0)，其中p假，即沒(méi)有孩子有泥巴�！�
結論5。在可能世界(1,0,1)中，孩子1雖然認為(0,0,0)是不可能的，但認為孩子3可能在(0,0,1)中認為(0,0,0)是可能的�！�
當老師說(shuō)至少有一個(gè)孩子額上有泥巴后，這個(gè)命題立即成為所有孩子的共同知識，這樣，任一孩子都不可能在任一可能世界中認為(0,0,0)是可能的，這樣，通向(0,0,0)的可通達關(guān)系中斷，(0,0,0)世界可移去，圖2中的立方體因而坍塌成如下圖所示：
附圖
結論6。在可能世界(1,0,0)，主體1知道自己額上有泥巴。因為在(1,0,0)，孩子1認為可能的世界只有(1,0,0)（注意R關(guān)系的自返性。圖2、3省略了圖1中表示自返關(guān)系的圓弧線(xiàn)段），而在(1,0,0)中，孩子1額上有泥巴。同理，在可能世界(0,0,1)，主體3知道自己額上有泥巴，在可能世界(0,1,0)，主體2知道自己額上有泥巴。由結論6直接可得：
結論7。如果事實(shí)上只有一個(gè)孩子有泥巴（即真實(shí)世界是(1,0,0)或(0,1,0)或(0,0,1)），那么，在老師第一遍提問(wèn)后有泥巴的孩子就會(huì )舉手�！�
結論8。結論7是所有孩子的共同知識。不難驗證，結論7在圖3所有的可能世界中都真。例如，結論7在(1,0,1)中真，因為在該可能世界中，有兩個(gè)孩子有泥巴，因此，作為條件句的結論7的前件假，結論7自身因而真。再如，由結論6，立即可得結論7在(1,0,0)中真�！�
當老師的第一遍提問(wèn)后無(wú)人舉手時(shí)，由結論8，所有的孩子都立即知道(1,0,0)、(0,1,0)和(0,0,1)是不可能世界。這樣，任一孩子都不可能在任一可能世界中認為這三個(gè)世界是可能的，這樣，通向這三個(gè)世界的可通達關(guān)系中斷，這三個(gè)世界可因此移去，圖3繼續坍塌而成下圖所示：
附圖
圖4顯示，當老師的第一遍提問(wèn)后無(wú)人舉手時(shí)，如果只有兩個(gè)孩子有泥巴，他們立即明白自己有泥巴�！�
一般地，在上述語(yǔ)義圖中，如果老師的第k遍提問(wèn)后無(wú)人舉手，那么即可移去包含k個(gè)1的可能世界，并顯示如果只有k+1個(gè)孩子有泥巴，那么，這些孩子都知道自己有泥巴。另一方面，如果老師不告訴大家至少有一個(gè)孩子有泥巴，老師的任何一次提問(wèn)，都不會(huì )使上述語(yǔ)義圖發(fā)生任何變化�！�
博奕、商業(yè)談判、戰爭謀略等都是典型的進(jìn)行互知推理的多主體系統。這里的對手們，就是一個(gè)個(gè)沾有或不沾有泥巴的孩子。對多方體認知系統中互知推理的研究，是近十年來(lái)國際上新發(fā)展起來(lái)的研究領(lǐng)域，其成果對于經(jīng)濟學(xué)、軍事學(xué)、博奕論、人工智能和計算機科學(xué)的發(fā)展具有重要的價(jià)值，正引起密切的關(guān)注。
【參考文獻】
① Ronald Fagin etc:Reasoning about Knowledge,The MIT Press.1995．
② Halpern,J.Y.:"Reasoning about only knowing with many agents",In Proc.National Conference on AI(93)．
③ Aumann,R.J.:"Agreeing to disagree",In Annals of Statistics．
【多主體認知系統中的互知推理】相關(guān)文章：
關(guān)于鐵路主體化機車(chē)信號系統中的安全冗余設計03-02
多端口存儲器在多機系統中的應用03-20
紡機中的微機遠程多電機同步傳動(dòng)控制系統03-18
多傳感器信息融合技術(shù)在智能駕駛系統中的應用03-18
Blackfin系統引導過(guò)程中的多應用程序管理03-07
定性推理在矩形phase-portrait近似中的應用11-22
多源圖象處理與分析系統的設計03-18