作业 8 · 前束范式与 Skolem 化

正确。先把等价消成两个蕴含的合取，再把各分支中的约束变量换成互不冲突的新名字，最后依次前移量词。

选 D：

关系中可以存在一个非对角有序对，而所有对角对都不在关系中。

选 B。$Q,\neg R\models1$ 永远成立，因为 $1$ 在任何解释下都真，不能据此推出 $Q\models R$。用于推出 $Q\models R$ 的不可满足条件应是 $Q,\neg R\models0$。

选 A。一般不成立的是

左侧正确移入时要把 $\forall$ 换成 $\exists$。

前件给出同一个见证 $a$，使任意 $y$ 都满足 $Q(a,y)$；后件针对每个 $y$ 都可选 $x=a$。

三式均普遍有效。第一式把前件任一存在见证沿用到后件；第二式分“存在 $P$”与“不存在 $P$”两种情况；第三式把 $P$ 的存在见证代入全称前提即可得到 $Q$ 的存在见证。

若两个前提都真，则每个对象都满足 $P$，且每个满足 $P$ 的对象满足 $Q$，因此每个对象都满足 $Q$。

它可满足但不普遍有效。取二元素论域，让 $P$ 只在一个对象上真、$Q$ 只在另一个对象上真，则 $\forall xP(x)$ 为假，外层前件为真；但有对象满足 $P$ 而不满足 $Q$，后件为假。

源答案在先改名约束变元后得到：

先把第二个约束变量改名为 $z$：

第一式的两个存在变元分别依赖此前的全称变元：

第二式最外层存在量词用新常元 $a$ 代替，$v$ 只依赖此前的 $x$：