我知道你不知道我知道你知道

技术宅结城浩写了几本Java,C,Perl的书后估计是觉得程序猿的钱不好赚,于是打起了宅们的主意,一本数学少女就这么红起来了。第一次听说这本书还是大一,听介绍还挺有趣的,可惜当时没有中文版,真正看到还是几年后的事了。前些日子听说这书居然还出系列了,并且还漫画化了,我该说11区已经没有救了么。看了漫画第一话的内容,居然是经典的泥孩子问题,上次说到的模态逻辑和可能世界理论正巧能够用的上,那么既然上次只是很简单的说了一下大概,这次借这个机会我就再多说两句好了。

泥孩子问题是这样的:

想象一下有n个孩子在一起玩,他们的母亲告诉他们如果他们弄脏了自己,后果会很严重。所以,理所应当的,这些孩子不愿意自己变脏,但是却非常乐意别人变脏(这腹黑的......)。现在,我们假设在这n个孩子中有k个在玩的时候弄脏了他们自己的额头,每个人都能看到其他人的的额头但是不能看到他们自己的额头。所以,没人会坦白他看到了什么。当然为了不至于回家后面对不知道是什么的“很严重的后果”,他们一起来到了父亲那里。这个父亲显然也不是省油的灯,他并没有直接告诉这些小孩他们头上有没有泥巴,只是说了“你们之间至少有一个人头顶有泥巴”。之后这个父亲就一遍又一遍的问“你们知道自己头上有泥巴么?” 我们假设所有小孩都足够聪明,诚实,并且他们总是同时回答,那么将会发生什么?

我们先假设只有3个孩子,那么如果我们用一个三元组\((q_1, q_2, q_3)\)来表示这三个孩子的状态,以0或1分别表示某人头上没有或有泥巴,则我们知道所有的可能世界有8种:(0,0,0),(1,0,0),(0,1,0),(0,0,1),(0,1,1),(1,0,1),(1,1,0),(1,1,1)。如果我们把“0个孩子头上有泥巴”,“1个孩子头上有泥巴”,“2个孩子头上有泥巴”,“3个孩子头上有泥巴” 分成4组的话,我们可以画出下面的这副图\(M_0\)
Photobucket

其中每个点代表一个可能世界,这个可能世界的状态则被标注在旁边,那么边是按照什么规矩连接起来的呢?从数值上讲,是连接有且仅有一位与起始点不同的点,所以(1,0,0)可以连接(1,0,1),(1,1,0),(0,0,0)而不能连接(0,1,1)因为他们有3位不同而不是一位。从含义上来讲,由于某个点代表着一个可能世界,则和它连接的点就是这个可能世界的所有可能世界,但是这里稍微有点复杂,因为这些可能世界是从不同人眼里出发得到的可能世界。回到具体的含义上来,(1,0,0)代表了孩子A头上有泥巴而孩子B,C上没有,那么这个世界中,由孩子A看来,他知道B和C头上没有泥巴,但是不知道自己头上有没有泥巴,所以A的所有可能世界是(1,0,0)和(0,0,0)。同理,B的所有可能世界则是(1,0,0)和(1,1,0),C的就是(1,0,0)和(1,0,1)。

那么为了明确区分到底是谁眼里的可能世界,我们在每条边上对此做出标示,则这个图就可以变为\(M_1\)
Photobucket Pictures, Images and Photos

所以在他们的父亲说任何话之前,所有可能世界和他们的关系就如上如图所示。但是,当父亲说:“你们之间至少有一个人头上有泥巴”的时候这些可能世界就发生了变化,(0,0,0)变成不可能的了,所以就成了这样,图\(M_2\)
Photobucket Pictures, Images and Photos

此时,如果只有一个孩子头上有泥巴,那么头上有泥巴的那个孩子则必然知道自己头上有泥巴,而另外两个孩子则仍没有足够的信息来确定是否自己头上有泥巴。为什么呢?我们假设此时的世界是(0,0,1)那么以这个世界为基准,对于A而言虽然他不知道自己所在的世界,但是通过观察其他的两个孩子,他可以知道自己必定在(0,0,1)和(1,0,1)这两个世界其中之一,但是这两个世界里A头上有没有泥巴是不一样的,所以A无法判定自己头上有没有泥巴,B同理。唯独C在这里除了(0,0,1)外不存在其余的可能世界,所以对于C而言,他可以确定自己头上一定有泥巴。到这里,我们可以说,如果孩子们可以判断在所有可能世界里,自己头上有没有泥巴这件事情况都是一样时,他就可以确定自己头上有没有泥巴了。

那么数学上我们如何表示?在这里我们最终要推出的是A,B,C知道自己头上有(或没有)泥巴,于是如果我们用p表示自己头上有泥巴,q表示自己头上没泥巴,那么p,q就是我们常说的命题(一个能区分真假的语句),\(K_A\)\(K_B\)\(K_C\)分别表示A,B,C知道,我们把它们叫做模态算子。则\(K_A p\)的含义就是A知道自己头上有泥巴,如果我们再加入\(\lnot\)来代表否定,那么\(K_A \lnot K_B p\)就表示A知道B不知道自己头上有泥巴。当然这么下去也可以造出像标题一样绕口的句子,不过把人绕晕乎是没有任何好处的,就在此打住。所以上面提到的(0,0,1)世界的情况,我们就可以写为:

  • \((M_2, (0, 0, 1))\models \lnot K_A p\)
  • \((M_2, (0, 0, 1))\models \lnot K_B p\)
  • \((M_2, (0, 0, 1))\models K_C p\)

这些式子的含义是,在图\(M_2\)所示的情况下,当世界为(0,0,1)时,A,B,C三者的知识情况,言下之意就是当世界为(0,0,1)时,A,B一定不知道自己头上有没有泥巴,而C一定知道自己头上有泥巴。

回到最初的问题,如果世界不是(0,0,1)而是(1,0,1)呢?(M_2, (1, 0, 1))又能得到什么?此时我们可以看到,无论是A,B,还是C,在(1,0,1)这个世界下,对于他们自己的总有另一个可能世界,在那个可能世界中自己头上有没有泥巴是不一样的,所以要是这样,他们都不会知道到底自己头上有没有泥巴,于是三人都会回答:不知道。这时情况又起了变化,当所有人回答不知道时,这就意味着必定存在着两个或两个以上的人,他们头上有泥巴,于是这个世界又变成了\(M_3\):
Photobucket Pictures, Images and Photos

此时,除了对于B而言还存在两个可能世界以外,A,C均只有一个可能世界,所以在图\(M_3\)的情况下我们有:

  • \((M_3, (1, 0, 1))\models K_A p\)
  • \((M_3, (1, 0, 1))\models \lnot K_B p\)
  • \((M_3, (1, 0, 1))\models K_C p\)

那么,当世界是(1,1,0)时也可以“同理可得”,就不用多说了吧。如果你对这些感兴趣,可以另外参考MIT出版的Reasoning About Knowledge,上面说的很详细,当然数学上也要严谨的多。

TNND,回头看这文的时候突然反应过来,这泥马的拿手摸一下不就知道有没有泥巴了,还弄得这么麻烦,搞数学的还真是没事干啊。

3 thoughts on “我知道你不知道我知道你知道

发表评论

电子邮件地址不会被公开。 必填项已用*标注