如何证明有的命题公式无法写成前束范式？
2023-05-28 阅读 42
要证明一个命题公式无法写成前束范式，需要使用反证法。假设该命题公式可以写成前束范式，然后通过构造一个矛盾的例子来证明这个假设是错误的。
举个例子，考虑命题公式 $P(x) \land \forall y(Q(y) \rightarrow R(x,y))$。假设它可以写成前束范式，那么它必须具有以下形式：
$\forall x \exists y_1 \exists y_2 \cdots \exists y_n (P(x) \land Q(y_1) \land Q(y_2) \land \cdots \land Q(y_n) \land R(x,y_1) \land R(x,y_2) \land \cdots \land R(x,y_n))$
但是，考虑当 $n=0$ 时，这个前束范式就变成了 $\forall x P(x) \land \forall y \neg Q(y)$，这明显与原命题公式不等价，因此我们得出结论，该命题公式无法写成前束范式。
更新于 2023年05月29日
