命题作为博弈的求真表示

在Giorgi Japaridze引入的可计算性逻辑中,提出了将命题作为博弈,命题的真值由博弈结果得到的基本思想.本文通过引入环境状态概念,给出了命题求真过程的形式化表示方法.基于这样的处理,利用从命题逻辑到模态命题逻辑的研究方法,我们可以研究模态可计算性逻辑、线性时序可计算性逻辑、以及行为时序可计算性逻辑.     

可逆矩阵概率测试系统

利用概率测试方法考虑矩阵可逆的近似判定,构造出α(素数)元数域F上m阶方阵可逆判定的概率测试系统,其中验证者使用O(mαmlogα)个随机数码,阅读O(αmlogα)个神谕数码。     

论n=3情形下V.I.Arnold问题——中心,焦点的判定

V.I.Arnold 于1976年提出如下问题:如果一个矢量场是由具有固定次数的带有有理数的多项式来给定,那么能否给出一个判定准则的算法,来确定这一矢量场中驻定点的稳定性。中国科学院数学研究所王联,王慕秋解决了 n=2的情形,贵州大学数学系杨世藩解决了 n=3时高次奇点的情形,本文使用[3]中的中心焦点判定的方法给出了判定公式,这些公式皆用矩阵表示。全文分两个部分,第一部分:判定方法——给出了 n=3情形下,中心、焦点的判定公式。第二部分:推广的判定方法——给出了 n=k(k≥3)的情形下中心、焦点的判定公式。     

NT-HIT(k)公式的存在性

一个合取范式(CNF)公式F是NT-HIT公式,如果F中的任意两个不同的子句中恰有一对互补文字。NT-HIT(k)是公式的子句数与变元数之差为k的NT-HIT公式类。通过构造一个命题公式Hn,m,我们证明了：(1)Hn,m可满足当且仅当存在一个含有n个变元和m个子句的NT-HIT公式。(2)对于NT-HIT(1)中的任意一个公式F,存在一个文字L,L在F中仅出现一次。进一步,我们证明了：对于k≥2,公式Hn,n k是一个不可满足公式。于是,对于k≥2,NT-HIT(k)是一个空集。从而就解决了[1]中的两个公开的问题。     

MAX+(k)中公式改名的多项式时间可判定性

MAX^ (k)是极小不可满足公式的一个子类。作者引入了MAX^ (k)中公式的一种递归构造方法,基于分裂技术并通过证明MAX(1)中公式改名问题在多项式时间内可以判定。证明了MAX^ (k)中公式的改名问题在多项式时间内可以判定。     

带中介的鸽巢公式

鸽巢公式的一个真值指派可以用一个边带标记的完全二分图表示。在完全二分图中插入一个新的中介结点集,可以将鸽巢公式推广到带中介的情形,从而形成一类新的消解难例公式。文中提供了一种新的消解难例的构造方法。     

MU(1)内公式改名的多项式可判定性

研究判定合取范式公式F和H之间是否存在一个改名φ使得φ(F)＝H的计算复杂性。公式的改名是将命题变元映到变元本身或变无的否定的一个映射，对于极小不可满足公式的子类射MU／(1)中的公式，我们证明了其改名判定问题在多项式时间内是可判定的。     

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

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

基于矩阵直积的膨胀图构造

将矩阵直积的概念引入图论,证明了直积图的结点数、度及特征值分别等于原图结点数之积、度之积和特征值之积,并将这些性质应用于由两个膨胀图构造一个新的膨胀图,分别从矩阵的角度和图的角度给出了构造算法。