Coq：使用归纳法证明两个阶乘函数的相等性

Question

我想用归纳法证明两个阶乘函数在 Coq 中是等价的。

基础案例n = 0很简单，但是归纳案例更复杂。我明白了，如果我可以将 (visit_fac_v2 n' (n * a)) 重写为 n * (visit_fac_v2 n' a)，我就完成了。然而，将这个想法转化为 Coq 给我带来了麻烦。

如何在 Coq 中证明这一点？

Fixpoint fac_v1 (n : nat) : nat :=
  match n with
  | 0 => 1
  | S n' =>  n * (fac_v1 n')
  end.

Fixpoint visit_fac_v2 (n a : nat) : nat :=
  match n with
  | 0 => a
  | S n' => visit_fac_v2 n' (n * a)
  end.

Definition fac_v2 (n : nat) : nat :=
  visit_fac_v2 n 1.

Proposition equivalence_of_fac_v1_and_fac_v2 :
  forall n : nat,
    fac_v1 n = fac_v2 n.
Proof.
Abort.

Answer 1

在归纳情况下，可以应用归纳假设，将目标简化为：

visit_fac_v2 n 1 + n * visit_fac_v2 n 1 = visit_fac_v2 n (S n)

为了证明这一点，您可以使用以下引理：

Lemma visit_fac_v2_extract:
  forall n a : nat,
    visit_fac_v2 n a = a * visit_fac_v2 n 1.

Answer 2

在证明直接式函数与其基于累加器的等价函数相等时，典型的做法是声明一个更强的不变量，该不变量对于累加器可能持有的任何值都应该成立。

然后您可以将其专门化为调用函数的值，从而获得您感兴趣的语句作为更一般语句的必然结果。

这里的大致表述如下：

Theorem general_equivalence_of_fac_v1_and_fac_v2 :
  forall n a : nat,
    a * fac_v1 n = visit_fac_v2 n a.

它的证明相当简单（你必须小心并确保 induction 出现在 intro a 之前，因为你希望归纳假设对任何 a):

Proof.
intros n; induction n; intro a.
 - simpl ; ring.
 - simpl ; rewrite <- IHn ; ring.
Qed.

你的命题是这个更一般定理的直接推论。

Coq：使用归纳法证明两个阶乘函数的相等性

Coq: Prove equality of two factorial functions using induction

functional-programming

factorial

coq