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

Question

在我的问题here之后，我有一个函数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上进行归纳以证明lemmakeepnotEmpty。

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.