理论计算机科学电子笔记125（2005）115-147www.elsevier.com/locate/entcs逻辑序贯呈现中证据搜索策略分析的若干问题塔季扬娜·卢托瓦茨1 詹姆斯·哈兰德2澳大利亚墨尔本皇家理工大学计算机科学与信息技术学院摘要许多证明搜索策略可以表示为对微积分规则的应用顺序的限制。这些策略的性质，然后显示的置换参数，如显示，一个给定的策略是完整的，通过转换一个任意的证明到一个服从的策略。这样的分析涉及到一些非常繁琐的证明操作，对人类来说可能是压倒性的。在本文中，我们调查的系统技术的发展，分析结石。我们展示了一个特定的推理规则如何导致对这些规则的置换属性的详细分析，我们还研究了如何检测这些规则产生的证明中的冗余。保留字： 证明搜索，一阶逻辑，线性逻辑，循环检测。1介绍已经有各种证明理论技术用于设计和分析定理证明和逻辑编程的证明搜索策略[2，1，6，7，10，15，20]。从这些不同的方法中可以得出的一个教训是，仅仅找到一个证明通常是不够的;大多数情况下，一旦找到一个证明，就需要从证明中提取信息，例如确定哪种策略或战术导致成功，识别常见的结构，1电子邮件：tlutovac@eunet.yu2 电子邮件地址：jah@cs.rmit.edu.au1571-0661 © 2005 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2005.01.002116T. Lutovac，J.Harland/Electronic Notes in Theoretical Computer Science 125（2005）115其他证明，找到所有证明或所有本质上不同的证明，生成答案替换，最小化证明的不必要部分，并识别未使用的公式。因此，证明搜索不仅仅是确定一个给定的命题是否可证明的问题，而是提供关于可证明性的适当的值得注意的是，上面的许多分析都是相当复杂的，涉及复杂的证明操作许多被限制到特定的逻辑或公式类。几乎所有这些都是为人类在纸上进行分析而设计的，其中许多已经成熟，可以自动化，被正式定义为精确的细节，但对人类来说有点压倒性。在本文中，我们专注于系统技术的发展，以提取有用的信息，分析的证据。特别是，我们提出了一个更精确的具体化的微积分推理规则，我们使用的一般化和自动化的具体化的置换过程。我们的工作是出于这样一个事实，即有一些感兴趣的推理规则，不能用现有的框架（[4，6，12]）进行分析下面的例子说明了这种情况► φ，r► φ，Γ，？δ虽然这是线性逻辑的收缩和收缩规则的组合，但在LM中可以找到类似的规则，LM是直觉逻辑的多结论系统（例如，参见[22]）。我们还提出了一个机制，区分必要的和不必要的公式在证明。该机制被纳入到搜索规则中，并且独立于所使用的搜索策略我们的分析结果可以通过以下方式实现和利用一个自动化的校对助手。 我们的工作是一个图书馆的自动支持工具提取有用的信息证明，以设计和分析证明搜索策略。本文的组织结构如下。在第2节中，我们讨论了使用置换作为策略分析工具和扩展现有框架的动机。在第3节中，我们给出了微积分规则的具体化在第5节中，我们解决了证明中的冗余问题，在第6节中，我们描述了消除冗余的算法最后，在第7节中，我们提出了我们的结论。T. Lutovac，J.Harland/Electronic Notes in Theoretical Computer Science 125（2005）115117.2排列和策略分析2.1动机给定证明的两个相邻推理规则的置换是颠倒它们在证明中的顺序，但不干扰证明的其余部分（推理的上下部分模某些证明分支的重复和重命名某些自由变量），因此我们得到与给定证明等价的..► a、c、d、r..► b， ⊗..► c，d，a，r，► c、d、a、b、r、c、d、a、b、r、c、d、r、c、d、r、c、d、r、d、e、c► c d，ab，r，..⇐⇒►c℘d,a⊗b,Γ,∆..排列分析的结果对证明搜索策略的设计有很强的指导作用。这种分析的许多例子可以在[2，1，6，7，10，15，20]中定义的证明搜索策略中找到。Lygon[23]和Forum[16]的比较给出了置换属性和语言执行模型之间关系的一个关键示例; Lygon基于搜索策略，即右手规则的某些置换将导致证明，而Forum基于搜索策略，即右手规则的任何置换都将导致证明。 请注意，该战略 所讨论的是由对推理规则可以应用的顺序的限制来定义的。对于这样的策略，置换性质可以用来表明，对于一组给定的推理规则，给定的搜索策略可以找到所有可能的证明，或者构造一个不能用给定策略证明的可证明的例子。满足推理规则顺序约束的策略可以进行进一步的分析，例如最小化证明中的分支数量，或者延迟某些选择，直到最佳信息量可用。在这里，我们给出了一个简要的概述，一些应用程序的排列分析特定的逻辑编程策略。生成遵循不同策略的等价证明对于一个逻辑程序，对于同一个目标有许多证明（因此有许多目标返回相同的答案替换多次），通常被认为是有点缺陷的。不同的证明通常只有在它们导致不同的答案时才被认为是有趣的118T. Lutovac，J.Harland/Electronic Notes in Theoretical Computer Science 125（2005）115例如，考虑直觉逻辑中的p（a），yq（y）→p（y），q（b）xp（x）所有的一致证明3可以分为两组，这取决于x的答案替换。每个类别的代表在下面（其他是变体，取决于规则的应用顺序→L，W L和W L）。p（b）Δp（b）Axq（b）<$q（b）Axp（a），p（b）<$p（b）wLp（a）Δp（a）Axp（a），q（b）→p（b），q（b）<$p（b）→Lp（a），<$yq（y）→p（y），q（b）<$p（b）<$Lp（a），<$yq（y）→p（y），q（b）<$$>xp（x）<$Rp（a），q（b）p（a）wLp（a），<$yq（y）→p（y），q（b）<$p（a）wLp（a），<$yq（y）→p（y），q（b）<$$>xp（x）<$R显然，找到所有导致不同答案的证明的问题与找到所有等价证明模推理置换的问题有一些重叠。由于来自相同等价类的证明会导致相同的答案，所以只生成其中一个就足够了，然后它将代表整个类。还要注意，一些非均匀排列也可能是有用的。在上面的第一个例子中，选择x←b的原因在应用规则时并不明显：..p（ a），y q（ y）→ p（ y），q（ b） p（ b）p（a），<$y q（y）→p（y），q（b）<$$>xp（x）<$R这个替换由公式yq（y）→p（y），q（b）产生。如果用户要求解释为什么生成该替换可以选择产生下面的排列，它不是统一的，但更直接地证明了替换的起源，如步骤（1）所示。q（b）q（b）Axp（b）p（b）Axp（a），p（b）p（b）wLp（a），p（b）xp（x）Rp（a），q（b）→p（b），q（b）xp（x） →L中文（简体）p（a），yq（y）→p（y），q（b）xp（x）[17 ]一个程序P的一致证明[17]是指目标导向的证明，在某种意义上，目标G是一致分解的，只基于它的结构，而不参考程序P，直到达到原子目标。只有当需要证明原子目标时，才需要查阅该程序。T. Lutovac，J.Harland/Electronic Notes in Theoretical Computer Science 125（2005）115119一种新的证明搜索策略给定逻辑片段的推理规则的排列属性对定义处理推理规则顺序的有效证明搜索策略有直接影响我们通过线性逻辑中所谓的“正常证明”[ 6 ]策略来解释这种影响事实上，我们通过线性逻辑的线性逻辑可以被看作是经典逻辑的一种细化从本质上讲，这些特征是由于删除了收缩和弱化的规则，并以受控的方式重新引入它们。因此，公式必须在线性证明中只使用一次。一元连接词？还有！允许受控应用弱化和收缩。两种不同的传统书写经典连词的规则，导致两种不同的连词和&，以及两种不同的析取词和。一个特定的搜索策略通常对在证明构造的下一个步骤中要分解的公式的选择施加约束。这些约束基于推理规则的可置换性，减少了证明构造过程中的一些不确定性来源。在自下而上的证明构造中（其中搜索从树的根开始），这种方法总是首先应用存在“保证”的规则，即如果该树是可证明的，则在该树中证明树例如，考虑一个函数A<$B，C <$D，Γ。在证明构造过程中，我们必须有一个完整的策略来选择下一个要分解的公式。这种选择对于自底向上的证明构造至关重要。在[6]中给出的置换结果的基础上，我们得到了下表，其中表中的情形（t1，t2）包含pi i，且存在推论t1在推论t2上向下置换的证明，且存在推论t1和t2不可置换的证明.120T. Lutovac，J.Harland/Electronic Notes in Theoretical Computer Science 125（2005）115t1t2℘∀⊗⊕∃w？℘ppNPppp∀ppppNPp⊗pppppp⊕pppppp∃ppppppw？pppppp表1.作为np对于情形（n，n）和p对于情形（n，n）的结果，对于任何可证明的n，nAnB，C n D，r，有一个证明，其中n在n规则之前应用（比n规则更接近根），但不一定是n在n之前应用的证明。例如，只有当在之前时，ab，ab的证明结构才能成功终止：► 一把战斧► b，bAx什么？► a，a，b，b，什么？？b，a► ab，a，b℘► a，a，b，℘℘► ba℘► b，ab℘► 一个一个的，一个一个的► 一个b，一个bb► 一个b，一个bb而在一个证明建设的martensa martensb，一个martensa？b、b、b、适用规则的顺序并不重要：► 一把战斧你是说一个小女孩？B？阿富汗b，b► 一个小女孩，一个小女孩，？b，b℘► 一个小女孩，一个小女孩？b，b► 一把战斧► 一个，一个，？B？你是说一个小女孩？bb，bAx► 一个小女孩，一个小女孩？b，b因此，在一个矩阵A B，C D，Γ的证明构造中，选择先分解C D有更大的成功机会，即成为导致证明的选择。一些策略我们在一个简化版本的“正常证明”策略上解释了这一点假设在我们所考虑的逻辑片断中，相继式是单侧的：r。Γ是目标公式的多重集，记为G并由以下语法定义：G：=A|GG|G G|GG|公司简介|公司简介|？GT. Lutovac，J.Harland/Electronic Notes in Theoretical Computer Science 125（2005）115121该策略由以下算法定义：如果πr包含一个形式为？F，则∑r是w的结论。规则else如果r包含一个最上面的连接词是或的公式则是引入该特定公式的规则的结论否则，r包含一个最上面的连接词是或或的公式，► Γ是引入该特定公式的规则的结论所概述的策略的完整性属性直接遵循相关线性逻辑片段的可置换性属性，如表1所示。任何来自这个逻辑片段的证明，都可以通过其推论的排列转化为服从给定策略的证明► 一把战斧► 一个，一个，？bw？► p（t），p（t）Axa，a► p（t），p（t）Ax℘► 一个，一个小女孩？B► p（t）a，yp（y），a► p（t）a，p（t），？ba► p（t）a，yp（y），？ba► x（p（x）b a<$−→► p（t）a，yp（y），？b，a，b，℘► p（t）a，yp（y），？ba► x（p（x）ba2.2现有框架置换分析的问题不是新的（[4，12，6]）。在本小节中，我们简要描述[6]中给出的术语和定义。一个推理的有效公式是存在于前提中而不存在于结论中的公式。一个推论的主要公式是存在于结论中的公式，而不是存在于前提中的公式。直观地，推理将活动公式转换为主公式。当要置换两个推论的顺序时，有必要检查上一个推论的主公式不是下一个推论的活动当这个性质发生时，这两个推论被称为处于置换位置（[6]的定义3.1）。我们将其称为GP置换位置。例如，考虑以下两个推论：qp，q，rEURRqp，q r<$p，q<$q<$r <$L<$p<$q <$q <$r <$L<$−→qp，q，r<$p，q<$q，r<$LEURRp，qp在这两种推论中，我们都有以下结论：122T. Lutovac，J.Harland/Electronic Notes in Theoretical Computer Science 125（2005）115规则主要公式活性配方L普什克p，q我ppEURR普什克p，q注意，在左边的子证明中，<$L和<$L不在置换位置，而<$L和<$R在置换位置。如以下示例所示，GP置换位置中的两个相邻规则不一定是可置换的。 在左手证明下面的规则？还有！在GP排列位置，但它们不是可排列的（LL规则！要求前提中的所有非活动公式都要被前缀！）：► AB？∆► A，？B，？你说呢？►！A，？B，？快！/›−→► AB？∆\/！定义2.1（[6]的定义3.2）（推理可置换性）. D.我一个推论I在一个给定证明J的推论J上是可置换i.它们满足以下条件：A.I和J处于排列位置;B1.J在I的适当前提下适用;..B2.J的结论-. D. D..I JC.子证明J和I有相同的结论，假设模复制其中一些和重命名某些自由变量。在其他情况下，我们说I在J上不可置换。2.3现有框架现有的置换分析技术已被应用于特殊的推理规则集。在许多情况下，排列不能用上述定义来解释。特别地，上面通过主动公式和主公式的概念对排列的分析有时太粗糙而不能捕捉排列何时是可能的。此外，现有的技术都是为人类在纸上分析而设计的，其中许多技术已经成熟，可以自动化。我们的目标是使DT. Lutovac，J.Harland/Electronic Notes in Theoretical Computer Science 125（2005）115123显式和系统的置换分析现有的微积分和推广和扩展现有的方法。首先，我们的论点是，需要一个更精炼的语法来定义微积分规则。有一些感兴趣的推理规则，不能用现有的框架进行分析。这里我们举几个例子。例2.2考虑来自LJ以及来自多重结论LJ（[5]）演算的以下规则：Γ，a，FGΓ，a，a→F<$G→L显然，我们有以下几点：主要公式活性配方上下文a→ FFΓ，G但是，关于公式a可以说些什么呢？根据现有的框架公式a是上下文公式。但是，它有一个特定的“角色”，不应该表征任何上下文公式。也就是说，在规则→L的前提中a的出现对于规则的应用是必要的，因此，a既不能被省略，也不能被另一个公式自由地替换。另一种可能性是将公式a在前提和结论中的出现分别解释为主动公式和主在这样的解释下，例如，在下面的推导中，在公式a→F1、a→F2中，接下来要分解的公式的选择将不是任意的。这意味着一些可能的排列不能被检测到：规则实例不在置换位置，因为a既是上→L推理的主公式，又是下→L推理的活动公式..Γ，a，F1， F2<$GΓ，a，a→F1， F2，G→LΓ，a，a→F1，a→F2，G →L....Γ，a，F1，F2<$GΓ，a，F1，a→F2，G→L-Γ，a，a→F1，a→F2，G→G →L..这背后的直觉是，一个公式的出现，其在前提中的存在对于规则的应用是必要的（但不是足够的），并且它被原封不动地复制到结论中，应该与规则的上下文、主动部分和主要部分分开考虑和处理。我们称这样的公式为拟活动公式。在下面的三重上下文124T. Lutovac，J.Harland/Electronic Notes in Theoretical Computer Science 125（2005）115.⎧⎪演算TC [11]用于具有强否定的直觉线性逻辑ILL[11]。例2.3考虑规则：α，γ; Γ;γ*δ，; Γ;，！∼α∧β►γα，γ; Γ;α，γα，γ; Γ;γ吸收2这里的规则*是一个混合的字符串，sim！W，还有！从TC移动规则ILL的微积分吸收2规则中的公式α不能被认为是上下文公式，因为它是规则应用所必需的。它也不能属于主动部分或主要部分，因为在下面的左推导中，排列位置（因此排列）将不会被识别：..，，电子邮件*..，*，I'm sorry. I'msorry.，吸收剂2例2.4现在考虑一个来自聚束蕴涵逻辑（BI）的微积分的例子让我们用以下规则代替左蕴涵− −L规则：Γ1<$φΓ2，aaJΓ1， Γ2，φ− aa−L（根据[19]的引理3.7.4，由这种替换产生的系统等价于原来的系统。只有在准主动项中分析−规则（在后继项中出现a是准主动公式）才能识别和判断以下排列：- 是 的Γ2，aα AxΓ3，aα Ax.r.⎪123.⎪'−L2，aaΓ1，Γ2，− aaAx'−LΓ3，aαAx⎪ Γ 1，Γ2，Γ3，− a，a − a a⎪⎨Γ1、Γ2、Γ3、−a、a−aa−L→或 ⎪⎪⎪⎪⎪⎪..Ax⎪Γ► ϕ Γ，Γ，a−a，aa'⎪1 2 3r1，r2，r3，例2.5现在考虑规则“”，它是"“和”“的组合。W规则，以及下面的排列：↔''⎪T. Lutovac，J.Harland/Electronic Notes in Theoretical Computer Science 125（2005）115125'''► φ、φ、ΓJ..►？A，？A、B、I..►？A，？A、B、ΓJj► φ，Γ，？δ你说呢？A，B，Γc？x？A，？J一个小女孩，℘你，？一图式规则j►？A B，Γ，？一Jc？►？A B，Γ，？一规则C？虽然它们在左子证明中不在置换位置，但它们是可置换的。这是因为公式？A是在同一时间的积极和主要公式的c？规则和一个主动公式的规则。J因此，在上面的左子证明中，规则消耗公式？的a是C？规则，因此存在于前提中J并且在规则的最终反转之后，可用于规则B1此外，一个非常这里的重要细节是公式的“恢复”？A通过主体部分的规则。所以，在反转之后，？A又可用于C？.现在让我们集中讨论上述的“解释”。考虑一下主公式的当前定义。考虑目前的分类，并注意下表所示规则的主要公式（e）之间的差异：逻辑规则活性主要上下文会Γ►∆你呢？A，P.E. W？► φ、φ、τ ℘► φ，Γ，？δA，ΓBAA， EURR，ΓA，B，A？一你说什么？δAB，A组 B组A组B组Γ， π会φ，φΓLJT多重-结论甲乙丙Γ会甲乙丙Γ，， Γ，会甲乙丙Γ， π注意，在规则W？的主要公式中， 有一些公式不是某些有效公式消失的结果（？A，？δ和δ分别）。我们的论点是，这种公式应区别于那些主要公式，是转换的结果，J126T. Lutovac，J.Harland/Electronic Notes in Theoretical Computer Science 125（2005）115某些活性配方的我们把这样的公式称为额外公式。一个额外的公式可以用在一个置换中（正如我们在上一个例子中看到的），以在下一个例子中，我们指出区分额外的和普通的主公式的另一个理由。也就是说，如果一个可接受的规则（结构规则或反演）是允许的，一些不可能的排列可以被例2.6再次考虑规则Γ►φ⊃ψEURRΓ，φ，φ从LM，一个多结论的直觉逻辑演算，在[22]中给出，以及下面左手子证明中的不可能置换。ABwRABR► A、B、CA、B、C<$C，A B<$L<$CAB，<$L~<$CAB，R显然，左边的规则不在排列位置（下面规则的有效公式是上面规则的主公式从额外公式的角度对这些情况进行分析得出以下结论：额外的额外费用 ={A，C}，Active，L ={C}，以及 Active<$LExtraR最后一个关系表明，不可能置换可以通过插入一个弱化规则来克服，该弱化规则的额外部分等于Active<$L，如上面右边的子证明所示还应该注意的是，一旦我们有了拟活动公式，这就允许我们对压缩法则给出更自然（也可以说更简单）的分析。因此，例如，对于压缩规则（下面以线性逻辑的形式呈现），我们将有如下的分类：∆|{z}►？F|{z}、、怎么样？F|{z}， Γ|{z}上下文主动公式准主动公式∆|{z}►？F|{z}， ΓC？|{z}准主动式因此，收缩定则现在有一个有效公式和一个准有效公式，但没有主公式。3顺序规则的一种细化结构我们的论点是，需要一个更精细的语法来描述微积分规则，因为它是由以下定义提出的（为了简单起见，我们假设单侧推理系统，即前件总是空的）：T. Lutovac，J.Harland/Electronic Notes in Theoretical Computer Science 125（2005）115127我定义3.1微积分推理规则的结构：• 规则I的主动公式是在结论中不存在的前提中的公式。• 一个推论I的准主动公式是一个公式事件，它在前提中的存在对于规则的应用是必要的（但不是充分的），并且它被原封不动地复制到规则的结论中。4• 规则I的主公式是一个结论的公式出现，该结论不存在于前提中，并且是规则I的某些活动公式消失的结果。• 在规则I的结论中出现的公式，如果不存在于前提中并且不是主公式，则称为额外公式。• 活动部分（用Ai表示）和准活动部分（用QAi表示）我我一个推论的第i个前提的I是（可能是空的）多集其有效和准有效公式，分别。推论I的主要部分（记为PI）和额外部分（记为EI）分别是其主要公式和额外公式的（可能是空的）多集。一个推论I的第i个前提的上下文（用上下文i表示）是它的活动和准活动部分的（可能是空的）多集补。上述定义通过下表中的线性逻辑示例进行说明：4我们对兑换规则作例外处理。然而，本文中使用的所有例子都是交换逻辑，因此我们可以将前件和后件视为多集，这就不需要这个规则了。128T. Lutovac，J.Harland/Electronic Notes in Theoretical Computer Science 125（2005）115的1一个2问答1问答2PE上下文1上下文2混合料► Γ， πA、⊗► AB，Γ，► A、Γ、B、Γ► A、B、Γ&A，► Γ，双截►Γ► 你，？fw？►？F，？F、Γ►？F，Γ c？？FΓ∆一BA组 B组Γ∆一BA BΓΓ一A.Γ∆？FΓ？FΓ请注意，我们可以根据两个规则的上下文如何组合来对二元规则进行分类。我们可以识别乘法规则，其中每个前提的上下文被不变地复制到结论中（规则强加法规则，其中每个前提和结论的上下文是相同的（规则）。注意，也有弱加法规则，其中前提和结论的上下文的某些部分是相同的。4精化结构如上所述，现有的置换分析技术没有覆盖所有可能的情况。此外，从自动化的角度来看，它们太隐式了所提出的对排序规则的更精细的规范允许发展与排序规则的置换分析相关的更精确和更一般的概念在本节的其余部分，我们将开发一个更详细的，广义的和面向自动化的置换过程规范。注4.1在下面对任何两个相邻推论I和J的考虑中，只要J是一个二元规则并直接跟随I，我们将考虑，除非另有说明，I在左（即第一）前提► A1，QA1，Context1，J.J J JT. Lutovac，J.Harland/Electronic Notes in Theoretical Computer Science 125（2005）115129我我我4.1置换位置定义4.2（弱置换位置和强置换位置）给定证明的两个推论I和J是：1. 在弱置换位置i中：i) J直接跟在I后面，ii) AJ， QA J背景I， QAI52. 在强置换位置i中：i) J直接跟在I后面，ii) 如果I是一元规则，AJ，QAJ 环境背景I、QAI 和（AJ\ContextI）AJ\ContextIEJ）其他k∈ {1，2} AJ， QAJ（AJ） /上下文k）（AJ\Contextk）我我我（EJ）值k= 1（相应地k= 2）对应于强左（相应地强右）置换位置。例如，在下面的第一个证明中，k和k的规则是在weakper ut t iposiny中的，例如Ak，QAk={ak，bk} kContextk，QAk={a，b，？c}和有效公式（公式a_c和b_c）属于不同的前提。在第二个证明中，由于双规则的有效公式与双规则属于同一个前提，因此双规则同时处于弱置换和强置换的位置。► a，a，► b，b►？c，b，b？w？► a，a，► b，b►？c，b，b？w？► 一个小女孩，一个小女孩，？c、b℘► b a，a b，？C弱烫发位置 为和► 一个小女孩，一个小女孩，？c、b℘► 你好c，a， b，a，强、弱置换位置 为和强置换位置更仔细地考虑了来自AJ，QAJ的公式在多集上下文I，QAI之间的分布。要求AJ，QAJ保持上下文k，QAk防止活动的情况我我和/或拟活动公式属于I的不同前提。这样的情况在弱置换位置是不能被5对于二元规则I，上下文I（相应地QAI）是上下文k（相应地QA I）的并集。QAk）对于每个前提k。130T. Lutovac，J.Harland/Electronic Notes in Theoretical Computer Science 125（2005）115i)（ii）（iii）► a，a，► b，b► a，a，► b，b，►？c，b，b？w？.► ab，a，b℘► ab弱（/弱）不可置换规则► 一个小女孩，一个小女孩，？c、b℘► 你好c，a， b，a，强（弱）可置换规则► A、B、C► A，B，CD℘► A、B、C、 D强（惠弱）置换规则条件（AJ/Context k）（AJ\Context k （二）确保情况--我我其中已经被下部J“消耗”（即，用作J的有效公式）的上部推理I通过额外的部分EJ再次恢复（以这种方式，在I和J的顺序最终颠倒之后，它（它们）仍然可用于I）。例如，考虑2.3小节的示例4中的置换：..►？A，？A、B、I►？A，B，Γc？..►？A，？A、B、Γ"►？A，？AB，Γ，？一"►？A B，Γ，？A=0c？►？A B，Γ，？一我们使用强置换位置的概念作为进一步检查给定规则的可置换性的前提我们可以说，强置换位置的概念致力于分析给定证明中可能的置换，即当我们有给定推理规则的具体实例时。回想一下，在一个给定的证明中，这样的排列和推理运动对于重新安排证明以满足特定的策略是必不可少的。它还帮助我们检测一个给定的证明，它只在推理规则的顺序不同。弱置换位置的概念适用于识别给定证明树中的不可置换规则（关于第3部分。下面的引理4.3），以及用于识别表示永远不能置换的规则的模式规则对。GP置换位置的条件对应于条件AJ，QAJ=ContextI。在没有准活动公式的情况下，GP置换位置对应于弱置换位置。像弱者GP置换位置更适合于在给定的模式规则集合的水平上的置换分析，而不是直接在给定的证明中分析可能的置换。我们可以在不同的置换之间建立以下依赖关系'T. Lutovac，J.Harland/Electronic Notes in Theoretical Computer Science 125（2005）115131操作位置：引理4.3对于给定证明的任意两个相邻的推理规则I和J：1. 强置换位置<$弱置换位置。2. 弱置换位置/强置换位置。3. I与 J不处于弱置换位置，且I在J上不可置换。4. GP置换位置<$弱置换位置，5. GP置换位置/GP强置换位置，6. 弱置换位置/弱GP置换位置，7. 若QAJ=QAI=θ则弱置换位置惠 GP置换位置，8. 强置换位置/强GP置换位置。证据 1., 4., 7.从定义2.1和4.2可以明显看出;2. 参见上述示例;3. 1的推论。;5. 见上文实施例i）;6.，8. 参见第2.3小节的示例4。Q因此，为了研究可能的排列，我们采用定义2.1，但条件为A。（“处于置换位置”）变为A s：I和J处于“强置换位置”。4.2自动化排列我们使用所提出的结构的特征化的演算规则的自动化导向的规范的置换过程。在这里，我们概述了一些结果，这些结果已在[13]中详细描述并正式证明。• 我们的框架特征集的推理规则，并打算尽可能一般。虽然很难有把握地说，这里描述的置换性质适用于任意逻辑片段，但我们相信，这里涵盖的推理规则类别包括所有著名的微积分和许多不太知名的微积分。• 在给定的证明中，推理规则的有效部分、准有效部分、主要部分和额外部分不因其上下排列而推理的上下文部分可以在推理置换期间改变。已详细说明上下文的适当变动132T. Lutovac，J.Harland/Electronic Notes in Theoretical Computer Science 125（2005）115J► A1、2• 置换的一些“先决条件”已被详细分析，并限制在推理规则的特定部分，最低限度的充分测试。• 给出并证明了置换规则的方法与其类属性质及证明特征之间的依赖关系。例如，强可加规则的向上排列需要一组特定条件。此外，置换结果的形式取决于所讨论的规则的一般属性，因此可以独立于直接置换来确定。我们将以一元规则I和强可加规则J为例解释我们的一些结果：► AI、 QAI、上下文I1 2JQAJ，Context JQAJ，Context JJCROP、 QA、上下文、 EI► P、QA1、QA2、上下文、EI我我我JJJJJ命题4.4在置换之后，置换规则的上下文I和J的变化如下：上下文I：=[上下文I，EJ]\A1，PJ，QA2J J上下文J：=上下文J\[PI，EI]，AI证据假设强左置换位置，置换之前和之后的子证明将分别为：► AI，QAI，上下文I► 质量保证一级| {z}、你好，我好|{z 个文件夹"""AJ，QAJ，q AIAJ、QAJ、CI|{z}""“”2 2► AJ，AJ，QAJ，QAJ，PI，EI，CI，qAI，Q AJ，QAJ，上下文J|{z}1J|{z}问答1|{z}上下文J1 2J► PJ、 QAJ、 QAJ、上下文J、EJ|{z}''AJ，eJ一T. Lutovac，J.Harland/Electronic Notes in Theoretical Computer Science 125（2005）115133：►AI，QAI，| {z}上下文I|{z 个文件夹"""AJ，QAJ，qAIAJ，QAJ，CI22|{z}A1、 QA1、AI、CI、q AI► AJ， QAJ，上下文JJ J1 2J► PJ，QAJ| {z}'，QAJ，qAI，AI，CI，EJ|{z}""QAJ， QAJAJ，eJ|{z}"2► AI， AJ， QAJ，q AI， QAJ， QAJ， CI， PJ，eJ|{z}|{z}QAI上下文I►PI，QAI、上下文I、EI、I证明是直接从一个简单的检查分布的公式在上述子证明。Q定理4.5一元规则I在强加法规则J上是可置换的，并且它们满足条件：i)I和J处于强置换位置;ii)PI=λ，EI=AI;iii) 多重集[ContextI，EJ]\A1，PJ，QA2可以（即满足所有J J第一条规则的范围证据 在命题4.4和定义2.1的基础上，下列等价关系是直接的：i)⇐⇒ As（三） 电子邮件 *由于J是一个强加法规则，因此两个表达式的上下文必须相同。因此，它必须是：上下文J=上下文J\[PI，EI]，AI表示 PI，EI=AI。AsPIAI=，其中PI=，EI=AI。根据命题4.4，在置换之后，J的左前提中的新上下文将是上下文J\[PI，EI]，AI。条件ii）PI=π，EI=AIgiveshefollowing owing：上下文J\[PI，EI]，AI=上下文J。 这确保了J在I的适当前提下的适用性（定义2.1的条件B1）。尾序列的相等性（即定义2.1的条件C）是平凡真的（并且可以直接检验QQ：134T. Lutovac，J.Harland/Electronic Notes in Theoretical Computer Science 125（2005）115α 我.例如，考虑来自线性逻辑的规则，这是一个强加法规则，以及cw规则，这是一个弱化和压缩的组合：你好，你好，你&好？F，？F、 联合国► φ，φ考虑以下转换：►？C，？C、ACW你说呢？CA？CB，？C，？C► A&B，？C，？C= 0►？F、Gulf，G你是谁？C，？CB，？C，？C► A&B，？C，？C&CW►？C，A，B，？C注意，满足定理4.5条件ii）的规则实例实际上是证明中的冗余步骤;换句话说，所有这些潜在的排列都可以从证明中完全删除。注意，在上面的例子中，cw规则是冗余的（在置换之前和之后）。因此，没有必要置换这些规则;我们可以简单地消除cw实例。如果我们采用“在任何其他证明转换之前消除给定证明中的冗余步骤”的策略永远不可能将一元规则之一置换为强可加规则。换句话说，当找到这样的组合时，我们应该消除冗余推理，而不是置换它。正如[6]的第4.2节所指出的，有一些不可置换性可以通过考虑特殊情况来克服。一个这样的情况是当一元规则不仅在低级规则的左前提之上，而且在它们两者之上。这个想法是注意左边所示的子证明（如果它存在），并（尝试）将其转换为右边的子证明：...βγ1γ2I... αβ。γJδJ<$−→ δI我们称这种排列为特殊排列。作为例子，考虑以下来自线性逻辑的特殊置换。..► A，C，D..► B，C，D..► A、C、D..► B、C、D&► A、C和D► B、C和D&► A、B、C、DAB，C
我的内容管理
展开
