如何在给定规范的情况下证明 Coq 中函数的唯一性?
How to prove uniqueness of a function in Coq given a specification?
给定一个函数的规范,例如 specification_of_sum
,我如何在 Coq 中证明只有一个这样的函数存在?
我正在学习数学,我可以手头证明这一点,但我在 Coq 方面的技能有限(证明使用 rewrite
和 apply
)。
我找到了下面的代码片段,我已经为此苦苦挣扎了一段时间。
我尝试在证明中展开规范,但使用我的老朋友 rewrite
似乎并不能让我更进一步。
谁能解释一下如何使用简单的语法解决这个问题?
Definition specification_of_sum (sum : (nat -> nat) -> nat -> nat) :=
forall f : nat -> nat,
sum f 0 = f 0
/\
forall n' : nat,
sum f (S n') = sum f n' + f (S n').
(* ********** *)
Theorem there_is_only_one_sum :
forall sum1 sum2 : (nat -> nat) -> nat -> nat,
specification_of_sum sum1 ->
specification_of_sum sum2 ->
forall (f : nat -> nat)
(n : nat),
sum1 f n = sum2 f n.
Proof.
Abort.
您需要在 n
上使用归纳法证明这一点。想一想,您的规范涵盖了 0
和 n.+1
的情况,因此很自然地使用归纳法。
您基本上可以在自己选择的 Coq 书籍中阅读有关归纳的内容。
关于如何使用您的规范的示例是:
intros sum1 sum2 s1_spec s2_spec f n.
specialize (s1_spec f) as [s1_spec0 s1_specS].
specialize (s2_spec f) as [s2_spec0 s2_specS].
下面的开始基本上与 ejgallego 已经描述的一样。
intros sum1 sum2 H1 H2 f n. (* introduce all the hypotheses *)
unfold specification_of_sum in *. (* unfold definition in all places *)
specialize H1 with (f := f). (* narrow statement to be about f *)
specialize H2 with (f := f). (* narrow statement to be about f *)
inversion_clear H1. (* split up the AND statements *)
inversion_clear H2.
(* induction on n, and do rewrites *)
我已经包含了一些更基本的命令,以使其更慢但更简单。剩下的证明只需要 rewrite
和 reflexivity
.
给定一个函数的规范,例如 specification_of_sum
,我如何在 Coq 中证明只有一个这样的函数存在?
我正在学习数学,我可以手头证明这一点,但我在 Coq 方面的技能有限(证明使用 rewrite
和 apply
)。
我找到了下面的代码片段,我已经为此苦苦挣扎了一段时间。
我尝试在证明中展开规范,但使用我的老朋友 rewrite
似乎并不能让我更进一步。
谁能解释一下如何使用简单的语法解决这个问题?
Definition specification_of_sum (sum : (nat -> nat) -> nat -> nat) :=
forall f : nat -> nat,
sum f 0 = f 0
/\
forall n' : nat,
sum f (S n') = sum f n' + f (S n').
(* ********** *)
Theorem there_is_only_one_sum :
forall sum1 sum2 : (nat -> nat) -> nat -> nat,
specification_of_sum sum1 ->
specification_of_sum sum2 ->
forall (f : nat -> nat)
(n : nat),
sum1 f n = sum2 f n.
Proof.
Abort.
您需要在 n
上使用归纳法证明这一点。想一想,您的规范涵盖了 0
和 n.+1
的情况,因此很自然地使用归纳法。
您基本上可以在自己选择的 Coq 书籍中阅读有关归纳的内容。
关于如何使用您的规范的示例是:
intros sum1 sum2 s1_spec s2_spec f n.
specialize (s1_spec f) as [s1_spec0 s1_specS].
specialize (s2_spec f) as [s2_spec0 s2_specS].
下面的开始基本上与 ejgallego 已经描述的一样。
intros sum1 sum2 H1 H2 f n. (* introduce all the hypotheses *)
unfold specification_of_sum in *. (* unfold definition in all places *)
specialize H1 with (f := f). (* narrow statement to be about f *)
specialize H2 with (f := f). (* narrow statement to be about f *)
inversion_clear H1. (* split up the AND statements *)
inversion_clear H2.
(* induction on n, and do rewrites *)
我已经包含了一些更基本的命令,以使其更慢但更简单。剩下的证明只需要 rewrite
和 reflexivity
.