可满足公式到极小不可满足公式MU(1)的扩张复杂性

可满足合取范式（CNF）公式F到极小不可满足公式MU（1）的扩张是,对给定的CNF公式F,是否存在一个公式G满足条件var（G）包含var（F）并使得F＋G∈MU（1）。Horn公式到MU（1）公式的扩张问题可在多项式时间内解决,但对一般CNF公式F的扩张问题,至今尚未解决。这里我们将给出一个多项式时间的算法解决这一问题。     

一种结合CCgscore算法的SMT求解技术

提出了对SMT问题的另一种方法.首先,编译SMT公式并转换为CNF公式.然后充分借鉴求解SAT问题中所用的方法,把它和SMT理论相结合,借鉴在2014SAT竞赛中的CCgscore算法,得到一个满足CNF公式的解.最后把得到的当前解与T-solver进行交互并且检查其在特定理论背景下的可满足性.由于在SMT求解的过程中结合了先进的CCgscore算法,所以在求解某些SMT问题时效果比较好.     

一种增加了对称破缺的改进子集可满足性算法

为了消除子集可满足性算法在布线过程中带来运行时间增加的负面影响,提出了一种新的布线流程.针对子集可满足性算法在求解同时增加额外的变量和字句,而使得对称数量按指数级增长的问题,选用增加静态对称破缺的方法对合取范式(CNF)进行预处理,侦测并破缺其中的对称,从而达到减少搜索路径的目的.用简化图自同构的方法侦测所有对称,在增加合适的对称破缺判定(SBPs)后,限制搜索在空间的非对称领域进行,从而减少了搜索空间,而不影响CNF公式的可满足性.然后把预处理过的CNF送入布尔可满足性(SAT)解法器进行求解.试验结果表明,这种方法可以显著减少运行时间,加速求解过程.     

MXX和MARG中公式改名的复杂性

研究了判定问题“对于命题CNF公式F和H,是否存在一个变元(或文字)改名(?),使得(?)(F)=H?”的复杂性．对于极小不可满足公式的子类MAX和MARG,我们证明了:其变元改名和文字改名的复杂性等价于图同构问题GI．     

混合exactly-one约束的模型计数研究

模型计数是求给定命题公式的模型数，是人工智能领域的一个基本问题.在贝叶斯网络、有界模型检测、精确集合覆盖等众多实际问题中，存在许多exactly-one约束.常见的处理方法是将exactly-one约束编码为CNF公式，再调用模型计数器求解.这种方法扩大了命题公式的规模，容易导致求解时间过长.本文分别提出从CNF公式中还原exactly-one约束的ECR算法和处理exactly-one约束的ECP算法.ECR算法能明显提高C2D编译器的求解效率.基于最新的模型计数器ExactMC，本文改进了能识别和单独处理exactly-one约束的模型计数器ECMC.实验结果表明，ECMC的时间效率相比ExactMC有显著提高.     

一个从k-CNF到t-CNF归约的有效算法

根据极小不可满足公式的特征,对于固定的3 ≤t＜k.我们给出了一个将k-CNF公式归约到t-CNF公式的有效算法.对于给定的k-CNF公式F,t-CNF公式的转换可以在公式F的长度的线性时间内完成.     

一次性求解多个SAT问题

在实际应用中通常需要求解对应CNF(Conjunctive Normal Form)公式之间仅相差几个子句的一系列SAT(Satisfiability Problem)问题,但目前绝大多数SAT求解算法都是针对单一SAT问题设计的。为此,基于DPLL提出了nDPLL算法,并在随机问题上对该算法的效率进行测试。实验结果表明,nDPLL算法能一次性求解多个SAT问题,对于特定范围的CNF公式集具有较高的效率,CNF公式集的规模越大、相近因子越高、子句数和变量数的比值越大,则nDPLL算法的效率越高。     

迁移系统关于一类时态逻辑公式的满足度

从分析Words(φ)的结构入手,引入用线性时态逻辑(LTL)公式φ表示的规范的特征概念,证明了一类LTL公式特征的存在性定理以及特征的计算方法.引入了LTL公式的T-范式概念,证明了这类LTL公式均可等价地表示为T-范式的形式,从而为简化φ的特征计算奠定了基础.引入了迁移系统TS关于给定规范φ的满足度概念,证明了TS关于φ的满足度等于1当且仅当TS满足φ.对于给定的原子公式集AP,给出了满足度计算的复杂度估计.     

Taylor公式及其余项的证明

Taylor公式作为高等数学中的重要内容,是一元函数微分学中非常重要的公式之一.Taylor公式可以解决很多数学方面的具体问题,因此对Taylor公式的研究具有非常大的理论价值和实际应用意义.本文首先从Taylor公式的一般型出发,在理解泰勒公式基本含义的基础上,对Taylor公式一般型进行了一系列的推导,分别得到了Peano、Lagrange以及积分三种不同形式的余项,并对其科学性进行了详细的证明,从而进一步加深对Taylor公式的理解以及对函数性态的研究,形成发散性思维.     

量化单一带标公式的消解

在引入量化单一带标公式的概念后,给出其消解算法,并证明该消解算法是健全的和拒绝性完备的。因此该算法可用于对量化单一带标公式进行理论上的研究,同时也可用于在实际应用中解决这类公式的可满足性问题。最后,根据消解算法,得出一个可以在多项式时间内判定可满足性的量化单一带标公式的子类。     

命题公式真值表的生成与公式类型的机械判定

在文[1]的基础上,给出了命题逻辑中任一命题公式的真值表的生成算法与命题公式类型的判定算法,实现了利用计算机对有限多个命题公式的真值表的直接计算和输出,以及对一个命题公式是重言式、矛盾式或可满足式的机械判定.     

不可满足公式的完备证明系统

合取范式(CNF)公式H到F的同态是一个从H的文字集合到F的文字集合的映射、并保持补运算和子句映到子句。同态映射保持一个公式的不可满足性。一个公式是极小不可满足的是指公式不可满足而且从中删去任一个子句后得到的公式可满足。MU(1)是子句数与变元数的差等于1的极小不可满足公式类。S．Szeider证明了：每个不可满足公式F是MU(1)中某个公式日的同态像。从而，基于MU(1)的同态证明系统与树消解证明系统是p-等价的。MU(1)中的公式可以用基础矩阵表示，本文用基础矩阵的方法证了同态证明系统ПMU（1）的完备性。     

量子力学中的守恒量

文章论述了量子力学中的守恒量与对称性的关系,具体讨论了空间平移不变性与动量守恒、空间转动不变性与角动量守恒、时间平移不变性与能量守恒的关系.     

极小蕴涵和析取范式表示

析取范式的极小表示是命题逻辑和计算机科学理论中的一个重要问题．本文研究了在若干极小标准下的蕴涵和析取范式表示的一些性质,并阐述了极小蕴涵和极小析取范式表示在模型检测中的应用．     

解 packing 及 CNF-SAT 问题的拟物拟人方法

提出拟物拟人方法．论述了如何按此种方法为ＮＰ难问题设计出高效实用的快速求解算法．作为例证，所得出的关于ＣＮＦ－ＳＡＴ问题及ｐａｃｋｉｎｇ问题的算法，其先进性在国际竞赛及工业生产中得到了显示．     

代换定理的证明及其应用

本文给出了代换定理的优于文献[1]的证明方法,并把代换定理与其他定理结合,构造了一个判定DNF表达式永真性的算法,使代换定理得到实际应用。     

基于CNF权重学习求解3-SAT问题的进化算法

SAT（Satisfiability）可满足性问题研究具有很广的应用价值,是计算机和人工智能领域内的一个重要问题,也是第一个被证明为NP完全的问题。随着对SAT问题的深入研究,已经提出了很多高效的算法,其中随机算法（WalkSAT）、进化算法等启发式算法是今年来研究的热点。进化算法是遗传算法的一种,通过对生物组织进化的学习,形成的一种高效算法。针对CNF（Coniecture Normal Formula）权重和生物进化算法相结合,提出一种有效求解难SAT问题的不完全算法WOSAT．