无法弄清楚为什么重写不起作用

Question

我正在学习 coq，无法弄清楚为什么重写不起作用。

我的代码如下所示：

Inductive nat : Type :=
| zero
| succ (n : nat)
.

Fixpoint add (a b : nat) : nat :=
  match b with
  | zero => a
  | succ b' => add (succ a) b'
  end.

Theorem add_succ : forall a b : nat,
    add a (succ b) = succ (add a b).

Proof.
  induction b as [ |  b' IHb ].
  - simpl.
    reflexivity.
  -

我目前的证明状态是这样的：

- a, b' : nat
- IHb : add a (succ b') = succ (add a b')
============================
add a (succ (succ b')) = succ (add a (succ b'))

我的期望是，如果我运行

rewrite -> IHb.

然后，coq 会将我目标的左侧重写为

succ (add a (succ b')

我这样想的原因是 (succ b') 是 nat 类型，而 b' 是 nat 类型，没有其他限制。所以我希望 coq 注意到 IHb 中的模式与目标的左侧匹配。但这并没有发生。

我做错了什么？

Answer 1

您的假设 IHb 只允许重写确切的术语 add a (succ b')，因为 a 和 b' 在您的上下文中是变量。如果您的假设 IHb 在 b' 上普遍量化，您可以执行您指出的重写步骤，例如IHb : forall x, add a (succ x) = succ (add a x)。也许你可以修改你的证明以获得更强的归纳假设（相关策略可能是 revert 和 generalize）。

Answer 2

很简单：

Theorem add_succ : forall a b : nat,
    add a (succ b) = succ (add a b).

Proof.
  intros *. revert a. induction b as [|b' IHb].
  - simpl. reflexivity.
  - simpl. intro a'. rewrite <- IHb with (succ a'). reflexivity. 
Qed.

无法弄清楚为什么重写不起作用

Can't figure out why re-write does not work

coq

coq-tactic