在 Coq 中证明 "rev (rev l) = l"

Question

这是给我的练习之一，我在对 l 进行了归纳后几乎立即卡住了。我不知道在这里还能做出什么其他断言。

我不允许使用自动、直觉等高级策略

Fixpoint snoc {A : Type} l a : list A :=

match l with

  | nil    => a :: nil

  | h :: t => h :: (snoc t a)

end.

Fixpoint rev {A : Type} l : list A :=

match l with

  | nil    => nil

  | h :: t => snoc (rev t) h

end.

(Prove the following)

Theorem rev_rev : forall A (l : list A),

rev (rev l) = l.

Answer 1

我们不会帮你做功课，你应该像@gallais 说的那样先用纸笔证明。

提示：您可能需要稍微概括一下属性（使用中间引理）才能证明 rev_rev。你应该看看 rev_append.

Answer 2

我们都是新手，一开始获得帮助很有用，不会在尝试掌握一门新学科时陷入困境和失去勇气。我会尽量给你一个提示，但不会透露太多。

这比前面的练习更棘手的原因可能是因为这个证明涉及两个归纳推理步骤。您可能在第一个进球中表现不错，并取得了第二个进球

  ...
  IHl : rev (rev l) = l
  ============================
   rev (snoc (rev l) a) = a :: l

不幸的是，您不能立即使用您的归纳假设 IHl，因为 rev 的参数不正确。

所以，在这里您可以尝试证明 另一个 关于 rev (snoc l a) = ... 的引理，它将把目标变成您可以用 IHl 重写的东西。
如果你能解决这个问题，并在引理中证明这一点，那么你应该没问题。

在 Coq 中证明 "rev (rev l) = l"

Prove "rev (rev l) = l" in Coq

coq

induction