作为当前自动定理证明器中常用的推理机制,传统基于二元演绎超归结方法的推理过程限定每次有且只有2个子句参与演绎,这种分离的演绎步骤导致演绎缺失导向性和预判性,演绎效率有待提升。为了提升演绎效率,在理论上,针对传统的超归结方法...作为当前自动定理证明器中常用的推理机制,传统基于二元演绎超归结方法的推理过程限定每次有且只有2个子句参与演绎,这种分离的演绎步骤导致演绎缺失导向性和预判性,演绎效率有待提升。为了提升演绎效率,在理论上,针对传统的超归结方法引入多元演绎思想,提出矛盾体分离超演绎定义和方法,它具有多元性、动态性和导向性的演绎特性;在算法实现中,考虑子句参与演绎具有多元和协同特性,并灵活设定演绎的条件,提出一种具有回溯机制的矛盾体分离超演绎算法。将所提算法应用于Eprover3.1证明器,以国际自动定理证明器2023年竞赛例和TPTP(Thousands of Problems for Theorem Provers)问题库中难度系数为1的问题作为测试对象,在300 s内,应用所提算法的Eprover3.1证明器比原始Eprover3.1多证明了15个定理;当测试相同数量的定理时,所提算法的平均证明时间缩减了1.326 s,能够证明7个难度系数为1的定理。测试结果表明,所提算法能有效地应用于一阶逻辑自动定理证明,提升自动定理证明器的证明能力和效率。展开更多
The traditional program refinement strategy cannot be refined to an executable program,and there are issues such as low verification reliability and automation.To solve the above problems,this paper proposes a nonline...The traditional program refinement strategy cannot be refined to an executable program,and there are issues such as low verification reliability and automation.To solve the above problems,this paper proposes a nonlinear program construction and verification method based on partition recursion and Morgan’s refinement rules.First,we use recursive definition technique to characterize the initial specification.The specification is then transformed into GCL(Guarded Command Language)programs using loop invariant derivation and Morgan’s refinement rules.Furthermore,VCG(Verification Condition Generator)is used in the GCL program to generate the verification condition automatically.The Isabelle theorem prover then validates the GCL program’s correctness.Finally,the GCL code generates a C++executable program automatically via the conversion system.The effectiveness of this method is demonstrated using binary tree preorder traversal program construction and verification as an example.This method addresses the problem that the construction process’s loop invariant is difficult to obtain and the refinement process is insufficiently detailed.At the same time,the method improves verification process automation and reduces the manual verification workload.展开更多
文摘作为当前自动定理证明器中常用的推理机制,传统基于二元演绎超归结方法的推理过程限定每次有且只有2个子句参与演绎,这种分离的演绎步骤导致演绎缺失导向性和预判性,演绎效率有待提升。为了提升演绎效率,在理论上,针对传统的超归结方法引入多元演绎思想,提出矛盾体分离超演绎定义和方法,它具有多元性、动态性和导向性的演绎特性;在算法实现中,考虑子句参与演绎具有多元和协同特性,并灵活设定演绎的条件,提出一种具有回溯机制的矛盾体分离超演绎算法。将所提算法应用于Eprover3.1证明器,以国际自动定理证明器2023年竞赛例和TPTP(Thousands of Problems for Theorem Provers)问题库中难度系数为1的问题作为测试对象,在300 s内,应用所提算法的Eprover3.1证明器比原始Eprover3.1多证明了15个定理;当测试相同数量的定理时,所提算法的平均证明时间缩减了1.326 s,能够证明7个难度系数为1的定理。测试结果表明,所提算法能有效地应用于一阶逻辑自动定理证明,提升自动定理证明器的证明能力和效率。
基金Supported by the National Natural Science Foundation of China(62262031)Science and Technology Key Project of Education Department of Jiangxi Province(GJJ2200302,GJJ210307)the Graduate Innovative Special Fund Projects of Jiangxi Province(YJS2022064)
文摘The traditional program refinement strategy cannot be refined to an executable program,and there are issues such as low verification reliability and automation.To solve the above problems,this paper proposes a nonlinear program construction and verification method based on partition recursion and Morgan’s refinement rules.First,we use recursive definition technique to characterize the initial specification.The specification is then transformed into GCL(Guarded Command Language)programs using loop invariant derivation and Morgan’s refinement rules.Furthermore,VCG(Verification Condition Generator)is used in the GCL program to generate the verification condition automatically.The Isabelle theorem prover then validates the GCL program’s correctness.Finally,the GCL code generates a C++executable program automatically via the conversion system.The effectiveness of this method is demonstrated using binary tree preorder traversal program construction and verification as an example.This method addresses the problem that the construction process’s loop invariant is difficult to obtain and the refinement process is insufficiently detailed.At the same time,the method improves verification process automation and reduces the manual verification workload.
