计算满足性问题的2个版本的还原性

Question

我需要帮助解决这个问题。

有2个可满足问题的版本：

[1]决策版本：确定任意公式f是否是 满意或不

[2]搜索版本：如果任意公式f是满足的，则返回 将真实值分配给制作f的公式中的变量 满意。如果F不可挑例，则返回NIL。

表明[2]将降低到[1]。

我必须证明[1]的Oracle算法需要[2]，以说“[2]是图4的减少到[1]”。

我看到[2]只是[1]的Oracle算法，因为它鉴别任意公式f的可靠性。

这可能意味着[1]的Oracle算法需要[2]？如果可以，原因是什么？

Answer 1

任何确定公式可满足性的算法也可用于找到满足公式的分配：

虽然不是所有变量都被分配：

• 选择一个变量，选择值0.

• 如果公式不再可满足，则用1.

替换值