AN APPROXIMATELY FAST ALGORITHM FOR DECIDING THE VALIDITY OF DISJUNCTIVE NORMAL FORMS (DNFs)

The NP-complete problems have been shown to be hard problems in the theory of computational complexity. They include many problems of great significance both in theory and in practice. If there is a fast (in the sense of polynomial time) algorithm for the dual problem of an NP-complete problem, then there are fast algorithms for all. But so far,

从合取范式到析取范式的转换研究

为了解决粗糙集分辨函数的计算、概念格中内涵缩减的计算、逻辑程序设计的规则简化等问题,抽象出了从合取范式到析取范式转换这一核心问题。提出了利用极小覆盖来实现从合取范式到析取范式的转换,给出了一个增量式的算法。为了扩大范式转换的使用范围,定义了伪合取范式,并给出伪合取范式到析取范式的转换方法。

两类动态信息规律模型及其在信息伪装、风险识别中的应用

函数P-集合是P-集合的函数形式,是通过改进P-集合得到的一个具有动态特征、规律(函数)特征的信息规律模型。在函数P-集合中,函数的属性满足数理逻辑中的合取范式。函数逆P-集合是函数P-集合的对偶模型,在函数逆P-集合中,函数的属性满足数理逻辑中的析取范式。这里定义函数P-集合是一类动态信息规律模型,定义函数逆P-集合是另一类动态信息规律模型;在函数P-集合与函数逆P-集合的结构、动态特征与它们的属性范式特征的基础上,给出函数P-集合在信息图像拼接与伪装中的简单应用,以及函数逆P-集合在商品利润的风险估计-识别中的简单应用。函数P-集合、函数逆P-集合是关于动态信息规律应用研究的新理论、新模型。

双枝模糊逻辑

在双枝模糊集基础上,建立了双枝模糊逻辑的框架,这是对单枝模糊逻辑的合理扩展。从双枝模糊命题入手,给出双枝模糊逻辑的性质和双枝模糊逻辑公式,以及双枝模糊逻辑的析取范式与合取范式。这些结果为研究双枝模糊推理和双枝模糊控制奠定了基础。

基于Skowron分明矩阵的快速约简算法

属性约简是Rough集理论的核心内容之一,计算所有的属性约简已经被证明是NP完全问题。本文基于分而自治思想,在Skowron分明矩阵法的基础上,给出了最小析取范式的判定定理,从而提出了计算所有属性约简的算法。理论分析和实验结果表明,该约简算法在效率上较现有的算法有显著提高。

Rough Set规则自动生成的关键算法改进

基于RoughSet理论,研究从Skrowon分辨矩阵到规则自动生成过程中的关键算法的改进问题。提出由分辨矩阵到合取项矩阵的计算方法,建立了从属性约简的合取项矩阵到析取项矩阵转换的数学模型,基于数学模型,提出直接搜索的转换方法。同时,提出了属性值约简的改进方法,使得改进后的算法从总体上节省了运算空间,降低了算法的时间复杂性,提高了规则生成的效率。最后通过UCI数据库的实例验证了改进算法的有效性。

对于析取范式构造的进一步分析

本文考虑具有优先代表资格的ＮＰ完全问题的对偶问题——析取范式永真性判定问题．本文从构造的角度对析取范式作了分析，得出了如下结果：在由ｎ个确定的命题变元所可能构成的一切不含均覆盖的析取范式中，含有三角式的析取范式占绝大多数．基于这个结果，本文得出了一个求解析取范式永真性判定问题的近似快速算法．

双枝模糊逻辑(II)

在双枝模糊集基础上,通过对单枝模糊逻辑的合理扩展,建立了双枝模糊逻辑的框架。从双枝模糊命题入手,给出双枝模糊逻辑的性质和双枝模糊逻辑公式,以及双枝模糊逻辑的析取范式与合取范式。这些结果为研究双枝模糊推理和双枝模糊控制奠定了基础。

属性约简中的范式转换算法研究

通过研究属性约简中合取范式到析取范式的转换过程,发现减少冗余项和重复计算可以适当提高转换效率。同时考虑到范式的动态变化,设计一种边转换边化简的增量转换算法,可以利用已有结果直接进行计算。对于减量情况,抽象出范式转换的数学模型,给出相应转换的构造形式和分析过程,并提出一种近似减量转换算法,从而实现了不同变化情况下生成析取范式的动态计算。最后通过仿真实验验证了算法的可行性和高效性。

基于多线程技术的分辨函数析取范式生成算法

基于分辨矩阵计算信息系统的所有约简,都需要将合取范式转化为析取范式,但是该转化过程存在组合爆炸问题。为解决该问题,根据合取范式、合取运算和析取运算的特点,构建析取范式转化的并行模型,提出基于多线程技术的分辨函数析取范式生成算法,利用Windows的自动线程调度功能提高范式转换的效率。实验结果表明,该算法的析取范式转化效率会随着合取范式长度的增加而提高,适合在多核CPU计算机上运行。

异构空间数据系统查询分解算法的研究

介绍了利用析取范式进行查询分解的算法,该分解方法在语义分析和规范化的基础上,对查询语句进行重组,可以大幅度地减少连接运算的时间,提高查询效率。

完全析取范式群判定SHOIN(D)-可满足性

针对非循环概念提出了一种对SHOIN(D)-概念可满足性进行判断的方法——CDNF(complete disjunctive normal form)算法.该算法通过把非循环定义的概念描述本身构建成分层次的析取范式群,并通过子句重用技术阻止无谓的子概念扩展,这样的析取范式群具有可满足性自明性,从而可以实现对SHOIN(D)-概念可满足性的直接判断.该算法基本上消除了判断过程中描述重复的现象,从而在空间、时间性能上都比Tableau算法有更好的表现.关键词:描述逻辑推理;可满足性;析取范式;SHOIN(D);

多值Lukasiewicz逻辑公式的范式表示和计数问题

将符号化计算树逻辑中的Shannon展开式做了推广,在n值ukasiewicz逻辑系统n中,研究了由逻辑公式导出的n值McNaughton函数的展开式,给出了m元n值McNaughton函数的准析取范式和准合取范式.在此基础上,给出了m元n值McNaughton函数的计数问题,并在n值ukasiewicz逻辑系统n中,给出了m元逻辑公式的构造方法及其逻辑等价类的计数问题.

基于极小析取范式的属性约简算法

属性约简是粗糙集理论的核心问题之一,针对求取决策表所有决策约简集的NP问题,化繁为简将问题转化为对象动态增加下的决策约简求取问题。在深入分析了可辨识矩阵中可辨识集的特点及相互关系的基础上,优化改进决策辨识矩阵:①两对象之间不作逆向比较;②将决策可辨识矩阵列简化为属性等价类;③正域等价类作为决策可辨识矩阵的行,分情况给出了新决策表求取所有决策约简集的极小析取范式属性约简方法。该方法统一解决了相容和不相容决策表所有决策约简集的求取问题,最后通过实例分析验证了算法的可行性与有效性,为决策表的属性约简提供了一条高效的途径。

实化外连接视图的增量计算

针对实化外连接视图的增量维护问题,提出了利用独立计算表达式计算辅助增量的算法。该方法利用外连接运算的连接析取范式,为各个析取项建立独立计算表达式,然后利用多个独立表达式之间的公共子表达式来计算实化外连接视图的辅助增量。该方法对实化外连接SPOJ(select project outer-join)视图定义没有其他的限制条件,试验结果表明,与相同条件的算法比较起来,该算法有效地降低了计算代价。

基于下确界不可约的概念格属性约简方法

对概念格的属性约简方法进行研究。证明概念格中任意属性亏值都为可辨识属性集,下确界不可约概念的属性亏值集合与全部属性亏值集合的辨识函数具有相同的最小析取范式,概念元素为下确界不可约概念当且仅当其必为属性概念,并且每个属性概念的属性亏值中任取一个元素构成的集合必定是一个属性约简。在上述研究的基础上,提出一种针对大背景概念格快速获得全部属性约简的方法,并给出相应算法,证明其时间复杂度与空间复杂度都是多项式形式。分析结果表明,该方法无苛刻条件,化简幅度较大,运行时间快,具有较好的约简效果。

主范式的计算方法及其在命题公式中的作用

针对数理逻辑中主范式的求解难度较大、方法繁琐,充分利用极小项与极大项的特征及其与二进制数的关系,综合求解主范式的各种传统方法,给出较为简洁实用的计算方法。同时系统论述两种主范式在命题逻辑中对于理解和分析命题公式诸多方面的作用。

合取范式化为析取范式的DNA表面计算

合取范式化为析取范式的计算复杂度是指数级别的,为了降低它的计算复杂度,提出了合取范式化为析取范式的DNA表面计算.因为DNA中碱基对的配对可以同时进行,所以DNA表面计算具有并行计算能力,它实现了将合取范式化为析取范式的计算复杂度降低到多项式级别.

用均覆盖和锥形式对析取范式的结构分析及其近似快速求解算法

本文对析取范式的结构作了结构分析，得出了如下结果：在恰由ｎ个确定的命题变元所可能构成的一切析取范式中，含均覆盖的析取范式的比例当ｎ趋于无穷大时等于１．在其余的析取范式中，含锥形式的比例当ｎ趋于无穷大时亦等于１．基于分析结果，给出了一个判定析取范式永真性的快速算法．

命题逻辑中的数字表示

讨论了命题逻辑中的数字表示,给出了一系列重要结论,并通过实例说明了基于整数运算的求命题公式主范式和进行逻辑推理的方法,它为计算机处理命题逻辑提供了一种有效的途径.