证明 coq 中列表的所有元素

Question

如何证明 H 和我的目标对于列表的所有元素都是相同的？

X : Type
P : X -> Prop
l : list X
H : forall n : X, ~ (In n l /\ ~ P n)
______________________________________(1/1)
forall b : X, In b l -> P b

~ (In n l /\ ~ P n)和In b l -> P b这两个语句是等价的。我尝试 apply imply_to_or 以简化为目标，但无法统一。

谢谢，

Answer 1

首先，我们需要一些导入：

Require Import Coq.Logic.Classical_Prop.
Require Import Coq.Lists.List.

我们在将引理应用于目标时推理 "backwards"。这意味着你需要一个引理作为其结果的蕴涵，不是前提。

我们可以 Search (~ ?p \/ ?c -> ?p -> ?c). 得到它，这会让你：

or_to_imply: forall P Q : Prop, ~ P \/ Q -> P -> Q

上面的引理可行，但我们可以做得更好：我们可以利用 tauto 策略，瞧，你有一个简单的证明：

Goal forall (X : Type) (P : X -> Prop) (l : list X),
       (forall n, ~ (In n l /\ ~ P n)) ->
       forall b, In b l -> P b.
  intros X P l H b.
  specialize H with b.
  tauto.
Qed.

证明 coq 中列表的所有元素

Proving for all elements of a list in coq

coq