没有合适的资源?快使用搜索试试~ 我知道了~
H↓可在www.sciencedirect.com在线获取理论计算机科学电子笔记278(2011)3-16www.elsevier.com/locate/entcs未排序的函数翻译Carlos Areces1FaMAF,阿根廷国立大学丹尼尔·戈林2SKS摘要在这篇文章中,我们首先展示了如何从模态逻辑的功能和优化的功能翻译许多排序的一阶逻辑可以自然地扩展到混合语言(@,). 翻译不仅在对所有模型的类进行推理时是正确的,而且对于任何一阶可定义类都是正确的。 我们然后显示排序可以被安全地移除(即,(不考虑公式的可满足性)对于可以用基本模态语言定义的框架类,并给出一个使用名词定义的框架类的反例。关键词:自动定理证明,函数翻译,排序。1引言功能翻译是一种自动模态推理的工具,它在20世纪80年代末和90年代初的一些出版物中几乎同时独立出现[12、13、6、20、3、4])。这种翻译以一种保持满意度的方式将公式从模态语言映射到一阶逻辑,就像标准翻译一样(见[5])。但是功能翻译使用了关系结构的语义替代,并且已经被论证和经验证明,它产生的公式可以比标准翻译获得的公式更紧凑,并且具有更浅的术语结构[15,9]。这两个属性在尝试使用一阶自动推理时至关重要。此外,与其他为自动推理量身定制的满足性保留翻译不同(例如,[1])的分层翻译,功能翻译1电子邮件:carlos. gmail.com2电子邮件:daniel. dfki.de1571-0661 © 2011 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2011.10.0024C. Areces,D.Gorín/Electronic Notes in Theoretical Computer Science 278(2011)3除了所有模型的类之外,可以用于在广泛的模型类上进行推理。我们在本文中讨论的第一个结果是函数翻译自然地扩展到覆盖混合语言H(@,↓)[2]。函数翻译通常使用多排序的一阶语言来引入,以简化表示。这意味着,在实践中,我们需要使用一个处理多排序一阶逻辑的定理证明器(例如,SPASS[19])或在未排序的一阶逻辑中模拟排序,引入额外的一位谓词符号.当我们尝试进行自动定理证明时,这两种方法都可能对性能产生影响。例如,在[17]中有人认为,通过命题符号来模拟排序会导致不相关的推理。像SPASS这样的系统避免了这些推理,但另一方面,需要考虑处理排序推理所需的机器的额外复杂性(在SPASS的情况下,良好排序的统一[18很难正确地衡量排序是否有助于或阻碍自动定理证明器,我们将不在这里讨论这个问题。相反,我们将证明,在某些情况下,可以简单地安全地“擦除”所有排序注释,而不改变公式的可满足性状态。这可以在基本模态逻辑的情况下完成(当推理所有模型的类时)已经由Hustadt和Schmidt在[10]中观察到,尽管没有证据。在第2节和第3节中,我们将介绍基本的和优化的函数变换。为了使这篇文章自成一体,我们包括了可靠性的原始证明基于这些证明,我们在第4节中发展了我们的主要结果:当推理任何模态可定义的模型类时,从使用(优化的)函数翻译获得的公式中删除排序注释是安全的。另一方面,在第5节中,我们通过提供一个具体的反例,证明了当对一个可由纯混合公理定义的类进行推理时,排序擦除是不合理的。2功能模型,功能翻译通过所有的文章,我们将工作在多模态混合语言H(@,↓)。对于由一组命题符号Prop、一组名词Nom和一组关系符号Rel组成的固定签名,所有这些符号都是成对不相交的,其公式由下式给出:::= p|我|¬ ϕ |ϕ ∧ ϕ |@我爱你|↓ i.|[r]不,其中p∈Prop,i∈Nom,r∈Rel.我们将自由地使用具有通常意义的典型的导出算子、→、r等。对于语义,我们取模型对I,g,其中I = W,I是一个关系型的解释,使得对于p ∈ Prop,pI=W,对于r∈Rel,r I = W × W,而g:Nom→ W是一个对名词的赋值。然后,我们可以通过一阶逻辑的标准转换来赋予H(@,↓)的公式意义。即对于C. Areces,D.Gorín/Electronic Notes in Theoretical Computer Science 278(2011)35w∈W和j∈Nom不发生在n中,我们有:JI,g, w|=I|=FOS T j(ω)[gw]。(一)标准的翻译与布尔连接词和满意度互换:def defSTj(p)=p(j)STj(i)=i=jdef defS T j(@i)=S T i()S T j(↓i. )= (i=j<$ST j())defS T j([r]k)=k。(r(j,k)→STk(k))(k是新鲜的)对于一类模型C,ε是C-satisfiable(C-valid,记作C |=)如果对于某个模型(对于每个模型)I,g in C,I,g,w|对于某些w(对于所有w)= 1。如果C是所有模型的类,我们说C是可满足的(有效,符号|= 0)。模型的基本框架是I对Rel中的符号的限制(即,忽略Prop)。由于它是模态逻辑中的标准,我们通常对定义为基础框架满足某些条件的模型的类感兴趣传递性)。任何这样的类C都可以说是由一个公式定义的,只要<$I,g<$i在C i <$I,g,w中|对于所有w,详情见[5]我们可以把标准翻译看作是模态算子的语义子句在一阶逻辑中的直接编码。翻译是非常简单的,但它是,在一般情况下,不适合基于推理的自动推理。很容易找到简单的模态公式,当使用ST转换为一阶逻辑,然后通过归结求解时,会导致有限子句集(见[1])。 这就是我们将在下面描述的功能翻译的主要动机,可以说是更复杂的。理解功能翻译的关键是关系结构的替代表示。假设Rel={r}。考虑一下图1a,它显示了一个关系结构,域由三个元素组成。我们也可以用三个全函数f、g和h以及一个谓词de来表示这个特定的结构,只要下面的性质成立:我是说... . r(x,y)Participate(<$de(x)<$(f(x)= y<$g(x)= y<$h(x)= y)<$.(2)我们用de(表示“死胡同”)来“标记”那些没有r -继承者的状态,f、g和h在每个状态上 有许多有效的图1b和1c示出了两个这样的表示。很容易验证它们都满足条件(2)。命题2.1设I是具有两位关系符号r的签名的有限一阶解释。则存在将I扩展到另外包含一位关系符号de和一元函数符号f1,f2,.的签名的解释Ij,fn,使得:IJ|= F0-xxy。. r(x,y)Participate(x)<$(f1(x)= y <$f2(x)= y. (n(x)= y)6C. Areces,D.Gorín/Electronic Notes in Theoretical Computer Science 278(2011)3GHfhf和hFG(一)f、gH(b)第(1)款f、g、hfdeGg,hde(c)第(1)款图1.一、关系模型(a)在(b)和(c)中用函数f、g、h和谓词de表示。函数f1,f2,...,fn可以替换地仅使用一个二元函数f来表示,该二元函数f将函数索引作为附加参数。这很容易用两种语言来表达,前者是指模型的适当节点,后者是指函数索引。命题2.2设I是一个关系符号为r:ω × ω的签名的排序一阶解释。 那么存在一个解释IJ,I到另外包含关系符号de:ω和函数符号f:1×ω→ω的签名,使得:ω:ω。. r(x,y)Participate(x)z:i.f(z,x)= y).与命题2.1不同,这种编码适合无限解释。我们现在已经具备了定义函数模型概念的一切条件首先,对于Prop和Rel的每一个选择,我们分配一个函数(排序)对应语言,其排序为ω和ι,其中每个p∈Prop和每个der(r∈Rel)是排序为ω的一位谓词符号,并且其中对于每个r∈Rel有一个二元函数符号fr:ι×ω→ω。定义2.3[函数模型]函数模型是函数对应语言的多种解释,即,结构I=I×W,I,·I×其中W和I分别是ω和I类的非空域;对于每个p∈Prop,pI×W;对于每个r∈Rel,fr:I×W→W和der×W.很明显,每个函数模型都导出一个关系模型,使得对于每个关系r,以下成立:f(z,x)= y)。(三)因此,我们说一个函数模型满足一个模态公式,当且仅当它的导出关系模型满足一个模态公式。在第3节中,我们将对极大模型感兴趣,也就是说,函数模型,其中每个可能的函数都被实现。定义2.4[最大模型]考虑一个函数模型I=W,I,·I,设rI是由(3)导出的关C. Areces,D.Gorín/Electronic Notes in Theoretical Computer Science 278(2011)37系,对于每个r∈Rel。我们说I是极大的,如果对每个全函数γ:W→W使得(w,γ(w))∈rI对所有w∈W,存在i∈I使得fr(i,x)=γ(x)对所有x。8C. Areces,D.Gorín/Electronic Notes in Theoretical Computer Science 278(2011)3在不改变导出的关系模型的情况下,任何函数模型都可以扩展到最大值。因此:命题2.5基本模态逻辑的一个公式是可满足的,如果存在一个满足它的(极大)函数Kripke模型把所有的部分放在一起,然后,我们可以看到函数翻译简单地作为一个定义2.6[FT]设j是函数式语言的项t中出现的ω类变量。到一阶逻辑FTt的函数转换将H(@,↓)的公式映射到具有自由j的函数对应语言中的一阶逻辑公式,如下所示(它与布尔连接词交换def defFTt(p)=p(t)FTt(i)=i=tdef defFT t(↓i. ω)= ωi:ω。(i=tFTt())FTt(@i)=FTi()defFT t([r] t)=<$de r(t)→ π z:i。FTfr(z,t)(z是新鲜的)定理2.7设H(@,↓)的一个公式为H(@,↓),i为不出现在H(@,↓)中的一个有理数.然后,下面的保持:(i) |=i|=FO i:ω。FTi(π)。(ii) 这是令 人 满意的 ,我的意思是:ω。FTi(m)是令 人 满意的。很容易看出,定理2.7可以推广到我们对一类一阶可定义模型进行推理例如,假设我们要求r被解释为传递关系,它在一阶逻辑中可表示为xyz。(r(x,y)<$r(y,z)→r(x,z))。通过将其与等价式(3)结合并执行一些有效的变换,我们获得了函数等价式:x:ω。(<$de(x)→ Bab:i c:i.fr(b,fr(a,x))= fr(c,x))。(四)H(@,↓)中的公式R在其中r是传递性的模型类中将是满足的,当且仅当(4)和FT(R)的合取是满足的。3优化的功能翻译考虑以下简单的模态公式:[r](p → n r n p)。(五)根据定理2.7,这个公式是可满足的,当且仅当它的函数平移也很满意i:ω。(<$de(i)→ y:i. (p(f(y,i))→(<$de(f(y,i)z:i.p(f(z,f(y,i))。(六)C. Areces,D.Gorín/Electronic Notes in Theoretical Computer Science 278(2011)39w w wppFGppfg fgf、gFGppgf fgf、gpp(一)pf,gf,g p(b)第(1)款pf,gf,g p(c)第(1)款图二、公式(5)的模型(a)和其函数翻译的两个模型(b)和(c)通过对i和z进行skolemizing,我们得到等式:<$de(c)→ y:ι。(p(f(y,c))→(<$de(f(y,c))<$p(f(g(y),f(y,c)。(七)这个公式包含两个斯科伦符号:常数c和一元函数g。所谓的由于斯科伦函数可能导致在解析期间建立复杂项,因此优化的转换可以大大减少饱和过程。此外,这简化了终止解决策略的开发[16]。为了说明优化翻译背后的思想,让我们再次考虑公式(5)。图2a显示了在节点w满足(5)的模型。另一方面,图2b显示了(7)的功能模型。使用(3)很容易验证该模型引起图2a的模型。现在注意,如果i被解释为w(记法:i<$→w),y有两个可能的值,即f和g。如果y<$→f,那么我们必须选择z<$→f,而对于y<$→g,我们必须选择z<$→g。 因此,z的正确值是y的函数,正如skolemization所证明的那样。但有趣的部分来了:我们可以图2c给出了一个例子,该模型也导出了(a),但这里正确的选择是z→g,与y的值无关。在最大模型中(cf.定义2.4)在包含所有可能的函数“重排”的地方,总是可以使每个变量的解释独立于其他变量。Ohlbach和Schmidt [14]利用这一观察结果,证明了交换两个连续的量化器在满足性方面是合理的。因此,我们可以采用一个使用基本函数翻译得到的公式,并简单地使所有的存在性量化器位于泛量化器之前,从而有效地避免引入Skolem函数。这正是优化的函数翻译所做的。定义3.1到一阶逻辑OFT的优化函数转换被定义为OFTj()=(FTj()),其中(γ)将γ带到前束范式,并将所有类型为i的存在量化器移到前面。10C. Areces,D.Gorín/Electronic Notes in Theoretical Computer Science 278(2011)3一B这个翻译的合理性来自下一个命题[14]。命题3.2如果γ是一个具有无量化因子矩阵δ的前束规范形式的公式,并且γ等价于一个模态公式的函数平移,则γ是可满足的,如果x:ιδ:ιδ也是可满足的,其中所有的x和y在γ中分别是存在的和泛量化的。我们将遵循[14]中给出的证明来验证该结果在混合情况下也成立。该证明使用了一个语法不变式,该语法不变式是功能翻译项所拥有的,称为直观地说,这个属性的意思是,我们可以从公式中出现的项和子项的集合中构建一棵树(或森林),使得:i)树的节点是项,ii)弧被标记为i类变量,iii)t1是t2的父亲,使用yit2 =fr(y,t1)标记的弧,对于某些r∈Rel,以及iv)每个i类变量只标记一个弧。定义3.3[预稳定性]我们说一个公式γ是预稳定的,如果给定所有出现在γ中的项的集合Tγ,它成立,对于Tγ中的每个i类变量y,存在一个项t和一个函数符号f,使得如果y出现在Tγ中的一个项中,则y的每次出现都是f(y,t)的形式。我们将f(y,t)称为y在x中的上下文。作为一个例子,考虑变量y出现在(5)的函数翻译中:它的所有出现都具有相同的上下文,即f(y,x)。从翻译中构建功能术语的方式可以直接这个句法属性有一个语义对应物。再次假设,对于固定的t和f,i类变量y的所有出现都在上下文f(y,t)中。然后,对于任何函数模型,由y“索引”的函数这在下面的引理中被正式表达。引理3.4设γ是函数对应语言中的一个预稳定公式,设y是γ中的一个自由变量,它出现在上下文fr(y,t)中,其中t中的所有变量在γ中都是自由的。进一步,设I = W,I,·I是一个函数模型,g是一个(排序的)赋值,a,b∈I使得frI(a,g(t))= frI(b,g(t)),其中g(t)是使用I和g对项t的解释. 然后我们有:yy我|= FOγ[ga]I| = FOγ[gb]证据 这个证明是通过对γ的归纳法得到的。我们只看基本情况。假设γ的形式为p(tJ),其中fr(y,t)是t j的子项。让我们定义ga=gy,gb= gy。首先要注意的是,因为y不发生在t中,所以我们有ga(t)=gb(t)=g(t)。因此,我们也有ga(fr(y,t))=gb(fr(y,t))。最后,再次由于预稳定性,我们知道在tJ中没有其他y的出现,因此ga(tJ)=gb(tJ),由此得出预期的结果。一个类似的推理可以用来处理的情况下,其中的一个等式的形式为t1=t2。归纳的事例简单地由归纳的假设来遵循QC. Areces,D.Gorín/Electronic Notes in Theoretical Computer Science 278(2011)311一FOB的1ak α(a1.这个引理是[14]中引理4.6的修正版本在[14]中,y在t中明确允许在γ中发生,但在这种情况下,|= FO γ[g]保持不需要依赖于frI(a,g(t))的值。3在任何情况下,使用引理3.4可以证明下面的结果(cf.[14,定理4.7])。定理3.5设γ是函数对应语言中的一个预稳定公式,y是γ中的一个自由变量,它出现在上下文fr(y,t)中,其中t中的所有变量都是自由的。最后,设I = W,I,·I是一个极大泛函模型。然后,对于每个赋值g,我们有:我|= FO x1. xk:ιμ y:ι.γ [g] μI| = FO y:1 x1. xk:1.γ [g]。证据从右到左的蕴涵在一般情况下已经有效,所以我们只需要考虑从左到右的蕴涵。那么,假设前件成立。这意味着一定存在某个函数α :Ik→我 这样,y我|= γ [gX1.. . xk]成立,对于每一个1…ak∈ I。现在,让b ∈ 我是使得frI(b,gJ(t))= α(a1. ak),其中gJ= gx1. . xk. 这样的b一定存在a1ak因为I是极大模型。因此,使用引理3.4,我们可以得出结论,y我|= FO γ [gJ]必须成立。 但由于b与a1无关。。k,我们最终得到我|= FO y:1 x1. xk:1.γ [g]。Q定理3.6设λ是H(@,↓)-公式,i是不出现在λ中的一个有理数.然后,下面的保持:(i) |=F O i:ω。|=FO∀i: ω. OF T j(π).(ii) 这是令 人 满意的 ,我的意思是:ω。i(i)是满意的。证据这足以证明FTi(n)是满足的i(FTi(n))。从右向左蕴涵一般是有效的。 另一方面,假设我|= FOFT i(n)[g]对于某些I和g。在不失一般性的情况下,我们可以假设I是最大的。设是取OFTi()并将所有类型为i的存在性量化器移到每个泛量化器之后的结果。观察到FT i(ω)→ ωJ是普遍有效的,因此,我|= FO [g]。现在,使用定理3.5,我们可以将每个存在量化器移到前面,每次一个(因为必须总是存在一个,使得它的绑定变量y出现在上下文fr(y,t)中,并且t中的所有变量都是泛量化的,或者它们的存在量化器已经移到顶部)。这个过程只能无限次重复,得到的公式满足I|= FOJ[g]并且等价于(FT i())。Q上面的证明只要求对于一个可满足的公式总是存在一个极大模型。这意味着当我们对一阶可定义框架条件的满足感兴趣时,优化的函数翻译也有效。3例如,takeI=f {u,v},{a,b},frI(u,a) =frI(v,a) =frI(u,b) =v,frI(v,b) =u,pI={v};g(w)=v,g(z)=b且γ=πz:i.p(fr(y,fr(z,w),其中t=fr(z,w)。12C. Areces,D.Gorín/Electronic Notes in Theoretical Computer Science 278(2011)3−4模态可定义模型我们准备讨论从函数翻译中删除排序注释的合理性。直观地说,我们需要看到的是,每一个可满足的、函数转换的公式都被一个函数模型满足,其中W和I的基数匹配。只有极大模型在这里会造成问题,但是我们将看到不相交并下的闭包保证了在需要时可以提高W让我们从正确地形式化我们所说的排序擦除开始。定义4.1排序擦除变换(·)-采用一个多排序的一阶公式,并消除所有排序如下:a−=a,对于a一阶原子(a-1)−=a-1-1(<$x)−=<$(<$x:α.<$x)−=<$x。()−。未排序的函数模型是用于结果签名的模型。显然,在一般情况下,不等于−但是再次考虑图1a的模型。 在图1b和1c中,它被第2节)使用三个函数,但我们当然可以用任何更多的函数来表示它,因为我们不关心重复的函数。另一方面,由于该模型的其中一个节点的扇出为3,因此它不能用少于3个函数表示。因为具有域W的关系结构的最大扇出(通过关系r)是|W|我们得出以下建议。命题4.2对于任何H(@,↓)-公式,以下是等价的:(i) 这是满意的。(ii) FT()是满意的。(iii) FT()−是满意的。证据根据前面的讨论,如果满足一个函数模型I=W,I,·I,使得|W|为|我|.使用W和I之间的任何双射,我们定义了一个满足FT(n)的未排序模型。 Q因为W → W的可能函数的数目是|W||,这个基数参数与最大模型不兼容。|, thiscardinality argument is not compatible with maximal models.然而,使用经典的preservation结果,我们表明,可以做一个较弱的形式的最大值:只有实现的功能的节点是定义4.3[生成的子模型]设I=W,·I和IJ=WJ,·I′是两个关系模型,g:Nom→W是一个赋值。我们说IJ是由g生成的I的子模型, 只要:(i) 范围gWjW,C. Areces,D.Gorín/Electronic Notes in Theoretical Computer Science 278(2011)313If(ii) 如果w∈WJ,则要么w∈range g,要么它可以通过模型中的关系从v∈range g以有限步(iii) 如果w∈WJ且(w,v)∈rI,对某个r∈Rel,则v∈WJ,(iv) pI′=pI<$WJ对于eachp∈Prop,(v) rI′ = rI(W J× W J),其中r ∈ Rel.定义4.4[g-最大模型]考虑一个未排序的函数模型I=设rI<$W×W是由I对每个r∈Rel导出的关系。设g:Nom→W是一个赋值,Ig=Wg,·Ig是I由g生成的子模型。我们称I是g-极大的,如果对任意函数α:Wg→Wg,使得(v,α(v))∈rI,对任意v∈Wg,存在i∈W,使得frI(i,v)=α(v),对任意v∈Wg.定理4.5设γ是未排序函数对应语言中的预稳定公式,其自由变量y出现在上下文fr(y,t)中,其中t中的所有变量在γ中都是自由的。那么,对于每个g-极大模型I,我们有:我|= FO x1. xky.γ [g] iI| = FO y x1. xk.γ [g].这个证明类似于定理3.5。命题2.5指出,在多排序的情况下,我们可以假设每个可满足的公式都被最大模型满足,这是证明优化函数翻译正确性的关键因素对于基本情况,我们有一个类似的g-极大模型:命题4.6H(@,↓)的公式f满足,如果存在未排序的函数模型I使得:(i) 我归纳出一个模型,满足在某个世界w,(ii) I是gw-极大的,其中gw是常数赋值gw(x)= w。证据我们只需要证明从左到右的方向。假设,然后,I,g,w|= n,对于某些I=W,·I,w∈ W和g:Nom→ W,并选择任何诱导I的未排序函数模型If=W,·If。对于每个r∈Rel,令Γ r={α:W→ W|好吧v/∈de r 定义了集合Γ= Γ r。然后,我们构造了一个n个未排序的函数模型IJ, =Wr,·I′,deIr′ =d eIr对于所有p∈Prop,f是一个fI′IfI′R满足frI′(α,v)=α(v)的任意函数,对所有α∈Γr和所有v∈W。It可以直接证明IJ是gw-极大的。此外,W上的恒等式是I和由IJ导出的关系模型之间的部分同构,因此后者也必须满足在w处的条件。Q利用命题4.6可以简单地重现定理3.6的证明。定理4.7设λ是H(@,↓)的一个公式. 以下是等价的:(i) 这是满意的。(ii) i:ω。i(i)是满意的。14C. Areces,D.Gorín/Electronic Notes in Theoretical Computer Science 278(2011)3(iii) 我是阿吉OFTi()−是令人满意的。现在,命题4.6的证明一般不起作用,如果我们对一类受限制的模型的可满足性感兴趣。例如,对于由模态公理[r]p→ rp定义的模型类,它显然是不成立的,因为在证明中得到的gw-极大模型不满足序列性条件xy.r(x,y)。接下来我们将看到,有可能得到一个gw-极大模型,它保持任何在不相交并下不变的框架条件。上述连续性条件属于这一类。事实上,根据Goldblatt和Goldblason的一个著名结果,每一类一阶和模态可定义(即由基本模态公式定义)的模型都必须在不相交并下闭合[7]。我们首先定义模型上的运算κ直观地说,<$K(I)是通过取I的K个同构副本(特别是<$0(I)=I)获得的定义4.8设I=W,·I是一个关系模型,κ是一个序数;则κ(I)= W,·是一个模型,使得W=W(κ×W),r=rI{((a,w),(a,v))|a∈κ且(w,v)∈rI},且pI=pIII(κ×pI).显然,对于基本模态公式,I,g,w| =当且仅当κ(I),g,w| = 0。此外,由于κ(I)是I的κ+1个拷贝的不交并,所以每一类模态可定义的模型C都被κ封闭。命题4.9设C是一类由κ封闭的关系模型,κ是H(@,↓)的公式。然后,如果存在未排序的函数模型,则C是C -可满足的,使得:(i) I在某个世界w上诱导了一个C模型并满足,(ii) I是gw-极大的,其中gw是常数赋值gw(x)= w。证据这个论点与命题4.6非常相似。给定一个混合模型I=I,W,·I,使得I,g,W|对于一些g和w,我们首先建立模型I J=κ(I),其中κ=|W||.|.通过构造,IJ在C中,并且如上所述,IJ,g,w |= 0。现在很容易将任何诱导IJ的函数模型转化为gw-极大模型。Q推论4.10设C是一类模态可定义的模型,设H是H(@,↓)的公式。以下是等价的:(i) C-满意。(ii) i:ω。OFTi(OFT)符合C-要求。(iii) 我是阿吉OFTi()−是C-可满足的。5OFTi类擦除的一般不可靠性人们可能想知道在优化的函数转换上执行排序擦除在一般情况下是否合理,也就是说,在基本模态语言中无法定义的类上。我们给出了一个否定的答案,这个问题展示了一类模型,这是由一个混合公式,排序擦除失败定义。C. Areces,D.Gorín/Electronic Notes in Theoretical Computer Science 278(2011)315RRRr⟨ ⟩ ∀ ¬ ∧∀∃伊日RK L图三. 一个C-模型,用于表示(关系s被省略)。让我们来考虑一下溷合公理:众所周知,它定义了一类满足一阶公式的模型,S(x,y)4。由于在这个类中s的行为就像一个普遍模态,我们可以使用混合逻辑的机制来对模型施加基数条件。例如,下面的公式仅适用于具有四个元素的模型,分别标记为i、j、k和l:[s] (i<$j<$k<$l ) <$@i<$j <$@ i<$k <$@i <$l<$@j <$k<$@j <$l<$@k<$l(8)现在,设<$是(8)与以下公式的合取:@i(rjrkrl[r]<$i)@j(rirkrl [r]<$j)@k(rirj r l [r]<$k)@l(rir j rk[r]<$l)显然,这是C-满意的。事实上(假设Prop= λ)任何λ的模型都与图3中的模型同构。最后,设为以下的连词[s]r(ij)[s]r(ik)[s]r(il)[s]r(jk)[s]r(jl)[s]r(kl)图3中的模型也满足条件,因此也满足条件。现在,考虑公式OFTm(最小值),它在C中也必须满足。我们将看到,OFTm(n)的C-模型需要的类型为1的元素的最小数量是6个(实际上,它需要的正好是6个由于这样的模型不能有多于四个的ω类元素,我们将得出结论,在这种情况下,排序不能被安全地删除首先要注意的是,对于所需的类型为i的元素的数量有一个上限,由OFTm(n)中存在量化变量的数量给出后者是钻石的数量,即18。我们需要一个函数来证明这些存在性量化变量中的每一个,而排序为i的元素的最小数量就是所需的不同函数的最小数量我们的注意力仅限于钻石。在每个合取中正好出现一个菱形;非正式地,我们说需要一个函数来解释它们中的每一个。 最后,我们得出结论,需要六个不同的功能设I= I = W,·I =是图3的模型,并假设W ={i,j,k,l}。此外,假设g(w)=w,其中w∈W。 (1)考虑到[s]r(ij);由于[s]是一个4我们可以从函数上翻译公理 s ias x:ω。 des(x)xy:ω. j:1。(x=fs(j,y))。这表16C. Areces,D.Gorín/Electronic Notes in Theoretical Computer Science 278(2011)3明,当我们使用功能模态时,我们不需要任何特殊的特设机制来处理普遍模态。翻译.C. Areces,D.Gorín/Electronic Notes in Theoretical Computer Science 278(2011)317α1( i)= jα1( j)= iα1( k)∈ { i,j}α1( l)∈{ i,j}α2( i)= kα2( j)∈ { i,k}α2( k)= iα2( l)∈{ i,k}α3( i)= lα3( j)∈ { i,l}α3( k)∈ { i,l}α3( l)= iα4( i)∈ { j,k}α4( j)= kα4( k)= jα4( l)∈{ j,k}α5( i)∈ { j,l}α5( j)= lα5( k)∈ { j,l}α5( l)= jα6( i)∈ { k,l}α6( j)∈ { k,l}α6( k)= lα6( l)= k表1满足OFTm(m)的函数的要求。普适模态,我们有I,g,w|=<$r<$(i<$j),对于每个w∈ W。 设α1为见证菱形的函数。则I,g,α1(w)|=(ij).因为rI是不可逆的,所以α1满足α1(i)=j和α1(j)=i。我们可以对所有六个合取的合取进行分析;约束如表1所示。因为α1、α2和α3在i的值上不同,所以它们必须都是不同的函数。类似地,α4在j的值上与α1不同,在k的值上与α2不同,在任何地方都与α3不同从对α5和α6的类似分析中,我们得出结论,需要六个不同的函数来满足这六个公式。6结论和今后的工作在处理函数翻译时,多排序一阶逻辑对于表示的原因是非常有用的。在这篇文章中,我们讨论了在哪些情况下,由于技术原因,也需要多类逻辑。我们证明了,只要推理被限定为由不相交的并集封闭的模型类(例如,模态可定义类)排序可以被消除。在[14]中表明,优化的函数翻译也可以用于推理一些模态定义的类,这些类不是一阶的,比如麦肯锡公理QQp→QQp定义的类。很容易看出,在这种情况下也不需要排序。当然,消除排序的经验优势需要评估。原则上,人们可以选择一个现成的自动证明器,并在一些函数转换的公式(随机生成或从给定域生成)上对其性能进行基准测试,无论是否有排序注释。然而,人们是否有理由从这种黑箱实验中得出有意义的结论,这一点也不清楚。例如,在一个示例中,没有明显的差异可能是由于子句化过程中的瓶颈,或者甚至是一个证明器实现了一个相当于擦除排序的启发式算法;未排序情况下的更好的执行时间可能是由于对较大公式的处理不足,等等。这篇文章表明,功能翻译非常适合混合情况(参见[8]中分层翻译的情况Schmidt在[16]中建立了,当限制到基本模态情况时,任何归结的细化加上(急切应用的)压缩规则[11]都终止于优化的函数翻译的输出。大多数一阶定理证明器都有因式分解和包容删除规则,因此当实现公平时,压缩实际上是隐式的。这意味着任何标准(完整和公平)18C. Areces,D.Gorín/Electronic Notes in Theoretical Computer Science 278(2011)3与优化翻译一起使用的分解定理证明器构成了所有模型类上的基本模态语言的判定方法。还研究了某些帧类的终止条件。作为未来的工作,看看在H(@)的情况下是否可以实现终止将是有趣的引用[1] C.阿雷塞斯河Gennari,J. Heguiabere,and M.德·赖克模态定理证明中的树基算法。在proc 的ECAI'2000,第199-203页,2000。[2] C. Areces和B.十个凯特。 混合逻辑。 《模态逻辑,第821-868页。Elsevier,2006年。[3] Y.作者声明:by P.模态定理证明:一个等式的观点。第11届IJCAI,第441摩根·考夫曼酒吧,一九八九年[4] Y.作者声明:by P.模态定理证明:一个等式的观点。J. of Logic and Computation,2(3):247[5] P. Blackburn,M. de Rijke和Y.维尼玛模态逻辑剑桥大学出版社,2002年。[6] L. FarinaustriasdelCerro和A. 赫茨格 线性模态扣除。 在Proc. CADE-9,第310卷,LNCS,第487-499页。Springer,1988年。[7] R. Goldblatt和S.杰森命题模态逻辑中的公理类。《代数与逻辑》,数学讲义第450卷,第163斯普林格,1975年。[8] D. 去吧 一种用于混合逻辑学的自动化技术。 PhDthesis,Uni versidaddeBuenosandUni versi t'eHenriPoinca r'e,2009.[9] I.霍罗克斯大学胡斯塔特大学Sattler和R.施密特计算模态逻辑。 《模态逻辑手册》,第181Elsevier,2006年。[10] 联合Hustadt和R. A.施密特模态定理证明器的实证分析。应用非经典逻辑学杂志,9(4):479[11] W. 小乔伊纳作为决策程序的解决策略 J. of the ACM,23(3):398 -417 , 1976 .[12] H. Ohlba ch. 一个求解M odalLogic s的演算。 博士论文,Uni versit?atKaiserlestern,1988年。[13] H.奥尔巴赫模态逻辑的归结演算。在Proc. of CADE-9,Volume 310 ofLNCS,pages 500-516中。Springer,1988年。[14] H. Ohlbach和R.施密特模态逻辑的函数平移与二阶框架性质J. of Logic and Computation,7(5):581[15] R. 很抱歉。 优化模型转换和解决方案。 博士论文,Uni versit?atdesSaarlandes,Saarb ru?cken,Germany,1997年。[16] R.施密特命题模态逻辑的归结可判定性。J. of Automated Reasoning,22(4):379[17] C.瓦尔特自动定理证明中的多分类推论。《人工智能的分类和类型》,LNCS第418卷,第18Springer,1989年。[18] C.魏登巴赫结合叠加,排序和分裂。在Handbook of Automated Reasoning,第2卷,第27章,第1965Elsevier and MIT Press,2001.[19] C. 魏登巴赫河施密特,T.希伦布兰德河Rusev和D.话题系统描述:Spass version3.0. 在proc 的CADE-21,编号4603,LNAI,第514-520页。Springer-Verlag,2007.[20] N.扎莫夫 模态分辨率。 Soviet Math,33(9):23
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功