证明两个 rev_append 实现的等价性

Question

免责声明：这不是作业问题。

我试图在 Coq 中实现我自己的 rev_append 版本，然后证明它等同于内置版本。以下是我的实现。

Fixpoint my_rev_append (l1 l2 : list nat) : (list nat) * (list nat) :=
  match l1 with
  | nil => (l1, l2)
  | hd :: tl => my_rev_append tl (hd :: l2)
  end.

然后我尝试证明它等价于rev_append

Theorem my_rev_append_correct : forall (l1 l2 : list nat),
    my_rev_append l1 l2 = (nil, (rev_append l1 l2)).
Proof.
  intros l1 l2.
  induction l1.
  reflexivity.

然后我实现了以下目标，但我看不到前进的方向。

  IHl1 : my_rev_append l1 l2 = (nil, rev_append l1 l2)
  ============================
  my_rev_append (a :: l1) l2 = (nil, rev_append (a :: l1) l2)

无法使用IHl1，因为当前子目标的RHS是(nil, rev_append (a :: l1) l2)，不包含(nil, rev_append l1 l2)。我尝试了运行 simpl 策略，但它没有用，因为 IHl1 仍然不适用。

我完全明白，我可以通过将 my_rev_append 中的 | nil => (l1, l2) 行更改为 | nil => l2 来证明这一点。但是，有没有可能在不改变my_rev_append的定义的情况下来证明这个定理？

Answer 1

您的定义 l2 通过归纳法有所不同。因此，定理的证明也应该有l2通过归纳变化。为此，在开始归纳之前不要 introduce l2，将其留在目标中。归纳假设的类型基于此目标，然后允许您在递归情况下为其传递不同的值。

Theorem my_rev_append_correct : forall (l1 l2 : list nat), my_rev_append l1 l2 = (nil, rev_append l1 l2).
Proof.
  induction l1 as [ | x l1 rec]; intros l2.
  - reflexivity.
  - apply rec.
Qed.

证明两个 rev_append 实现的等价性

Proving equivalence of two rev_append implementations

formal-verification

proof

coq