由一阶逻辑公式得到命题逻辑可满足性问题实例

命题逻辑可满足性(SAT)问题是计算机科学中的一个重要问题.近年来许多学者在这方面进行了大量的研究,提出了不少有效的算法.但是,很多实际问题如果用一组一阶逻辑公式来描述,往往更为自然.当解释的论域是一个固定大小的有限集合时,一阶逻辑公式的可满足性问题可以等价地归约为SAT问题.为了利用现有的高效SAT工具,提出了一种从一阶逻辑公式生成SAT问题实例的算法,并描述了一个自动的转换工具,给出了相应的实验结果.还讨论了通过增加公式来消除同构从而减小搜索空间的一些方法.实验表明,这一算法是有效的,可以用来解决数学研究和实际应用中的许多问题.     

基于n-值(L)ukasiewicz命题逻辑的概率计量化推理系统

通过把n-值Lukasiewicz命题逻辑中公式的概率真度函数抽象为模态词,把概率真度函数的基本恒等式抽象为关于模态词的公理,建立一个模态化的形式推理系统,构建其语构理论及语义理论,证明该系统关于概率真度函数的完备性定理,从而为概率计量逻辑奠定逻辑基础.     

具有三种否定的模糊命题逻辑形式系统FLCOM的λ-归结

考虑到模糊逻辑中定理自动证明的重要性以及目前主要研究具有一种否定的模糊逻辑的归结原理,文中对具有三种否定(矛盾否定、对立否定和中介否定)的模糊命题逻辑(FLCOM)的归结原理进行研究.基于FLCOM的一种无穷值语义解释提出λ-可满足的和λ-不可满足的概念.将λ-归结方法引入FLCOM,给出FLCOM的λ-归结演绎定义,讨论FLCOM的λ-归结原理,并证明FLCOM的λ-归结方法的完备性.基于λ-归结方法和已证明的结论给出实例以佐证文中λ-归结方法和结论的正确性和可行性.因此,在FLCOM范围内可判定任一模糊命题公式是否是λ-可满足的或λ-不可满足的.     

中介命题演算系统MP^M的公理完备集

本文基于中介逻辑命题演算系统MP^M构造了一个公理集合，证明了该公理集合的完备性。该公理集合中的公理均是由等式的形式给出，可以方便地对MP^M、MF^M系统上的等值公式进行推导和证明。本文还讨论了该公理集合在不完全信息数据库查询优化上的应用。     

基于n-值ukasiewicz命题逻辑的概率计量化推理系统

通过把n-值ukasiewicz命题逻辑中公式的概率真度函数抽象为模态词,把概率真度函数的基本恒等式抽象为关于模态词的公理,建立一个模态化的形式推理系统,构建其语构理论及语义理论,证明该系统关于概率真度函数的完备性定理,从而为概率计量逻辑奠定逻辑基础.     

实例化空间:一种新的安全协议验证逻辑的语义模型

给出了一个称为“实例化空间（instantiation space）”的安全协议验证逻辑的语义模型．该语义模型是建立在一种自然的加密信息交换（cryptographical message exchange）模型上的．在此语义模型基础上，文章提出了一系列与安全属性相关的验证公理，由此可以证明它们在此语义模型下的正确性．更重要的是，在此语义下的公理集在算法上是完全可以实现的，其对应的工具SPV（Security Protocol Verifier）已经开发成功，并且可以验证复杂的协议．在这套安全协议验证模型理论下，可以很方便地处理包括公钥、私钥、共享密钥和Hash函数组成的复杂信息格式．而且，在此语义基础上的公理集是纯命题逻辑的，因此所需要的验证目标可以很方便地转化成可满足性问题（SAT），从而可以利用工业上快速高效的SAT求解器实现．     

命题模态逻辑的模型构造和完备性证明

模态逻辑是研究必然、可能及其相关概念的逻辑。模态公式的可满足性问题和证明系统的完备性问题是模态逻辑中的两个经典的问题。为了解决这两个问题,提出一个构造模态公式的canonical model的方法。通过这个方法,对于给定模态公式φ,如果φ是可满足的,可以得到φ的一个canonical model;如果φ是不可满足的,可以得到φ的证明。此外,还给出命题模态逻辑完备性的一个构造性证明方法。     

模态逻辑中的(n)真度理论与和谐定理

首次在模态逻辑中通过有限模型建立了模态公式的(n)真度理论,得到了当模态词不出现时(n)真度与经典二值命题逻辑中的真度保持一致的和谐定理.研究了时态逻辑中命题的(n)真度随n变化的性态.提出了模态公式间的(n)相似度理论,并由此在全体公式之集中建立了(n)伪距离.得出了(n)模态逻辑度量空间,该空间以经典逻辑度量空间为子空间,从而可将经典命题逻辑中的近似推理理论推广到模态逻辑之中.     

命题公式真值表的生成算法

真值表是命题逻辑理论中的一个重要概念,利用它可以求命题公式的主范式、判定命题公式的类型以及进行命题逻辑的推理等。本文给出了任意命题公式真值表的生成算法,为利用计算机解决命题逻辑中的其它问题奠定了基础.     

社会认识优化在非线性规划问题中的应用

社会认识优化(Society Cognitive Optimization,SCO)是一种基于社会认知理论提出的模拟人类社会的演化算法.社会认识优化是通过竞争选择和领域搜索来模拟社会认知理论中的社会学习能力,用代理来代表社会中的人,用知识库来代表社会中的知识,通过代理与知识库之间不断的交互来模拟人类的社会学习过程,从而达到优化学习的目的.命题逻辑中合取范式的可满足性(Satisfyability,SAT)问题是当代理论计算机科学的核心问题,是一典型的NP完全问题.可满足性问题的有效解决有着重要的理论意义和实际应用价值.文中将社会认识优化算法应用于求解可满足性问题,得到了比较满意的结果.     

语义网的一阶逻辑推理技术支持

研究了一阶逻辑推理工具对语义网的推理支持.语义网的关键推理问题可以化为公式的可满足性判定问题.一阶逻辑的自动定理证明器可以证明不可满足性,而有限模型查找器为可满足的公式在有限域内构造模型.提出在语义网的推理中,同时使用定理证明器和有限模型查找器.实验结果表明,这样可以解决描述逻辑工具的不足,并可以弥补定理证明器对可满足的公式推理的不完备性.     

QBF求解算法研究综述

近10年来,布尔可满足性(SAT)求解技术飞速发展,并已经成功应用于模型检验、定理证明等领域,特别是在限界模型检验(BMC)中取得了明显的进展,然而,由于命题逻辑公式的长度随系统规模指数倍增长,基于SAT的模型检验仍然存在状态空间爆炸问题.带量词的布尔公式(QBF)作为SAT公式的自然扩展,具有紧凑的空间结构、更强大、更直观的表达能力,能够简洁地描述模型检验中的公式.基于QBF的模型检验有希望缓解状态空间爆炸问题,成为当前研究的一个热点.总结了当前主流的QBF求解算法及常用的优化技术,指出了该领域中值得关注的新趋势.     

一阶逻辑中约束求解的局部搜索法*

以一阶谓词逻辑为基础,讨论约束满足问题.着重研究一阶逻辑公式可满足性的局部搜索法,并与命题逻辑中的可满足性过程加以比较.以皇后问题和哈密顿回路问题为例,说明基于一阶逻辑的方法能处理较大的问题实例.     

可满足性问题全部解的求解算法

SAT问题在人工智能、计算机基础理论研究和人工智能等领域有着广泛的应用,近年来,证明该问题的可满足性取得了巨大的成功,但在求出SAT问题的所有解方面还有待进一步研究。利用一个简单的变换,将可满足性（SAT）问题转化为多项式形式,然后根据命题逻辑的性质以及多项式的性质,得到一个求解出SAT问题所有解的算法。实验结果显示该算法是有效和可行的。     

相干命题逻辑自然推理系统NR的自动证明*

给出了相干命题逻辑自然推理系统NR的自动证明算法。首先将待证命题公式A的子公式组成一个初始集合P,对其中的元素采用系统NR的推理规则得到新的命题公式加入P,当得到秩为0的A时命题得证;然后对A的证明树进行整理即得到演绎序列。对系统NR的大部分定理证明取得了良好的效果,算法生成的演绎序列清晰可读,接近手工推理。     

国家知识基础设施中的数学知识表示

数学知识表示是知识表示中的一个重要方面,是数学知识检索、自动定理机器证明、智能教学系统等的基础.根据在设计NKI(national knowledge infrastructure)的数学知识表示语言中遇到的问题,并在讨论了数学对象的本体论假设的基础上提出了两种数学知识的表示方法:一种是以一个逻辑语言上的公式为属性值域的描述逻辑;另一种是以描述逻辑描述的本体为逻辑语言的一部分的一阶逻辑.在前者的表示中,如果对公式不作任何限制,那么得到的知识库中的推理不是可算法化的;在后者的表示中,以描述逻辑描述的本体中的推理是可算法化的,而以本体为逻辑语言的一部分的一阶逻辑所表示的数学知识中的推理一般是不可算法化的.因此,在表示数学知识时,需要区分概念性的知识(本体中的知识)和非概念性的知识(用本体作为语言表示的知识).框架或者描述逻辑可以表示和有效地推理概念性知识,但如果将非概念性知识加入到框架或知识库中,就可能使得原来可以有效推理的框架所表示的知识库不存在有效的推理算法,甚至不存在推理算法.为此,建议在表示数学知识时,用框架或描述逻辑来表示概念性知识;然后,用这样表示的知识库作为逻辑语言的一部分,以表示非概念性知识.     

逻辑系统NMG 的满足性和紧致性

紧致性是模糊逻辑的一个重要性质.现已经证明?ukasiewicz 命题逻辑、G?del 命题逻辑、乘积命题逻辑和形式系统L^*都是紧的.通过刻画逻辑系统NMG 中的极大相容理论和证明NMG 的满足性,进而证明了NMG也是紧的.     

G-逻辑及其归结推理

该文提出了一种粒-逻辑，简记为G-逻辑，并构造了这种逻辑的近似推理系统，定义了G-公式、G-子句和G-文字，提出了这种逻辑的G-归结方法．G-归结的完备性定理也被证明了．这种逻辑公式的结构是有序二元对，第一元是断言；第二元是对应于这个断言的可定义集或不可定义域集的近似集．这种逻辑是定义在信息系统IS=(U，A)上，所以其公式中的个体变量被赋予U上的实体．公式中的命题或谓词被解释为属性集A上的属性，因此命题或谓词的意义集是U上的一个子集、属性及其意义集一起构成的二元对，被称做一个基本粒(granule)．而这种基本粒被当做这种逻辑中的一个G-原子，用G逻辑联结词组合这些G-原子便得到这种逻辑中的G-公式．公式的可满足性是其相应断言的意义集不空．当这种公式的定义域集不可定义时，则可将它移到其定义域集的Rough下和上近似集上去讨论．G-逻辑的提出为经典逻辑的应用开辟了新途径，也为处理非规范知识提供了较好的理论工具．G-逻辑的运算涉及整体到局部的分解和局部到整体的合并，以此提供了AI中问题求解的新思路．G-逻辑也是Rough逻辑的新扩充，其真值概念及其运算都不同于经典逻辑，也不同于其它非标准逻辑．这种逻辑中的演算既是逻辑的，又是集合论的．于是当处理真值及其运算时适合使用逻辑方法；而处理归结中的文字合一时可用集合论方法，这样可避免复杂的文字合一计算．最后，用实例说明了这种逻辑的G-归结方法的可行性和有效性，并给出了G-逻辑中机器定理证明的相关定理，讨论了G-归结反演的完备性和完全性．     

基于SAT工具的限界模型检测归约方法

限界模型检测主要对路径上的属性进行检测,基于此给出一种编码方法,将LTL公式在路径上展开,从而将限界模型检测转换为命题逻辑的可满足性问题,使用SAT求解工具来完成模型检测过程。阐述归约过程的正确性与完全性,通过一个具体例子证明了该方法的有效性。     

命题逻辑提升到一阶逻辑上的子句消去方法

在基于命题逻辑的可满足性问题（SAT）求解器和基于一阶逻辑的定理证明器上，子句集简化一直是必不可少的步骤，而其中子句消去方法在这些子句集简化方法中是非常重要的组成部分。将命题逻辑中的子句消去方法归结隐藏恒真消去方法（RHTE）和归结隐藏包含消去方法（RHSE）提升到一阶逻辑上，并且利用蕴含模归结原则（IMR）证明了这种提升方式在一阶逻辑上具有可靠性（Soundness），即依据这两种子句消去方法删除一阶逻辑公式集中的子句，并不会改变公式集的可满足性或者不可满足性。此外，将这两个方法与一阶逻辑子句消去方法锁子句消去方法（BCE）和归结包含消去方法（RSE）进行组合推广，发展得到一阶逻辑上新型子句消去方法（BC+RHS）E、（RS+RHT）E和（RHS+RHT）E，并且证明了这3种子句消去方法在一阶逻辑上的可靠性。最后，分析比较了这些子句消去方法的有效性，并且证明了这3种新型子句消去方法比组成它们的原始子句消去方法均具有更高的有效性。