3-CNF一秒钟求出解

姜咏江

给出5个变量的合取范式，能够在一秒中之内求出解吗？利用我设计的运算器，一秒就可以求出。例如合取范式:

(x1’+x2’+x3’)(x3+x4+x5’)(x2+x4’+x5)(x1’+x2’+x3)(x2’+x3’+x4)(x1’+x4’+x5)(x1+x3+x5’)

(x1’+x2+x3)(x1+x3’+x4’)(x1’+x2+x4)(x1’x3+x4’)(x1’+x4+x5)(x2’+x3’+x5)(x2’+x4’+x5)

(x2’+x3+x5)(x1+x2’+x3’)(x1+x2’+x4)(x3+x4+x5).

该运算器求解结果如下图，用我的子句消去计数法，你立即就可以从图中看出解是多少。子句消去计数法见http://blog.sciencenet.cn/blog-340399-905817.html

补充说明一下，不然不明白硬件电路时序仿真的人看不懂了。

Name栏是子句，x'用‘_x’表示，这是软件标识符规定，不能用撇号做标识符字符。右面图中在上粗实线表示那段时间有该行左面Name中的子句，下细实线表示没有。

最下面的输出变量c是32个一侧计数器的非零标志线组成的向量，从右到左，分别表示一侧计数器0号至31号不为0标志，即该位置是1，即表示该位置编号的计数器不为零。本例给出的合取范式用子句消去计数法，进行求解，只有2号计数器值仍然是0。2号计数器的名称是x5'x4'x3'x2x1'，于是依子句消去计数法，此合取范式有惟一解x5=1,x4=1,x3=1,x2=0,x1=1。