使用 MSet 在 coq 中证明

Question

所以我对 coq 还是个新手，MSets 给我带来了一些问题。这里有两个函数来计算一个元素是否在列表或集合中，如果您认为 set_contains 定义正确或者是否有更好的方法，请告诉我。感谢您的帮助。

    Require Import MSets ZArith.
    Module mset := MSetAVL.Make Positive_as_OT.
    Notation pos_set := mset.t.

    Definition set_contains (x : positive) (s : pos_set) :=
      mset.mem x s.

    Fixpoint list_contains (x : positive) (l : list positive) : bool :=
      match l with
      | nil => false
      | y :: l' =>
        if Pos.eqb x y then true
        else nodelist_contains x l'
     end.

   Lemma nodelist_nodeset_contains :
      forall x  (s : pos_set),
        (nodelist_contains x (mset.elements s)) = (nodeset_contains x s).
    Proof.
      induction s.
      destruct list_contains.
      destruct set_contains.
      auto.

似乎 set_contains 在析构后的基本情况下评估为真，我不确定为什么。在证明的那个阶段，集合不会是 mset.empty 吗？

我也不知道如何使用 mset.In，我对这个证明的基本情况有疑问，显然我有同样的问题。我想最终声明：

    Lemma nodelist_containsP :
      forall x (l : pos_set),
        reflect (mset.In x l) (nodeset_contains x l).

万一有人感兴趣，这里是我如何做这个证明的。

       intros.
       apply iff_reflect.
       unfold nodeset_contains.
       symmetry.
       apply mset.mem_spec.
       Qed.

Answer 1

list_contains 和 set_contains 是函数，因此尝试 destruct 它们没有意义。 Coq 会尝试推断您的意思并猜测您想要区分以 list_contains 和 set_contains 开头的表达式的值。

这不是你想要的。您想要的是观察两个函数在同一输入上的行为。你可以通过检查它来做到这一点。

这应该会向您发送正确的方向：

  destruct s as [mset mset_isok].
  induction mset.
  + unfold set_contains, mset.mem.
    simpl.
    reflexivity.
  + unfold list_contains, set_contains, mset.mem.
    simpl.

使用 MSet 在 coq 中证明

Proofs in coq using MSet

set

coq