Coq：列表对的证明

Question

我写了这个 Inductive 谓词及其（强）规范的部分证明：

Inductive SumPairs : (nat*nat) -> list (nat*nat) -> Prop :=
| sp_base : SumPairs (0,0) nil
| sp_step : forall (l0:list (nat*nat)) (n0 n1: nat) (y:(nat*nat)), SumPairs (n0,n1) l0 -> SumPairs ((n0+(fst y)),(n1+(snd y))) (cons y l0).

Theorem sumPairs_correct : forall (l:list (nat*nat)), { n: nat | SumPairs (n,n) l }.
Proof.
...

问题是我不认为这个定理是正确的，因为 Coq 不接受像 {n0 n1: nat | ...} 这样的东西。有没有办法解决这个问题，还是我想错了？

我认为谓词 SumPairs 是正确的，但由于我不确定，下面是它应该如何工作的示例：输入 [(1,2),(3,4)]，预期输出 [3,7]

Answer 1

您可以在结果中输入一对，例如：

Inductive SumPairs : (nat*nat) -> list (nat*nat) -> Prop :=
| sp_base : SumPairs (0,0) nil
| sp_step : forall (l0:list (nat*nat)) (n0 n1: nat) (y:(nat*nat)), SumPairs (n0,n1) l0 -> SumPairs ((n0+(fst y)),(n1+(snd y))) (cons y l0).

Theorem sumPairs_correct : forall (l:list (nat*nat)), { p: nat * nat | SumPairs p l }.
Proof.
intros l.
induction l as [|p l [[x y] IH]].
- exists (0, 0); constructor.
- now exists (x + fst p, y + snd p); constructor.
Qed.

然而，对于这个特定的任务，实际上最好只使用一个普通的函数式程序：

Require Import Coq.Lists.List.

Definition sum_list l := fold_left Nat.add l 0.

Definition sum_pairs l := (sum_list (map fst l), sum_list (map snd l)).

这个定义比第一个版本更容易阅读、理解和修改。请注意，您仍然可以使用 Coq 对函数进行推理：

Lemma sum_list_cat l1 l2 : 
  sum_pairs (l1 ++ l2) = 
  (fst (sum_pairs l1) + fst (sum_pairs l2),
   snd (sum_pairs l1) + snd (sum_pairs l2)).
(* Exercise! *)

Coq：列表对的证明

Coq: Proof of list pair

coq

coqide