如果在 Coq 中两个归纳类型的构造函数表达式相等，我可以根据它们对应的参数进行重写吗？

Question

我确实有一个 4 元组归纳类型如下：

Inductive my_tuple :=
  | abcd : byte -> nat -> byte -> nat -> my_tuple.

在我的上下文中，我确实有以下内容：

H : abcd b1 n1 b2 n2 = abcd b1' n1' b2' n2'

考虑到归纳类型的所有构造函数都是单射且不相交的（也讨论了），我想知道我是否可以得出相应参数相等的结论（即 b1 = b1'， n1 = n1'、b2 = b2'、n2 = n2')，然后用它们重写其他我证明中的方程式。如果是这样，我该怎么做？我已经看过这些帖子（和），但仍然不知道该怎么做。

提前感谢您的任何评论。

Answer 1

通常情况下，注入很简单，Coq 自动化就可以解决大部分简单的问题。例如在你的情况下，注入策略非常简单。

Theorem Injective_tuple : forall b1 n1 b2 n2 b1' n1' b2' n2',
  abcd b1 n1 b2 n2 = abcd b1' n1' b2' n2' -> b1 = b1' /\ n1 = n1' /\ b2 = b2' /\ n2 = n2'.
  intros.
  injection H.
  intros.
  subst.
  do 4! constructor.
  Show Proof (*what actually coq is doing ? *).
Qed.

但我假设您想了解上述定理中发生的事情。在那种情况下，嗯......，仍然很简单。可以看看Coq生成的定理，本质上就是：

(* A not so beautiful proof *)
Definition Raw_Injective_tuple b1 n1 b2 n2 b1' n1' b2' n2' :
  abcd b1 n1 b2 n2 = abcd b1' n1' b2' n2' -> b1 = b1' /\ n1 = n1' /\ b2 = b2' /\ n2 = n2' :=
    fun H => 
      let first := (f_equal (fun x => match x with
                       |abcd x _ _ _ => x
                    end) H) in
       let second := (f_equal (fun x => match x with
                       |abcd _ x _ _ => x
                     end) H) in
       let three := (f_equal (fun x => match x with
                       |abcd _ _ x _ => x
                     end) H) in
       let four := (f_equal (fun x => match x with
                       |abcd _ _ _ x => x
                     end) H) in conj first (conj second (conj three four)).

f_equal 或同余（如 Agda）是一个定理，表示如果你有一个函数，你可以在相等的两边应用它，它会保持相等的关系 (x = y -> f x = fy）。好吧，如果你能够提取等式两边的值，那么这些值是相等的并且函数是单射的，在这种情况下通过模式匹配就足够了。

如果在 Coq 中两个归纳类型的构造函数表达式相等，我可以根据它们对应的参数进行重写吗？

If two constructor expressions of an inductive type are equal in Coq, can I do rewriting based on their corresponding arguments?

coq

proof

coq-tactic

formal-verification