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