关于求解DNF永真性问题的近似快速算法的研究

本文研究了用吸收关系与补关系构造求解DNF的永真性的近似快速算法问题。在第二节给出了偏序集〈S;≤〉的定义,研究了〈S;≤〉上的链与反链的性质。在第三节巧妙地借助补关系图构造了一个求解DNF的永真性的分治算法。

用锥形式判定析取范式永真性的算法研究

定义了一种既永真又易于识别的析取范式－锥形式，用它对析取范式的结构进行了分析，得出如下结果：在由ｎ个确定的例题变元所可能构成的一切析取范式中，含锥形式的占绝大多数。基于这个结果，得出了一个判定析范式永真性的近似快速求解算法。

求解析取范式永真性问题的一个近似快速算法

NP完全问题是一类在计算复杂性理论中被证明为较难求解的问题,这类问题中包含有很多在理论和实际中很有意义的问题。NP完全问题中的一个问题的对偶问题若存在快速(多项式意义下)的求解算法,则所有NP完全问题都有快速的求解算法。但目前人们还没有找到一个求解NP完全问题的真正快速算法,并且有迹象表明求解NP完全问题的真正快速算法是不存在的。

金岳霖的归纳理论述评

金岳霖教授是我国现代著名的哲学家、逻辑学家，其归纳理论既是其哲学思想的核心内容，又是他的逻辑思想的重要方面。本文以金氏的归纳思想为研究对象，对之进行较为系统的阐述。

金岳霖与罗素的归纳思想之比较

在归纳问题的解决方式上 ,金岳霖与罗素有师承关系。金岳霖对归纳问题的解决是对罗素归纳思想的深化。他们的共同之处主要表现在 :都把对归纳问题的解决建立在归纳原则的合理性上。他们不同在于 :前者对归纳原则的永真性进行了论证 ,而后者对归纳原则的合理性主要建立在信念上。

代换定理的证明及其应用

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

金岳霖归纳原则理论的逻辑维度解读

休谟问题,无论从哲学还是逻辑学角度看,都是极复杂而难解的问题。金岳霖为解决休谟问题而提出归纳原则理论,并对这一理论从"休谟问题与归纳原则""归纳原则及其表述""归纳原则的永真性及其证明""归纳原则与归纳推论、完全归纳法的区别"等方面加以分析与论证。其分析与论证或有可商榷之处,然而从总体上看,金岳霖对归纳原则所进行的独到深刻的分析、精细严密的论证,为解决归纳问题而提供的灵活多变的思路,给人们试图解决休谟问题以有益的启示。

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

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

永真假性的研究

我们假定读者已经知道一个狭义谓词演算公式α(其中可出现“等号”,下同)的永真性和可满足性的定义及其一些最简单的性质。不可满足的公式亦叫做永假公式。所谓永真假性问题是: