为什么反转策略在以下 Coq 证明中不起作用？

Question

Require Import FMapAVL.
Require Import OrderedTypeEx.

Module M := FMapAVL.Make(Nat_as_OT).
Fixpoint cc (n: nat) (c: M.t nat):bool :=
  match M.find n c with
  | None => false
  | Some e => true
  end.

Lemma l: forall (n: nat) (k:nat) (m: M.t nat), cc n m = true  -> cc n (M.add k k m) = true.
Proof.
  intros.
  inversion H.

调用前环境inversion H:

1 subgoals
n : nat
k : nat
m : M.t nat
H : cc n m = true
______________________________________(1/1)
cc n (M.add k k m) = true

根据我对inversion tactic的理解，使用tactic inversion H，应该可以预测M.find n m = Some e。但它只是复制了 H。

谁能帮我看看 Coq 是如何解释这里的东西的？

Answer 1

当假设的主谓词是归纳谓词时，反转有效。这里假设 H 的主要谓词是一个等式，并且碰巧深层的等式是由归纳谓词表示的。所以inversion认为它可以工作。

直觉上，inversion 试图帮助您推理可以使用的构造函数，并且这种推理是通过添加与使用此构造函数时必须满足的约束相对应的相等语句来进行的证明假设。

在您的例子中，相等性由只有一个构造函数的归纳定义表示。所以inversion看看使用这个构造函数的约束是什么：相等的两个成员应该是相同的。所以 inversion 增加了一个新的等式，说明等式的两边应该相同。这就是为什么你会看到这个假设的重复。

碰巧 inversion 不是在这里使用的正确策略。

在之前对your questions之一的回答中，我写到你不应该使用Fixpoint来定义函数cc，因为这个函数不是递归的。请按照我的建议写

Definition cc (n: nat) (c: M.t nat):bool :=
match M.find n c with
| None => false
| Some e => true
end.

这将使其余的证明更容易（我们也可以使用 Fixpoint 定义的 cc 来解决您的问题，但它会增加不必要的复杂性）。我现在对你问题的回答假设你确实遵循了这个一点建议。以下是您的证明的进展方式。

Proof.
intros n k m H; unfold cc in H.

此时您的假设 H 包含模式匹配语句和 true 之间的等式。你想要的是通过在你的证明中执行相同的案例分析来研究这个匹配语句的两种可能的计算。这是如何做到的。

case_eq (M.find n m); [intros v Hfind | intros Hfind].

在此之后，您将有两个目标。一个有 H : match ... with ... end = true 和 Hfind : M.find n m = Some v，另一个有 H : match M.find n m with ... end = true 和 Hfind : M.find n m = None。使用 Hfind 在 H 中重写，您会将假设更改为 H : false = true，这将可以使用 discriminate 求解。请记住这一点以备后用。

对于第一个目标，您应该可以在 unfold cc 后再次取得进步。

现在 M.find n (M.add k k m) 的值是多少？如果 n 是 k，则此值为 Some k。如果 n 不同于 k，则 M.find n (M.add k k m) 的值与 M.find n m 的值相同。我们已经给这个值起了个名字，这个名字是v，假设Hfind就是这么说的。

为了生成n是否等于k的案例分析建议写成destruct (M.E.eq_dec k n) as [kn | knn].

因此您将有一个假设为 kn : k = n 的第一个目标。在那种情况下，我建议您通过键入以下命令来证明一个中间事实。

assert (step : M.find n (M.add k k m) = Some k).

这个你应该可以用M.find_1、M.add_1来证明。

完成此证明后，用 step 重写，然后得出结论。

然后你将有第二个目标假设 knn : k <> n，对于这个你必须证明一个不同的中间陈述，你再次使用 M.find_1 来证明它，然后你使用 M.add_2 和 M.find_2.

为什么反转策略在以下 Coq 证明中不起作用？

Why inversion tactic doesn't work in the following Coq proof?

coq