3

(∀u∃va(u,v)) ∧ (∀x∃ya(x,y)) 的 skolemized 形式是什么？

我不确定，因为可能有不同的 perenex 范式：

  • ∀u∃v ∀x∃y (a(u,v) ∧ a(x,y))
  • ∀u∀x ∃v∃y (a(u,v) ∧ a(x,y))
  • …</li>

会有不同的 skolemized 形式如下：

  • ∀u ∀x (a(u,f(u)) ∧ a(x,g(u,x)))
  • ∀u∀x (a(u,f(u,x)) ∧ a(x,g(u,x)))

在我看来，它们并不等同于彼此。还是我在这里错了？

4

1 回答 1

2

是的，prenex 范式对于给定的 FO 公式不是唯一的，相应地，Skolemizations 也不是唯一的。我认为您试图展示的相同“范围逃逸”的一个更简单的示例是公式∃xAx→∃yBy，前缀形式为∀x∃y（Ax→By）和∃y∀x（Ax→By），以及相应的 sklemizations ∀x (¬ Ax ∨ Bf(x)) 和 ∀x (¬ Ax ∨ B a)，具有 aa 常数。

现在，相关的问题是这些公式的不等价性是否对您的特定问题很重要。如果是这样，那么 Skolemization 可能不是最适合您的工具：Skolemization是一个旨在保持公式可满足性的过程，有时会以等效性为代价。

（无论如何，如果仅在上面的示例中，了解为什么单个公式的不同 skolemization 是可以等值的，这是一个很好的练习）

于 2011-12-27T11:45:56.977 回答