在 Coq 中用匹配表达式分解构造函数的相等性

Question

我有一个类似于的问题，但是，我的等式包含一个 match 表达式。考虑示例（这是荒谬的，但仅用于澄清）：

Fixpoint positive (n : nat) :=
  match n with
  | O => Some O
  | S n => match positive n with
    | Some n => Some (S n)
    | None => None (* Note that this never happens *)
    end
  end.

Lemma positiveness : forall n : nat, Some (S n) = positive (S n).
Proof.
intro.
simpl.

此时，环境中有n : nat，目标是：

Some (S n) =
match positive n with
| Some n0 => Some (S n0)
| None => None
end

我想将其转换为环境中的两个子目标 n, n0 : nat:

positive n = Some n0  (* Verifying the match *)
S n = S n0            (* Verifying the result *)

而且我希望如果 match 证明相等性有多个可能有效的情况，那么新目标是所有可能性的析取，例如对于

Some (S n) =
match positive n with
| Some (S n0) => Some (S (S n0))
| Some O => Some (S O)
| None => None
end

我希望

   (positive n = Some (S n0) /\ S n = S (S n0))  (* First alternative *)
\/ (positive n = Some O      /\ S n = S O)       (* Second alternative *)

是否有 Coq 策略可以执行此操作或类似操作？

Answer 1

我无法理解你的动机。在您的示例中，使用更一般的引理更容易证明您的结果：

Fixpoint positive (n : nat) :=
  match n with
  | O => Some O
  | S n => match positive n with
    | Some n => Some (S n)
    | None => None (* Note that this never happens *)
    end
  end.

Lemma positiveness n : positive n = Some n.
Proof.
  now induction n as [|n IH]; simpl; trivial; rewrite IH.
Qed.

Lemma positiveness' n : Some (S n) = positive (S n).
Proof. now rewrite positiveness. Qed.

也许您要执行的案例分析更适合不同的应用程序？

Answer 2

Is there a Coq tactic which does this or something similar?

如果你运行destruct (positive n) eqn:H，你会得到两个子目标。在第一个子目标中，您得到：

  n, n0 : nat
  H : positive n = Some n0
  ============================
  Some (S n) = Some (S n0)

在第二个子目标中你得到

  n : nat
  H : positive n = None
  ============================
  Some (S n) = None

这不是你要求的，但是在第二个子目标中，你可以写assert (exists n0, positive n = Some n0)；这将为您提供您寻求的目标，您可以通过 destructing exists 并使用 congruence 或 discriminate 来显示剩余的目标 positive n不能同时为 None 和 Some。

在 Coq 中用匹配表达式分解构造函数的相等性

Decomposing equality of constructors with match expressions in Coq

coq

coq-tactic