处理指针相等关系不确定的指针逻辑

为类C小语言PointerC设计的指针逻辑是Hoare逻辑的一种扩展,可用来对指针程序进行精确的指针分析,以支持指针相等关系确定的程序的安全性验证.通过增加相等关系不确定的指针类型访问路径集合,可扩展这种指针逻辑,使得扩展后的指针逻辑可以应用于有向图等指针相等关系不确定的抽象数据结构上的指针程序性质　证明.     

一种汇编语言指针逻辑的设计与实现

软件的安全性日益重要,软件满足安全策略的证明方法成为一个研究热点.而指针程序的安全性质证明是难点之一.根据已经提出的安全程序设计与证明的框架以及PointerC指针逻辑,提出一种汇编语言指针逻辑.该逻辑解决了Hoare逻辑处理别名问题面临的困难,保证通过验证的汇编指针程序不存在空指针引用和内存泄露等安全问题.此逻辑的可靠性证明已在证明辅助工具Coq中完成.此外,本文还实现一个原型系统,并使用该系统对链表、二叉树等非平凡的指针程序的进行了自动的安全验证.     

一个程序验证器的设计和实现

形式验证是提高软件可信程度的重要方法,基于逻辑推理对程序性质进行严格的自动证明是当前的研究热点,但尚无可供工业界使用的产品,其根源在于自动定理证明方面的困难.介绍在通过程序分析建立起各程序点的形状图的基础上,如何利用形状图提供的信息来支持程序验证的方法.提出一种利用形状图信息来消除访问路径别名,使得指针程序中非指针部分的性质仍然可以用Hoare逻辑来进行验证的方法,并证明了该方法的可靠性.还提出一种在不使用自定义谓词的情况下,易变数据结构上数据性质的描述和验证方法.另外,介绍所设计并实现的基于上述方法的PointerC语言的程序验证器的原型.它不仅能自动验证操作易变数据结构程序的性质,也能自动验证使用一维数组的程序的性质.     

一种用于指针程序安全性证明的指针逻辑

在高可信软件的各种性质中,安全性是被关注的重点,其中软件满足安全策略的证明方法是研究的热点之一.文中根据作者所设想的安全程序的设计和证明框架,为类C语言的一个子集设计了一个指针逻辑系统.该逻辑系统是Hoare逻辑系统的一种扩展,它用推理规则来表达每一种语句引起指针信息的变化情况.它可用来对指针程序进行精确的指针分析,所获得的信息用来证明指针程序是否满足定型规则的附加条件,以支持程序的安全性验证.该逻辑系统也可用来证明指针程序的其它性质.     

一个出具证明编译器后端的设计与实现

设计并实现一个类C语言PointerC的出具证明编译器后端。该后端采用最强后条件演算同步处理整型断言和指针断言实现整型验证条件和指针验证条件的证明,能够完全自动地产生目标级程序的指针安全性证明,处理常见递归数据结构中的非一致性别名问题。后端包括独立的定理检查器,能够检验携证明代码的完整性。     

时序逻辑语言XYZ/E中指针的形式化表示与验证

指针是一种重要的数据类型,使用指针能使程序更加有效和优美.可是指针却以不易驾御而闻名,至今在时序逻辑语言中未见到对它的形式化工作.XYZ/E既是一个时序逻辑系统也是一个程序设计语言,它能表示普通高级语言中几乎所有的重要机制.本文主要讨论在时序逻辑语言XYZ/E中指针的形式化表示问题以及在结构化XYZ/SE程序中指针的验证问题.     

一个用于指针程序验证的自动定理证明器的设计与实现

对高可信软件需求的增加使得指针程序的验证成为近期的研究热点.指针逻辑作为Hoare逻辑的扩展,可以对指针程序进行精确的分析.介绍一个针对指针逻辑的自动定理证明器的设计和实现,描述了一些算法.实验结果表明,该定理证明器可以完全自动的证明用类C语言编写的关于单链表,双链表和二叉树的指针程序的验证条件,并生成机器可检查的证明.     

一种汇编程序的形式验证框架

在高可信软件的各种性质中,安全性是关注的重点.软件满足安全策略的证明方法是安全性研究的热点之一.根据前期提出的安全程序设计与证明的框架以及指针逻辑推理系统,介绍在所实现的出具证明编译器(certifying compiler)原型系统中有关目标机器的形式定义、汇编程序的形式验证框架以及汇编程序指针程序性质证明等方面的研究.它们的主要特点是汇编验证框架是基于Hoare风格的程序验证方式;与指针有关的性质使用和源语言一级类似的指针逻辑推理系统进行证明;使用一个简单的类型系统完成有关指针的类型检查.     

断言语言支持自定义谓词的程序验证器原型

基于逻辑推理的方法进行程序验证是形式化程序验证的研究热点.目前的自动验证工具为了保证自动性,对描述程序性质的断言语言都有较多限制,导致程序的某些递归性质难以用断言语言表述.本文在一个面向指针程序、基于先前自行设计的形状图逻辑、依赖于自动定理证明工具Z3的自动程序验证原型系统上,通过在断言语言中引入自定义谓词来增强断言语言的表达能力,使得该原型系统不仅能自动验证含操作易变数据结构的程序的性质,也能自动验证一些不含指针的程序的性质.     

二维逻辑PPTLSL的可满足性检查

由于指针的灵活性以及别名现象的存在,程序的运行可能会出现悬空指针引用、内存泄漏等诸多问题.PPTLSL是一种二维(时间和空间)时序逻辑,它结合了分离逻辑(Separation Logic)与命题投影时序逻辑PPTL(Propositional Projection Temporal Logic),能够描述和验证操作链表的指针程序的时序性质.本文简要回顾了PPTLSL的相关理论,并详细介绍工具SAT-PPTLSL的工作原理.该工具主要利用PPTLSL与PPTL之间构建起来的“同构”关系进行PPTLSL公式的可满足性检查.此外,本文结合一些实例展示了SAT-PPTLSL的执行过程,并通过实验分析了关键参数对SAT-PPTLSL执行效率的影响.     

The Nature of Nonmonotonic Reasoning

Conclusions reached using common sense reasoning from a set of premises are often subsequently revised when additional premises are added. Because we do not always accept previous conclusions in light of subsequent information, common sense reasoning is said to be nonmonotonic. But in the standard formal systems usually studied by logicians, if a conclusion follows from a set of premises, that same conclusion still follows no matter how the premise set is augmented; that is, the consequence relations of standard logics are monotonic. Much recent research in AI has been devoted to the attempt to develop nonmonotonic logics. After some motivational material, we give four formal proofs that there can be no nonmonotonic consequence relation that is characterized by universal constraints on rational belief structures. In other words, a nonmonotonic consequence relation that corresponds to universal principles of rational belief is impossible. We show that the nonmonotonicity of common sense reasoning is a function of the way we use logic, not a function of the logic we use. We give several examples of how nonmonotonic reasoning systems may be based on monotonic logics.     

逻辑函数的双逻辑综合与优化

针对传统布尔逻辑在电路面积优化中存在的不足,提出了一种用传统布尔逻辑和Reed-Muller(RM)逻辑相结合的双逻辑优化算法.通过将原逻辑函数的乘积项转化为不相交乘积项,并利用不相交乘积项的位操作,将逻辑函数的覆盖分成2个部分,使之分别适合布尔逻辑综合和RM逻辑综合;同时提出了适合双逻辑函数的逻辑功能验证方法.双逻辑优化算法用C语言编程实现并用MCNC标准电路进行测试.实验结果表明,与单一的布尔逻辑综合结果相比,在绝大多数情况下文中算法可使电路面积获得进一步优化.     

基于四值语义的缺省逻辑

基于公式变换,给出一组缺省理论的变换方法,将命题语言L中的缺省理论变换到对应的命题语言L^-＋中,保证了所得到的缺省理论的所有扩张均不平凡,并通过一种弱变换可同时保证缺省扩张的存在性．为缺省理论定义了各种四值模型,使得缺省逻辑具有非单调超协调推理能力,并证明了L^-＋中的缺省扩张与L中缺省理论的四值模型之间具有一一对应关系．四值模型描述了公式变换的语义,基于四值语义的缺省推理通过缺省理论的变换技术能在标准的缺省逻辑中实现．     

Intuitionistic hybrid logic: Introduction and survey

Intuitionistic hybrid logic is hybrid modal logic over an intuitionistic logic basis instead of a classical logical basis. In this short paper we introduce intuitionistic hybrid logic and we give a survey of work in the area.     

超协调限制逻辑

本文给出了一阶超协调限制逻辑ＬＰｓ的定义，并证明了它与悖论逻辑（ＬＰ与ＬＰｍ）和限制逻辑（ＣＩＲＣ）的关系，ＬＰ作为一种非单调超协调逻辑具有非单逻辑和超协调逻辑的优点，而用能解决非单调逻辑和超协调逻辑存在的问题，它可作为在不完全与不协调知识下常识推理的形式化，因此它的知识表示中具有广泛的应用。     

Naming Worlds in Modal and Temporal Logic

In this paper we suggest adding to predicate modal and temporal logic a locality predicate W which gives names to worlds (or time points). We also study an equal time predicate D(x, y)which states that two time points are at the same distance from the root. We provide the systems studied with complete axiomatizations and illustrate the expressive power gained for modal logic by simulating other logics. The completeness proofs rely on the fairly intuitive notion of a configuration in order to use a proof technique similar to a Henkin completion mixed with a tableau construction. The main elements of the completeness proofs are given for each case, while purely technical results are grouped in the appendix. This revised version was published online in August 2006 with corrections to the Cover Date.     

概率逻辑、不确定逻辑和模糊逻辑之比较

通过一个实例分析比较了概率逻辑、主观概率逻辑、不确定逻辑和模糊逻辑的思想方法。提出了自己的观点：基于数据统计的概率逻辑是最科学的。不确定逻辑比主观概率逻辑更科学。当具有不确定性的原子命题具有独立性时,不确定逻辑和模糊逻辑的观点是一致的。而对于处理带有不确定性的相关性命题,不确定逻辑比模糊逻辑更科学。但是模糊逻辑在建立推理理论方面见长。     

Temporal Languages for Epistemic Programs

This paper adds temporal logic to public announcement logic (PAL) and dynamic epistemic logic (DEL). By adding a previous-time operator to PAL, we express in the language statements concerning the muddy children puzzle and sum and product. We also express a true statement that an agent’s beliefs about another agent’s knowledge flipped twice, and use a sound proof system to prove this statement. Adding a next-time operator to PAL, we provide formulas that express that belief revision does not take place in PAL. We also discuss relationships between announcements and the new knowledge agents thus acquire; such relationships are related to learning and to Fitch’s paradox. We also show how inverse programs and hybrid logic each can be used to help determine whether or not an arbitrary structure represents the play of a game. We then add a past-time operator to DEL, and discuss the importance of adding yet another component to the language in order to prove completeness.     

人工智能中概率逻辑的研究

概率论是在不完备的、不确定的数据中进行推理的,它是度量不确定性的重要手段。在人工智能中,研究者结合概率和逻辑各自的优点,进行概率逻辑的研究。本文介绍了传统概率逻辑的三大派别,阐述了二值逻辑概率和三值逻辑概率的发展;最后介绍了泛逻辑,通过对概率逻辑和泛逻辑学的研究,将概率逻辑纳入泛逻辑学的框架内。     

Mediative fuzzy logic: a new approach for contradictory knowledge management

In this paper we are proposing a novel fuzzy method that can handle imperfect knowledge in a broader way than Intuitionistic (in the sense of Atanassov) fuzzy logic does (IFL). This fuzzy method can manage non- contradictory, doubtful, and contradictory information provided by experts, providing a mediated solution, so we called it Mediative Fuzzy Logic (MFL). We are comparing results of MFL, with IFL and traditional Fuzzy logic (FL).