没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记125(2005)13-23www.elsevier.com/locate/entcsCVC Lite*中部分函数的实用方法谢尔盖·别列津a 克拉克·巴雷特b IgorShikanianb/ Arie Gur finkelc David L. 迪尔aa斯坦福大学,{berezin,dill}@ stanford.edub纽约大学,{barrett,chikania}@ cs.nyu.educ多伦多大学,{chechik,arie}@ cs.toronto.edu摘要大多数验证方法假设一个数学形式,其中函数是全函数,即使部分函数在许多应用中自然出现。此外,尽管有各种关于部分函数逻辑的建议,但对于哪种逻辑是用于验证应用的“正确”逻辑,没有达成共识。在本文中,我们提出使用三值Kleene逻辑,其中部分函数在其域之外应用时返回“unfined”值。特定的语义是根据对用户最小惊讶的原则来选择的;如果各种方法对公式的值应该是什么有分歧,那么它的评估就不确定了。我们表明,在三值逻辑检查有效性的问题可以减少到检查有效性在一个标准的二值逻辑,并描述了这种方法已成功地实现在我们的工具,CVC建兴。保留字:CVC,Kleene,部分函数,三值逻辑1介绍一阶逻辑是对系统的属性和行为进行建模的宝贵工具。自动推理和定理证明的最新进展导致了逻辑作为分析工具的更广泛和更成功的应用。*本研究由GSRC合同DABT 63 -96-C-0097-P00005和国家科学基金会CCR-0121403支持。本文的内容不一定反映GSRC、NSF或政府的立场或政策,也不应推断得到官方认可。1571-0661 © 2005 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2004.06.06414S. Berezin等人/理论计算机科学电子笔记125(2005)13系统.大多数使用一阶逻辑进行定理证明和演绎的标准方法都假设所有函数和谓词都是总和。但是,许多应用程序使用部分函数和谓词进行建模更自然。虽然人们普遍认为,一个逻辑,可以容纳部分功能是有用的各种各样的应用程序,有普遍的分歧,应该使用的逻辑。不同方法的概述可参见[4,7]。在认真对待问题而不是试图解决问题的方法中,有两种主要的替代方案。第一个允许术语被定义,但要求所有公式要么是真的,要么是假的。这种方法的不寻常之处在于,应用于未定义项的谓词被定义为假。虽然这种逻辑保留了经典逻辑的一些好的特征(例如演绎定理),但在某种意义上,由于未确知性不会传播到公式中,因此存在信息损失。例如,如果我们假设1/0项是未定义的,那么公式<$P(1/ 0)将有效。第二种方法基于Kleene的强三值逻辑[ 8 ],并且允许项和公式都被定义。这种方法更保守,因为任何在第二种方法中有效的公式在第一种方法中也是有效的,但有一些公式,如<$P(1/0),在第一种方法中可能有效,但在第二种方法中将被定义。虽然我们的定理证明器的先前实现采用了第一种方法[13],但我们更喜欢基于最小惊喜原则的第二种方法。也就是说,只有在对一个公式是否合理的结论没有分歧的情况下,这个公式才是有效的这在验证应用中尤其重要,因为系统的完整性可以通过关于系统的定理是否有效来判断此外,我们的经验是,任何真正应该有效的定理都可以用这样一种方式来表述,即它根据第二种方法是有效的一个必须处理的更务实的问题是,大多数定理证明器都是基于经典逻辑的。各种方法已被提倡修改标准定理证明,以适应逻辑部分功能[6,7,9,14]。然而,我们感兴趣的是找到一种方法来支持不修改定理证明。这样做的一种方法是为公式建立过近似和欠近似该技术已成功应用于三值模型检查[3,5]。PVS(原型验证系统[11])使用完全不同的方法,包括构造和证明称为类型正确性条件(TCC)的附加公式部队派遣国的有效性保证了所有S. Berezin等人/理论计算机科学电子笔记125(2005)1315相关术语和公式总是有定义的。然而,PVS中的TCC可以产生令人惊讶的结果。例如,有可能有一个形式为AA有一个无效的TCC。本文提出了一种检验三值逻辑中公式有效性的方法,将问题归结为检验标准二值逻辑中的两个公式与PVS类似,我们构造了一个TCC公式,其有效性意味着原始公式总是被定义的。检查完变矩器离合器后这两种检查都可以使用标准的二值逻辑来完成。请注意,与PVS不同,我们的方法是精确的,因为如果TCC无效,则原始公式的有效性确实在三值语义中未定义。本文的结构如下。第二节给出了我们的三值逻辑的语法和第三节给出了证明归约为二值逻辑的两个基本定理。第4节描述了在定理证明器CVC Lite中实现这些思想所获得的结果,第5节总结了这些结果。2三值逻辑:语义与语义语法.设S =(S,F,P,C)是签名,其中S ={s1,. . }是一组排序,F={f1,. . },P ={pi,. . }和C ={c1,. . }是函数、谓词和常量符号的集合。每个符号都有一个由XML中的排序构建的类型。定义项t如下:t::= x|C|f(t1,.,tn)|ifφthent1elset2endif,其中x是一个变量,符号c和f来自于f,条件运算符中的φ是一个公式。公式φ定义如下:φ::=真|虚假|p(t1,...)= 1,p(t 1,...),tn)|t1=t2|φ1∨φ2|¬φ1|ifφ0thenφ1elseφ2endif|艾利克斯:s。 φ1,其中,p是来自n的谓词。我们也使用常用的句法缩写φ1<$φ2、φ1<$φ2、φ1惠φ2和φx:s。φ。检查一个项或公式是否排序良好是很简单的。我们忽略这个问题,简单地假设所有的项和公式都是有序的。区分if-then-else运算符的两个版本很重要:一个用于术语,另一个用于公式。还要注意的是,if-then-else运算符不能用其他运算符或三值逻辑中的逻辑连接词来表示11明显的二值平移(φ0<$φ1)<$(<$φ0<$φ2)和(φ0<$φ1)<$(<$φ0<$φ2)是ac-16S. Berezin等人/理论计算机科学电子笔记125(2005)13为了我们的目的,我们假设每个签名都包含一组域公式,每个函数和谓词符号都有一个域公式。函数符号f的定义域公式是一个具有k个自由变量的定义域公式,其中k是f的系数,且不等于dδf[x1, . . . . ,xk]。元数为k的谓词符号p的主公式被类似地定义,并表示为δp[x1, . . ,xk]。本文给出了带t1,t2,t3,t4项的模δ f的整环的一个例子. . ,tkiswrittenδf[t1, . . ,tk],并且nd表示用hti替换eachxi的结果,对于mulaδf[x1, . . . ,xk]。直觉上,f的定义域公式定义了f被定义的点的集合。注意,我们的方法假设这个集合总是一阶可定义的。幸运的是,对于我们考虑的实际情况,情况总是如此。为了有一个明确的语义,重要的是域公式本身总是被定义的。 确保这一点的一个简单方法是要求如果s是出现在域公式中的函数或谓词符号,则δs [x1,...,xn] =真。具有部分函数的三值语义。给定一个签名,一个模型是一个对M = A,I,其中A是一个S-索引的非空载波集族A ={A,|s ∈ S},I是一个解释,它是从常数符号c:s,函数符号f:s1×···× sn→s,谓词符号p:s1×···× sn→bool到元素cM∈As,部分函数fM:As1×···×Asn→As,关系pM<$As1×···×Asn。给定一个模型M和一个变量赋值e,它将每个变量映射到一些As的一个元素,表达式(项或公式)α的值记为[α]]Me,并在图1中定义。项的值可以是某些A的元素,也可以是不在任何A中的可区别值。公式的值可以是true、false或φ。我们将使用来表示t和φ,因为项和公式总是在语法上彼此分离,并且特定类型的总是从上下文中清楚模型需要满足以下由域公式施加的附加条件:[[δf[x1, . . . ,xk]Me=true i n fMisdefineddat([x1]]Me, . . . ,[[xk]]Me)。我们说两个表达式α和β在逻辑上是等价的,并写α<$β如果[α]]Me=[[β]]Me,对于每个模型M和变量分配e。3值算子的过逼近和欠逼近,如果φ0,则φ1,否则φ2endif。S. Berezin等人/理论计算机科学电子笔记125(2005)1317⎪⎨⎪2个月⎨⎨⎨2个月⎨[[c]]Me=cM[[x]]Me=e(x)[true]]Me=true[[false]]Me=false⎧[[t1]] Me,. ,[[tn]] Me),⎪⎨[[f(t1,. ,tn)]]Me =⎪⎪⎪如果[ti]] Me i = m,则对于所有i ∈ [1. n]和[δf[t1, . . . ,tn]Me=true;[[ifφthent1很抱歉,否则。⎧如果[φ]]Me=φ;elset2endif]]Me=n[[t1]]Me, if[φ]]Me=true;[t]]e,如果[φ]]e=fal se。⎧pM([[t1]] Me,. ,[[tn]] Me),⎪⎨[[p(t1,... ,tn)]]Me =⎪⎪⎪如果[ti]] Me i = m,则对于所有i ∈ [1. n]和[δp [t1,. [i]]i = true;很抱歉,否则。⎧[[t1]]Me=[[t2]]Me,如果[t1]]Me=/[[t1=t2]]Me=0很抱歉,否则。[t2]]Me/=t;如果[φ1]]Me=true或[φ2]]Me=true,则为true;如果[φ1]]Me=false且[φ2 ]] Me=false,则[[φ1<$φ2 ]] M e = false;我知道你在想什么。⎧true,if[φ]]Me=false;[[<$φ]]Me=falseif[φ]]Me=true;如果[φ]]e=φ,则为CIMM[[ifφthenφ1如果[φ]]Me=φ;否则φ2endif]]Me=φ[[φ1]]Me,如果[φ]]Me=真;如果[φ]]e=fal se,则为[ φ ] ] e。⎧真,如果对某个a∈As:[[φ]]Me[x←a] =真;[[1996] s.φ]] Me=false,如果对所有a∈As:[[φ]] Me [x←a] = false;我知道你在想什么。Fig. 1. 三值语义:[φ]] M e.18S. Berezin等人/理论计算机科学电子笔记125(2005)13if-then-else的语义请注意,如果条件是unfined,则if-then-else运算符(对于项)的解释是unfined的,即使其他两个子项的计算结果相同。选择这种语义的一个原因很简单,它在实际应用中是实用的。在实际的程序中,如果一个分部函数应用于其域之外的参数,程序可能会崩溃或引发异常;换句话说,它会导致异常行为。因此,在if-then-else的条件下检测可能的错误值为用户提供了有用的信息,即程序在某些条件下执行期间可能崩溃。例如,考虑以下C代码:int *p = malloc(sizeof(int)); int x =(*p> 0)?y:z;在本例中,if-then-else运算符(即(·)?如果p恰好为NULL,即使在这个特定的程序状态中y = z,也会导致程序崩溃。这里*p是一个部分函数,定义在指向整数的非空指针上,并返回一个整数。逻辑if-then-else的定义类似于术语if-then-else,因此,对于否定的DeMorgan定律和对于任何谓词符号p的if-lifting性质都是保留的:<$(ifφthenφ1elseφ2endif)<$if φthen <$φ1else<$φ2endifp(ifφthent1elset2endif)如果φthenp(t1)elsep(t2)endif三值有效性三值语义可以通过以下方式扩展到公式的有效性。一个公式被认为是有效的,如果在所有的模型M和所有的变量分配e,[[φ]]Me=true。一个公式是无效的,如果至少有一个这样的模型M和一个这样的分配e,[φ]]Me=false。否则(如果公式的计算结果总是为true或false),则有效性不确定。我们将三值有效性表示为|= φ,它可以持有,不持有,或未被确定。3三值逻辑到二值逻辑的约化假设我们希望确定某个π-公式φ的三值有效性。我们的一般策略是首先计算一个称为类型正确性条件(TCC)的公式,它可以用来检查φ是否可以被定义。如果检验成功,也就是说,φ总是有定义的,那么我们就可以检验原始公式。这两种检查都可以使用标准的二值S. Berezin等人/理论计算机科学电子笔记125(2005)1319M逻辑为了证明这一说法,我们首先介绍了TCC,然后展示了如何使用它们来确定三值有效性。类型正确性条件(TCC)。我们的三值逻辑的公式φ的类型正确性条件是计算为真的公式iφis notunfined。首先,观察到如果我们有一个项f(x),那么通过定义它的TCC是yδf[x]。 我们可以很容易地把它推广到任意的术语或多个问题。图2给出了Dφ的递归定义,即任意公式φ的TCC。DxtrueDctrueDf(t1,. . ,tn)nδf[t1, . . ,tn]ni=1DtiDifφthent1elset 2endif<$Dφ<$(ifφthenDt 1elseDt 2endif)Difφthenφ1elseφ 2endif<$Dφ(ifφthenDφ1elseDφ2endif)nDp(t1,.,tn)δp [t1,. ,tn]Dt1=t 2<$Dt 1<$Dt2D<$φ<$φi=1DtiDφ1<$φ2<$(Dφ1<$φ1)<$(Dφ2<$φ2)<$(Dφ1<$Dφ2)D. φ(φx. Dφφ)(x. Dφ)图二. 部队派遣国术语和公式的定义。TCC不仅可以识别公式φ是否被定义,而且还可以用来将φ的三值求值简化为具有全模型的标准二值逻辑中的求值。SupposeMisamodelof. Let除了所有的其域公式为真(我们称这样的签名为全签名,acorrespondinggmodelatot almodel). LetMbea(total)mo delofhose函数和谓词符号的解释与M一致,只要定义域M为真(我们称M为M的扩展)。最后,用[S]]2e表示在M阶模中S上的一个x项的估计使用标准二值语义下面两个定理证明了我们的使用的TCCs。证明是通过一个简单的归纳公式的结构,并省略了由于其简单性。20S. Berezin等人/理论计算机科学电子笔记125(2005)13MM定理3.1设S是一个新的项或公式,设M是一个代数模型M到代数模型M的扩张。你好,[[DS]]2e = true[[S]]2e =[[S]]Me。表示任意MM定理m3.2设S是一个新的项或公式,设M是一个代数模型M到代数模型M的扩张。你好,[[DS]]2e = false[[S]] Me =。表示任意Dφ的另一个重要性质是,如果φ表示为DAG,则Dφ作为DAG的最坏情况大小与φ的大小成线性关系。这是因为在计算Dφ的每一步中,除了φ中已经存在的节点之外,只引入了恒定数量的附加节点。这对于φ的大小可能非常大的许多应用是至关重要的,并且甚至超过φ的大小的二次增加可能是不可接受的。实际上,情况通常更好。通常,部分函数的实例相对稀疏,并且Dφ相对于φ非常小。检查有效性。定理3.1和3.2以及构造Dφe的过程间接地提供了一个算法,用于检验一个公式在(部分)模型M中是否有效(对所有变量赋值为真)。我们所要做的就是构造一个决策过程DP,它可以确定公式是否有效,M是M的一个常见的分支。假设我们想确定φ在M中是否为真。我们首先检查Dφ,即φ的TCC。如果DP(Dφ)为假,则对于某个赋值e,[Dφ]]2e=假,因此根据定理3.2,[φ]]Me=π。因此,φ在M中无效。另一方面,在一项研究中,如果DP(Dφ)为真,则[Dφ]]2e=对所有e为真,因此[[ φ ]] 2 e=[[φ]]Me对所有e,MM定理3.1.因此,DP(φ)有效地决定了φ在M中的有效性。从实际实现的角度来看,这个性质是非常有用的,因为我们可以为M的任何方便的扩展建立一个决策过程,其中所有函数都是全的。由于求值和简化是决策过程中的常见步骤,这消除了将部分函数作为特殊情况处理的需要,我们可以像对待任何其他函数一样对它们求值或简化。作为一个具体的例子,考虑带除法的算术模型,其中除以零是未定义的。算术的决策过程通常需要能够将项置于正规形式中。特别地,期望能够对常数表达式求值以获得常数。在除法是部分函数的标准模型中,S. Berezin等人/理论计算机科学电子笔记125(2005)13211/ 0,但是如果我们扩展这个模型,比如将除以0定义为0,那么所有的常量表达式都可以很容易地被求值。 我们的方法表明,具有该附加假设的判定过程可用于判定除法是部分函数的模型中4在CVC Lite我们已经在我们的工具CVC Lite [2]中实现了上面描述的三值Kleene语义。CVC Lite针对一阶理论的特定组合检查公式的有效性该工具接受公式φ作为输入,并返回Valid或Invalid。CVC Lite基于用于组合一阶决策过程的标准技术[1,10,12],目前支持多种理论,包括未解释函数,数组和线性实数运算。它对量化器也有一些有限的支持。CVC Lite的输入语言是类型化的,支持谓词子类型化,即形式为τJ={x:τ|φ(x)},其中τ是一个类型,φ(x)是变量x上的一个无量化因子公式。类型τJ称为τ的一个子类型,带有类型谓词φ。任何类型τJ的项t的值被限制为也满足φ(t)的类型τ的值例如,operator over reals是一个类型为:div:real×{y:real|y/= 0} →实数。注意,这样的函数也可以被认为是从(real×real)到real的部分函数,当第二个参数为0时未定义。事实上,由于在谓词子类型存在的情况下精确的类型检查涉及操作任意的逻辑公式,因此正确的类型检查被限制为仅匹配函数参数和项的基本类型(即,最大超类型)。特别是,div(x,0)将是类型正确的,因为0是real类型,这是第二个参数的基类型更精确地检查输入公式φ是否总是定义的是通过计算Dφ并检查其有效性来单独完成的如果Dφ的有效性无法确定,CVC Lite将返回类型错误。如果Dφ是有效的,那么φ的有效性被检查,就好像它是经典二值逻辑中的一个公式,其中所有函数都是全的。如上所述,算术的决策过程可以将div扩展为全函数,而不会损害结果的正确性。例如,考虑以下公式:φ0div(x,y)=div(x,y),22S. Berezin等人/理论计算机科学电子笔记125(2005)13其中x和y是real类型的变量。这个公式在经典二值逻辑中显然是有效的。然而,这个公式Dφ0y= 0的TCC是无效的,因此,φ0在三值语义中的有效性是不确定的。CVC Lite检测到这一点并返回一个类型错误。然而,添加条件y/= 0使得公式在三值语义中有效:φ1y= 0div(x,y)=div(x,y),自其TCC:Dφ1 <$(true <$$>(y = 0))<$(y = 0 <$div(x,y)= div(x,y))<$(true <$y/= 0)由于第一个和最后一个析取而平凡为真。2事实上,由于完全相同的原因,该公式的逆置在三值语义中也是有效的,尽管该公式的这个版本对数学家来说可能有点令人吃惊:φ2<$div(x,y)div(x,y)<$y = 0.CVC Lite正确地证明了这两个公式确实有效。从实现的角度来看,这种方法非常容易编码:实现和调试只需要几个小时。此外,检查TCC不会明显影响工具在经典示例(没有子类型或部分函数)上的性能,因为此类公式的TCC会立即简化为真。它是如何影响具有部分功能的大型实例仍有待观察。5结论我们已经提出了一个三值Kleene逻辑中使用的应用程序是最自然的部分功能建模。我们已经展示了如何在这个逻辑中检查公式的有效性的问题可以通过检查公式和类型正确性条件来解决,该条件这两种检查都可以使用标准的二值语义来完成。我们在定理证明器CVC Lite中实现了这些想法的原型。我们的实现能够确定三值有效性[2]回想一下,那个2(12),蕴涵的TCC和相应析取的TCC是相同的。S. Berezin等人/理论计算机科学电子笔记125(2005)1323和小例子的无效性。我们计划使用这些想法来测试CVC Lite中更大的示例。未来的工作包括使用这些想法来开发一个更一般的有效性概念,在理论中使用排序和子排序,并处理非严格函数和谓词(如布尔运算符)。如果它们的一个子表达式的计算结果为“”,则整个表达式的计算结果为“”,则“”和“”不具有这样的属性。引用[1] C.巴雷特检验一阶理论组合中的无量化因子公式的有效性。斯坦福大学博士论文,2003年。[2] 克拉克·巴雷特和谢尔盖·贝雷辛。CVC Lite:协作有效性检查器的新实现。第16届计算机辅助验证国际会议(CAV),2004年4月。地出现。[3] G. Bruns和P. Godefroid. 3-Valued Temporal Logics的部分状态空间模型检验在Proceedings ofProceedings of 11th International Conference on Computer-Aided Verification(CAV斯普林格。[4] William M.农场主面前.丘奇的简单类型理论的部分功能版本。符号逻辑杂志,55(3):1269[5] A. Gur Finkel 和 M. 你 好 通 过 经 典 模 型 检 查 进 行 多 值 模 型 检 查 。 在 Proceedings of 14thInternational Conference on Concurrency Theory(CONCUR[6] M. Kerber和M.科尔哈塞 强Kleene逻辑对部分函数的机械化。 以. Bundy,编辑,第12届自动演绎国际会议,LNAI第814卷,第371-385页。Springer Verlag,1994年。[7] M. Kerber和M.科尔哈塞机械化的部分性,无需重新实现。第21届德国人工智能年会,LNAI第1303卷,第123Springer Verlag,1997年。[8] S. C. 克林元数学导论。New York:Van Nostrand,1952.[9] Francisca Lucio-Carrasco 和 Antonio Gavilanes-Franco 。 部 分 函 数 的 一 阶 逻 辑 。 在Proceedings STACSSpringer,1989年。[10] G. Nelson和D.奥彭通过合作决策程序简化。 ACM Transactions on Programming Languagesand Systems,1(2):245[11] N. Shankar,S. Owre和J.M. 拉什比 PVS计算机科学实验室,SRI International,MenloPark,CA,1993年。也出现在1993年4月丹麦欧登塞正式方法欧洲93年正式方法[12] R. 肖斯塔克决 定理论的组合。Journal of the Association for Computing Machinery,31(1):1[13] 亚伦·斯汤普检查有效性和证明与CVC和CVC。斯坦福大学博士论文,2002年。[14] Pawel Tichy部分类型理论的基础。《数理逻辑报告》,14:59-72,1982。
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- VMP技术解析:Handle块优化与壳模板初始化
- C++ Primer 第四版更新:现代编程风格与标准库
- 计算机系统基础实验:缓冲区溢出攻击(Lab3)
- 中国结算网上业务平台:证券登记操作详解与常见问题
- FPGA驱动的五子棋博弈系统:加速与创新娱乐体验
- 多旋翼飞行器定点位置控制器设计实验
- 基于流量预测与潮汐效应的动态载频优化策略
- SQL练习:查询分析与高级操作
- 海底数据中心散热优化:从MATLAB到动态模拟
- 移动应用作业:MyDiaryBook - Google Material Design 日记APP
- Linux提权技术详解:从内核漏洞到Sudo配置错误
- 93分钟快速入门 LaTeX:从入门到实践
- 5G测试新挑战与罗德与施瓦茨解决方案
- EAS系统性能优化与故障诊断指南
- Java并发编程:JUC核心概念解析与应用
- 数据结构实验报告:基于不同存储结构的线性表和树实现
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功