人工基础智能及逻辑 6

第6章知识与信念的逻辑6.1泥孩难题引入认知推理的经典案例6.2认知逻辑：语言和语义形式化表达知识6.3公理系统$$K^n$$、$$S4^n$$、$$S5^n$$系统6.4信念逻辑信念与知识的区别6.5多智能体系统中的群体知识普遍知识、公共知识、分布式知识6.6实例与结语硬币案例与应用展望6.1泥孩难题本节内容：通过一个经典的认知推理案例，引入关于"知识"的推理问题，为后续认知逻辑的形式化表达奠定基础。例18（泥孩难题）场景设定玩耍场景三个孩子在泥地里玩耍，两个孩子额头上沾上了泥巴。视觉限制每个孩子都能清楚地看到其他孩子的额头，但看不到自己的额头。父亲的宣告与问题父亲的宣告："你们当中至少有一个人的额头上沾了泥巴。"父亲的问题："如果你已经知道自己的额头是否有泥巴，就请站出来。"6.1泥孩难题的推理过程第一轮没有孩子站出来第二轮两个有泥巴的孩子站了出来第三轮第三个孩子（那个干净的）知道自己是干净的推理逻辑："如果我额头是干净的，那么我看到的那位额头脏的孩子看到的就只有两个干净的孩子。那他就会立刻知道自己是脏的。但他并没有立刻得出这个结论。所以，我一定是脏的！"这个推理对于两个有泥巴的孩子来说是对称的——因此他们都会在第二轮知道自己是脏的。6.1泥孩难题的核心特征1.关于"知识"的推理个体知道什么、别人知道什么，或者不知道什么2.多主体交互情境三个孩子之间的认知状态相互影响3.认知状态的动态变化父亲的宣告和问题使孩子们的认知状态发生了变化引出的问题：如何用形式化语言表达这类推理？如何刻画认知状态的变化？这正是认知逻辑和动态认知逻辑所要探讨的核心问题。6.2认知逻辑：语言和语义本节内容认知逻辑的形式语言定义多主体认知逻辑的基本语言$$ℒⁿ$$的语法规则克里普克模型与可能世界语义可能世界、认知可及关系与赋值函数真值条件的递归定义公式在模型和状态上为真的递归定义形式化表达实际案例用认知逻辑语言表达日常推理6.2认知逻辑的语言定义43（认知逻辑的语言）令$$P$$是可数的原子命题集，$$G$$是有穷的主体集。$$p$$是任意的原子命题，$$a$$是任意的主体。多主体的认知逻辑的基本语言$$ℒⁿ$$由下面的规则定义：$$φ:=p|¬φ|(φ∧φ)|K_aφ$$符号说明：$$K_aφ$$读作"主体$$a$$知道$$φ$$"一元算子$$K_a$$对每个主体$$a$$而言，加入了新的一元算子$$K_a$$主体的范围主体可以是人、机器人、博弈中的玩家，或程序6.2知识算子的对偶基本算子的定义：遵循逻辑中基本算子之间的相互定义或简化的规定。有了否定符和合取符，可以定义其他的逻辑算子。对偶算子：$$⟨K_a⟩φ:=¬K_a¬φ$$与模态逻辑的类比：$$K_aφ$$类似于模态逻辑中的$$\Box$$算子（必然性）$$⟨K_a⟩φ$$类似于模态逻辑中的$$\Diamond$$算子（可能性）6.2认知逻辑的应用实例符号约定$$a,b,c$$分别表示小王、小李和小张$$p$$表示"该算法可行"$$q$$表示"该算法是小张提出来的"形式化表达(i)小王知道小李知道该算法可行：$$K_aK_bp$$(ii)小王知道小李可能知道该算法可行：$$K_a⟨K_b⟩p$$(iii)小王知道是不是小张提出了该算法：$$K_aq∨K_a¬q$$(iv)如果小王知道小李知道该算法可行，他知道小张不知道：$$K_aK_bp→K_a¬K_cp$$6.2认知逻辑的模型定义44（认知逻辑的模型）给定可数的原子命题集$$P$$和有穷的主体集$$G$$，一个克里普克模型$$𝔐=(S,{~_a|a∈G},V)$$，其中：(a)可能世界集合$$S$$$$S$$是可能世界（或可能状态）的集合(b)认知可及关系$$~_a$$对每个主体$$a∈G$$，都有一个认知可及关系$$~_a$$连接$$S$$到所有她不能区分的可能世界(c)赋值函数$$V$$$$V$$是赋值函数：$$P→𝒫(S)$$，其中$$𝒫(S)$$是$$S$$的幂集，$$V(p)$$是$$p$$为真的所有世界的集合6.2真值条件定义45（真值条件）给定一个模型$$𝔐$$和一个状态$$s∈S$$，以下递归定义一个公式在$$𝔐,s$$上是真的：原子命题$$𝔐,s⊨p$$当且仅当$$s∈V(p)$$否定$$𝔐,s⊨¬φ$$当且仅当并非$$𝔐,s⊨φ$$合取$$𝔐,s⊨φ∧ψ$$当且仅当$$𝔐,s⊨φ$$并且$$𝔐,s⊨ψ$$知识算子$$𝔐,s⊨K_aφ$$当且仅当所有的$$t$$，若$$s~_at$$，则$$𝔐,t⊨φ$$核心思想：主体$$a$$知道$$φ$$，当且仅当在所有$$a$$认为可能的世界中$$φ$$都为真。6.2泥孩难题的形式化表达练习35—用认知逻辑的语言表示下面的句子，用$$a,b,c$$表示泥孩难题中的3个孩子。(1)$$a$$额头上有泥巴，$$b$$额头上也有泥巴，但他们不知道自己有泥巴(2)$$c$$是干净的，他自己也不知道(3)$$a$$和$$b$$知道$$c$$是干净的(4)$$c$$知道$$a$$和$$b$$额头上有泥巴6.2泥孩难题初始模型练习36—图6-1是泥孩难题的初始模型，请验证每个孩子的知识状态。图6-1泥孩难题初始模型思考问题初始知识状态每个孩子在初始状态下知道什么？认知可及关系认知可及关系如何刻画孩子们的认知状态？6.3公理系统本节内容最小正规模态逻辑$$K^n$$分配公理与推理规则认知逻辑系统$$S4^n$$和$$S5^n$$事实性、正自省性与负自省性公理系统的元定理可靠性、完全性、有穷模型性与复杂度全局模态算子算子$$A$$及其对偶$$E$$的语义6.3公理系统$$K^n$$定义46（公理系统$$K^n$$）认知逻辑$$K^n$$由下面的公理和推理规则构成：公理(1)命题逻辑重言式所有命题逻辑重言式的特例(2)分配公理$$K_a(φ→ψ)→(K_aφ→K_aψ)$$推理规则分离规则(MP)从$$⊢φ→ψ$$和$$⊢φ$$，推出$$⊢ψ$$必然化规则(Nec)从$$⊢φ$$，推出$$⊢K_aφ$$公理(2)的含义：如果一个主体知道一个蕴涵式，并且他知道蕴涵式的前件，那么他也知道蕴涵式的后件。6.3关于逻辑全知问题公理(2)的争议：有学者认为分配公理是导致臭名昭著的"逻辑全知问题"的罪魁祸首。逻辑全知问题问题一如果主体知道所有逻辑定理问题二如果主体知道$$φ$$，且$$φ$$逻辑蕴涵$$ψ$$，则主体知道$$ψ$$现实困境这在实际中往往不成立（有限理性）现实中的解释区分知识类型可以区分"隐性知识"和"显性知识"资源有界可以引入资源有界的认知逻辑参考文献感兴趣的读者可以参考相关文献6.3认知主体的性质通过添加其他的公理，可以获得更强的认知逻辑系统。新的公理对应的是框架的性质，可以理解成是主体的认知能力。(T)事实性$$K_aφ→φ$$知识是事实：如果主体知道$$φ$$，则$$φ$$为真(4)正自省性$$K_aφ→K_aK_aφ$$如果主体知道$$φ$$，则主体知道自己知道$$φ$$(5)负自省性$$¬K_aφ→K_a¬K_aφ$$如果主体不知道$$φ$$，则主体知道自己不知道$$φ$$6.3公理系统$$S4ⁿ$$和$$S5ⁿ$$系统$$S4ⁿ$$在系统$$K_aⁿ$$的基础上添加公理T和4系统$$S5ⁿ$$在系统$$K_aⁿ$$的基础上添加公理T、4和5关于系统选择的讨论：在哲学和逻辑学文献中，有很多讨论关于采用$$S5ⁿ$$还是$$S4ⁿ$$刻画知识更合适对于负自省能力，有学者认为要求太强也有学者认为应该将主体的类型作为认知逻辑的核心内容进行研究本课程采用：将$$S5ⁿ$$作为知识的逻辑系统，它对应等价的框架类（满足自返性、传递性和对称性）6.3$$S5ⁿ$$系统的元定理定理23公理系统$$S5ⁿ$$对于等价的框架类既是可靠的，又是完全的。定理24公理系统$$S5ⁿ$$具有有穷模型性。任意的公式$$φ$$是可满足的，当且仅当$$φ$$在一个有穷模型上是可满足的。定理25多主体认知系统$$S5ⁿ$$的可满足性问题是PSPACE-完全的。注意：单个模态算子的系统S5是NP-完全的。定理26多主体认知系统$$S5ⁿ$$的模型检测问题是在多项式时间内可判定，是P-完全的。6.3全局模态算子局部性vs全局性模态逻辑的局部性一个公式是否为真，参照系是某个世界，相关的依据是与该世界有关（可及）的世界的信息一阶逻辑的全局性量化算子是全局性的，它是对论域的任何对象而言的通过添加全局模态算子$$A$$及其对偶$$E$$来扩展基本模态语言语义定义$$𝔐,s⊨Aφ$$当且仅当所有的$$t$$，$$𝔐,t⊨φ$$$$𝔐,s⊨Eφ$$当且仅当存在$$t$$，$$𝔐,t⊨φ$$注意：定义中的$$t$$可能与当前世界$$s$$没有任何认知可及关系。6.4信念逻辑本节内容信念与知识的区别知识必须为真，信念可以为假信念逻辑的语言和语义信念算子$$B_a$$及其可能世界解释公理系统$$KD45^n$$一致性公理D与正负自省性信念逻辑的元定理可靠性、完全性与复杂度结果6.4信念与知识的核心区别知识的特点公理T成立：$$K_aφ→φ$$知识必须是真的信念的特点主体相信的命题可以是假的公理T不成立：$$B_aφ→φ$$不一定成立信念的一致性要求主体的信念具有内部一致性一个人不能自相矛盾尽管相信的命题可能最后证明为假，但信念需要具备内部一致性6.4信念逻辑的公理公理D（一致性公理）：$$¬B_a⊥$$含义：主体不会相信一个自相矛盾的错误命题等价形式D'：$$B_aφ→¬B_a¬φ$$含义：若主体相信$$φ$$，他不能同时相信$$φ$$的否定公理D取代了公理T，使得信念可以为假，但必须保持内部一致性。6.4信念逻辑的语义可能世界模型：可能世界之间的可及关系是基于主体的信念，从而可以对信念算子进行解释：$$𝔐,s⊨B_aφ$$当且仅当所有的$$t$$，若$$s~_at$$，则$$𝔐,t⊨φ$$框架类解释信念的模型一般基于KD45-框架类，满足K、D、4、5公理所表达的性质，可及关系满足：串行性、传递性、欧几里得性更精细的刻画下节介绍信念动态变化的理论时，还将给出基于合理性排序的可能世界模型6.4公理系统$$KD45^n$$定义47（公理系统$$KD45^n$$）信念逻辑$$KD45^n$$由下面的公理和推理规则构成：公理(1)所有命题逻辑重言式的特例(2)$$B_a(φ→ψ)→(B_aφ→B_aψ)$$(3)一致性公理D$$¬B_a⊥$$(4)正自省$$B_aφ→B_aB_aφ$$(5)负自省$$¬B_aφ→B_a¬B_aφ$$推理规则分离规则(MP)从$$⊢φ→ψ$$和$$⊢φ$$，推出$$⊢ψ$$必然化规则($$B_a$$-Nec)从$$⊢φ$$，推出$$⊢B_aφ$$6.4$$KD45ⁿ$$系统的元定理定理27公理系统$$KD45ⁿ$$对于KD45-框架类是可靠的，也是完全的。定理28公理系统$$KD45ⁿ$$具有有穷模型性。定理29单主体KD45和多主体$$KD45ⁿ$$的可满足性问题是NP-完全的。定理30单主体KD45和多主体$$KD45ⁿ$$的模型检测问题是P-完全的。关于以上技术结果的证明，参考文献Blackburnetal.(2001)。6.4知识与信念的关系基本原则：含义：如果主体知道$$φ$$，则主体相信$$φ$$知识蕴涵信念知识蕴涵信念，这是刻画知识与信念二者之间关系的一个基本原则知识的充分性知识是有充分证据支持的真信念信念的可错性信念可能为假，但知识必为真6.5多智能体系统中的群体知识本节内容群体知识的概念多智能体系统中群体知识的引入背景普遍知识$$E_Gφ$$群体中每个主体都知道$$φ$$公共知识$$C_Gφ$$无穷层次的相互知道分布式知识$$D_Gφ$$群体成员知识放在一起蕴涵$$φ$$群体知识的性质不动点公理、单调性等重要性质6.5群体知识的引入背景：在多智能体系统中，几个智能体可能形成一个群体，相互协作，完成任务。这时，需要对该群体进行描述，这就需要群体知识的概念。三个关键概念：1.普遍知识$$E_Gφ$$"群体$$G$$中每个主体都知道$$φ$$"，或者"$$φ$$是群体$$G$$的普遍知识"2.公共知识$$C_Gφ$$"$$φ$$是群体$$G$$的公共知识"3.分布式知识$$D_Gφ$$"$$φ$$是群体$$G$$的分布式知识"6.5普遍知识E_G语义定义：\mathfrak{M},s\modelsE_G\varphi当且仅当对所有的a\inG，\mathfrak{M},s\modelsK_a\varphi含义：群体中每个成员都知道\varphi例子群体中的每个智能体都收到了同样的信息p这时每个智能体都知道p则p是该群体的普遍知识性质(1)这个性质可以根据定义直接得到。6.5公共知识C_G公共知识的要求更严格：第一层每个人都知道\varphi第二层每个人都知道"每个人都知道\varphi"第三层每个人都知道"每个人都知道'每个人都知道\varphi'"……以此类推无穷层次的相互知道使用普遍知识定义公共知识：E_G^0\varphi作为\varphi的简写E_G^{k+1}\varphi作为E_GE_G^k\varphi的简写E_G^1\varphi是E_G\varphi的简写\mathfrak{M},s\modelsC_G\varphi当且仅当\mathfrak{M},s\modelsE_G^k\varphi，k=1,2,\ldots6.5公共知识的可达性定义从语义上看公共知识意味着在语义模型中，从当前世界s出发，通过群体中k个主体的认知关系，最后达到世界t，\varphi在t上为真。这时，也称t是从s

可达的（Reachable）。等价定义\mathfrak{M},s\modelsC_G\varphi当且仅当对所有从s可达的世界t，\mathfrak{M},t\models\varphi6.5公共知识的不动点公理性质(2)—不动点公理：含义\varphi是群体G的公共知识则G中每个成员知道\varphi并且每个成员知道\varphi是公共知识归纳原则若\varphi\toE_G(\psi\land\varphi)，则\varphi\toC_G\psi这个性质给出推演公共知识的一个规则。通过对k施归纳，可以证明，对任意的k，\varphi\toE_G^k(\psi\land\varphi)是有效的。6.5分布式知识D_G语义定义：\mathfrak{M},s\modelsD_G\varphi当且仅当对所有t，(s,t)\in\bigcap_{a\inG}\sim_a，\mathfrak{M},t\models\varphi含义：群体G具有分布式知识\varphi意味着群体G中成员的知识放在一起蕴涵\varphi例子：主体a的认知在世界s上认为s和t是可能的，u是不可能的主体b的认知在世界s上认为s和u是可能的，t是不可能的合并结果若主体c把a和b的知识放在一起，则得到只有s是可能的。原因：c可以根据a的知识排除u，根据b的知识排除t实现方式通过取两个主体认知关系的交，得到分布式知识6.5分布式知识的性质性质(3)D_{\{a\}}\varphi\leftrightarrowK_a\varphi含义：当群体只有一个主体时，分布式知识就是个体的知识性质(4)—单调性若G\subseteqG'，则D_G\varphi\toD_{G'}\varphi含义：群体的大小与分布式知识之间的关系满足单调性群体越大，分布式知识越多因为更多主体的知识结合在一起可以排除更多可能世界6.5群体知识概念小结三种群体知识的比较：概念符号要求强度典型特征普遍知识E_G\varphi最弱每个人都知道公共知识C_G\varphi最强无穷层次的相互知道分布式知识D_G\varphi中等知识的集合蕴涵应用场景：普遍知识信息广播后的状态公共知识协调行动的前提分布式知识知识整合的潜力对这些概念感兴趣的读者，可以进一步参阅文献vanDitmarschetal.(2007)、Faginetal.(1995)、Wáng(2013)等工作。6.6实例与结语本节内容硬币盒案例分析通过具体案例理解知识与信念的形式化刻画知识与信念的形式化刻画初始状态与交流后状态的形式化表达信任程度对认知状态的影响完全信任与部分信任的不同推理结果认知逻辑的应用展望多智能体系统与认知规划的核心工具6.6硬币盒案例场景场景描述初始设置桌上有一个密封的盒子，盒子中有一枚硬币，硬币正面朝上(H)主体A偷偷查看了硬币，因而知道硬币是正面的；A也知道B不知道硬币的状态主体B没有查看硬币，因此不知道硬币究竟是正面还是反面后续交流A告诉B"硬币是正面的"根据B对A的信任程度不同，B可能只形成"相信"，也可能上升为"知道"。6.6初始状态的形式化将硬币是正面这一命题记为H。初始状态：(1)A知道硬币是正面：K_AH(2)B不知道硬币是正面：\negK_BH(3)A知道B不知道：K_A(\negK_BH)(4)B当前不相信正面也不相信反面：\negB_BH\land\negB_B\negH6.6A与B之间的交流公开告知规则：若B公开告知A\varphi，且B完全信任A，则可以使用下面的规则推理：(A\text{向B公告}\varphi)\land(B\text{完全信任A})\LongrightarrowK_B\varphi注意：这是一个较强的假设，意味着B把A的话当作无可置疑的客观真理。当A对B说："硬币是正面的"（即宣布H）根据B对A的信任程度不同，B的状态可能出现以下情况。6.6情况1：B完全信任A推理规则：A\text{公告}H\landB\text{完全信任}A\RightarrowK_BH结果B不仅相信硬币是正面的，而且在我们的模型中，他知道硬币是正面的解释B将A的话当作事实，A的告知使B获得了知识，满足知识的事实性要求（公理T）6.6情况2：B部分信任A推理结果：B可能仅将此当作"高概率"或"可信度高"的信息，但尚未达到严格的"知识"层次：B_BH\land\negK_BH含义B现在相信硬币是正面的，但并不知道硬币是正面的（仍存怀疑可能）解释B对A的话有保留，形成了信念但未达到知识的确定性。信念可能为假，但知识必为真。6.6知识与信念的差异总结通过这一示例，可以进一步看到认知逻辑与信念逻辑在刻画主体认知态度时的差异：知识(K)要求所断言的命题实际上为真主体拥有充分的证据或理由满足公理T：K_a\varphi\to\varphi信念(B)仅表示主体主观上将该命题视为真无论它是否客观为真满足公理D：\negB_a\bot（一致性）建模必要性对应日常语言中知识与信念在表达上的区别体现了在逻辑建模中对智能体不同认知态度进行细致刻画的必要性6.6不确定信息的处理关键差异：在