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

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

一种利用扩展广义表来实现逻辑表达式自动推导的算法

探讨了如何将数据结构中广义表进行扩展 ,并利用这个扩展广义表来设计逻辑表达式在计算机上的逻辑结构和存储结构 ,以及在这种结构上如何实现逻辑表达式的基本运算 ,进而实现其它复杂的表达式自动推导     

粗糙集理论中析取范式生成算法

知识约简是粗糙集理论研究的主要内容之一,而析取范式的生成又是知识约简的重点,本文提出的析取范式生成算法可以直接从合取范式生成析取范式,同时给出了属性约简算法的具体步骤,还进行了时间复杂性的分析和实例验证,表明算法的有效性。     

命题逻辑的计算机实现

命题逻辑是逻辑学的基础,要实现逻辑学的计算机处理首先需要实现命题逻辑的计算机处理。由于每个命题公式都与一个由小项下标组成的集合相对应,这样实现命题逻辑的计算机实现就可以通过集合这个工具,首先将命题逻辑转化成集合,然后在计算机上对集合进行表示和处理,最后再将由集合处理的结果还原成命题逻辑的形式输出。本设计主要是基于这一集合理论,在计算机上实现命题逻辑中的两个最基本的处理,命题公式的证明和命题公式的主析取范式求解。     

一种高效的分辨函数范式转换算法*

基于分辨矩阵获取一个决策表所有约简的过程实质上是一个将分辨函数从合取范式转换为析取范式的过程,其效率对于属性约简算法性能至关重要。依据人工范式转换的运行机制,充分利用合取运算和析取运算的吸收率,并借助队列结构,提出了一种面向分辨函数的范式转换算法。该算法易于理解,实现简便。仿真实验表明算法能够高效地完成范式转换。     

基于浓缩布尔矩阵的属性约简算法

属性约简是粗糙集理论研究的核心内容之一,最常用的计算属性约简的方法是基于Skowron可辨识矩阵的方法.为解决该类方法中存在的如应用范围受限、时间及存储空间浪费和效率瓶颈等问题,提出了一种基于浓缩布尔矩阵的属性约简算法:通过提出浓缩布尔矩阵的概念,以布尔代数的形式有效解决了现有可辨识矩阵存储空间大、生成效率低等缺点;利用一种新的用于直接生成分辨函数最小析取范式的算法,有效改善了算法的时间和空间复杂度,从而提高了属性约简算法的效率.     

对于析取范式的构造的一个全局性分析

我们考虑具有优先代表资格的NP完全问题——析取范式的永真性判定问题。本文从全局性构造的角度对它作了某种分析,得出如下结果:在由n个确定的命题变元所可能构成的一切析取范式中,永真析取范式的个数与非永真析取范式的个数之比当n趋于无穷时为无穷大。 基于所得结果,对于析取范式永真性判定问题得出了一个近似快速的求解算法,按此算法,对绝大多数的析取范式,其永真性问题,在多项式时间内都可解决。     

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

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

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

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

极小子集问题的逻辑代数解法

在粗集论中，决策表简化问题可转化为极小子集问题.本文给出极小子集问题的逻辑代数解法，即通过求逻辑函数的极小析取范式或极小合取范式来获得极小子集.