Coq：如何证明涉及字符串的 if 语句？

Question

我有一个 string a 和 string b 比较，如果 equals 有一个 string c，否则有 string x。我知道假设fun x <= fun c。我如何证明以下陈述？ fun 是一些接受 string 和 returns nat 的函数。

fun (if a == b then c else x) <= S (fun c)

逻辑似乎很明显，但我无法拆分 coq 中的 if 语句。任何帮助将不胜感激。

谢谢！

Answer 1

如果你能写一个 if-then-else 语句，这意味着测试表达式 a == b 是一个有两个构造函数的类型（如 bool）或（sumbool ).我首先假设类型是 bool。在这种情况下，证明期间的最佳方法是输入以下命令。

case_eq (a == b); intros hyp_ab.

这将产生两个目标。在第一个中，您将有一个假设

hyp_ab : a == b = true

断言测试成功并且目标结论具有以下形状（if-then-else 替换为 then分支）：

乐趣 c <= S（乐趣 c）

第二个目标，你会有一个假设

hyp_ab : a == b = false

并且目标结论具有以下形状（if-then-else 被 else 分支替换）。

fun x <= S (fun c)

你应该可以从那里继续。

另一方面，Coq 的 String 库有一个函数 string_dec，return 类型为 {a = b}+{a <> b}。如果你的符号 a == b 是 string_dec a b 的漂亮符号，最好使用以下策略：

destruct (a == b) as [hyp_ab | hyp_ab].

行为将与我上面描述的非常接近，只是更易于使用。

直觉上，当您对 if-then-else 语句进行推理时，您会使用 case_eq、destruct 或 [=26] 这样的命令=] 引导您分别研究这两个执行路径，请记住假设您选择这些执行路径中的每一个的原因。

Answer 2

让我补充一下 Yves 的回答，指出一个通用的 "view" 模式在需要案例分析的许多情况下都能很好地工作。我将使用 math-comp 中的内置支持，但该技术并不特定于它。

让我们假设您的初始目标：

From mathcomp Require Import all_ssreflect.

Variables (T : eqType) (a b : T).
Lemma u : (if a == b then 0 else 1) = 2.
Proof.

现在，您可以使用 case_eq + simpl 到达下一步；但是，您也可以使用更专业的 "view" 引理进行匹配。例如，您可以使用 ifP:

ifP : forall (A : Type) (b : bool) (vT vF : A),
      if_spec b vT vF (b = false) b (if b then vT else vF)

其中 if_spec 是：

Inductive if_spec (A : Type) (b : bool) (vT vF : A) (not_b : Prop) : bool -> A -> Set :=
    IfSpecTrue : b -> if_spec b vT vF not_b true vT
  | IfSpecFalse : not_b -> if_spec b vT vF not_b false vF

看起来有点混乱，重要的一点是类型族的参数bool -> A -> Set。第一个练习是"prove the ifP lemma!".

确实，如果我们在证明中使用 ifP，我们会得到：

case: ifP.
Goal 1: (a == b) = true  -> 0 = 2
Goal 2: (a == b) = false -> 1 = 2

请注意，我们不必指定任何内容！实际上，形式为 { A } + { B } 的引理只是这种视图模式的特例。这个技巧适用于许多其他情况，例如，您也可以使用 eqP，它有一个规范将布尔相等与命题相等相关联。如果你这样做：

case: eqP.

你会得到：

Goal 1: a = b  -> 0 = 2
Goal 2: a <> b -> 1 = 2

非常方便。事实上，eqP 基本上是 type_dec 原则的通用版本。

Coq：如何证明涉及字符串的 if 语句？

Coq: How to prove if statements involving strings?

coq

coq-tactic