CNF公式赋值空间上可满足解的概率性质

来源：计算机科学与探索杂志2018年第11期北京时间：

作者：莫孝玲，许道云

单位：贵州大学 计算机科学与技术学院，贵阳 550025

摘要：为分析合取范式（conjunctive normal form，CNF）公式的赋值空间在可满足性情况下的结构性质，引入一个变元翻转次数控制的参数[k, k]不小于1且不大于[n, n]为公式中出现的变元个数，以赋值作为结点，基于翻转界控制下赋值满足子句数的大小，引入一类有向图——BF（bounded flips）图。研究带翻转控制参数的BF图的若干基础性质，根据BF图的性质研究CNF公式可满足解的概率性质。对于含有[n]个变元[m]个子句CNF公式，随着翻转控制参数[k]的增大，在其BF图上取得可满足解的概率也相应增大。当[k]靠近[n]时，概率稳定。对于可满足的CNF公式，在其任意[k]值下的BF图上进行[t]次随机游走。当[t]足够大时，取得可满足解的概率最终会收敛于1。最后，实验仿真支持性质的正确性。

关键词：合取范式（CNF）公式,赋值空间,翻转控制参数,可满足解