Coq:为什么我不能从Decidable的实例中获得显式的见证？

在 Coq 中，Decidable 是一个用于表示命题是否可判定的类型类。它通常与 sumbool 类型一起使用，sumbool 是一个包含两个布尔值的类型，表示一个命题的真或假。Decidable 的实例允许你在编译时确定一个命题的真假，并且可以提供一个显式的证明（witness）来支持这个结论。

如果你不能从 Decidable 的实例中获得显式的见证，可能有以下几个原因：

1. 缺少显式构造函数

Decidable 类型的实例可能没有提供显式的构造函数来创建真或假的证明。例如，eq_dec 类型通常用于比较两个值是否相等，但它可能只提供了一个隐式的决策过程，而没有提供显式的证明。

2. 使用了自动推导

在某些情况下，Coq 的自动推导机制可能会隐藏了显式的证明。例如，当你使用 Qed. 来结束一个证明时，Coq 可能会自动推导出一个隐式的证明，而不是一个显式的证明。

3. 缺少类型类实例

如果你没有为特定的类型提供 Decidable 的实例，Coq 将无法为你生成显式的证明。你需要手动定义这些实例，或者使用现有的库来提供这些实例。

解决方法

提供显式构造函数

你可以为 Decidable 类型提供一个显式的构造函数，以便在需要时生成显式的证明。例如：

Definition eq_dec (A : Type) := forall x y : A, {x = y} + {x <> y}.

Instance bool_eq_dec : eq_dec bool.
Proof.
  intros x y.
  destruct x, y; try (left; reflexivity); right; congruence.
Qed.

在这个例子中，bool_eq_dec 是一个 eq_dec 类型的实例，它为布尔类型提供了显式的相等性决策。

使用 sumbool_to_bool

如果你有一个 sumbool 类型的值，你可以使用 sumbool_to_bool 函数来获取一个布尔值和一个显式的证明。例如：

Definition sumbool_to_bool (P : Prop) (b : {P} + {~ P}) : bool :=
  if b then true else false.

Lemma sumbool_to_bool_correct : forall P (b : {P} + {~ P}),
    sumbool_to_bool P b = true <-> P.
Proof.
  intros P b; destruct b; split; congruence.
Qed.

在这个例子中，sumbool_to_bool_correct 提供了一个显式的证明，表明 sumbool_to_bool 函数返回 true 当且仅当命题 P 为真。

使用 Decidable 库

你可以使用现有的库，如 Coq.Logic.Decidable，它提供了许多常见类型的 Decidable 实例，并且通常会提供显式的证明。

应用场景

显式的见证在以下场景中非常有用：

• 形式化验证：在形式化验证中，你需要能够提供明确的证据来支持你的结论。
• 程序提取：当你从 Coq 中提取程序时，显式的见证可以帮助你生成更高效的代码。
• 交互式证明：在交互式证明过程中，显式的见证可以帮助你更好地理解证明的结构。

总之，如果你不能从 Decidable 的实例中获得显式的见证，你可以尝试提供显式的构造函数，使用 sumbool_to_bool 函数，或者使用现有的库来解决这个问题。