不使用对称策略重写

Question

这是我使用的 coq 版本：

sibi { ~ }-> coqc --version
The Coq Proof Assistant, version 8.4pl4 (November 2015)
compiled on Nov 04 2015 12:56:53 with OCaml 4.02.3

这是我要证明的定理：

Require Import Coq.Lists.List.
Import ListNotations.

Theorem rev_app_distr: forall l1 l2 : list nat,
  rev (l1 ++ l2) = rev l2 ++ rev l1.
Proof.

注意我会在证明中使用这个定理（我已经证明了）：

Theorem app_nil_r : forall l : list nat,
  l ++ [] = l.

好的，现在这是我尝试通过通常的归纳法证明定理：

Theorem rev_app_distr: forall l1 l2 : list nat,
  rev (l1 ++ l2) = rev l2 ++ rev l1.
Proof.
  intros l1 l2.
  induction l1 as [| n l1'].
  - simpl.
    rewrite -> app_nil_r with (l := rev l2) at 2.

但是在执行 rewrite 策略时，它给了我以下错误：

Error: Tactic failure:Nothing to rewrite.

但是如果我使用 symmetry 策略，我实际上可以通过相同的代码证明它：

Theorem rev_app_distr: forall l1 l2 : list nat,
  rev (l1 ++ l2) = rev l2 ++ rev l1.
Proof.
  intros l1 l2.
  induction l1 as [| n l1'].
  - simpl.
    symmetry.
    rewrite -> app_nil_r with (l := rev l2) at 1.

那么，为什么不对称重写它不起作用？

Answer 1

问题不是您错过了 symmetry 调用，而是您在调用策略时添加了 at 2 修饰符。由于该点的目标只有一次出现在 app_nil_r 的左侧（即 rev l2 ++ []），因此 rewrite 策略变得混乱并且不执行任何操作。如果将 at 2 替换为 at 1，或者简单地删除它，问题就会消失。您可以在 Coq manual.

中了解有关 at 修饰符的更多信息

不使用对称策略重写

Re-writing without using symmetry tactic

coq

coq-tactic