Coq/SSReflect: 反映&&和/\时如何进行案例分析

Question

我有以下反映谓词：

Require Import mathcomp.ssreflect.all_ssreflect.

Inductive reflect (P : Prop) (b : bool) : Prop :=
| ReflectT (p : P) (e : b = true)
| ReflectF (np : ~ P) (e :  b = false).

我正在尝试将布尔合取与逻辑合取联系起来，并通过以下单行证明：

Lemma andP (b1 b2 : bool) : reflect (b1 /\ b2) (b1 && b2).
Proof.
  case b1; case b2; constructor =>//; by case.
Qed.

不过，我不明白最后的; by case.是怎么应用的。当我们检查没有最后一个 ; by case.:

的证明时

Lemma andP (b1 b2 : bool) : reflect (b1 /\ b2) (b1 && b2).
Proof.
  case b1; case b2; constructor =>//.

我们得到 6 个子目标（其中 2 个基本正确）：

6 subgoals (ID 45)

  b1, b2 : bool
  ============================
  true /\ false

subgoal 2 (ID 46) is:
 true && false = true
subgoal 3 (ID 116) is:
 false /\ true
subgoal 4 (ID 117) is:
 false && true = true
subgoal 5 (ID 187) is:
 false /\ false
subgoal 6 (ID 188) is:
 false && false = true

我不确定如何从这里开始，因为它们都是 false - 我们如何证明这一点？我尝试单独执行 . case. 但这不起作用。 ; by case 如何一次承认这些子目标？

谢谢。

Answer 1

我不确定你为什么得到 6 个子目标：case b1; case b2; constructor 产生 4 个子目标，对应于布尔值组合的四种可能情况：

  true /\ true

subgoal 2 (ID 13) is:
 ~ (true /\ false)
subgoal 3 (ID 15) is:
 ~ (false /\ true)
subgoal 4 (ID 17) is:
 ~ (false /\ false)

第一个被 // 认为微不足道。

Set Printing Coercions 会告诉你你的子目标或实际如下：

  is_true true /\ is_true true

subgoal 2 (ID 13) is:
 ~ (is_true true /\ is_true false)
subgoal 3 (ID 15) is:
 ~ (is_true false /\ is_true true)
subgoal 4 (ID 17) is:
 ~ (is_true false /\ is_true false)

展开 is_true 可能有帮助：case b1; case b2; constructor; rewrite /is_true.:

  true = true /\ true = true

subgoal 2 (ID 19) is:
 ~ (true = true /\ false = true)
subgoal 3 (ID 20) is:
 ~ (false = true /\ true = true)
subgoal 4 (ID 21) is:
 ~ (false = true /\ false = true)

最后 3 个子目标的形式为 (_ /\ _) -> False（因为 ~ P 代表 not P，展开为 P -> False。

因此在 constructor 之后添加的 case 策略破坏了顶级假设，将最后三个目标变成了以下内容：

  true = true -> false = true -> False

subgoal 2 (ID 145) is:
 false = true -> true = true -> False
subgoal 3 (ID 155) is:
 false = true -> false = true -> False

在这里，我们将 false = true 作为每个子目标的假设之一，这意味着我们得到了一个矛盾，SSReflect 可以立即识别并使用 principle of explosion.

完成证明

Answer 2

战术的顺序组合行为在最近几年发生了一些变化。如今，像 constructor 这样的策略可以在执行它们的延续时回溯。因为您对 reflect 的定义与标准定义有点不同，如果您只是调用 constructor，Coq 将立即应用 ReflectT，导致在以下三种情况下卡住目标：

Lemma andP (b1 b2 : bool) : reflect (b1 /\ b2) (b1 && b2).
Proof.
case b1; case b2=> /=.
- constructor=> //.
- (* constructor. *) (* Stuck *)

当您使用顺序组合时，constructor 策略回溯，正确找到 ReflectF 构造函数。

  constructor; by try case.
- constructor; by try case.
- constructor; by try case.
Qed.

Coq/SSReflect: 反映&&和/\时如何进行案例分析

Coq/SSReflect: How to do case analysis when reflecting && and /\

coq

coq-tactic

ssreflect