使用嵌套 ∃ 和等式化简表达式

Question

我遇到了一个证明，在我将这个引理放入 Isabelle 的简化器集合之前，我无法轻易地实现自动化：

lemma ex_ex_eq_hint:
  "(∃x. (∃xs ys. x = f xs ys ∧ P xs ys) ∧ Q x) ⟷
   (∃xs ys. Q (f xs ys) ∧ P xs ys)"
  by auto

现在我想知道：简化器或经典推理器不能一般地自动执行这种简化是否有充分的理由？是否可以将此引理的更一般形式添加到默认 simpset 中以实现此目的？

Answer 1

在Isabelle2015中，简化器知道一些规则来消除由相等决定的存在约束变量。对于您的情况，相关的是 simp_thms(36-40):

(∃x. ?P) ⟷ ?P
∃x. x = ?t
∃x. ?t = x
(∃x. x = ?t ∧ ?P x) ⟷ ?P ?t
(∃x. ?t = x ∧ ?P x) ⟷ ?P ?t

此外，ex_simps(1-2) 如果一侧没有提到绑定变量，则将存在项推入合取词：

(∃x. ?P x ∧ ?Q) ⟷ (∃x. ?P x) ∧ ?Q
(∃x. ?P ∧ ?Q x) ⟷ ?P ∧ (∃x. ?Q x)

在很多情况下，这些规则足以消除存在量词。但是，在您的情况下， xs 和 ys 之间还有更多存在量词。原则上，上述规则和 ex_comm，即 (∃x y. ?P x y) ⟷ (∃y x. ?P x y)（和 op & 的结合性，但无论如何这是默认的 simp 规则）足以通过重写来证明你的引理。但是，必须将合取词的存在拉出，然后置换量词，使 x 绑定在最里面。在一般情况下，这些步骤中的 None 是可取的。此外，交换性受制于 Isabelle 的项序，因此简化器甚至可能不会以预期的方式应用它。

因此，这个问题一般不能通过一组有限的重写规则来解决，因为可能有任意多的量词嵌套。然而，它可以通过 simproc 来解决，该 simproc 触发存在量词并在量化谓词项中搜索绑定变量的相等性。如果相等出现在可以消除存在性的位置，那么它必须当场产生适当的重写规则（转换可能对此有用）。

但是，simproc 应该确保它不会过多地干扰目标的结构。在您的示例中已经可以看到其中的一些干扰。在左侧，谓词Q不在内部量词的范围内，但在右侧。

这意味着尚不清楚这种转换是否在所有情况下都是可取的。例如，在左侧，auto、fastforce 等使用的经典推理器可以在一个存在量词下，然后使用经典推理找到 x 的实例化通过分析 Q。这可能会导致等式 x = f xs ys 的进一步简化，从而导致进一步的实例化。相反，在右侧，reasoner 在开始查看 Q.

之前必须首先为存在量词引入两个示意图变量

总而言之，我建议您分析您的设置，看看为什么这种形式的量词嵌套会在目标状态下发生。也许您可以调整它，使一切都符合现有的规则集。

使用嵌套 ∃ 和等式化简表达式

Simplify expressions with nested ∃ and an equality

logic

isabelle

simplification