理论计算机科学电子笔记126（2005）27-52www.elsevier.com/locate/entcs认知行为Alexandru Baltag亚历山德鲁·巴尔塔格1，2英国牛津大学计算机实验室Bob Coecke3英国牛津大学计算机实验室Mehrnoosh Sadrzadeh4哲学系Universit′eduQu′ebecA`Montr′ealMontreal，Canada摘要我们介绍了一个代数方法动态认知逻辑。这种方法的优点是：（i）它的语义是一个透明的代数对象，具有一组最小的原语，动态认知逻辑的大多数成分都是从这些原语中产生的，（ii）它伴随着非决定论的引入，（iii）它自然地延伸到命题的布尔集合之外，直到直觉主义和非分配的情况，因此允许容纳建设性的计算，信息理论以及非经典的物理环境，和（iv）介绍了一个结构的行动，现在构成了一个Quantale。我们还介绍了一个相应的Lambek演算（它扩展了Lambek演算），其中的命题，动作以及代理出现在一个资源敏感的动态认知逻辑的资源关键词：动态认知逻辑、Quantale、模组、资源。1571-0661 © 2005 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2004.11.01228A. Baltag等人/理论计算机科学电子笔记126（2005）271介绍动态认知逻辑（DEL）是一种PDL风格的逻辑，用于对多智能体系统中的认知动作和更新进行推理。它特别侧重于epis-temic程序，即更新代理的信息状态的程序，并且它具有关于代理之间的信息流和信息交换的建模和推理的应用。这是几个领域中的主要问题，例如安全通信，其中必须处理通信协议的隐私和认证，人工智能，其中代理人将被提供可靠的工具来推理他们的环境和彼此多智能体系统中信息流的标准方法已经在[9]中提出，但它没有提出认知程序及其更新的正式描述。第一次尝试正式化这些程序和更新是由Plaza [22]，Gerbrandy和Groeneveld [13]以及Gerbrandy [11，12]完成的。然而，他们只研究了一类有限的认知程序。在[4，5]中介绍了DEL然而，在这种方法中，命题的基本逻辑是布尔的。为了计算的目的，人们可能想把它放宽到一个直觉主义的设置，因此设想命题是在一个海廷代数中结构化的。另一方面，连续格也是知识分布的模型[10]，并且通常不是分配的。最后，诸如量子计算的实际物理计算情况需要（至少）非布尔设置。在本文中，我们推广这种概括与状态和动作的非确定性的引入密切相关，并为语义带来了代数清晰性。我们引入的特定代数对象是对以前使用的对象的改进，这些对象是为了研究计算机科学中的并发性[1，23]以及物理系统的动态和相互作用[7]。 这样一个抽象的认识系统由认识的QuantaleQ组成，程序，认知命题的Q-右模块M，每个代理是由外观映射编码，即，（M，Q）-结构的自同态我们表明，布尔DEL [5]是一个具体的例子，这种抽象1感谢S。Abramsky，A.Joyal，D.帕夫洛维奇和我。Stubbe进行有价值的讨论。M. S. 谢谢S。阿布拉姆斯基和牛津大学计算机实验室的热情好客和M。马里恩负责后勤支援。2 电子邮件地址：baltag@comlab.ox.ac.uk3 电子邮件地址：coecke@comlab.ox.ac.uk4电子邮件：sadrzadeh. courrier.uqam.caA. Baltag等人/理论计算机科学电子笔记126（2005）2729AA认知系统模态算子的公理直接从它们上面的量子和模的抽象性质得出DEL的关键概念是可定义的抽象概念，一些新的概念自然出现。通过一个非布尔理论也提供了一个新的洞察认识程序，如公开宣布和，一个令人惊讶的不同地位，公开反驳。我们勾勒出一个分析泥泞的儿童难题和密码攻击在我们的设置，也提供了一个激励的例子，通过一个非布尔理论。我们还提供了一个相应的递归演算，其中序列通常看起来像m1，...， q1，... 、A1、. ，mk，.，ql，. ，A nδ其中m1，.，m，k是命题，q1，.，q l是动作，A1，. A n是分解为单个命题或动作δ的主体。限制于动作的演算的片段是Lambek演算[19]，因此资源敏感2认识命题和认识纲领在这一节中，我们稍微改写和丰富的动态认知逻辑，[5]以这样的方式，它使一个顺利通过代数设置将在第4节中介绍。其中一部分涉及到对状态和行为的非决定论的引入.州模特。对于一组事实Φ和一组有限的代理A，状态模型是一个三元组S=（S，→A，μ）其中S是状态的集合，→AS×S是each的可容性关系agentA∈ A，μ：S→ P（Φ）表示满意度的赋值映射S| =优惠价∈μ（s）。 “事实”是世界的简单、客观的特征（非认识意义上的“客观”，即独立于主体的知识或信念），而赋值图告诉我们在给定的 每个可访问性关系都可以重新打包为一个映射F：S→P（S）：：s<$→f（s）：={t∈S|s→At}，叫做A特工的外貌图表观映射的意义如下：如果t∈fA（s），那么，每当代理A处于状态s时，他认为A∈A30A. Baltag等人/理论计算机科学电子笔记126（2005）27把t看作是一个“可能世界”。换句话说，如果系统的实际状态是s，代理A认为t可能是实际状态。例如，考虑两个运动员A、B和一个裁判C.在所有人面前，裁判员抛出一枚公平的硬币，用手掌接住并完全盖住，然后任何人（包括他自己）都可以看到硬币落在哪一边。 这里有两种可能的状态，硬币所在的Heads尾向上（= T ∈ Φ），因此μ（t）={T}。 我们将状态模型Toss描述为，Js，n：H，`，\，rz，Jt，n：，T，`，\.. 、A、B、C、.、A，B，C A，B，C对于每一个主体，任何两个状态（包括相同的状态）之间都有箭头，这意味着没有人知道我们还可以考虑这样一种情况，其中代理B和C可以看到硬币的正面，但代理A看不到（尽管他知道其他人看到了）。他不确定硬币是正面还是反面。在这种情况下，只有代理A在状态之间有几个箭头，而代理B和C在每个状态下只有一个箭头，这意味着如果硬币是正面朝上，他们知道它，同样也是反面朝上。因此PToss被描述为s，J，J：H，`，\，rz，Jt，J，：，`T，\.，A ，A，B，C A，B，C状态模型S上的认知命题P是S的子集P，包含命题为“真”的所有状态状态模型的映射μ和fA扩展到P的元素，如下所示μ（P）：={μ（s）|s∈P} ∈ P（Φ）f A（P）：={f A（s）|s∈P} ∈ P（S）.请注意，我们必须使用交集而不是并集来定义μ（P），因为当一个事实在命题的所有状态下成立时，它就被一个认识命题所蕴涵这使得从P（S）到P（Φ）的通路是反变的。换句话说，事实的实际代数是P（Φ）op，也就是说，完全布尔代数P（Φ）的顺序是相反的，即，2。虽然事实是简单的和非认知的，因此不能被认知行为改变（见下文），但认知命题可以表达复杂的世界的特征，这可能取决于代理人然而，注意每个事实<$∈Φ[5]关于认证协议的更详细的例子，我们请读者参考[2]。A. Baltag等人/理论计算机科学电子笔记126（2005）2731你好， 你好，对应于一个认识命题P ∈：={s∈S|∈μ（s）}，表示该事实在当前状态下成立。在Toss模型中，H和T是表示正面朝上或反面朝上的事实 的硬币。与这些事实相对应的认识论命题是这些事实存在的状态。这些位置分别是：{s}，{t}，{s，t}，{s，t，t}，{ s，T， t{s，t}。我们用双-围绕着被包含的国家，，Js，n：H，`，\，rz，Jt，n：，T，`，\，J，Js，，：H，`，`，\，\，rz，Jt，：，T，`，\，Js，：H，`，\，rz，J，J，t，：，T，`，`，\，\，J，Js，，：H，`，`，\，\，rz，J，J，t，：，T，`，`，\，\.、A、B、CA、B、C.，A、B、C、A、B、CA、B、C.，A、B、C.、A、B、CA、B、C、A、B、C、A、B、CA、B、C、A、B、C代表了托斯的四个认识论命题。当一个命题P恰好有一个状态s∈P（即P={s}是单例）时，我们将使用系统歧义，将命题与状态标识并写作例如P={P}。行动模式。给定状态模型S，S上的动作模型是三元组Σ=（μ，→A，μ）类似于状态模型，除了我们认为行为的元素是可能的行为而不是可能的状态，并且赋值μ：μ→ P（S）为每个行为σ分配了一个前提条件，即定义σ的适用范围的命题μ（σ）：行为σ可以发生在状态si μs∈μ（σ）中;例如，一个事实的真实宣布只能发生在该事实成立的那些状态中。注意，由于P（S）是布尔型的，我们可以等价地考虑动作不能发生的状态。这些状态是一个作用的前提条件的补充，记作Ker（σ）：=S\μ（σ），对于每个σ∈μ。动作对状态和外观映射的影响将在下面根据认知更新产品来定义。我们在Toss上引入了一个动作模型。当裁判接住硬币后，他可能会偷偷地看一眼硬币，然后在没有人注意到这一点的情况下盖上它动作模型现在描述为J，σ，σ`，z，A，BzJ，C A，B，C其中σ代表“作弊”，τ代表“什么也没发生”，µ（σ）= { s，t }。当用σH和σT代替σ时，可以细化动作模型，其中μ（σH）={s}和μ（σT）={t}，指定裁判在欺骗的情况下看到了什么。形象地A∈A32A. Baltag等人/理论计算机科学电子笔记126（2005）27，Jσ，，不 ，，C.，，JJ，，Z，，\J，Jσ，JH，`，\A，B z，J，'τC甲乙丙和218c动作模型π上的认知程序π是π的子集;μ和f-A映射都是通过连续性协变扩张的μ（π）：={μ（σ）|σ∈π}∈P（S）andndfA（π）：={f A（σ）|σ ∈ π} ∈ P（π）.程序的μmaps定义中的联合说，一个认知程序在它的至少一个动作适用的地方是适用的。这使得Ker映射通过布尔否定逆变地跟随，即Ker（π）：S\μ（π）或等价的Ker（π）：={Ker（σ）|σ∈π}。认知程序引入非决定性：只要π1<$π2，则π2通过增加非决定性从π 1获得; π={σ1，σ2}代表“要么动作σ 1要么动作σ 2发生”。在我们的例子与行动σH，σT和τ的认知程序{σH，σT}代表非确定性行为σ，在这个意义上，掷硬币的结果可以是。我们通过在包含动作的对象上画双圈来描述动作上的程序。因此，程序π={σH，σT}的图像是是甲乙丙z.，C甲乙丙和218c，JJ，σ，σ，T，z，与状态和命题的情况一样，我们使用系统模糊性来识别确定性程序π={σ}及其唯一的潜在动作σ。更新.GivenasoftenatemoddelSandnactinmoddelΣ在S上，我们定义它们的更新产品介绍S：=σ∈Σ是一个新的状态模型，μ（σ）×{σ}f A（s，σ）：=（fA（s）×f A（σ）））μ（s，σ）：= μ（s）.简单地说，我们有S ={（s，σ）|s ∈ μ（σ），σ ∈ <$}<$S × <$f A、、、、，z一、、、、z，一、，，CA. Baltag等人/理论计算机科学电子笔记126（2005）2733（s，σ）<$f A（s）×f A（σ），即（SJ，σJ）∈f A（s，σ）i <$SJ∈f A（s）且σJ∈f A（σ）.因为它将在下一节的抽象代数中变得更加明确，是一种结构保持操作，在这个意义上，它没有侧效应，34A. Baltag等人/理论计算机科学电子笔记126（2005）27s，σH，s，τ，rzt，，τ它所作用的状态模型。在我们的例子中，在作弊行为之后，σH硬币躺在哪里抬头，A和B认为没有人知道硬币躺在哪一边。但他们错了！这个动作之后的系统可以通过取上面描述的两个模型Toss和σHC，J，'，`，，\，A，，B甲乙丙，J，`，\、、、，Jr，，`，\. 、A、B、CA、B、C、A、B、C注意，一般情况下，S和S不一定不相交。6定义2.1我们定义epistemicpropositionP的updatepropduct和一个作为认识命题的认识程序πΣPπ：=σ∈π（μ（σ）<$P）× {σ}<$P×πover S <$ 。命题P<$π提供了P关于认识程序π的最强后置条件。这意味着如果命题P在程序π的输入处为真，则Pππ是在π的输出处为真的最强命题。可以看出，Pπ=iPμ（π）=， 其中是假命题（即，S上的平凡假认识命题）。模式。我们将每个施事A∈ A的认识模态定义为一元连接词，它将命题P∈S赋给另一个命题..ΣQAP：=s∈S。fA（s）在S.我们把QAP读作7Σ我们定义了每个认知程序π的动态模态，作为一元连接词，它赋予命题PSoverS另一个命题..- 是的.Σ[π]P：=s∈S。{s}<$π <$P=Q ∈ P（S）. Q π P在S.[6]事实上，我们后面要考虑的最重要的模型（DEL模型）在更新产品方面是封闭的，即SS。[7]根据语境，选择A. Baltag等人/理论计算机科学电子笔记126（2005）2735注意（如前所述）一些状态s∈S本身可以是状态和动作（s，σ）的对，这使得上面的定义得到了很好的定义。命题[π]P提供了P关于认识程序π的最弱的前提条件。这意味着如果命题P在程序π的输出为真，那么[π]P是在π之前应该为真的最弱命题。顺序组成。顺序组成ΣΣ1· Σ2个版本的SoffasteningwoactionmodelsΣ1和2都在S上意味着1、然后做21·简单地说，（σJ，σJ）∈fA（σ1，σ2）i <$σJ∈fA（σ1），σJ∈fA（σ2），1 2 1 2也就是说，μ（σ1，σ2）={s ∈ S |s ∈ μ（σ1），s <$σ1∈ μ（σ2）}。再次注意到，和U1（或U2）不一定不相交。8在状态模型S上的动作模型包含动作跳过，在动作跳过中没有发生任何事情。skip={skip}μskip = S = TP（S）f A（skip）={skip}.注意系统歧义的使用：我们用相同的名字表示（skip）程序跳过和它的唯一动作。很容易看出，跳跃是一个单位，直到同构，无论是更新产品和顺序组成。第二章.我们定义了两种生殖保护的必要组成部分，将π1over1和π2over2表示为外延表达式π1·π2：=π1×π2超过1· 2。具体的认知系统。我们现在有了所有的工具，使DEL的通过在这个意义上，[5]到“具体的认识系统”，我们提出作为一个垫脚石，向“抽象的认识系统”。一个DEL模型本质上是一个在更新乘积和序列组合下封闭的模型（并且包含一个跳跃），而一个具体的认知系统由一个DEL模型的所有认知命题和所有认知程序组成定义2.3ADELmodelisapair（S，Σ其中S是状态模型，并且是S上的一个动作模型，使得skip∈S，（S）S和（S·）。定义2.4给定一个DEL模型（S，S），一个具体的认知系统是对（P（S），P（S）），它配备了估值μ，外观图[8]事实上，我们稍后只考虑那些在其中存在着“零”的模型。[9]在前面的例子中，这个作用被表示为τ。36A. Baltag等人/理论计算机科学电子笔记126（2005）27{fA}A∈A和DEL模型的所有其他运算扩展到P（S），P（n），如前所述。3程序和命题一个子格L是一个完备格，其映射保持任意连接为同态。回想一下，每个子格也有任意的交，即ai=我{b ∈ L |n i，b ≤ a i}对于任何一个A。因此，“超晶格”这个名称指的是这样一个事实，我们只需要结构保持映射来保持任意连接（参见完全Heyting代数的locale和frame的命名[17]）。我们分别用T和T表示L的底部和顶部，并将其原子集定义为Atm（L）：={p ∈ L\{n} |a ≤ p <$a = n}。一个格L是原子的，a∈L，a={p ∈ Atm（L）|p ≤ a}。每一个变形的m函数：L→M有一个（unique）rightGaloisadjointf满足f（a）≤ba≤f（b）并且可以明确地给出为f∈：M→L：：b<$→ {a∈L|f∈（a）≤b}。左伽罗瓦伴随f还保持任意交。我们用f_y_E_f_i表示一个相邻的p。在计算测试中，没有人能想到左Galoisadjoi ntfassssssingges ttprecnt Ionswithes p et o n t ope t o p e p e t o p e t o p o p etopo p epQuantale10是配备有幺半群结构（Q，·，1）的超格Q，满足.Σa·bi=我（a·bi）我.Σai·b=我（a i·b）。我[10] Quantale一词关于quantales的调查，我们参考[24]。关于quantale和Q-模的有见地的范畴观点，我们参考[18]和[25]。A. Baltag等人/理论计算机科学电子笔记126（2005）2737因此，对于所有a∈Q，映射a·−：Q→Q和−·a：Q→Q保持任意连接，因此它们具有Galois伴随（a· −）E（a\ −）和（−·a）E（−/a），由下式显式给出：a\b：={c ∈ Q |a·c ≤ b}b/a：={c ∈ Q |c·a ≤ b}。我们将（a\−）和（−/a）称为剩余运算。Quantale同态既是一个超同态又是一个幺半群同态。量子数的例子有：完备格L按点序的所有上自同态的集合sup（L）;从集合X到其自身按点包含序的所有关系的集合--这个量子数同构于sup（P（X））;任何幺半群的幂集，其复合被连续性扩展。一个QuantaleQ的Q-右模是一个超格M，它配备了一个模作用− M−：M×Q→M，即，m1 =mm<$（q1·q2）=（m<$q1）<$q21000万元人民币（我qi）=我（mqi）我mi）q=（miq）我同样，我们有两个右伽罗瓦伴随- <$qE[q]-和m<$-E{m}-哪里[q] m：= {mJ∈ M |mJ<$q ≤ m}{m}mJ：={q ∈ Q |m <$q ≤ mJ}。对于一些例子，QuantaleQ是其自身上的Q-右模，其中复合作为张量，并且完备格L是sup（L）-右模，其中函数应用作为张量。定义3.1一个系统是一个对（M，Q），其中Q是Quantale，M是Q-右模[1]。当M和Q都是原子性的并且下面的方程成立时，系统是原子性的m∈Atm（M），q∈Atm（Q）=<$m<$q∈Atm（M）<${<$}q1，q2∈ Atm（Q）=<$q1·q2∈ Atm（Q）.这些条件可以解释为提议3.2一. 认知程序P（P）具有as、序列组合为·和“skip”为1，形成Quantale。11二.认识命题[11]这种结构隐含在[15]中动态行为的关系构成中。38A. Baltag等人/理论计算机科学电子笔记126（2005）27一一一P（S）与as和更新乘积as形成右P（S）-模12。iii. 对（P（S），P（S））是一个原子系统。模P（S）的原子对应于态s∈S，而QuantaleP（S）的原子对应于作用量σ∈ S。提案3.3 i. 表观映射fA：P（S）→ P（S），以及对所有π∈ π，映射−ππ：P（S）→ P（S）都是超同态。二. 表观映射fA：P（n）→ P（n），对所有π∈ n，映射π· −，−·π：P（n）→ P（n）是量子同态。三. 对于每个认知命题P∈ P（S）和每个认知程序π∈ P（S），我们有fA（P <$π）<$fA（P）<$fA（π）.iv.对于每个状态（即原子命题）s∈S和每个动作（即原子程序）σ∈S，我们有：如果s <$σ/=<$，则f A（s <$σ）= f A（s）<$f A（σ）。最后一个性质可以通过引入相干性的概念来推广：定义3.4一对（P，π），其中P是一个认识命题，π是一个认识程序，是连贯的，<$s∈P， <$σ∈π s <$σ <$故，凡有相，皆是虚妄。这意味着命题P确保了程序π所包含的所有动作的可能性。一个不涉及状态或动作的等价定义<$PJ<$P，<$πJ<$π（PJ<$πJ=<$$>PJ=<$或πJ=<$）。命题3.5如果（P，π）是一个相干对，那么我们有fA（P <$π）=fA（P）<$fA（π）.提案3.6 i. 对于A ∈ A，右伽罗瓦伴随到外观f S（−）：P（S）→ P（S）是知识QS一- （=认知模态）。 二.对于π∈P（S）是更新− π的右伽罗瓦伴随：P（S）→ P（S）是动态模态[π] −。三. 右伽罗瓦伴随着出现f（−）：P（）→ P（）引入了一个关于动作的认知模态Q−。四. 左和右复合π· −，−·π的右伽罗瓦伴随：P（n）→ P（n）分别引入最弱预规范π\−和最强后规范π/−，[12]通过这种构造，我们可以清楚地看到，update是epistemic命题上的一个结构保持映射，并且没有边效应。A. Baltag等人/理论计算机科学电子笔记126（2005）2739FMQ而右伽罗瓦伴随到P<$−：P（<$）→ P（S）引入了{m}−，这是它的一个变体。13证据所有这些都是由关于集合、卡鲁埃积和关系的结构和基本事实来说明的。Q4抽象认知系统上一节的命题使我们得出以下定义：定义4.1系统自同态（M，Q）→（M，Q）是一对.Σf：M→M，f ：Q→Q其中fM是超同态，fQ是Quantale同态，fM（m<$q）≤fM（m）<$fQ（q）（1）对所有的m∈M和q∈Q.定义4.2一个（抽象的）认知系统是一个元组（M，Q，{fA}A∈A）其中（M，Q）是一个系统，{fA}A∈A是系统自同态.解读。QuantaleQ的元素被认为是认知程序，它的单位是跳跃，模M的元素被认为是认知命题，或者如果需要的话，不一定是确定性的状态，标签A∈ A是具有自同态{fA}A∈A的主体，他们的外貌地图一个程序q∈Q的核是Ker（q）：={m ∈ M |m q =}它包括前提条件：它包含不能应用q的认识论命题。稳定器Stab（Q）：={m∈M| <$q∈Q，[q] m= m}[13]残差π\−将最弱的程序π\δ分配给它的自变量δ，在计算π之后必须计算该程序，使得净有效值低于δ。 残差−/π将最强的程序δ/π赋给它的自变量δ，这个程序在计算π之前必须计算，使得净结果低于δ。右伽罗瓦伴随{m}−将最弱命题{m}P在导出π之前赋给它的自变量δ，从而保证了π之后的P。关于预规范和后规范的讨论，我们参考[8，16]。40A. Baltag等人/理论计算机科学电子笔记126（2005）27一一A Aa一一由事实构成：它由那些在认识活动下是稳定的认识命题构成满足关系包含在M的偏序中：对于一个状态m∈M和事实m∈Stab（Q），我们有m| =优惠m≤1。在命题3.6中讨论和引入的所有模态和其他右伽罗瓦伴随在这里也作为右伽罗瓦伴随出现，因此它们的解释仍然成立，例如，fM“。模式的性质我们确定的方式的基本属性。命题4.3在任何认知系统中，QM MJMMJm≤mJAT=TQ（m<$m）=Qm<$QmQMm ≤ QMmJ。A A证明：自QM是一个右伽罗瓦伴随，它保持任意交，QM（Aimi）=i QMmi，因此它保留了空的满足和二进制满足，并且是单调的。Q由于所有其他模态保持任意满足，所以相同的结果对它们和所有其他右伽罗瓦伴随都成立。在一个直观的上下文中，人们可能会把M作为一个框架（即一个具有超同态的（完备）Heyting代数），我们可以使用Heyting代数的定义性质来内化偏序，因此我们得到► m→mJ► QMm → QMmJ。A A因此，在Q={1}和A={2}的特殊情况下，我们得到[27]的直觉模态逻辑IntKQ我们的结论是，直觉主义认知系统，即M是一个框架的认知系统，直觉主义模态逻辑推广到多个代理和动态的认知程序。如果M是一个完备的布尔代数，如第2节的幂集，那么KripkeQM（m → mJ）→（QMm → QMmJ）。A A a在这种情况下，钻石和相应的规则通过二元性而产生。学习定义4.1中的等式（1）是一个不等式，这一事实表达了学习的代理人。更新时代理出现的一些条款A. Baltag等人/理论计算机科学电子笔记126（2005）2741乘积可能从等式（1）的左侧被消除，仅仅因为程序的某些子动作可能不适用于命题的某些子状态。这意味着智能体在更新后学习到了一些新的东西（左侧比右侧更强）。我们也可以通过引入一致性的概念来强制平等：定义4.4一个对（m，q），其中m∈M和q∈Q是相干的，<$mJ≤m，<$qJ≤q（mJ<$qJ=<$$>mJ=<$或qJ=<$）例如，在原子系统中，每个原子对（m，q）∈Atm（M）×Atm（Q），其中m∈ker（q）是cohent。定义4.5强认知系统是一个元组（M，Q，{fA}A∈A），其中（M，Q）是一个系统，对于所有相干对（m，q），我们有以下等式fM（m <$q）= f M（m）<$f Q（q）.表示定理。定理4.6任何原子论强认知系统，只要M和Q都是完全分配布尔代数，都可以表示为一个具体的认知系统。证明：假设S：=Atm（M），Φ：=Atm（Q）和Φ：=Stab（Q）。可达性关系产生于外观映射，满足条件为：对于s∈S和φ∈Φ，满足条件为：μ（σ）：=S\Ker（σ）。Q定理4.7每个具体的认识系统（P（S），P（S））都是原子的强（抽象）认识系统（M，Q，{fA}A∈A）.证明：通过命题3.2、3.3和3.5。Q5一些动态认知情境对于一个给定的认知系统（M，Q，fA）A∈A，下面是一些可以在系统中定义的一些特殊的认知程序的例子。野手Ker（q）= ↓（Ker（q）），其中↓a：={b∈L|b≤a}，因此，在q42A. Baltag等人/理论计算机科学电子笔记126（2005）27.，. ，A∈ . ，/β.，(i) 命题m∈M的公开反驳是一个认识程序q∈Q，{fA（q）}A∈A=q，Ker（q）=↓m. 我们把它描绘成J，，r，，，~q，~`，，，z，A∈A(ii) 对子群的私人反驳这也是一个程序，它将一个命题m私人地反驳给代理的子群β。 Ker（q）与前面相同，并且{fA（q）}A∈β=q和{fA（q）}A∈A\β= 1。它被描绘成J，n，，r，~q，~`，z，Jz，n，1`，zA∈β A ∈A(iii) 命题m的失败测试是当m失败时测试的程序q。这是一个特殊的私人反驳的情况下，其中m被反驳到一个空的代理集Ker（q）=↓m和{fA（q）}A∈A= 1。形象地J，r，~q，~`，z，A∈AzJ，n，1`，，z，A∈A(iv) 公开宣布在我们的环境中也是可以定义的。然而，虽然“不在q的前提条件下”是M中的一个命题，对于所有q ∈ Q，这不是“在q的前提条件下”的情况。看到这考虑格{k ≤a，b，c≤T}，其中q使得Ker（q）=其中在第2节的语言中，我们有μ（q）={b，c}，它不能用M的单个元素表示。其原因这个格子是非布尔型的因此，命题m∈M的公开宣告是一个认知程序q∈Q 其中fA（q）=q并且其中Ker（q）具有布尔补数（Ker（q））c，满足（Ker（q））c=m。我们现在介绍一些案例研究。给定一个认知系统（M，Q，fA）A∈A，我们在其上施加特定的条件，这些条件编码所需的状态和动作模型。作弊考虑第一部分的回想一下，在状态模型Toss，s中有两种可能性，其中硬币是正面朝上的，而t是反面朝上的。 我们通过假设给定一个认知系统（M，Q）来模拟这个抽象，其中s，t∈M，σH∈Q。事实被编码为稳定器，即。我们被赋予A. Baltag等人/理论计算机科学电子笔记126（2005）2743命题H，T∈Stab（Q）.所有这些都假定满足以下条件： fi（s）=fi（t）=s<$T，对所有i∈As≤H，t≤T，H<$T=<$，认知程序σH∈Q有映射fA（σH）=fB（σH）= 1和fC（σH）=σH，核Ker（σH）=↓t.这个程序描述了一个硬币正面朝上的作弊实例。s<$σH∈M是用σH更新后的命题s。让我们用我们的代数设置e来推理这个场景证明了s<$σH≤QCH.事实上，通过{fA}A∈A是系统同态，并且等式（1），我们有fA（s<$σH）≤fA（s）<$fA（σH）=（s<$t）<$1 =s<$t，f B也是如此。另一方面fC（s<$σH）≤fC（s）<$fC（σH）=（s<$t）<$σH=（s<$σH）<$（t<$σH）=s<$σH因为t∈Ker（σH）.我们有s≤Hi <$s<$σH≤H<$σH，通过Stab（Q）的定义，我们得到s<$σH≤H。因此，fC（s<$σH）≤H，通过附加我们得到s<$σH≤QCH，这意味着在通过偷看更新他的初始状态后，裁判知道硬币是正面朝上的。如果裁判是诚实的，他不会偷看硬币。然后，他公开驳斥了在这种情况下，认识程序是命题t的公开反驳，其中fA（q）=fB（q）=fC（q）=q和Ker（q）={t}。因此，s<$q ≤QAH，B和C也是如此。因此，所有的代理人都知道，硬币是在公众反驳后抬头泥泞的儿童拼图。我们建议读者在[9]中详细描述泥泞儿童难题的一般情况。在[6]中，这个一般的版本已经被编码，并像往常一样在我们的代数环境中通过归纳法求解。本文讨论了三个孩子A、B、C在泥中玩耍的情况，其中A和B的额头上都有泥。他们的父亲公开宣布，他们中至少有一个人的额头上有泥，并问他们是否知道自己很脏。当他们都同时回答“不！”有一次，泥泞的孩子A和B会知道他们是泥泞的。这种简单的情况只有一轮（因为脏孩子的数量是2），但是具有k个脏孩子的一般情况应该有k-1轮的“不！”回答。如前所述，我们通过假设给定一个认知系统（M，Q）来对此进行建模。代理A的集合包括子{A，B，C}。模M包括所有可能的初始状态sβ，其中β∈ A是44A. Baltag等人/理论计算机科学电子笔记126（2005）27我都脏了 由于孩子们看不到自己的额头（可能是脏的，也可能不是），我们对每个孩子i有fM（s β）=s β\{i}<$s β<${i}。设D是没有孩子有脏前额的事实，D i是孩子i有脏前额的事实，因此{D} <${Di∈M|i∈A}<$Stab（Q），且对所有i∈β，al sos β≤Di. 设q是3个孩子的无答案的一轮，即q是QAD A<$QBD B<$QCD C的公开反驳，因此Ker（q）= QAD A<$QBD B<$QCD C，并且对于每个孩子i，fi（q）=q。设q0∈Q是父亲宣布至少有一个孩子额头上有泥，因此Ker（q0）=↓D，且对每个孩子i，fi（q0）= q0. 我们必须证明，在第一轮反驳q之后，每个泥泞的孩子（例如， A）知道他是脏的，即s{A，B}≤[q0·q]QADA，对于孩子B也是如此。通过添加动态模态和认知模态以及模方程（m <$q1）<$q2= m <$（q1·q2），我们得到f A（（s{A，B}<$q0）<$q）≤ D A.（二）根据fA不等式（即等式（1）），其表面上示出fA（s{A，B}<$q0）<$fA（q）≤DA再次由等式（1）和假设fA（q0）=q0fA（s{A，B}<$q0）≤fA（s{A，B}）<$q0通过fA（q）=qfA（s{A，B}<$q0）<$q≤（fA（s{A，B}）<$q0）<$q因此，为了证明等式（2），它可以表明：（fA（s{A，B}）<$q0）<$q≤DA用它的值代替fA会得到（（s{A，B}<$s{B}）<$q0）<$q≤DA因此（（s{A，B}<$q0）<$q）<$（（s{B}<$q0）<$q）≤ D A.第一个析取命题由假设s{A，B}≤DA给出，并且DA是一个事实，因此在更新下是稳定的，即（DA<$q0）<$q≤DA。对于另一个析取命题，我们将证明s{B}<$q0≤QBD∈Ker（q），这使我们得到（s{B}<$q0）<$q=<$且<$Q ≤DA。要看到这一点，请使用加法来获得fB（s{B}<$q0）≤DB，通过等式（1），它可以显示fB（s{B}）<$fB（q0）≤DB。现在用它的值替换fB，得到（s{B}<$s{A，B}）<$q0≤DB，它等于A. Baltag等人/理论计算机科学电子笔记126（2005）2745（s{B}<$q0）<$（s{A，B}<$q0）≤D B.这个不等式成立，因为假设s{B}≤DB，且s{A，B}≤DB。因此，结果如下。注意，这个证明可以通过对脏孩子的数量的归纳密码攻击。两个代理A和B共享一个密钥，以便他们可以通过某个通信信道相互发送加密消息。通道是不安全的：某个局外人C可能会解释这些消息或阻止它们被传递（尽管他不能阅读它们，因为他没有钥匙）。假设加密方法是公开的，但密钥是秘密的。我们也知道A是唯一知道一个重要秘密的人，例如某个事实P是否成立。现在假设A发送一条加密消息给B，传达秘密。B收到信息后，相信它一定是真实的。现在A和B都确信他们分享了秘密，而C然而，假设C注意到特定加密方法的两个特征：加密的消息可以显示它是否包含秘密或它只是垃圾，其次，在不知道消息的密钥或内容的情况下，他可以将加密的消息修改为其相反的内容，即，如果它最初说P保持，现在它会说P不保持。现在局外人C会暗中拦截消息，适当地改变它并在不知道秘密的情况下将其发送给B。现在A和B错误地认为他们分享了秘密，而事实上B得到了错误的秘密！C成功地操纵了他们的信念。我们可以将这种情况编码到一个认知系统中。涉及的代理包括{A，B，C}。设s，t∈M满足s≤P和t#P.唯一知道P是否成立的主体是A，因此fA（s）=s，类似地fA（t）=t。另一方面，B和C不知道这一点，所以fB（s）=fC（s）=fB（t）=fC（t）=s<$t。调用P持有P的消息和它不持有P的消息。与密码图icak相对应的事件如下：α，消息P被拦截、修改并发送到B;β，消息P被拦截、修改并发送到B;αJ，消息P被拦截、修改并发送到B。A将信息P发送给B，βJ，其中A将信息P发送给B，最后是γ，对应于发送垃圾消息。因此{α，β，αJ，βJ，γ}<$Q和P，P<$∈Stab（Q）和P<$P<$=<$，P<$P<$=T.在α和β两种情况下，当年龄为P或P ′时，C是不确定的，因此f C（α）=f C（β）= α<$β。另一方面，代理人A确信他已经发送了一个消息（P持有或46A. Baltag等人/理论计算机科学电子笔记126（2005）27已经接收到完全相同的秘密，即fA（α）=αJ和fA（β）=βJ。然而，如果P是存在的，则B得到了B（α）=βJ的P ′ s，并且在f B（β）= αJ附近也是如此。此外f A（αJ）= f B（αJ）= αJ，f A（βJ）= f B（βJ）= βJ，f C（αJ）= f C（βJ）= αJ<$βJ <$γ。C也认为可能只发送了一条垃圾消息，这就是为什么他在αJ和βJ中看到Γ。如果发送了一条垃圾消息，A和B都确定它，f A（γ）= f B（γ）= γ，而C不确定它是垃圾消息还是P或P<$，因此fC（γ）=αJ <$βJ <$γ。 每个动作的核心是动作不能应用到的状态。因此，我们编码Ker（α）=Ker（αJ）=↓P<$且Ker（β）=Ker（βJ）=↓P。认知程序α β表达了在above场景中传递秘密P或P ′的行为。现在让我们用扩展程序αβ更新状态s，因为这等于s<$（α <$β）≤ QAQBP。（s<$α）<$（s<$β）≤QAQBP，且s≤P∈Ker（β），则得到s∈β=Ker，因此它表明，s<$α≤QAQBP，但通过附加fB（fA（s<$α））≤P.通过等式（1），我们得到fA（s<$α）≤fA（s）<$fA（α），fB的保序性将给出f B（f A（s<$α））≤f B（f A（s）<$f A（α））≤f B（f A（s））<$fB（f A（α））.现在看来，f B（f A（s））<$f B（f A（α））≤ P.用它的值替换f A，证明f B（s）<$f B（αJ）≤P，对f B做同样的事情 ， 得 到 （ s<$t ） <$αJ≤P ， 因 此 （ s<$αJ ） <$ （ t<$αJ ） ≤P 等 于（s<$αJ）≤Psincet≤P<$∈Ker（αJ）。 通过假设s≤P，我们可以得到s<$αJ≤P <$αJ，因为P是一个事实。
我的内容管理
展开
