极小不可满足公式相关论文
经典逻辑中的SAT问题是指布尔表达式的可满足性问题,它是计算机科学中的核心问题。SAT问题是NP完全问题,从理论上说,SAT问题不能在多......
研究命题公式 (合取范式 )的极小不可满足性 .设公式F含有n +k个子句(n是F中所有变元的个数 ) ,其中包括子句x1∨…∨xn 和┐x1∨......
一个合取范式(CNF)命题公式F称为极小不可满足公式,如果F不可满足,但从F中删去任何一个子句后得到一可满足公式。极小不可满足公式类......
经典逻辑中的SAT问题是指布尔表达式的可满足性问题,它是计算机科学中的核心问题。SAT问题是NP完全问题,从理论上说,SAT问题不能在多......
命题公式的满足性问题(简称SAT问题)是指布尔表达式的可满足性问题.它是理论计算机科学中的一个重要问题.在数理逻辑、人工智能、......
通过具体公式在增加或删去某些文字或子句后生成的新公式的可满足性来研究极小不可满足公式类的常见子类Dis-MU,HIT-MU,Unique-MU,......
研究了判定问题“对于命题CNF公式F和H,是否存在一个变元(或文字)改名ψ,使得ψ(F)=H?”的复杂性.对于极小不可满足公式的子类MAX......
研究判定合取范式公式F和H之间是否存在一个改名ψ使得ψ(F)=H的计算复杂性.公式的改名是将命题变元映到变元本身或变元的否定的一......
改名是一个将变元映射到变元本身或它的补的函数,变元改名是公式变元集合上的一个置换,文字改名是一个改名和一个变元改名的组合,研......
利用极小不可满足公式的临界特性,可以将任意的一个3-CNF公式多项式时间归约转换为一个正则(3,4)-CNF公式,从而得到一个保留NP完全......
根据极小不可满足公式的特征,对于固定的3 ≤t<k.我们给出了一个将k-CNF公式归约到t-CNF公式的有效算法.对于给定的k-CNF公式F,t-CN......
研究了判定问题“对于命题CNF公式F和H,是否存在一个变元(或文字)改名φ,使得φ(F)=H?”的复杂性.对于极小不可满足公式的子类MAX和MARG,我......
通过构造适当的极小不可满足公式,利用子句拼接技术,引入了一个一般化的从k-CNF公式(k≥3)到3-CNF公式之间的归约转换。基于该转换,给出......
通过具体公式在增加或删去某些文字或子句后生成的新公式的可满足性来研究极小不可满足公式类的常见子类Dis-MU,HIT-MU,Unique-MU,......
合取范式(CNF)公式F是极小不可满足的,如果F不可满足,并且从F中删去任意一个子句后得到的公式可满足,(r,s)-CNF是限制CNF公式中每个子......
合取范式(conjunctive normal form,简称CNF)公式F是线性公式,如果F中任意两个不同子句至多有一个公共变元.如果F中的任意两个不同子句......
SAT问题(可满足性问题)是理论计算机科学的核心问题,研究SAT问题的方法很多,利用极小不可满足公式的性质来研究SAT问题是近几年兴......
改名规则在创建有效的满足性算法和简化某些消解难例的证明中起到了重要作用,对于一些具有对称结构的难例公式,可以通过改名来降低其......
可满足合取范式(CNF)公式F到极小不可满足公式MU(1)的扩张是,对给定的CNF公式F,是否存在一个公式G满足条件var(G)(∪)var(F)并使得......
研究一个极小不可满足公式子类(MAX(1))的等价结构.考虑了MAX(1)上的变元改名问题和文字改名问题.此两个问题均可在O(nlog2(n))时......
对于极小不可满足公式和它的子类的研究是近年来兴起的一个热门方向。极小不可满足公式通过分裂得到的公式保持了极小不可满足性,......