學(xué)習(xí)啦 > 論文大全 > 畢業(yè)論文 > 哲學(xué)論文 > 邏輯學(xué) >

多主體認(rèn)知系統(tǒng)中的互知推理

時間: 陳慕澤1 分享

在多主體認(rèn)知系統(tǒng)中,每個主體都是一個推理者。多主體之間互知推理的復(fù)雜性在于,這種推理的對象中,不僅包括對象世界的知識,而且包含系統(tǒng)中其他的同樣正在進(jìn)行推理的主體;推理者對其他主體的思考及其結(jié)果進(jìn)行推理,這些主體同樣對推理者的思考及其結(jié)果進(jìn)行推理。這使得推理的素材是彈性的,動態(tài)的,隨著推理的過程不斷變化的。這種推理,是對人的日常思維能力的挑戰(zhàn),也是對邏輯學(xué)的挑戰(zhàn)?!?
本文通過構(gòu)造關(guān)于知道的模型,用邏輯語義學(xué)的方法,來刻劃多主體之間的互知?!?
形式語言K 
在形式語言K中: 
1,2,…,n分別表示系統(tǒng)中n個不同的主體?!?
p,q,r,s…分別表示如“舊金山正在下雨”、“冰冰額上有泥巴”這樣一些原子命題,它們的集合Φ構(gòu)成作為主體認(rèn)知和推理對象的外部世界的知識。 
模態(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蘊(yùn)含B”,表示“如果A,那么B”)定義為┐A∨B; 
附圖(讀作“A當(dāng)且僅當(dāng)B”)定義為(A→B)∧(B→A); 
T是p∨┐p這樣的永真公式(稱為重言式)的縮寫,表示“真”;F定義為┐T,表示“假”。 
現(xiàn)在,我們可以把在自然語言中非常復(fù)雜的關(guān)于知道的命題表述得十分簡明。例如,公式


  K[,1]K[,2]p∧┐K[,2]K[,1]K[,2]p 
表示“主體1知道主體2知道p,但是主體2不知道主體1知道主體2知道p”?!?
我們可以用“知道”來定義主觀模態(tài)“可能”:主體i認(rèn)為A是可能的,當(dāng)且僅當(dāng)主體i不知道┐A,即┐K[,1]┐A。而像“主體i不知道是否p”這樣的斷定,實際上是說“主體i認(rèn)為P和┐p都是可能的”,也就是說“主體i既不知道┐p也不知道p”,即┐K[,i]┐p∧┐K[,i]p?!?
考慮下面這個有關(guān)水門事件的斷定:迪恩不知道尼克松是否知道迪恩知道尼克松知道麥卡德偷竊了奧博林在水門的辦公室。令主體1表示迪恩,主體2表示尼克松,p表示“麥卡德偷竊了奧博林在水門的辦公室”,則該斷定可表達(dá)為

  ┐K[,1]┐(K[,2]K[,1]K[,2]p)∧┐K[,1](┐K[,2]K[,1]K[,2]p) 
形式語言K的語義解釋,關(guān)于“知道”的模型 
模型M,是一個克里普克結(jié)構(gòu)(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上的二元關(guān)系。如果w[,j]和w[,k]有關(guān)系R[,i],記為w[,j]R[,i]w[,k],表示主體i依據(jù)在可能世界w[,j]中的信息,認(rèn)為可能世界w[,k]是可能的。(一個世界,是一個事件集,只要其中不包括矛盾事件,就是一個可能世界;但一個可能世界,對于某個主體來說,完全可能是不可能世界,如果這個主體知道這個可能世界中某個事件的矛盾事件。)這里,我們進(jìn)一步規(guī)定R[,i]是同時滿足自返、對稱和傳遞關(guān)系的等價關(guān)系,這樣,如果主體i在可能世界w[,j]中覺得w[,k]是可能的,這說明在可能世界w[,j]和w[,k]中,主體i具有對外部世界同樣的信息,從而對他來說,這兩個世界是無法區(qū)分的。因此,w[,j]R[,i]w[,k]也表述為 “主體i無法區(qū)分w[,j]和w[,k]”?!?
一個公式A在一個結(jié)構(gòu)(模型)M的一個給定的可能世界w[,i]中真,記作附圖 
附圖 
上述模型所表達(dá)的核心意思是:主體i知道p,當(dāng)且僅當(dāng)p在主體i認(rèn)為可能的所有可能世界中都真。我們用一個實例的圖示來描述這一點,克里普克結(jié)構(gòu)的優(yōu)點之一是可圖示的。 
附圖 
上圖所示的模型M=(W,V,R[,1],R),其中,W={w[,1],w[,2],w[,3]},p在w[,1]和w[,3]中真,而在w[,2]中假。主體1不能區(qū)分w[,1]和w[,2](即主體1在w[,1]認(rèn)為w[,2]是可能的,由R的對稱性,自然在w[,2]同樣認(rèn)為w[,1]是可能的,即w[,1]R[,1]w[,2]和w[,2]R[,1]w[,1]成立),主體2不能區(qū)分w[,1]和w[,3]。標(biāo)有1,2的線段在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];標(biāo)有1的線段的兩端指向w[,1]和w[,2],表示主體1不能區(qū)分w[,1]和w[,2],并表示R關(guān)系的對稱性。同樣,標(biāo)有2的線段表示主體2不能區(qū)分w[,1]和w[,3]?!?
令p表示“北京天晴”,則依據(jù)上圖,可得出以下結(jié)論: 
結(jié)論1。在可能世界w[,1],北京天晴,但主體1并不知道這一點,因為他在w[,1]中認(rèn)為w[,1]和w[,2]都是可能的(或者說依據(jù)他在 w[,1]的知識,他無法確定w[,1]和w[,2]究竟哪個是真實世界,即無法區(qū)分w[,1]和w[,2]),而p在w[,1]中真,但在w[,2]中假。 
結(jié)論2。主體2在可能世界w[,1]知道北京天晴,因為在可能世界w[,1],主體2認(rèn)為可能的世界是w[,1]和w[,2],在這兩個可能世界中,p都是真的。 
結(jié)論3。主體2在可能世界w[,2]知道并非北京天晴,因為主體2在w[,2]中認(rèn)為可能的世界只有w[,2]自身,而在w[,2]中,┐p真。同理,主體1在可能世界w[,3]中知道北京天晴?!?
結(jié)論4。在可能世界w[,1],主體1知道主體2知道北京是否天晴,因為在可能世界w[,1],主體1認(rèn)為可能的兩個世界是w[,1]和w[,2],在這兩個世界中,主體2都知道北京的天氣(見結(jié)論2和結(jié)論3)。也就是說,雖然在可能世界w[,1],主體1并不知道北京是否天晴,但是他知道主體2知道這一點?!?
結(jié)論5。和結(jié)論4成為對比的是,在可能世界w[,1],雖然主體2知道北京天晴(結(jié)論2),但是他不知道主體1不知道這一點。因為在可能世界w[,1],主體2認(rèn)為可能的兩個世界是w[,1]和w[,3],在w[,1]中,主體1不知道北京天晴(結(jié)論1),但在w[,3]中,主體1知道北京天晴(結(jié)論 3)?!?
以上結(jié)論,可以用一個邏輯表達(dá)式概括: 
附圖 
前面已經(jīng)指出,一個可能世界是一個事件集,相應(yīng)的命題在其中真或假。在以上的討論中,構(gòu)成w[,1]和w[,3]的事件都是“北京天晴”,因此,似乎是兩個相同的世界因而可以略去一個。但事實上卻不能這樣。因為一個可能世界的規(guī)定,不光基于構(gòu)成它的事件,而且基于主體認(rèn)為它是否可能。例如,在可能世界 w[,1],主體1認(rèn)為可能世界w[,2]是可能的,但在可能世界w[,2],他卻不這么認(rèn)為,這樣,他在w[,1]不知道北京天晴,而在w[,3]則知道這一點?!?
多主體系統(tǒng)中的共同知識 
在n主體系統(tǒng)中,如果所有的主體都知道所有的主體都知道…(重復(fù)≥n遍)A,則稱這n個主體掌握了關(guān)于A的共同知識,或稱A是這n個主體的共同知識。這一多主體認(rèn)知系統(tǒng)中的重要概念,最早是由路易斯在討論“協(xié)約”時提出的,他認(rèn)為,某種東西要成為多方的“協(xié)約”,必須成為締約各方的共同知識,也就是說,締約各方不但都要知道協(xié)約的內(nèi)容,而且要知道各方都知道協(xié)約的內(nèi)容,等等?!?
為了對共同知識進(jì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中所有主體的共同知識”。在不引起歧義的情況下,作為下標(biāo)的G可以省略,即E[,G]A和C[,G]A分別記為EA和CA。 
如果{1,2,…,i}是G的一個真子集(即i表示在{1,2,…,i}中每個主體都知道A。這種寫法同樣用于C。這樣,附圖就表示主體3知道p不是主體1和主體2的共同知識?!?

在模型M中作如下定義: 
附圖,當(dāng)且僅當(dāng)對任一附圖,即在可能世界w[,i]中,EA真,當(dāng)且僅當(dāng)每個主體都知道A?!?
令E[1]A表示EA,E[k+1]A表示EE[k]A,則 
附圖,當(dāng)且僅當(dāng)附圖,即在可能世界w[,i]中,CA真(A是所有主體的共同知識),當(dāng)且僅當(dāng)所有的主體都知道所有的主體都知道…(重復(fù)≥n遍)A。(注意,事實上,對于任意k>1和任意w[,i]∈W,如果附圖,則附圖附圖。) 
對共同知識可以作出一種有意思的直觀圖示,為此,先來定義何為從一個可能世界到另一個可能世界可通達(dá)。(1)對任意可能世界w[,j1]和w[,j2],如果存在主體i,w[,j1]R[,i]w[,j2],則稱從w[,j1]至w[,j2]可通達(dá),并稱這種通達(dá)為一步可通達(dá);(2)對任意可能世界 w[,j1]、w[,j2]和w[,j3],如果從w[,j1]至w[,j2]可通達(dá),并且從w[,j2]至w[,j3]可通達(dá),可從w[,j1]至 w[,j3]可通達(dá)。并且,如果從w[,j1]至w[,j2]是k步可通達(dá),從w[,j2]至w[,j3]是1步可通達(dá),則從w[,j1]至w[,j3] 是k+1步可通達(dá)。 
雖然一般模態(tài)邏輯都把結(jié)構(gòu)中的R關(guān)系稱為可通達(dá)關(guān)系,但這里定義的可通達(dá)關(guān)系不同于R[,i]關(guān)系。第一,R[,i]關(guān)系是相對于某個主體i而言的,可通達(dá)關(guān)系不是相對于某個主體i而言的;第二,存在可通達(dá)關(guān)系的可能世界之間,不一定有R關(guān)系成立。例如,圖1中從w[,2]至w[,3]可通達(dá),但 w[,2]R[,1]w[,3]和w[,2]R[,2]w[,3]都不成立?!?
關(guān)于可通達(dá)關(guān)系,有兩條重要推論?!?
推論1。附圖,當(dāng)且僅當(dāng)附圖并且對所有w[,j],如果從w[,i]至w[,j]k步可通達(dá),則附圖 
推論2。附圖,當(dāng)且僅當(dāng)對所有w[,j],如果從w[,i]至w[,j]可通達(dá),則附圖 
可以設(shè)想這樣一個示圖,其中,每個可能世界表示為一個點,任意兩個一步可通達(dá)的可能世界之間用線段聯(lián)接。以上兩個結(jié)論的意義在于,判定A是否為可能世界 w[,i]上的共同知識,只須看A是否在從w[,i]可通達(dá)的點(可能世界)上都真;判定E[k]A在w[,i]上是否為真,只須看A是否在從 w[,i]k步可通達(dá)的點上都真?!?
下面,運(yùn)用以上的模型方法,來分析一個很有意思的實例。 
“額上沾泥巴的孩子” 
一個教室中有10個孩子。其中,有7個孩子額上沾有泥巴。每個孩子都能看到別的孩子額上是否有泥巴,但無法看到自己的。這時老師走進(jìn)教室,對孩子們說:“ 你們之中至少有一人額上有泥巴”。然后,他問:“誰知道自己額上有泥巴?知道的請舉手。”他如是連續(xù)問了六遍,無人舉手,當(dāng)問到第七遍的時候,所有額上有泥巴的孩子都舉起了手。假設(shè)所有的孩子都有理想的邏輯分析能力,那么,他們是如何思考并得出結(jié)論的? 
現(xiàn)在,嘗試構(gòu)造語義模型,對“額上沾泥巴的孩子”作形式分析。假設(shè)孩子有n個,要證明的是,沾泥巴的孩子的人數(shù),正好等于他們都舉手時老師提問的次數(shù)?!?
自然需要假設(shè)題目陳述的條件,例如,所有的孩子都足夠聰明,對所有孩子都是共同知識?!?
令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有泥巴。假設(shè)這個可能世界就是真實世界。在這個世界中,在老師說話之前,孩子1能看到孩子2沒有泥巴而孩子3有泥巴,他惟一不能確定的是自己額上是否有泥巴,因此,他認(rèn)為(1,0,1)(即真實世界)和(0,0,1)都是可能的。也就是說,孩子i在可能世界 (a[,1],…,a[,n])認(rèn)為可能世界(b[,1],…,b[,n])是可能的,即(a[,1],…,a[,n])R[,i] (b[,1],…,b[,n]),當(dāng)且僅當(dāng)除了a[,i]≠b[,i]以外,(a[,1],…,a[,n])和(b[,1],…,b[,n])完全相同?!?
令Φ={p[,1],…,p[,n],p},其中p[,i]表示“孩子i有泥巴”(i=1,…,n),p表示“至少有一個孩子有泥巴”。附圖當(dāng)且僅當(dāng)x[,i]=1。附圖當(dāng)且僅當(dāng)存在x[,j],x[,j]=1?!?
這樣,完成了對模型M=(W,V,R[,1],…,R[,n])的定義?!?
這一模型的優(yōu)點之一是基于之上可以作出清晰直觀的圖示解析?!?
令2[n]個點表示上述2[n]個不同的可能世界,并在任意兩個一步可通達(dá)的點之間用標(biāo)有數(shù)字i的線段聯(lián)接(即如果孩子i在w[,i]認(rèn)為w[,j]可能,則用標(biāo)有i的線段聯(lián)接表示這兩個可能世界的點),這樣,長于想象的讀者可以知道,我們因此得到了一個n維立方體。下圖表示的就是當(dāng)n=3(即假設(shè)只有 3個孩子)時這樣的一個三維立方體?!?
附圖 
圖2中共有8個點,表示所有的8個可能世界。每兩個可能世界之間都有標(biāo)有數(shù)字的線段聯(lián)接,例如,標(biāo)有1的線段聯(lián)接(1,1,1)和(0,1,1),表示孩子1在這兩個世界的任何一個中都認(rèn)為另一個世界是可能的。圖中也說明,從任何一個可能世界出發(fā),其余的可能世界都是可通達(dá)的?!?
從圖2立即可以得出(證明)許多結(jié)論,例如: 
結(jié)論1。每個孩子都知道除自己外哪個孩子額上有泥巴。不妨設(shè)可能世界(1,0,1)是現(xiàn)實世界,在這一世界中,孩子1認(rèn)為可能的世界是(1,0,1)和 (0,0,1),在這兩個可能世界中,孩子3都有泥巴,因此,孩子1知道孩子3有泥巴;同理,孩子2知道孩子1和孩子3有泥巴;孩子3知道孩子1有泥巴。 
結(jié)論2。“每個孩子都知道除自己外哪個孩子額上有泥巴”是所有孩子的共同知識。結(jié)論1的證明所選擇的可能世界帶有任意性,因此,“每個孩子都知道除自己外哪個孩子額上有泥巴”在所有可能世界中真,即在從任意一個可能世界可通達(dá)的所有可能世界中真,因此,是共同知識?!?
結(jié)論3。附圖,即在可能世界(1,0,1)中,所有的孩子都知道至少有一個孩子額上有泥巴。自(1,0,1)一步可通達(dá)的可能世界有(1,1,1)、(1,0,0)和(0,0,1),在這四個可能世界中,p即“至少有一個孩子有泥巴”都真?!?
結(jié)論4。附圖,即在可能世界(1,0,1)中,并非所有的孩子都知道所有的孩子都知道至少有一個孩子額上有泥巴。因為存在自(1,0,1)兩步可通達(dá)的可能世界(0,0,0),其中p假,即沒有孩子有泥巴。 
結(jié)論5。在可能世界(1,0,1)中,孩子1雖然認(rèn)為(0,0,0)是不可能的,但認(rèn)為孩子3可能在(0,0,1)中認(rèn)為(0,0,0)是可能的?!?
當(dāng)老師說至少有一個孩子額上有泥巴后,這個命題立即成為所有孩子的共同知識,這樣,任一孩子都不可能在任一可能世界中認(rèn)為(0,0,0)是可能的,這樣,通向(0,0,0)的可通達(dá)關(guān)系中斷,(0,0,0)世界可移去,圖2中的立方體因而坍塌成如下圖所示: 
附圖 
由圖3可得: 
結(jié)論6。在可能世界(1,0,0),主體1知道自己額上有泥巴。因為在(1,0,0),孩子1認(rèn)為可能的世界只有(1,0,0)(注意R關(guān)系的自返性。圖 2、3省略了圖1中表示自返關(guān)系的圓弧線段),而在(1,0,0)中,孩子1額上有泥巴。同理,在可能世界(0,0,1),主體3知道自己額上有泥巴,在可能世界(0,1,0),主體2知道自己額上有泥巴。由結(jié)論6直接可得: 
結(jié)論7。如果事實上只有一個孩子有泥巴(即真實世界是(1,0,0)或(0,1,0)或(0,0,1)),那么,在老師第一遍提問后有泥巴的孩子就會舉手?!?
結(jié)論8。結(jié)論7是所有孩子的共同知識。不難驗證,結(jié)論7在圖3所有的可能世界中都真。例如,結(jié)論7在(1,0,1)中真,因為在該可能世界中,有兩個孩子有泥巴,因此,作為條件句的結(jié)論7的前件假,結(jié)論7自身因而真。再如,由結(jié)論6,立即可得結(jié)論7在(1,0,0)中真?!?
當(dāng)老師的第一遍提問后無人舉手時,由結(jié)論8,所有的孩子都立即知道(1,0,0)、(0,1,0)和(0,0,1)是不可能世界。這樣,任一孩子都不可能在任一可能世界中認(rèn)為這三個世界是可能的,這樣,通向這三個世界的可通達(dá)關(guān)系中斷,這三個世界可因此移去,圖3繼續(xù)坍塌而成下圖所示: 
附圖 
圖4顯示,當(dāng)老師的第一遍提問后無人舉手時,如果只有兩個孩子有泥巴,他們立即明白自己有泥巴。 
一般地,在上述語義圖中,如果老師的第k遍提問后無人舉手,那么即可移去包含k個1的可能世界,并顯示如果只有k+1個孩子有泥巴,那么,這些孩子都知道自己有泥巴。另一方面,如果老師不告訴大家至少有一個孩子有泥巴,老師的任何一次提問,都不會使上述語義圖發(fā)生任何變化?!?
博奕、商業(yè)談判、戰(zhàn)爭謀略等都是典型的進(jìn)行互知推理的多主體系統(tǒng)。這里的對手們,就是一個個沾有或不沾有泥巴的孩子。對多方體認(rèn)知系統(tǒng)中互知推理的研究,是近十年來國際上新發(fā)展起來的研究領(lǐng)域,其成果對于經(jīng)濟(jì)學(xué)、軍事學(xué)、博奕論、人工智能和計算機(jī)科學(xué)的發(fā)展具有重要的價值,正引起密切的關(guān)注。


【參考文獻(xià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.

3253