用于程序固定点的 Coq simpl
Coq simpl for Program Fixpoint
是否有类似 simpl
用于 Program Fixpoint
的策略?
特别是,如何证明以下简单的陈述?
Program Fixpoint bla (n:nat) {measure n} :=
match n with
| 0 => 0
| S n' => S (bla n')
end.
Lemma obvious: forall n, bla n = n.
induction n. reflexivity.
(* I'm stuck here. For a normal fixpoint, I could for instance use
simpl. rewrite IHn. reflexivity. But here, I couldn't find a tactic
transforming bla (S n) to S (bla n).*)
显然,这个玩具示例不需要 Program Fixpoint
,但我在更复杂的设置中遇到了同样的问题,我需要手动证明 Program Fixpoint
的终止。
我不习惯使用 Program
所以可能有更好的解决方案,但这是我通过展开 bla
想到的,看到它是使用 [=14= 内部定义的] 并使用 SearchAbout Fix_sub
.
查看关于该函数的定理
Lemma obvious: forall n, bla n = n.
Proof.
intro n ; induction n.
reflexivity.
unfold bla ; rewrite fix_sub_eq ; simpl ; fold (bla n).
rewrite IHn ; reflexivity.
(* This can probably be automated using Ltac *)
intros x f g Heq.
destruct x.
reflexivity.
f_equal ; apply Heq.
Qed.
在您的真实示例中,您可能想要引入归约引理,这样您就不必每次都做同样的工作。例如:
Lemma blaS_red : forall n, bla (S n) = S (bla n).
Proof.
intro n.
unfold bla ; rewrite fix_sub_eq ; simpl ; fold (bla n).
reflexivity.
(* This can probably be automated using Ltac *)
intros x f g Heq.
destruct x.
reflexivity.
f_equal ; apply Heq.
Qed.
这样,下次你有一个bla (S _)
,你可以简单地rewrite blaS_red
。
是否有类似 simpl
用于 Program Fixpoint
的策略?
特别是,如何证明以下简单的陈述?
Program Fixpoint bla (n:nat) {measure n} :=
match n with
| 0 => 0
| S n' => S (bla n')
end.
Lemma obvious: forall n, bla n = n.
induction n. reflexivity.
(* I'm stuck here. For a normal fixpoint, I could for instance use
simpl. rewrite IHn. reflexivity. But here, I couldn't find a tactic
transforming bla (S n) to S (bla n).*)
显然,这个玩具示例不需要 Program Fixpoint
,但我在更复杂的设置中遇到了同样的问题,我需要手动证明 Program Fixpoint
的终止。
我不习惯使用 Program
所以可能有更好的解决方案,但这是我通过展开 bla
想到的,看到它是使用 [=14= 内部定义的] 并使用 SearchAbout Fix_sub
.
Lemma obvious: forall n, bla n = n.
Proof.
intro n ; induction n.
reflexivity.
unfold bla ; rewrite fix_sub_eq ; simpl ; fold (bla n).
rewrite IHn ; reflexivity.
(* This can probably be automated using Ltac *)
intros x f g Heq.
destruct x.
reflexivity.
f_equal ; apply Heq.
Qed.
在您的真实示例中,您可能想要引入归约引理,这样您就不必每次都做同样的工作。例如:
Lemma blaS_red : forall n, bla (S n) = S (bla n).
Proof.
intro n.
unfold bla ; rewrite fix_sub_eq ; simpl ; fold (bla n).
reflexivity.
(* This can probably be automated using Ltac *)
intros x f g Heq.
destruct x.
reflexivity.
f_equal ; apply Heq.
Qed.
这样,下次你有一个bla (S _)
,你可以简单地rewrite blaS_red
。