逻辑：evenb_double_conv

Question

Theorem evenb_double_conv : forall n,
  exists k, n = if evenb n then double k
                else S (double k).
Proof.
  (* Hint: Use the [evenb_S] lemma from [Induction.v]. *)
  intros n. induction n as [|n' IHn'].
  - simpl. exists O. simpl. reflexivity.
  - rewrite -> evenb_S. destruct (evenb n') as [H1 | H2].
    + simpl.

我卡在这里了：

n' : nat
IHn' : exists k : nat, n' = double k
============================
exists k : nat, S n' = S (double k)

我们可以使用归纳假设将 (double k) 重写为 n'，或者对目标进行注入，然后应用归纳假设。

但我可以做到 none 因为 exists。

rewrite <- IHn' 给出：

Error: Cannot find an homogeneous relation to rewrite.

injection 给出：

Error: Ltac call to "injection" failed. Not a negated primitive equality.

怎么办？

Answer 1

我们需要用 destruct 打破 exists 假设：destruct IHn' as [k HE].

Theorem evenb_double_conv : forall n,
  exists k, n = if evenb n then double k
                else S (double k).
Proof.
  (* Hint: Use the [evenb_S] lemma from [Induction.v]. *)
  intros n. induction n as [|n' IHn'].
  - simpl. exists O. simpl. reflexivity.
  - rewrite -> evenb_S. destruct IHn' as [k HE].  destruct (evenb n').
    (* Now find out which k we need to insert into the goal for every branch *)

注入在这里不起作用，因为它只在假设中起作用。

逻辑：evenb_double_conv

Logic: evenb_double_conv

coq

logical-foundations