没有合适的资源?快使用搜索试试~ 我知道了~
Hiproofs:层次化的证明树构建与可视化
理论计算机科学电子笔记155(2006)341-359www.elsevier.com/locate/entcsHiproofs:一种层次化的证明树Ewen Denneya,1,2,John Powerb,1,2和Konstantinos Tourlasb,1,2aRIACS,NASA艾姆斯研究中心,加利福尼亚州莫雷塞特场,94035,美国爱丁堡大学计算机科学基础实验室,爱丁堡国王大厦,爱丁堡EH9 3JZ,苏格兰摘要出于对定理证明的关注,我们将证明树的概念推广到层次证明树。 层次树通过向节点集合添加偏序结构来扩展普通树:这允许我们将节点可视化为平面中的矩形,而不是一个点,让我们使用包含关系来表示树所给出的结构之外的结构。 层次证明树,或简称hiproof,是一个层次树,节点标记为通过战术。我们通过参考战术定理证明中的战术行为来激发我们定义的细节。 我们构造了普通的证明树, 一个分层证明树作为左伴随。然后,我们分析的概念证明细化的层次结构,我们给出了一个特征的hiproofs,更直接地适合于实现。关键词:证明树,层次证明树,骨架,伴随,精化,战术定理证明1介绍考虑图1(a)所示的归纳证明:节点由策略标识符标记,一个节点包含在另一个节点中表示子策略关系,箭头表示顺序组合。该图如下所示:证明包括调用归纳策略,1这项工作得到了EPSRC赠款的支持。GR/M45030(Ewen Denney)GR/N64571/01和GR/586372/01(John Power)和GR/N12480(Konstantinos Tourlas)。第一作者在爱丁堡时做了大部分工作2电 子 邮 件 地 址 : edenney@email.arc.nasa.gov 、 ajp@inf.ed.ac.uk 、kosutamu@yahoo.co.uk1571-0661 © 2006 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2005.11.063342E. Denney等人理论计算机科学电子笔记155(2006)341感应步基地Ind-RuleT1DPWFT2重写羟脯氨酸正常化拉紧(a)(b)第(1)款Fig. 1. 两个层次证明入职。这包括应用归纳规则Ind-Rule,然后生成两个子目标。第一个子目标由基本战术处理,第二个子目标由步骤战术处理。反过来,Step被定义为首先应用Rewrite策略,然后是Replace-Hyp策略,Base,Rewrite和Replace-Hyp被视为原语。与通常的归纳证明相反,重点是策略,而不是目标和证明步骤。对于结构上更复杂的证明,考虑图1(b)。在最抽象的层次上,证明包括应用T1,然后是DP。策略T1首先应用T2,生成两个子目标,其中第一个由WF处理。第二个由DP处理,它应用Normalise然后Taut。这些例子反映了,虽然非常抽象,战术的层次结构,出现在证明助手,如[5,8,10]。在本文中,我们采取了第一个抽象的步骤来发展这种层次结构的定义和数学理论,最终目标是开发接口,这两种接口都是用于单个定理证明器的图形接口,以及基于公共策略结构(通常独立于底层逻辑)的定理证明器之间的接口。从图1(a)和1(b)中抽象出来的中心定义是分层证明树或hiproof。我们在第2节中分析了hiproofs公理的适当选择,在第3节中分析了hiproofs与其基础普通证明之间的关系,在第4节中分析了hiproofs的精化概念。最后,我们在第5节中用更易于实现的术语进行了证明。与现代计算机中通常实现的分层结构相比,E. Denney等人理论计算机科学电子笔记155(2006)341343对于定理证明者来说,我们的工作是抽象的第一步:hiproofs抽象了许多具体的和可操作的特征。关键的抽象如下:• 我们只为战术建模,不为目标建模层次结构本身独立于底层逻辑。此外,战术本身支持丰富的结构,我们寻求最简单的可能框架来研究它。• 我们把一个策略看作是一个黑盒子,除了其他策略定义它的记录之外,没有给出它的实现细节。我们把推理规则和公理看作是原始的策略。• 我们只模拟战术的静态结构,而不是动态结构。我们的图只表示导致证明的策略应用的序列,而不是策略定义本身或关于证明搜索的信息• 我们考虑树结构而不是DAG。实现通常使用dag,但形式逻辑通常不使用。我们的目标是研究证明的结构,而不是特定的实现,使我们能够独立于基本证明和实现技术的特定概念。中心结果的文件,在第3节,特点的骨架,或潜在的普通证明,一个hiproof,作为一个左伴随列入普通证明hiproof。人们希望通过骨架函子将普通证明的构造提升到hiproofs的构造。 因此,第4节和第5节的中心结果(分别用于细化和实现)表明,相关的结构尊重骨架。在逻辑学中使用图表并不新鲜[2]。Fitch风格的盒装自然演绎是在给定证明上绘制盒子的一种方法,与这里的情况形成对比。但是沿着我们的路线的分层证明出现在证明规划中[4]。例如,在[11]中出现了两个不同的表示。我们对证明的代数特征的分析知之甚少,但是参见[9],它研究了表示语言的动态:我们在这里只讨论静态,但是为了研究动态,需要这样的静态更一般地说,任何系统(如Coq,HOL和PVS)中的战术可以从其他战术中定义,自然会导致这里的分层证明。特别是,我们形式化的层次结构概念与Lambda Clam家族的证明规划器[10]相关,尽管Lambda Clam还不允许战术像我们在图1(b)中所做的那样留下开放目标。Tecton系统[8]也支持层次证明:它的层次是“两级”,而我们的允许任意嵌套。在Omega [3]和其他系统中实现的PDS数据结构[5]与我们的hiproofs具有类似的通用性,但不那么抽象,并且包括实现功能。PDS由名称、序列和称为正义和理由的元素组成。其中,命名的节点和公正元素在hiproofs中有对应物。344E. Denney等人理论计算机科学电子笔记155(2006)341AAAxAx=xReflA<$A<$(x=x)与-IImp-I► AA(x=x)图二. 一个简单的自然推论 证据顺序和原因实现目标和回溯,因此在hiproofs中否则,PDS(而且,它恰好是最低层的树)与hiproof的具体特征密切相关在 一 个 不 同 的 方 向 , hiproofs 是 密 切 相 关 的 higraphs ( 例 如 见[1]),但细化的概念不同。本文将被理解为证明层次的第一个抽象步骤,而不是试图给出上述语言和系统的实现结构2层次证明树在本节中,我们定义了分层证明树或hiproof的概念。为了激发它,我们首先通过一个例子来分析策略与形式证明的标准概念(如自然演绎风格的证明)之间的关系。例2.1考虑A<$A<$(x=x)的自然演绎证明,如图2所示。明显的(向后的)证明是蕴涵引入,接着是合取引入,然后将公理和反显性应用于两个子目标。证明的基本信息是推理规则的序列,这些规则的顺序由图3(a)中的证明树表示。然而,通常,定理证明器允许使用更高级别的策略,这些策略将许多低级推理的应用组合在一起例如,通常有一个Intros命令,它执行所有可能的引入规则。我们可以通过将Imp-I和And-I分组在一起来在证明图上表明这一点,如图3(b)所示。我们可以进一步定义一种策略,即Prop,它首先调用Intros,然后尽可能地使用这给出了图3(c)的分层结构。Q例2.1表明,证明可以表示为策略(或公理和推理)标记的树,在节点集上具有层次结构。树结构是直接的,但层次结构及其与树结构的相互作用更复杂。我们通过偏序形式化层次结构,其中v≤iw通过将节点v描绘为位于节点w内部来直观地表示。偏序满足公理E. Denney等人理论计算机科学电子笔记155(2006)341345引导轴反射S我杂质-I而-I杂质-I而-I道具引导页杂质-AxRefl而-I(一)(b) (c)图三. 通过分组在证明图中引入层次结构。它是由一个(有限的)森林产生的,有时候把它看作是这样是方便的。我们的层次树被标记为策略,因此我们假设Λ是策略标识符或方法标识符的固定非空集合。我们写isrootF(v)(或isroot→)来断言存在一个树在森林F与根v,我们写兄弟F(v,vJ)(或兄弟→(v,vJ))如果v和vJ具有相同的父节点或者都是根。的标准定义树木和森林见附录。定义2.2一个层次证明树,或简称hiproof,由一个(必然有限的)作为偏序集的森林i=V,≤i和一个森林s=V,→s,以及一个函数t:V→Λ,它用Λ中的策略标识符标记V中的节点,满足以下条件:(i) 箭头总是指向外部节点:每当v→sw1和w1iw2时,则vi w2(ii) 箭头总是从内部节点发出:只要w1≤iv且v→sw2则v=w1(iii) 包含和序列是互斥的:只要v≤iw,v→w,则v=w(iv) 给定任何两个节点v和vJ,它们都位于最高包含级别,或者都直接包含在同一节点中,那么v,vJ中的至多一个没有进入的边:兄弟姐妹(v,vJ)是根s(v)是根s(v j)=是根s(vJ)= vJ.Q请注意第一个条件的微妙之处,特别是与第三个条件结合使用时:从节点v出发的箭头只能指向相对于AxRefl346E. Denney等人理论计算机科学电子笔记155(2006)341T2T3T1T1T3T4T2T1T2T1T2T3v的包含水平。例如,例2.1满足条件。注意,第四个条件与有限性一起意味着存在一个唯一的节点,对于≤i是最大的,并且没有传入的→s边,充当一种层次根。证明这些公理的主要定理是定理3.9,它表明每一个hiproof都展开为一个普通的证明。但在得出这个结果之前,我们将通过考察一些非例子来分析这些公理。这些公理被设计成确保图4中的任何图都不会形成hiproof。(一)(b)第(1)款(c)第(1)款(d)见图4。 四个非证明的例子在策略定理证明中,一个策略紧接着另一个策略,展开后又给出另一个策略,如此类推,所以策略是在"最抽象的层次“上调用的。但图4(a)与此相矛盾,因为如果T1后面跟着T3,T2展开到T3,那么更抽象的T2应该跟在T1后面。同样地,T3跟随T1是允许的,但是T2是T3的抽象这一事实将与证明无关,并且不应该添加在T1和T3的合成之后。相反,当一个策略结束执行时,控制权从最近执行的策略开始,即,最里面的,向外的,但图4(b)与此相矛盾。我们也想排除图4(c),以避免解折叠和测序的循环。最后,图4(d)失败了,因为战术T1应该展开,给出一个唯一的后续战术来执行,而不是两个。hiproof定义中的第一个条件禁止包含hiproof被组合“向下”超越,例如,如图4(a)所示。第二个条件排除了图4(b)。第三个条件排除了图4(c):箭头指向另一个方向的类似结构已经被第二个条件排除了。并且第四条件排除了图4(d)以及通过移除标记为T1的节点从图4(d)获得的类似的非证明示例。对于hiproof的一个积极的例子,考虑图1(b)。hiproof定义背后的主要思想可以从图1(a)和1(b)中理解。虽然是由图表驱动的,但我们已经从几何抽象到了离散的数学结构。中心特征E. Denney等人理论计算机科学电子笔记155(2006)341347具体如下:• 我们不要求策略标识符是唯一的,因为策略可以在证明中重复应用。但是我们非正式地通过它们的策略标识符来指代证明节点,其中没有歧义。• 节点之间只有两种关系:包含,表示策略向其定义的展开,箭头表示顺序组合。例如,在图1(b)中,决策过程DP展开以给出Normalise与Taut的组合。• hiproofs基本上是树状的,因为子目标是独立的:策略作用于单个子目标。这在战术定理证明中通常不是这种情况,我们打算在未来的工作中相应地扩展定义。Tactics通常返回一个子目标列表,但是我们从子tactics的顺序中抽象出来。因此,一个hiproof由一个有限的策略标记节点集合组成,这些节点通过包含和组合来联系。虽然这些图代表了完整证明的抽象版本,但我们感兴趣的是这些证明是如何构造的,因此我们认为部分证明是良构的。3相关证明树和分层证明树在本节中,我们将层次证明树与证明树联系起来。证明不仅是具有平凡层次的hiproof的实例,而且更重要的是,每个hiproof展开给出一个普通的证明,我们称之为它的骨架。如例2.1所示,普通证明和hiproofs之间的关系是我们对hiproofs行为语义理解的基础。所以我们应该用公理化的方法来解释骨架的定义,我们在这里通过证明它充当规范包含的左伴随来做到这一点。我们保留第2节的术语约定。定义3.1证明树由一棵树,V,→,r,以及一个策略标记函数t:V→Λ组成。Q定义3.2证明树映射α:V,→,r,t→VJ,→J,rJ,tj是一个函数α:V→VJ使得α保持根并满足以下条件:• u→v<$α(u)→J<$α(v)• t(u)=tJ(α(u))。Q证明树与证明树映射一起形成了我们称为证明的范畴。证明范畴有有限积和有限余积。这样的范畴理论结构允许人们从较少的com构建复杂的证明348E. Denney等人理论计算机科学电子笔记155(2006)341F∗复杂的,它们提供证明之间的转换。 一对证明树的余积通过连接它们的根给出。该产品涉及具有成对标记的节点,参见。第5款.也有复杂的类幺半群结构,给定一个证明V,→,r和一族根与V,→,r的叶子一致的证明,允许人们在V,→,r的每一个叶子上附加后面的证明,参见[7]和第4节。在进一步的工作中,我们希望将这种构造从证明树提升到层次证明树。但首先,我们需要确定这两个概念之间关系的确切性质,我们通过找到一个附加词来做到这一点为了找到一个有趣的附加词,刻画一个hiproof的骨架的自然概念,我们需要使用偏序≤i的一个精化来精确定义hiproof映射的概念。定义3.3在hiproof中,设≤f表示≤i的子序,如果u是v的子,且u没有进入→s边,则将u≤fv生成Q从定义5.4的第四个条件可以得出,≤f总是有限链的有限集合。定义3.4一个双证明映射α:V,≤i,→s,t→VJ,≤J,→J,tj是一个函数,I sα:V→VJ使得α保持→-根并满足以下条件:• u≤fv<$α(u)≤Jα(v)• u→s vα(u)J→sα (v)• t(u)= tJ(α(u))。QHiproof和Hiproof映射形成一个类别Hiproof。证明可以自然地被认为是可验证的证明,如下所示:定义3.5设E:Proof→Hiproof将证明γ=V,→,r,t发送到V,id V,→,tQ命题3.6函子E是完全忠实的,并且保持有限乘积和有限余积。Q证明和hiproof之间最重要的关系是通过将hiproof展开为普通证明(称为其骨架)给出的,正如我们在分析图4的非示例时所讨论的那样。为了一般地描述和描述骨架,我们使用树和偏序之间的以下对应关系:注意,在下文中,v1≤v2意味着,在对应的树中,存在相反方向的路径,即,从V2到V1。E. Denney等人理论计算机科学电子笔记155(2006)341349WFT2正常化拉紧图五. 一个hiproof命题3.7给出一棵树等价于给出一个有限偏序集T=满足“非共享”条件的x,y,z ∈ F. x ≤ yx ≤ z意味着y ≤ z或z ≤ y,并且具有顶部元件T。生成的树是<$V,→,T <$,其中v→vJ,只要vJ∈cover≤(v),节点的cover定义为紧挨着它下面的节点的集合。Q推论3.8给出一个森林等价于给出一个满足Prop的“非共享”条件的有限偏序集<$V,≤ <$V。 3.7:x,y,z ∈ V。 x ≤y和x ≤z意味着y≤z或z ≤ y。Q现在我们可以定义和证明一个hiproof的骨架作为一个左伴随如下:定理3.9函子E有一个左伴随,记为sk,向我们称之为骨架的东西发送一个hiproof h=<$VT,≤i,→s,t <$,给出如下:Λ-标号树<$VT,→T,r<$,对应于有限偏序集T =<$VT,≤T<$,其中VT是≤ i的叶的集合,且v1≤v2当且仅当存在v∈V使得v2≤iv且v1→sv.Q例3.10图5给出了图1(b)中的hiproof的框架,图3(c)中描述的hiproof的框架是图3(a)中描述的证明。Q一个hiproof的骨架给了我们一个hiproof展开的概念,由底层的原子策略树给出。 如果我们考虑原子战术作为推论和公理,这给了我们一个标准的非层次证明。我们有时将骨架视为证明,有时将骨架视为证明:通常,这相当于应用复合函子Esk并自由使用350E. Denney等人理论计算机科学电子笔记155(2006)341T1T1T2WFDPT1T2WF(一)(b)第(1)款(c)第(1)款(d)其他事项 (e)见图6。 改进证明E的完全忠实,这使我们能够将Proof视为Hiproof的完全subcatory。正如我们在下面几节中所考虑的那样,我们对一个hiproof所做的任何构造或变换都需要通过保存它的骨架或在其骨架上进行相应的构造来4耐高温精炼人们想要对hiproof进行的基本构造是精化:其思想是当h2扩展h1中的证明时,h1精化为h2,其中扩展被非正式地理解为所以我们的目标是正式化。 证明可以通过两种方式成长:要么通过一种战术召唤,一个子策略,或者通过将一个新策略应用于一个子目标。这些分别对应于包含和顺序组成的策略。由于我们想要形式化一个语义上的而不是操作上的细化概念,我们对细化的定义相当于允许树木在“底部”任意生长,并且在森林的情况下,添加额外的树木。本节中的定义使其精确。例4.1图6从左到右显示了一个hiproof的细化。细化生成偏序,这不是唯一可能的序列。我们首先定义了树和森林的细化,这些简单的结构构成了hiproofs。我们需要补充一些定义。定义4.2树T=<$V,→,r<$的有根子树TJ是树<$VJ,→J,r<$哪里• VJ是V的向上闭非空子集:只要vJ∈VJ,则对于所有vJ J,使得vj →vJ,也有vJ J∈V;因此r也∈VJ• →J是→对VJ×VJ的限制。Q因此,我们把有根子树简称为子树。直观地说,细化一棵树相当于在根以下的任何级别上添加,DP正常化T1T2WFDPT1T2正常化拉紧E. Denney等人理论计算机科学电子笔记155(2006)341351S新的节点的数量。因此,原始树总是任何细化它的树的子树:定义4.3一棵树<$V1,→1,r1<$∈V2,→2,r2<$,V1,→1,r1如果前者是后者的子树。Q定义4.4森林F1定义为森林F2,记为F1±FF2,如果存在一个单射函数i:F1→F2,使得对所有树T∈F1,T±Ti(T)Q在实践中,将森林视为图或偏序集,更容易使用森林精化的以下特征:命题4.5给定森林F1=rot F2(v)且v→1vJ v→2vJ.Q命题4.6给定森林 F1=和 F2=, F1±FF2当且仅当f或alllv ,vJ∈V1 ,isrot F1(v) ⇐⇒是roo t F2(v)且v∈coverF1(VJ)=<$v∈coverF2(VJ).Q因此,森林改良的特点可以从保存树根和包含相应的秩序方面来描述。这就是我们定义高防精炼的方式。定义4.7一个hiproofh=V,≤i,→s,t被称为精化到hiproofhJ=<$VJ,≤J,→J,tJ<$,记作h±1hJ,若<$V,≤i <$ ±F<$VJ,≤J<$,<$V,→s <$±F伊什伊并且标签被保留,即,ttJ(将t和tJ中的每一个视为有限对集合,例如,v,t(v)Q普通证明的细化由树细化定义,如定义4.3所示,但须遵守标记。它遵循的定义检查,细化为hiproofs限制沿E细化为普通证明。更重要的是,sk将hiproof细化发送到普通细化,如下所示。定理4.8如果一个hiproof h归结为hJ,则sk(h)归结为sk(hJ)。Q我们将不会证明这一点在本节中,作为一个更强的结果,从我们的特点hiproofs在普通的标记树与更复杂的标签在第5节。因此,我们将在稍后制定更强有力的声明。352E. Denney等人理论计算机科学电子笔记155(2006)341我5Hiproofs的一个具体特征在本节中,我们将使用更易于实现的术语进行验证。hiproof的定义由两个森林组成。 但是,它们可以通过以下方式组合成一个具有更复杂标签的单一树。设R+表示二元关系R的传递闭包。命题5.1在hiproof中不<当v∈cover≤(vJ)时,则对所有v,vJ∈V,当v(>1→s)+vJ我我一个是VvJ.Q因此,作为第一次尝试用这样的术语来描述hiproofs的特征,我们可以试着把图1(b)表示如下,参见。【十一】:T1T2WF DP正常化拉紧实线表示组成,虚线表示内含物。但这种表示法并没有区分DP是T1的子策略的类似的hiproof。这可以通过配对策略与它们在包含层次结构中的级别来解决:在图1(b)中,T1和DP的级别为0,T2的级别为1,依此类推,但是我们不需要区分两种箭头,因为这些信息是由相邻节点的相应级别决定的。这就引出了以下定义:定义5.2类型2的一个证明是一棵树,它包含函数:t:V→Λ和l:V→N,满足以下条件:(i) l(r)= 0(ii) 如果v→vJ,则l(vJ)≤l(v)+1(iii) 若v→v1,v→v2且l(v1)=l(v)+ 1,则v1=v2.Q我们经常将节点v与一对λ,lλ标识,从而隐含地断言t(v)=λ和l(v)=l。函数l:V→N将节点发送到我们称之为包含层的位置。因此,定义的第一个条件断言树的根位于包含级别0。第二个条件是节点只(直接)连接到它们直接包含或组成的那些节点在后一种情况下,节点可以E. Denney等人理论计算机科学电子笔记155(2006)341353我一个任意低的包含水平。第三个条件是,如果增加包含级别,则断言子节点的唯一性。在定义5.2中,组成和包含深度都隐含在节点的结构中。因此,就认知特性而言,由类型2的hiproofs产生的图似乎不如由类型1的hiproofs产生的图适合人类用户。在后者中,两个不同的视觉关系,空间包容性和边缘连接性,用于表示战术包含和组成(见图1(b)),从而减少混淆的范围。相比之下,由于它们的经济性,类型2 hiproofs具有内部的,面向机器的表示的优势。稍微考虑一下层次,类型2的Hiproof很容易形成一个我们用Hiproof2表示的类别。我们有时把定义2.2的证明称为类型1的证明。例5.3图1(b)不仅构成了一个hiproof,而且构成了一个hiproof类型2. 图1(b)中的部分订单信息可以展开如下:T1 DP我我我标准化sT2 WF正常化拉紧WFDP拉紧其中箭头上的标记区分包含森林和组成森林。如果我们使用所有的s-标记的箭头,但只使用那些i-标记的箭头,其上域没有传入的s-标记的边,重新组合这些数据,我们得到类型2的hiproof如下:(T1,0)(T2(1)(WF,1)(DP,0)(Normalise,1)(Taut(1)其中节点由其策略标识符和包含级别非正式地表示。现在将类型2的hiproof与图5进行比较,图5是图1(b)的hiproof的骨架。根据我们对类型2的hi证明,骨架由l(v)局部最大的那些节点v确定,因此如果v→vJ且l(vJ)≤l(v),则v在骨架中。Q例5.3表明,任何证明都可以等价地表示为任一类型的hiproof。这两个字的意思是:T2SS354E. Denney等人理论计算机科学电子笔记155(2006)341我我我1我我范畴同构此外,我们可以直接和自然地描述hiproof的骨架在类型2的hiproof,所以hiproof的两个概念之间的对应关系尊重底层的证明结构。定义5.4定义函子μ12:Hiproof→Hiproof2,通过发送类型1的hiproof_V,≤i,→s,t_i给类型2的hiproof_V,→,r,t,l_i,由以下数据给出:• l(v)被定义为等于0,当v不≤ i(v)时,并且归纳地等于l(parent≤i( v ) ) +1 个 其 他 wise; ( expliterallyinforest-qua-posetnotation : 对 于eachvJ/=T,parent≤(vJ)是在≤i(v)上唯一的v,使得hatvJ∈c• 当verv→svJ或vJ∈cover≤i(v)且d是root→s(vJ)时,v→vJ;• r是hiproof的根(见定义后的注释Q定义5.5定义函子μ21:Hiproof2→Hiproof,通过发送类型2的hiproof_V,→,r,t,l_n到类型1的hiproof_V,≤i,→s,t_n,由以下数据给出:• 当v→vJ且l(vJ)≤l(v)时,v→svJ• ≤i是1的自相关和传递闭包,后者定义如下:<当(非空)路径vJ= v0→... → vn→ vn +1= v存在使得l(v1)=l(v0)+1和l(vi)=l(vi+1),其中1≤i≤n.Qμ12和μ21的良定性的证明相当于附录A中的命题A.3和A.5。我们现在证明它们是相互逆的。定理5.6函子μ12:Hiproof→Hiproof2和μ21:Hiproof2→ Hiproof 1是相互逆的。证据 我们只勾勒出论证的一个方向,因为另一个方向是相似的。设h1 = μ 12(h1)= μ 12(h2)= μ 12(h1)= μ 12(h2),μ 12(h1)= μ 12(h2),μ 12(h1)= μ 12(h2),μ 12(h1)= μ 12(h2),μ 12(h2)= μ 12(h1),μ 12(h2)= μ 12(h1),μ 12(h2)= μ 12(h1),μ 12(h2),μ 12(h2)= μ 12(h1),μ 12(h2),μ 12(h2)= μ 12(h1),μ 12(h2),μ 12(h2)= μ 12(h1),μ 12(h1),μ 12(h2),μ 12(h2),μ 12(h2),μ 12(h1),μ 12(h2=μ21(h2)=<$VJ,≤J,→J,tJ<$。从定义中直接得出V=VJ=V2,I st=t2=TJ.我们首先证明≤J≤i(要求证明≤J=≤i)。假设v≤JvJ和我我我通过归纳法得出森林中连接vJ和v的路径的长度V,≤J.基本情况是微不足道的。对于归纳情形,由归纳hy命题假设v≤ivjj,且VJJ∈cover≤J(VJ). 从后到后。五、5,路径vJ= v0→. →vn→vn+1=vJJ必须存在于h2中,使得l(v1)=l(v0)+ 1和l(vi+1)=l(vi),其中1≤i≤n.由定义式5.4可得:VJ=v0=parent≤i(v1)orr,equivalently,E. Denney等人理论计算机科学电子笔记155(2006)341355v1∈cover≤i(VJ). 从vi→vi+1和l(vi)= l(vi +1),得出vi和vi +1,对于i的范围如上,共享VJ=v0,因为in≤i。在≤ i(v,j)上sovjj ∈ c. 结合归纳假设VJJ≤ivj,证明了v≤ivj.356E. Denney等人理论计算机科学电子笔记155(2006)341我1S11关于≤i<$≤J很相近似 等式→s=→J也可以证明类似。Q我们现在来看骨架。我们需要对骨架的结构进行分析在类型2的证明方面。如果是2型防热h2=V,→,r,t,l,我们称一个节点为包含节点,如果它有一个具有更大包含级别的子节点。定理5.7给定一个2型双证明h2= kV,→,r,t,l,k,我们记为sk2(h2)的下列数据通过μ12与sk一致:其中VT是h 2的非包含节点的集合,且v→TvJ当且仅当v→v1→ ··· →vn→vJ,其中v1,.,vn是包含节点,r是最大非包含节点,并且标记由以下限制给出:的标记函数。Q证据通过对证据的有理有据的归纳。在每一个阶段,一个扩展的hiproof的一个叶,并表明,sk和sk2和μQ最后,正如在第4节末尾所承诺的,我们根据类型2的hiproofs来表示加细,并表明相对于等价性,该表示与我们在定义4.7中对类型1的hiproofs的加细表示一致。定义5.8一个hiproofh=V,→,r,t,l的2型函数定义为一个hiproofhJ =相同类型的<$VJ,→,rJ,tJ,lJ<$,记为h±2hJ,当且仅当<$V,→,r<$±T并且,t<$tJ和l<$lJ。Q定理5.9设h1和hJ做好防护。则h1±1hj成立当且仅当μ12(h1)±2μ12(HJ)。Q这表明,两个公式的hiproofs是等价的方面细化。定理4.8的证明直接如下6结论和进一步工作我们已经引入并开始发展分层证明树或hiproof的概念,抽象地反映了在定理证明中使用的策略我们已经提出了公理,允许一个展开一个hiproof产生一个普通的证明,我们已经说明了公理的例子和非例子。我们已经概述了细化的工作原理,并给出了更适合实现的定义的替代在实践中,战术拥有比我们在这里所讨论的复杂得多的结构,在这里我们将自己限制在简单的战术概念上E. Denney等人理论计算机科学电子笔记155(2006)341357抽搐和证据。我们认为这项工作只是为主题提供语义基础的第一步。我们相信,适当地发展,对hiproofs和概念扩展的一般性质和操作的研究将有助于给出一种原则性的方法,以设计独立于hiproofs表示的规范的接口,并允许人们对实现的正确性进行推理。我们正在积极调查的应用程序的hiproofs作为基础的证明协议,使用的操作- tional语义,形式化hiproofs是如何构建的序列的战术应用程序。为了开发我们已经定义的hiproofs,我们接下来试图定义由各种证明助手支持的hiproofs上的自然操作。例子是各种抽象操作。这种我们还计划重新定义语义结构和底层逻辑之间的关系,引入逐步细化的概念。确认第一作者感谢Alan Bundy的鼓励和对这项工作的兴趣。引用[1] 斯图尔特·安德森,约翰·鲍尔,康斯坦丁诺斯·图尔拉斯。缩小基于higraph的图:语法和语义问题。在CATS 2002会议录中,Australasian Symposium on Theory of Computing,第61卷Electronic Notes in Theoretical Computer Science(ENTCS)。Elsevier,2002年。[2] Jon Barwise和Eric Hammer。图与逻辑系统的概念In G.阿尔温和J. Barwise,编辑,逻辑推理与图表,第49-78页。牛津大学出版社,1996年。[3] Chr isto ph B en zmüller , L assaa d Cheikhr ouhou , D et lefFehr er , ArminFie d ler , XiaorongHu a n g,Manfred Kerber ,Michael Kohlhase,Karsten Konrad,Andreas Meier,Erica Melis,Wolf S ch aarschm i d t,JoürgSiekmann,and VolkerSorge. 我的天啊,这是一个很好的地方。在CADE-14的会议记录中,LNAI的第1249卷。Springer,1997年。[4] A. 邦 迪 规 划 论 证 。 芽 孢 杆 菌 中 Drabble , editor , Proceedings of the 3rd InternationalConference on AI Planning Systems,(AIPS)1996,pages 261-267,1996.也可作为DAI研究报告886。[5] Lassaad Cheikhrouhou和Volker Sorge。PDS -一种用于验证计划的三维数据结构。2000年3月在突尼斯莫纳斯提尔举行的人工智能和计算智能在工程和工业应用中的决策、控制和自动化国际会议'2000)上发表[6] 大卫·哈雷尔。 关于视觉形式主义。 Communications of the ACM,31(5):514[7] C. Hermida,M. Makkai和A. J. Power。高维重图在第13届LICS会议记录中,第199-206页。IEEE Press,1998.358E. Denney等人理论计算机科学电子笔记155(2006)341我S我[8] D.卡普尔角Nie,和D. R.马瑟Tecton证明系统的概述。Theoretical Computer Science,133(2):307[9] J. D. C. Richardson和A.斯麦尔证明策略的延续。自动推理国际联合会议,IJCAR 2001 - ShortPapers,2001年6月。Technical ReportDII11/01,Dipartimenod Ingegn eri ad ell'Informazione,Universit`adiSiena,Italy.[10] J. D. C Richardson,A.斯梅尔和我共享的系统描述:使用Lambda-Clam在高阶逻辑第15届国际自动演绎会议,129-133页[11] 朱利安·理查森和艾伦·邦迪证明规划方法作为模式。 DAI技术报告,爱丁堡大学信息学系,1999年。一定义和技术证明定义A.1一棵树T=v/V,→,r/v是一个有限的dagV/v,→ v,有一个特殊的顶点r∈V,称为根,使得从r到每一个其他的顶点v/=r都只有一条路。对于每一条边<$v,vJ <$∈→,我们将传统上写为v→vJ,我们说vJ是v的孩子,或者等价地,vJ具有父v。树中的顶点V通常也称为结Q定义A.2森林F是一个有限集合{T1,... ,Tn}的树Tj=<$Vj,→j,rj<$.我们将写v→FvJ(或当F理解时仅写v→vJ)表示在F中存在树Tj使得v,vJ∈Vj且v→jvJ。因此,我们通常也将森林F写为:V,→F,其中V是所有Vj。Q命题A.3 μ12定义明确,即:每个μ12(μV,≤i,→s,t∈)都符合Def。5.2.证据 根据命题5.1,并观察到→+(>1→s)+,可以得出:是一个无圈图。此外,当v1→v和v2→v时,有v1=v2:对于唯一可能的情况是v1→sv和v1→sv,或者,v∈cover≤i(v1)和v∈cover≤i(v2);v1=v2直接由v∈V,→s∈v和v ∈V得出,≤i∈ v是森林。因此,只要路径v0→vv存在,它就必须是唯一的。我们通过对d(v)的归纳证明了对于所有v∈V,r→v,d(v)是v关于→ s的“深度”,定义VJ→v且d(v)=0。当d(v)=0时,通常是rot→s(v)且兄弟s≤(v,r)(在roo t≤i(v)的s en s e中)。 不存在r=v和r→v的平凡成立。在归纳的情况下,假设对vJ和vJ→v为真。然后归纳假设产生r→VJ,因此,传递性地,也产生r→vv。通过实例分析,证明了当v→VJ时,l(VJ)≤l(v. CasevJ∈cover≤i(v)anddis roo t→s(vJ)isimmediate. 当nv→svJ时,给出了r为rot≤i(vJ)或rnot的一个矿s. 当n为0时,l(v,J)=0≤l(v)+1. WHENE. Denney等人理论计算机科学电子笔记155(2006)341359我SSSSSvJ∈cover≤i(vJJ)对于somevJJ,条件i产生svJ∈cover≤i(vJJ),由whichl(v)=l(v,J)+1 =l(v,J)。假设v→v1和v→v2使得l(v1)=l(v)+ 1。 然后你必须在f的y p e 1 hipr o中,havev=pa rent≤i(v1),hev1≤iv. 进一步地,我们区分gu是h的两种情况:首先是t,如果l(v2)=l(v1),则一个h作为兄弟s≤i(v1,v2),同时也是rot→s(v1),则rot→s(v2)。D e f的ncnditioniv.2.2按要求建立v1=v2。类似地,l(v2)≤l(v)意味着v→sv2,而v1≤iv,因此v1=v2是定义1型证明的第一个条件最后,l
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- 图书馆管理系统数据库设计与功能详解
- ***物流有限公司仓储配送业务SOP详解
- 机械专业实习经验与学习收获
- 阎良区生活垃圾卫生填埋场施工与运营管理详解
- 濮阳市生活垃圾无害化处理工程施工组织设计详解
- MATLAB均匀平面波仿真课程设计指南
- 北京市地铁9号线技术规格与设备详情
- 西门子PLC在中央空调自动控制系统的应用
- PLC驱动的电梯控制系统发展历程与未来趋势
- 外墙维修工程政府采购项目施工方案概述
- 项目方案委员会会议全程指南与文件清单
- Dreamweaver实战:创建简单网页与站点管理
- 国内升学与就业政策及信息搜集指南
- 国资公司2020上半年创新发展与资产管理工作总结
- 项目管理:目标控制与各方角色分工详解
- 构建项目管理体系:提升组织绩效的关键
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功