证明另一个属性在列表中找到相同的元素

Question

根据我的问题，我有一个函数 findshare 可以在两个列表中找到相同的元素。实际上，keepnotEmpty 是我在对引理 sameElements 的初始版本应用一些更改后在我的程序中需要的引理。引理 keepnotEmpty 证明如果函数 findshare 对两个列表的串联结果不为空，则应用于每个列表的函数结果的串联也不为空。我对如何证明引理感到困惑 keepnotEmpty。谢谢。

Require Import List .
Import ListNotations.
Fixpoint findshare(s1 s2: list nat): list nat:=
      match s1 with
        | nil => nil
        | v :: tl =>
           if ( existsb  (Nat.eqb v)  s2)
            then v :: findshare tl s2
            else findshare tl s2
      end.
Lemma sameElements l1 l2 tl :
        (findshare(l1++l2) tl) =
         (findshare l1 tl) ++ (findshare l2 tl ).
  Proof.
  Admitted.

Lemma keepnotEmpty l1 l2 tl :
  (findshare tl (l1++l2)) <> nil -> (findshare tl (l1) ++ (findshare tl (l2))<>nil).
Proof.

Answer 1

您需要对 tl 和属性 oneNotEmpty 列表进行归纳来证明引理 keepnotEmpty。

Lemma oneNotEmpty (l1 l2:list nat):
l1<>nil -> (l2++l1)<>nil.
Proof.
Admitted.

 Lemma keepnotEmpty l1 l2 tl :
 (findshare tl (l1++l2))<> nil -> (findshare tl (l1) ++ (findshare tl (l2))<>nil).
Proof.
induction tl. simpl; intro. congruence.
simpl.
rewrite existsb_app. 
destruct_with_eqn(existsb (Nat.eqb a) l1).
destruct_with_eqn(existsb (Nat.eqb a) l2);
simpl; intros H1 H2;  congruence.
destruct_with_eqn(existsb (Nat.eqb a) l2).
simpl. intros. apply (oneNotEmpty);
intro. inversion H0.
simpl; assumption. 
Qed.

证明另一个属性在列表中找到相同的元素

Proving another property of finding same elements in lists

coq

proof

证明另一个 属性 在列表中找到相同的元素

Proving another property of finding same elements in lists

coq

proof

证明另一个属性在列表中找到相同的元素