要证明一个命题公式无法写成前束范式,需要使用反证法。假设该命题公式可以写成前束范式,然后通过构造一个矛盾的例子来证明这个假设是错误的。
举个例子,考虑命题公式 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),这明显与原命题公式不等价,因此我们得出结论,该命题公式无法写成前束范式。