理论计算机科学电子笔记123（2005）139-149www.elsevier.com/locate/entcs一元语言（延伸摘要）迈克尔·卡明斯基1以色列海法理工学院计算机科学系朱莉娅·莫辛2海法大学校区以色列海法摘要在本文中，我们比较了语义和句法定义的开放默认理论的扩展我们证明，在一元语言，这些定义是等价的，不依赖于基数的基础在有限世界。我们还表明，在区域封闭性假设下，一个自由变量的开放式违约理论是可判定的。关键词：缺省逻辑，开放缺省，Herbrand解释，Monadic语言1介绍非单调逻辑旨在通过提供一种形式体系来模拟人类的推理过程，以便从对世界的不完全描述中得出一致的结论。Reiter1电子邮件地址：kaminski@cs.technion.ac.il2电子邮件地址：mjulia@il.ibm.com1571-0661 © 2005 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2004.04.045140M. Kaminski，J.Mosin/Electronic Notes in Theoretical Computer Science 123（2005）139通过逻辑编程和数据库理论对更广泛的计算机科学领域做出贡献。这种逻辑处理称为缺省的推理规则，缺省是以下形式的表达式：（一）δ（x）=α（x）：Mβ1（x），.，Mβm（x），γ（x）其中α（x），β1（x），.，βm（x），m≥ 1，γ（x）是自由变量在x =x1，. ，xn. 如果α，β1，.，βm，γ包含一个自由变量。否则它是开放的。粗略地说，默认值的直观含义如下。对于每一个n元组的对象t = t1，.，tn，如果α（t）是可信的，而βi（t）s与我们的信念是一致的，那么我们就可以推出γ（t）并将它加到“信念”中去。准备好了。”因此，开放缺省可以被认为是一种在[11]中可以找到各种默认扣除的虽然封闭式违约已经得到了相当彻底的研究，但对开放式违约却知之甚少。然而，缺省推理的有趣案例通常处理开放缺省，因为缺省的预期用途是确定对象是否拥有给定的属性，而不是接受或拒绝在[7]中指出，当应用开放式缺省时，必须指定基础理论的所有此外，在[3]中有人认为，必须区分明确定义的对象（封闭项）和隐含引入的对象（例如，通过存在公式）。在本文中，我们使用[7]和[3]中提出的开放缺省理论的扩展的语义定义，其中，与[10]和[11]中的语法定义相反，自由变量被视为对象变量，而不是理论封闭项的元变量。选择外延的语义定义的原因是，一方面，它提供了理论对象的完整描述，另一方面，它区分了显式和隐式定义的对象。由于开放缺省理论的语义处理允许人们描述所考虑的域的所有元素，因此在普通的一阶缺省逻辑中没有语法对应物，除非域由域闭包假设明确定义，即，公理M（二）x=ti，i=1其中t1，.，tm是闭项（[5]）。在域闭包假设下，扩展可以通过用一组无限的新常量符号扩展缺省理论的底层语言来在语法上描述，M. Kaminski，J.Mosin/Electronic Notes in Theoretical Computer Science 123（2005）139141用其所有关闭实例的集合替换每个打开的默认值。在[6]中表明，开放缺省理论的扩展依赖于域基数（cf. [4]），在可数3或有限域上，开放缺省理论的扩展可以在一阶逻辑中用无穷卡尔纳普推理规则扩展来（三）{n（t）}t∈TL，x表示为C。这里和以后的TL表示语言L的所有闭项的集合。在本文中，我们表明，当默认理论的底层语言是一元的，语义定义和上述的句法描述的开放默认理论的扩展是等价的，并不依赖于底层的无限域的基数。也就是说，在一元语言上的开放缺省理论的扩展可以（等价地）在用卡尔纳普推理规则扩展的一阶逻辑中进行语法描述。就像在明确定义的有限域的情况下一样，句法定义将开放缺省视为缺省理论的基础语言上的所有闭合实例的集合，并扩展了一组无限的新常量符号。然后，我们证明，在这种句法定义中，用一组新的常量符号的可数集合来扩展底层语言作为推论，我们得到了一元语言上的开缺省理论的扩张的原始语义定义总是可以限制到可数基。应该指出的是，尽管一元语言是相当严格的，但许多（如果不是大多数）开放默认的例子和案例研究都涉及一元语言。此外，我们证明，在域封闭假设（2）下，对于[1]中引入的单项违约理论，我们可以将自己限制在可计算的有限基上。因此，短期违约理论是可判定的。本文的结构如下。在下一节中，我们将回顾本文中使用的在第3节中，我们证明了缺省理论在一元语言上的扩展不依赖于底层无限域的基数。最后，在第4节中，我们证明了在域闭包假设下，单项缺省理论的扩展不依赖于基础域的基数，因此，我们可以将自己限制在一个显式定义的有限域上。3在本文中，142M. Kaminski，J.Mosin/Electronic Notes in Theoretical Computer Science 123（2005）139γ2背景在本节中，我们简要回顾缺省理论的定义和一阶逻辑的Her- brand语义学。我们假设读者熟悉经典一阶逻辑。2.1缺省理论Reiter缺省理论是一个对（D，A），其中D是一组缺省，A是一组一阶句子（公理）。一个缺省理论是封闭的，如果它的所有缺省都是封闭的。否则它是开放的。2.2闭缺省理论的推广在本节中，我们回顾了闭缺省理论的扩展的句法和语义定义回想一下，封闭默认值是以下形式的表达式：α： Mβ1，...，Mβm，γ其中α，β1，.，βm，m≥ 1，γ是封闭公式。定义2.1（[11]）设（D，A）是闭缺省理论。对于任何句子集合S，令Γ（D，A）（S）是满足以下三个性质的最小句子集合B（信念）。D1. 一个大的。D2. T h（B）=B，即，B是封闭的。D3. 如果α：Mβ1，.，Mβm ∈D，α∈B，和<$β1，.，<$βm/∈S，则γ∈ B.一组句子E是（D，A）的扩展，如果Γ（D，A）（E）=E，即，如果E是算子Γ（D，A）的不动点。接下来，我们给出了封闭缺省理论的扩展的语义定义。在这里和以后，对于任何类型的解释W，我们用T hL（W）表示W的所有元素满足的L上的所有闭公式的集合。定义2.2（[2]）设（D，A）是L上的闭缺省理论。对于任何类型的解释W，设W（D，A）（W）是满足以下条件的A的最大类型V的模型M. Kaminski，J.Mosin/Electronic Notes in Theoretical Computer Science 123（2005）139143γ如果α：Mβ1，...，Mβm则γ∈ThL（V）.∈D，α∈T hL（V），且<$β1，.，<$βm/∈T hL（W），从[2]可知，作为算子的不动点理论的扩张的定义等价于Reiter也就是说，一组句子E是闭缺省理论（D，A）的扩展，当且仅当E=T hL（W），对于W的某个固定点，（D，A）.2.3一阶逻辑的Herbrand语义在本节中，我们定义了一阶逻辑的Herbrand语义，它是开放缺省理论的语义方法我们用L表示底层一阶逻辑的语言。 设b为不包含L的符号的集合。我们用Lb表示从L通过用b的所有元素扩充其常数集而得到的语言。 该组语言Lb的所有闭项称为Lb的Herbrand论域。Herbrandb-解释是Lb的一组基（闭）原子公式.注意，L b上的封闭公式的形式为<$（t1，. .，tn），其中t1，. tn是语言L b的闭项，并且n（x1，...，xn）是L上的一个公式，其自由变量在x1，.，xn.集合b称为Herbrandb-解释的基.设W是Herbrandb-解释，且λ是环上的闭公式，Lb. 我们说w满足n，记为w|如果下列情 况 成立，则为• 如果n是一个原子公式，那么w |= n当且仅当n ∈ w;• W|当且仅当w =|=0或w|= 0;• W|当且仅当w =|=0;并且• W|=<$x<$（x）当且仅当对于每个t ∈ TLb，w|= t（t）。对于Herbrandb-解释w，我们定义w的L-理论（Lb-理论），记为T hL（w）（T hLb（w）），作为w满足的L（Lb）的所有闭公式的集合。 对于一组Herbrand b-解释W，我们定义了L-理论（Lb-理论），记为T hL（W）（T hLb（W）），作为所有封闭公式的集合L（Lb）满足W的所有元素。 也就是说，T hL（W）=T hL（w）（T hLb（W）=w∈WT hLb（w））。最后，设X是Lb上的闭公式集.w∈W我们说w是Herbrand b-模型，记为w |= X，如果X <$T hLb（w）。注2.3众所周知，对于一组无限的新常数符号b，Herbrandb-解释对于一阶逻辑是完备的和合理的。也就是说，对于L上的一组公式X和L上的一个公式X，如果144M. Kaminski，J.Mosin/Electronic Notes in Theoretical Computer Science 123（2005）139L（D、A）（D、A）且仅当满足X的所有Herbrandb-解释都满足X。特别是，Herbrandb-解释与无限基自然出现在亨金证明的完整性定理（[9，引理2.16，p。70]）。2.4开放缺省理论的扩展在本节中，从定义2.2出发，在[7]和[3]之后，我们给出了开放缺省理论的扩展的定义从[3]可知（也见下面的注释2.5我们从定义背后的直觉开始。 在缺省理论的范围内有两种类型的对象。一种类型由固定的内置对象组成，这些对象属于TL并且必须存在于任何Herbrand解释中，另一种类型由隐式定义的未知对象组成，这些对象可能因Herbrand解释而异，例如，由存在性量化公式引入的对象。 这些物体产生其他的函数符号来识别未知对象。因此，似乎很自然地假设理论域是原始语言的Herbrand宇宙，用一组新的（未知的）对象扩充，参见。[8，第1章，§3]。下面的开放缺省理论的扩展定义是定义2.2与Herbrandb-解释的相对化，其中包含一组无限的新常数符号b。之所以采用语义定义，是因为一般来说，不可能用标准证明论来描述赫布兰德宇宙。唯一的例外是理论域显式有限的情况（[5]），即，包含公理（2）。定义2.4（[3]）设b是一组新的常数符号，设（D，A）是默认理论对于任何Herbrandb-解释集，（W）是A的Herbrandb-模型的最大集合V，满足以下条件条件对于任何违约α（x）：Mβ1（x），.，Mβm（x）γ（x）∈D和任何el-的元组tTLb的元素 若α（t）∈T hLb（V）且<$β1（t），.，<$βm（t）/∈T hLb（W），则γ（t）∈ThLb（V）.一组句子E称为（D，A）的b-扩张，如果E=T hL（W），b的某个固定点W。我们也将集合b称为E的基。2.我的朋友[5]从Léowh eim-S kol emeor em可以得出，对于封闭缺省理论（D，A）和无限基b，一组句子是b-扩张M. Kaminski，J.Mosin/Electronic Notes in Theoretical Computer Science 123（2005）139145（D、A）γ（D、A）（D、A）对于（D，A），当且仅当它是（D，A）的从现在开始，除非我们另有说明，否则我们处理无限基，因为有限基b的基数可以从b-扩张中提取，这在一般情况下是不可取的。注2.6注意，对于基数不同的两个基b和bJ，开放缺省理论的b-扩张和BJ-扩张不一定一致，见[6，例7.1]。2.5开放缺省理论扩展的句法描述本节包含开放缺省理论扩展的句法定义。句法定义的基本思想大致如下。在[10]之后，我们将开放缺省视为语言Lb上所有闭合实例的集合-原始语言L扩展为b的碱基b。然而在明确定义的有限域上，域闭包假设的无限域对应是推论C（3）的卡尔纳普规则。下面的定义2.7是定义2.1到用C扩展的一阶逻辑的相对化。我们还需要一点符号。对于公式集合X，我们用ThC（X）表示在用C扩充的一阶逻辑中从X可推导的所有公式的集合。我们说一组公式X是C-相容的，如果ThC（X）在通常的一阶意义上是相容的。定义2.7（[6]）设（D，A）是闭缺省理论。对于任何一组句子Slet ΓC（S）是句子B（信念）的最小集合，满足以下三个属性。CD 1。 一个大的。CD2。T hC（B）=B，即，B是CD3。 如果α：Mβ1，.，Mβm ∈D，α∈B，和<$β1，.，<$βm/∈S，则γ∈ B.一个句子集合E是（D，A）的C-扩张，如果ΓC（E）=E，即，如果E是算子Γ C的不动点。为了定义开放缺省理论的C-扩张，我们需要开放缺省的封闭实例的概念。146M. Kaminski，J.Mosin/Electronic Notes in Theoretical Computer Science 123（2005）139LLLL（D、A）定义2.8设δ（x）= α（x）：Mβ1（x），.，Mβm（x）是一个开放缺省.γ（x）δ（x）的一个实例是闭缺省δ（t）= α（t）：Mβ1（t），. ，Mβm（t），γ（t）其中t = t1，. ，t，n是底层语言的封闭项的元组。 对于一个开放缺省δ，δ的所有封闭实例的集合用δ<$表示，对于一个缺省集合D，D<$L=δ∈Dδ<$s是所有闭合距离s（over）的所有默认值。与注2.6相反，下面的定理2.9对于（D<$Lb，A）的C-exten的限制是：dotdependonthecardinality of the（infinitite）base b.这个定理是我们的新结果，但它自然属于本节的背景。它用于证明第3节中所述的结果。定理2.9（Cf. 注2.6）设（D，A）是一个开缺省理论，b和BJ是新常数符号的无限集合。 则对于（D<$Lb，A）的任意C-扩张E，re是（D <$LbJ，A）的C -扩张Ej，使得E<$FmL=Ej<$F mL.42.6可数基本节讨论可数基b上的扩张。我们从“C -完全性”定理开始定义2.10Herbrandb-空基b被称为术语解释（模型）。显然，术语解释对于卡尔纳普规则是合理的。 下面的Theo-rem2.11也完成了。定理2.11（[6]）设是可数的。 如果X是C-相容的，则X有一个项模型。注2.12众所周知，定理2.11不适用于不可计数的语言，例如，见[6，例6.7]。下面的定理2.13表明，对于可数基，扩张的语义和语法定义是等价的。定理2.13（[6]）设（D，A）是一个开缺省理论，b是一个可数的新常数对称集.E是（DLb，A）的C -扩张，若且只有当有一个不动点W满足E=T hL（W）。B4我们用FmL表示L上所有闭公式的集合。M. Kaminski，J.Mosin/Electronic Notes in Theoretical Computer Science 123（2005）139147LLLLLB（D、A）推论2.14（[6]）设（D，A）是一个开缺省理论，b是一个新常数符号的可数集。 则E是（D，A）的b -扩张当且仅当e是（D<$Lb，A）的C -扩张Ej ，使得E=Ej<$FmL.注2.15注意上述推论在一般情况下不成立，见[6，例6.9]。因此，正如在[6]中所指出的，为了在不可数域上定义句法上的扩张，除了卡尔纳普规则之外，我们还必须使用允许表达集合论推理规则的有限语言对于域闭包假设的语法等价物来说，无穷逻辑似乎代价太高了。3一元语言这一部分涉及我们的论文的主要主题-一元语言上的开放缺省理论。我们证明了对于一元语言，b-扩张不依赖于（无限）基b的基数。我们从一阶逻辑的完备性定理和一元语言上的卡尔纳普规则开始。定理3.1（Cf. 定理2.11.） 让是一种单一的语言。 如果X是一个C-相容理论，则X有项模型。定理3.1可以等价地重述如下。定理3.2设L是一元语言，X是b上闭公式的C-演绎闭集。 则X = ThLb（V），其中V是X的所有项模型的集合。结合定理3.2和定义2.4，我们得到C-（DL，A）的推广与B的固定点理论相一致.定理3.3（Cf.推论2.14）设L是一元语言，（D，A）是上的开缺省理论，b是一组新的常数符号。则E是（D，A）的b-扩张当且仅当存在（D<$Lb，A）的C-扩张Ej使得E=Ej<$FmL。最后，下面的定理3.4指出，对于一元语言，b-扩张不依赖于基b的基数，这是定理2.9和3.3的直接结果。定理3.4设是一元语言，（D，A）是上的开缺省理论，设b和BJ是新常数符号的有限个集合。 则E是（D，A）的b-扩张当且仅当它是（D，A）的bj-扩张。148M. Kaminski，J.Mosin/Electronic Notes in Theoretical Computer Science 123（2005）139（D、A）∈L特别地，从定理3.4可以得出，当处理一元语言上的开缺陷理论时，我们可以将自己限制在可数基b上，这在一般情况下是不正确的，见注2.6。4单一期限违约理论本节讨论[1]中引入的一项违约理论，见下面的定义4.2我们表明，在域封闭假设下，当处理单项违约理论时，我们可以将自己限制在有限个基上。对于一般情况，从[5]可知，在区域闭合假设下，开放缺省理论（D，A）的b-扩张与（DLb，A）对L.定理4.1（[5]）设（D，A）是一个开缺省理论，使得对于某些常数a1，.，am，AxMi=1 x=ai，5 设b是一个无限的新集合恒定对称轴则E是（DLb，A）的扩张当且仅当re是b的一个固定点W，使得E = T hL（W）。B接下来，我们回顾一下单项违约理论的定义。定义4.2（Cf. [1，定义6和10]）设L是有限的一元语言。在同一个变量x上的原子公式的命题（布尔）组合称为x上的单式公式。一个缺省理论（D，A）称为单项的，如果对于每个缺省δ D，所有出现在δ中的公式都是关于同一变量的单项公式。本节的主要结果是，对于一个单项违约理论（D，A），d不依赖于基b的基数（定理4.3）。因此，在域闭合假设下，单项缺省理论的推广也不依赖于基数。定理4.3设（D，A）是一个单项缺省理论，b是一个新常数符号的无限集合。 存在一组新的常数符号bJ，使得re是（DLb，A）的扩张E当且仅当re是对于（D<$LbJ，A）的扩张Ej，使得E<$FmL=Ej<$FmL.现在由定理4.1和4.3可以得出，在区域封闭假设下，当处理单项缺省理论时，我们可以将自己限制在有限个基上。5参见（二）、M. Kaminski，J.Mosin/Electronic Notes in Theoretical Computer Science 123（2005）139149⊆定理4.4设（D，A）是一个单项缺省理论，使得对于某些M常数a1，...，am，A m，x= ai. 存在一组有限的新常数符号bJ，使得对于新的常数符号b的每个无限集合和每个EF mL，E是（D，A）的b-扩张当且仅当它是（D，A）。定理4.4的一个直接推论是，在区域封闭假设下，单项缺省理论的扩展是可计算的。引用[1] Ben-Eliyahu-Zohary，R.，N. Francez和M.Kaminski，Similarity preservation in defaultlogic，Annals of Mathematics and Arti-official Intelligence，25（1999），137[2] 格雷罗河，和M. Casanova，缺省逻辑的另一种语义，在第三届非单调推理国际研讨会上发表，南太浩湖，1990年。[3] Kaminski，M.，A comparative study of open default theories，Arti ficial Intelligence，77（1995），285[4] Kaminski，M.，关于逻辑程序的稳定模型语义的说明，人工智能，96（1997），467-479.[5] Kaminski，M.，闭域上的开放缺省理论，《国际公共图书馆杂志》，7（1999），577-589。[6] Kaminski，M.，J.A. Makowsky和M.Tiomkin，通过域闭包假设扩展开放缺省理论，逻辑与计算杂志，8（1998），169[7] Lifschitz，V.，在开放式默认情况下，J.W. Lloyd，editor，“Computational Logic：Symposium Proceedings”Springer-Verlag，Berlin（1990），80-95.[8] 劳埃德，J.W.，“Foundation of logic programming, second extended edition,” Springer–Verlag, Berlin,[9] Mendelson，E.，“Introduction to mathematical logic,” Wadsworth and Brooks, Monterey,California,[10] Poole，D.，A logical framework for default reasoning，Arti ficial Intelligence，36（1988），27[11] 赖特河，A logic for default reasoning，Arti ficial Intelligence，13（1980），81i=1
