开放与封闭问题的动态逻辑分析

可在www.sciencedirect.com在线获取理论计算机科学电子笔记278（2011）261-274www.elsevier.com/locate/entcs决策中的开放式和封闭式问题Zuojun Xiong熊左军1，2西南大学中国重庆杰里米·塞利格曼3新西兰奥克兰大学哲学系摘要通过提出问题，代理人可以修改做出决策的选项范围。[12]引入了一种逻辑来推理提问在决策过程中的作用。基本逻辑是一个模态逻辑与运营商D解释为：D i后，任何理性的选择，代理人可以作出，holds。在此之上，我们提出了一个分析的问题，作为动态运营商[？Q]和[！这以各种方式改变了代理人可用的选项范围。在本文中，我们提供了一个完整的公理化的动态逻辑，并扩展到复杂的问题的分析特定我们的方法的特点是，它不假设代理的偏好是可传递的。本文从偏好序的不变性出发，给出了偏好序传递性的一个刻画提出问题。这是适用于一个臭名昭著的情况下及物性失败：孔多塞的投票悖论。关键词：理性选择，偏好，封闭与开放问题，混合逻辑，偏好传递性，孔多塞，动态逻辑1决策问题做决定就是在许多选择中作出选择。可供选择的范围在某种程度上取决于作出决定的代理人无法控制的背景因素。但它也部分取决于代理人1作者得到国家社会科学基金（09CZX033）资助，国家教育部人文社会科学基金（08JC 72040002）和西南大学基础研究基金（SWU 0909512）。2电子邮件：xiongzuojun@gmail.com3电子邮件：j.m. gmail.com1571-0661 © 2011 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2011.10.020262Z. Xiong，J.Seligman/Electronic Notes in Theoretical Computer Science 278（2011）261状态特别是，代理人必须知道哪些选项是提供给她。在本文中，我们将集中在交换决策，其中代理人已经作出了一个特定的决定，然后考虑改变她的想法作为新的信息的结果。新的信息将来自于对可用的替代品提出某些问题例如，假设你每天沿着河的南岸步行上班。然而今天，你想知道是否有更好的路可走，并考虑是否过桥并沿着北侧走会更好。换句话说，你问一个问题，是否采取河的北岸或南岸有任何差异。这种“开放式”问题在决策中很常见。一个人使用这样的问题来扩大选择的空间，从而增加达成最佳决策的机会。当然，权衡的结果是，考虑更多的选择会带来时间成本、认知处理成本和其他与信息收集相关的成本。(One可能需要买一张地图！）在[12]中，我们介绍了一种逻辑，用于推理提问在决策过程中的作用。这个逻辑是由下面的例子的分析所激发的，我们在这里重复这个例子，以解释我们对这个逻辑的应用。爱丽丝正在考虑搬家。她对她的房子离公共汽车站很远这一事实感到不满。她在房源中搜索位置更好的房子，看到了几个她更喜欢的房子。她和她的好朋友贝蒂一起去拜访他们中的一个。当贝蒂看到房子时，她说：“花园怎么样？”这不是爱丽丝以前考虑过的问题。她自己的房子没有一个，但她是在贝蒂的敦促下回到上市，并检查出有花园的房子。最后，她找到了房子，搬家了。它有一个漂亮的大花园。但几个月后，她访问钱德拉，贝蒂的朋友谁住在一个混凝土房子。爱丽丝觉得它很迷人。她的新房子是木结构的，就像她的老房子和她住过的每一栋房子一样。那天晚上，她回到了列表。爱丽丝对她所看的房子印象深刻。为什么她从来没有想到过房子是用木头以外的任何东西建造的？下个月，她已经搬进了她的新石膏房子，看起来非常现代和时尚。但过了一会儿，她碰巧走过她的老房子-第一个。被它古朴的魅力和破旧的木制品所吸引这个故事说明了实际决策过程是如何被人们提出的问题所引导的。爱丽丝可能会问一些非常直接的问题，比如“它有屋顶吗？”还有“我能下命令吗”但往往是一些开放式的问题，如“花园怎么样？”这帮助她扩大了可供选择的范围，我们将重点关注这些问题。最终，很明显，爱丽丝的决策过程中出现了明显的问题。在搜索的兴奋中，有些东西不见了。一个简单的答案是，爱丽丝的偏好显然是不可传递的。因此，她在某种意义上是非理性的。但她的每一个决定显然都是合理的，这表明还有更多的话要说。一个类似的例子，没有考虑在[12]，涉及多数表决，Z. Xiong，J.Seligman/Electronic Notes in Theoretical Computer Science 278（2011）261263众所周知，它通常不能保持偏好的传递性。这可能会产生一些奇怪的结果。考虑下面的例子。三个朋友晚上一起出去，需要挑选一个指定的司机。起初他们以为安德鲁会开车，但他反对，并建议巴里代替。他们同意安德鲁开车，除非大多数人更喜欢巴里开车。但他们投票让巴里开车。这一次巴里反对，因为查尔斯甚至没有被考虑。他们决定让巴里开车，除非大多数人都希望查尔斯开车，在这种情况下，查尔斯被选为司机。这种情况发生了，查尔斯被选中，尽管大多数人更喜欢安德鲁（最初的选择）作为指定的司机。这是孔多塞的一个版本。4.假设没有人愿意让自己当司机，那么这三个朋友的偏好一定如下：A BB C一个C安德鲁是的是的是的A B C巴里没有是的没有B C AC哈尔斯是的没有没有cab公司大多数是的是的没有命题变量A、B和C分别代表“Andrew drives”、“Barry drives”和“Charles drives”。大多数人的偏好顺序是A B C A，这显然是不传递的。 我们可以用下面的方式来建模在图1中朋友们从一个司机的选择转移到下一个，一0B12CFig. 1. 孔多塞车手有什么问题吗起初，安德鲁被认为是司机，然后他问“巴里呢？”此时，分隔A和B的虚线消失，以显示B为首选驱动程序。他们问是安德鲁还是巴里，[4]这就是孔多塞侯爵在18世纪后期观察到的多数表决问题，它表明，在一个有两个以上选择的问题上，三个或更多的代理人的投票是不一定的。来产生一个可传递的偏好顺序。264Z. Xiong，J.Seligman/Electronic Notes in Theoretical Computer Science 278（2011）261确定是巴里这个决定重新建立了我们在A和B之间的界限。但后来巴里问“查尔斯怎么办？”B和C之间的线消失了，结果是查尔斯被选中了。我们将描述所提问题所带来的模型2优先选择的动态逻辑：原子事例[12]介绍了一种逻辑推理决策时，代理人我们假设，每一个决策都是在这样一个背景下做出的，在这个背景下，一些因素可以变化，而另一些因素保持不变。换句话说，我们遵循冯·赖特[11]和其他人（特别是吉拉德，在[6]中）基于其他条件不变的偏好进行判断。 最近关于逻辑的工作其他条件不变的运营商（[9]和[7]）提供了一种技术方法，在[12]中进行了调整，并进行了一些修改。具体地说，我们取一个原子的其他条件不变的选择模型M= F，V，P，它由一个选择模型F，V和一组命题变量P组成，我们把命题变量解释为在其他条件不变的情况下保持不变的原子事实。这意味着，代理人可用的选择范围包括当前情况的等价类中的那些选择，其中u<$vi <$p∈P，u∈V（p）i <$v∈V（p）我们要求P是有限的，因此只有有限个命题变量被允许变化。这些结构由语言我 |p|¬|∧|Q|D|U其中i∈NOM，一组名词，p∈Prop，一组命题变量，Q，D和U是一元模态算子。语言中包含了名词，这样我们就可以推理出特定主体对特定状态/实体的偏好。我们将<$i=<$Q<$，<$D<$i=<$D <$和E=<$U<$代入，得到相应的存在模态.我们的语言的语义条件必须受到限制，以遵守对“”的限制Z. Xiong，J.Seligman/Electronic Notes in Theoretical Computer Science 278（2011）261265M，w| = p我的w∈V（p）M，w |= I我的w∈V（i）M，w|=我的M，w|=M，w |=（）我的M，w |= m和M，w |=M，w |= Q我的M，v |=对于每个v w，使得w ≤ vM，w| = U我的M，v| =每个vw的M，w| = D我的M，v |=对于每个v w，使得v也≤-极大说一个状态u是至少和u（u≤v）一样好的u的n-等价类也不比u（v≤u）好。这是我们对在其他条件不变的情况下选择是理性的条件的分析。[5]特别要注意，我们不要求≤关系是传递的。“普遍”情态U在其他条件不变的情况下也是受限制的下面的公理化在[12]中被证明是完备的定理2.1在其他条件不变的原子类上有效的公式集偏好模型由基本混合逻辑H公理化，泛等价i→Eii→UEiEEi →Ei重显性i→重显性i内含物αi→Ei优先选择参与者（iQi）我们称之为优先选择的逻辑PC。在此基础上，我们添加了一些动态操作符。我们模拟了问一个开放性问题作为将模型M=<$F，V，P<$F改变为模型[？p]M=<$F，V，P\ {p}<$其中p已经从命题变量集合中减去，当我们搜索替代方案时，命题变量必须保持不变。或者，换句话说，代理人可以选择的替代方案的范围已经扩大到包括那些与p值不同的替代方案。更一般地，对于命题变量的有限集合Q，我们定义[？Q]M=F，V，P\Q对模型的这种操作由操作符[？Q）与M，w|=[？问：你是谁？Q] M，w|=这使我们能够对爱丽丝的决策进行以下分析请考虑图2所示的Alice偏好的表示我们使用所示的框架来模拟MAlice[12]第12话，这是一个很好的解释。266Z. Xiong，J.Seligman/Electronic Notes in Theoretical Computer Science 278（2011）261不0p321G86547图二. Alice的故事F，每个房子都有名词。t，g，p是命题变量。最初，在爱丽丝考虑移动之前，所有这些都是固定的，所以我们取P=Prop。当爱丽丝不喜欢住在离公共汽车站很远的地方时，她会搜索房子，并考虑1、 2和3。这些选项是可用的，因为她已经问了这个问题[？p]。她拒绝1，我们得到M，0 |= [？p]D（23）她决定搬到2号房子，但她的朋友贝蒂问：[？g]。然后房屋的列表被扩大，并且由于M，2 |= [？[？][？#36825;，她搬到了6号楼。当我们可以更多地讨论接下来发生的事情时，我们3条件相同逻辑的一个可解释的片断当前的方法与[9]和[7]的Ceteris Paribus逻辑之间存在系统的关系，该逻辑使用由下式定义的语言Lcp：p|¬|∧|⟨ Γ⟩其中，Γ是L_cp的一组公式。[6]在偏好模型M中解释时，“r”的语义条件是M，w|= riM，v|对于所有v ≥ w且对于所有<$∈ Γ，M，w| = i M，v|=公理化的有效性的LCP集仍然是一个开放的问题，但它是解决的情况下，该片段的详细信息在[7]中给出为了达到我们的目的，只要注意到，如果每个模态算子都是形式为的，那么就足以说明，如果每个模态算子都是形式为的，其中，Γ是命题变量的有限集合我们称之为有限公式。但是现在如果我们考虑原子的其他条件相同的偏好模型MJ=<$F，V，P<$，那么[6]这个循环定义可以用transfinite递归定义来理顺。Lcp是一个合适的类，但这在实践中不会造成问题详情见[7]Z. Xiong，J.Seligman/Electronic Notes in Theoretical Computer Science 278（2011）261267MJ，w| = [？[Q] Kazakhstan，w|=P\Q因为Q是有限的，P是有限的，所以P\Q也是有限的。两种语言之间的这种联系激发了我们对动态操作符的以下公理的考虑：问题分布图[？Q]p参与► [？Q]<$Particip<$[？Q]► [？Q]（参与者）Participate（[？Q]你好[？Q]）► [？Q1][？Q2]参与[？Q1[Q2]从左到右应用这些公理来将问题运算符推到最小范围，很容易看出我们语言的C-片段在逻辑上等价于Lcp的有限片段。[7]这足以建立这个片段的公理化。为了在这个方向上更进一步，我们将不得不将可伸缩Lcp扩展到多模态设置，这超出了本文的范围。相反，我们将直接使用用于可伸缩Lcp的方法来为原子的其他条件相同的偏好逻辑制定公理。主要思想是将公式中出现的所有问题运算符减少为单个问题运算符的多次出现。这可以使用以下有效的等效项来完成：问题扩展► [？Q]参与者（p[？p，Q]（p））（<$p[？p，Q]（<$p））► [？Q]EParticipate（p[？p，Q]E（p））（<$p[？p，Q]E（<$p））► [？Q]DParticipate（p[？p，Q]D（p））<$（<$p<$[？p，Q]D（<$p））现在对于任何公式，令Q={Q| [怎么样？Q]发生在换句话说，Q是在Q中被质疑的所有命题变量的集合。通过从左到右重复应用问题分布和问题扩展，我们可以计算逻辑等价的公式J，其中唯一出现的问题运算符是[？Q]。但是现在我们可以应用从右到左的问题分布来找到一个逻辑公式[？Q]JJ，其中JJ不包含疑问运算符。但F，V，P，w |= [？QJi F ，V，P\Q，w| = JJ这就提出了问题的最终推理规则：[7]这些公理使我们能够证明，任何一个公式都等价于一个公式，在这个公式中，问题的唯一出现是紧挨着模态算子的前面，而这些模态算子可以转化为Lcp算子。当一个人的时候，他是一个人的时候。普罗帕酮相当于。268Z. Xiong，J.Seligman/Electronic Notes in Theoretical Computer Science 278（2011）261问题概括如果然后[？Q]以上所述是合理的。如果是这样的话，那么，如果是这样的话，那么，如果是这样的话。Q]JJ，JJ也是，它不包含问题运算符，因此满足定理2.1。这建立定理3.1用PC加问题分布公理化了带有原子问题算子的Ceteris Paribus优先逻辑语言的有效公式集。问题扩展和问题概括。把这个逻辑称为QPC。这就是任意（原子）其他条件不变的框架的逻辑，但看看传递框架如何公理化也很有趣。当然，众所周知，这可以用i→i来完成。 但是，更有趣的是，它也可以通过以下原则来实现问题排列[？p][？q]您是否参与？q][？[p]i这就是说，在一系列选择中提问的顺序是无关紧要的。我们的Alice和Condorcet驱动程序的示例都依赖于此无效，并且我们已经看到了它们如何因此而支持定理3.2问题置换在其他条件不变的选择框架上有效，且它是传递的。证据 假设[？p][？q]您是否参与？q][？p]i在F上有效，F是不可传递的。则F必须包含三个状态1， 2和3，使得1≤ 2≤ 3但1/≤ 3。然后我们可以得到一个反例，M=F，Prop，V通过指定V如下所示：p，q qi1 2 3那么M，1 |=[？p][？q]i，但M，1 |=[？q][？[p]p.相反，假设矛盾，[？p][？q]您是否参与？q][？[p]i在传递框架F上是无效的。在不失一般性的情况下，假设存在一个模型，M=<$F，V，{p，q}<$，使得M，w| = [？p][？q]m和M，w| = [？q][？[p]p.所以F，V，{q}|=[？q]<$i，所以有一个v<${q}w，使得w≤v，且<$F，V，{q}<$，v| = [？[q]a. 所以这里又有一个u v使得v ≤ u，并且F，V，，u |= i.根据传递性，w≤u。 如我们所知，w u和。 所以我来了。 然后我们有F，V，W，|=i和F，V，{p}，w| = [？[p]p.从w≤ w，且w <$w，<$F，V，{p}<$，w |=[？p]i成立，所以M，w |=[？q][？[p]这与我们的假设相矛盾。Q4开放式、封闭式和复合式问题我们已经解释了这个问题作为一个开放性问题，不要求回答，但进一步调查的情况下，p可能是或可能不是这种情况。但是，人们也可以把这个问题解释为一个封闭的方式，作为一个答案的请求。通过找出p是否是这种情况来实现闭合，然后Z. Xiong，J.Seligman/Electronic Notes in Theoretical Computer Science 278（2011）261269坚持答案。我们可以很容易地添加一个操作[！p]（更一般地说[！我们的语言有这样的效果。设Lc是L的扩展以包含闭问题算子。给定一个模型M=<$F，V，P<$，设[！Q]M=F，V，P Q定义8M，u|=[！Q][！Q] M，u |=封闭式问题使我们能够给出一个实际决策的模型。如果我们询问Q并做出决定性的选择，[？]Q]通常是我们通过以下方式来代表这一点：[？QD！Q]问题的结束标志着决策过程的结束。这一点并不比那些决定涉及明确行动的例子更清楚，比如搬家。图9爱丽丝决定搬到一个有花园的房子里，然后实际上移动了，表示为：[？g]D[！g]在这之后，她不再考虑没有花园的房子。 如果爱丽丝保持花园问题开放，她就不会第二次搬家（搬到房子8），这不是一个稳定的选择。即男，0 |= [？p]D[？g]！g][？t]D 8但不是M，0 |=[？p]D[？g]D[？t]D 8最后，我们可以模拟爱丽丝故事的最后一部分即男，0 |=[？p]D[？g]！g][？t][D[？g][！p]D 0至于开放式问题，封闭式问题满足分布原则，允许我们找到任何公式的逻辑等价物，其中[!Q]是紧接在模态运算符之前的：10已关闭的问题分配表[！Q]p参与► [！Q]<$Particip<$[！Q]► [！Q]（）Participate（[！Q]你好！Q]）► [！问1][！Q2] 参与！Q1[Q2]► [！Q1][？Q2]参与[？问二\问一][！Q1\Q2]从这一点出发，封闭问题更容易公理化开放问题，因为它们满足以下归约公理，允许我们从公式中删除所有封闭问题：[8]请注意，如果P是有限的，Q也是有限的，那么P≠Q也是有限的。[9]下面对爱丽丝故事的延续的分析10最后一个是有效的，因为（P<$Q1）\Q2=（P\（Q2\Q1））<$（Q1\Q2）。270Z. Xiong，J.Seligman/Electronic Notes in Theoretical Computer Science 278（2011）261关闭问题缩减► [！p，Q] Participate（p！Q]（p））（<$p[！Q]（<$p））► [！p，Q]EParticipate（p[！Q]E（p））（<$p[！Q]E（<$p））► [！p，Q]DParticipate（p[！Q]D（p））（<$p[！Q]D（<$p））与Ceteris Paribus逻辑的相似性继续存在，因为我们逻辑的闭问题片段等价于Lcp的有限片段，Lcp在[9]中以类似的方式公理化。定理4.1 aQPC连同闭问题分布公理和闭问题归约公理是L c的有效公式集的完备公理化。将我们的语言扩展到复合问题有点困难。 问一个开放性的问题当P是保持不变的变量集时，有一个清晰的解释，正如我们所看到的。它简单地意味着，我们允许p变化，同时保持P中的其他一切不变。复合开放性问题更像是一个问题。如果我们问然后，我们希望允许（p<$q）的真值变化，同时保持其他一切不变。但在这种情况下，很难理解“其他一切”的含义。p可以保持不变，而（p<$q）变化，q也可以，但如果两者都保持不变，（p<$q）也将保持不变。对这个问题的最初反应是假设允许（p<$q）变化就是允许p和q都变化。在这种情况下，[？（pq）]将等同于[？p，q]。更一般地说，我们可以说，允许变化（对于某些纯布尔公式）就是允许Q变化，其中Q是包含在中的命题变量的集合。这不是一个糟糕的解决方案，但它有一些局限性。 首先以出现在循环中的命题变量的集合太粗糙了。例如，（（pq））的真值根本不受q的真值的影响，并且所以允许它变化只需要允许p变化。其次，有一个非平凡的互动与封闭的问题。假设我们问封闭式问题[！（pq）]。结果应该是（p<$q）的真值保持不变。一个与上面的论点类似的论点建议采取[！（pq）] = [！p，q]。但是现在如果我们问一个开放的问题[？（p<$q）]我们希望允许（p<$q）的真值变化，同时保持（p<$q）的真值不变。 但如果[？（p<$q）] = [？p，q]和[！（pq）]=[！p，q]则[！（pq）][？（pq）]=[！p，q][？p，q]=[？p，q]，因此我们失去了（p<$q）保持不变的要求所以，让我们首先将我们的语言扩展到LQ语言：我 |p|¬|∧|Q|U|[？Q] |[！Q]其中Q是L的有限子集。[11]一个其他条件相同的问题模型M= F，V，Γ，由一个偏好模型F，V，和一个L-公式集Γ组成我们定义了11个包含关于问题的陈述的问题超出了本文的范围Z. Xiong，J.Seligman/Electronic Notes in Theoretical Computer Science 278（2011）261271⊆其他条件不变的关系，以同样的方式在Lcp，即u∈ vi ∈ r，M，u |= i M，v |=也就是说，状态u和v是等价的，在其他条件不变的情况下，它们对Γ中的所有公式都为了更进一步，我们需要更多地说明保持某些公式不变如何影响其他公式的值 12给定有限个公式{101，...，是形式为±<$1<$.的公式。其中，要么是i要么是i 一组公式Γ确定公式 i13Γ确定公式的集合Q，并且它确定Q中的每个公式。引理4.2如果Γ决定Q，则在任何模型M和状态u，v中，如果u∈v，则对所有的u∈Q，M，u| = i M，v |=证据 设u∈M 且Γ决定Q。然后有一个有限的集合{101，.，确定Q的{\displaystyle {\fn方正黑体简体\fs18\b1\bord1\shad1\3cH2F2F2F}{\fnarialblack\fs12\bord1\shad1\4cH2F2F}{\fnarialblack\fs12\bord1\shad1\3cH2F2F}{\fnarialblack\fs12\bord1\shad1\4cH2F2F}{\fnarialblack\fs12\bord1\shad1\3cH2F2F}{\fnarialblack\fs12\bord1\shad1\4cH2F2F}{\fnarialblack\fs12\bord1\shad1\3cH2F2F2F}{\fnarialblack\fs12\bord1\shad1\4cH2F2F}{\fnarial bl 如此定义σ=（±0.1）±其中，如果M，u，|= i且是<$1，如果M，u| = 1000。 那么M，u| = σ。 现在设Q∈Q。则（σ→Q）或（σ→<$Q）是PC的定理。在不失一般性的情况下，假设（σ→Q）是定理。 那么M，u |= 0。 但u ∈ v且每个i∈ Γ，所以M，u| = ii M，v|所以M，v| = σ和M，v |= 0。Q例如，集合{p，q}清楚地确定（p<$q），但{（p<$q），p}不确定。要看到这一点，（p<$q）显然不是由{（p<$q）}或{p}确定的，对于{（p<$q），p}，注意<$（p<$q）<$$>p既不意味着（p<$q）也不意味着<$（p<$q）。现在，假设子集ΓJ Γ是Q-释放i，则ΓJ是Γ的最大非Q-确定子集，即，ΓJ不确定Q，并且对于任何也不确定Q的ΓJJ，如果ΓJ<$ Γjj<$ Γ，则ΓJJ = ΓJ。如果P是出现在某个布尔公式中的命题变量的集合，则Prop\P不确定。但这可能不会让你释放压力。例如，如果是我们之前考虑的公式（（pq）），那么Prop\{p，q}不是释放的，因为更大的集合Prop\ {p}也不能确定。此 外 ， 公 式 的 集 合 T 可 以 具 有 多 于 一 个 的 解 压 缩 子 集 。 例 如 ， 取 r={（p<$q），p，q}和r=（p<$q）。则{（p<$q），p}和{（p<$q），q}是Γ的释放子集Q-释放的概念正是我们定义开放式复合问句语义所需要的。对于这样的问题，[？Q]定义了模型M= F，V，Γj和M= F，V，Γj之间的以下M[？Q]MJ i <$rJ是r（inM）的Q-释放子集272Z. Xiong，J.Seligman/Electronic Notes in Theoretical Computer Science 278（2011）261PC[12]这个问题类似于信念修正中的收缩问题[13]当然，人们可以用更强的 逻辑来扩展决定的概念，但这对于目前的目的是足够的。Z. Xiong，J.Seligman/Electronic Notes in Theoretical Computer Science 278（2011）261273然后，我们使用模型之间的这种关系，给出的语义[？Q]。M，u|=[？Q]iM J，u|对于每个M [？Q]MJ新语言是旧语言在以下意义上的保守扩展：引理4.3如果M=<$F，V，P<$是一个原子的等条件问题偏好模型，那么它也是一个等条件问题模型，并且对于L的任何公式

下载后可阅读完整内容，剩余1页未读，立即下载