Coq中的非空列表追加定理

Question

我试图在 Coq 中证明以下引理：

Require Import Lists.List.
Import ListNotations.
Lemma not_empty : forall (A : Type) (a b : list A),
    (a <> [] \/ b <> []) -> a ++ b <> [].

现在我目前的策略是在 a 上进行析构，并且在打破析取之后我可以理想地声明如果 a <> [] 那么 a ++ b 也必须是 <> [] ... 那是计划，但我似乎无法超越类似于第一个“a ++ b <> []”的子目标，即使我的上下文明确指出“b <> []”。有什么建议吗？

我也查看了很多预先存在的列表定理，但没有发现任何特别有用的东西（减去 app_nil_l 和 app_nil_r，对于某些子目标）。

Answer 1

首先，我不确定您使用的是哪个 Coq 版本，语法肯定看起来很奇怪。其次，如果你不向我们展示你目前拥有的证据，我们很难提供帮助。我应该说确实你的策略似乎是正确的，你应该破坏两个列表，如果你先检查 or 看看哪个列表不为空会更好。

另一种选择是使用计算来显示你的引理，在这种情况下，将计算相等性，因此你将得到比较的结果。由于顺序或参数，在这种情况下仅销毁一个列表就足够了：

From mathcomp Require Import all_ssreflect.

Lemma not_empty (A : eqType) (a b : seq A) :
  [|| a != [::] | b != [::]] -> a ++ b != [::].
Proof. by case: a. Qed.

Answer 2

您 destruct a 的开始是正确的。

你应该在某个时候结束 a0::a++b<>0。它与 a++b<>0 相似，但它完全不同，因为这里有一个 cons，因此 discriminate 知道它不同于 nil。

Answer 3

从 destruct a 开始确实是个好主意。

对于a是Nil的情况，你应该推翻(a <> [] \/ b <> [])假设。会有两种情况：

正确的假设[] <> []是contradiction,
左边那个，假设b <> []是你的目标（因为a = []）

对于 a 为 a :: a0 的情况，您应该使用 Julien 所说的 discriminate。

Coq中的非空列表追加定理

Non-empty list append theorem in Coq

ocaml

formal-verification

theorem-proving

coq

coq-tactic