在 Coq 中使用 unfold 策略然后 fold 有什么作用吗？

Question

unfold def. fold def. 会在 Coq 证明中取得任何成就吗？

换句话说：这两种战术应用顺序之间会有区别吗？：

unfold def. fold def. cbn.
cbn.

Answer 1

当然。 unfold def 内联 def 的定义，并且也执行一些基本的归约，例如如果 def 在内联之前应用于任何内容。

Definition hold {T} (x : T) : Prop := True.
Goal (not False -> hold not).
unfold not.
(* inline not: (fun A : Prop => A -> False) False -> hold (fun A : Prop => A -> False)
   and reduce: (False -> False) -> hold (fun A : Prop => A -> False) *)

但是，fold def 不会“取消减少”def 的应用程序。如果你现在做

fold not.

它将不会折叠False -> False回到not False。它只会找到hold下的not，所以你得到(False -> False) -> hold not作为你的目标。（fold (not False) 会将 not False 减少到 False -> False，搜索它，然后最终给出目标 not False -> hold (fun A : Prop => A -> False，但同样，它没有正确撤消 unfold).因此，基本上，序列 unfold def. fold def. 内联并简化了 def 已被“使用”（例如应用）的用法，并试图保持其他用法不变。

另一个例子，这次使用 iota-reduction（减少破坏）而不是 beta-reduction。

Definition def : bool := true.
Definition truth (b : bool) : Prop := if b then True else False.
Goal ((if def then True else False) -> truth def).
unfold def.
(* inline def: (if true then True else False) -> truth true
   and reduce: True -> truth true *)
fold def.
(* goal: True -> truth def *)

在第一种情况下，cbn. 和 unfold not. fold not. cbn. 是不同的（在这两种情况下，cbn 都不做任何事情）。在后一种情况下，无论我们把它放在哪里，cbn. 都会直接将我们带到 True -> True。

Answer 2

如果您查看 fold (https://coq.inria.fr/refman/proof-engine/tactics.html#coq:tacn.fold) and unfold (https://coq.inria.fr/refman/proof-engine/tactics.html#coq:tacn.unfold) 的文档，您会发现它们并不期望相同类型的论点。 unfold 将标识符作为参数，而 fold 将术语作为参数。

所以如果你的目标中有 def x y，你可以 unfold def 访问它的定义，但是你可能必须使用 fold (def x y) 到 return最初的目标。

在任何情况下，都不能保证 unfold def ; fold (def x y) 不会产生任何结果，因为目标中可能还有其他展开的 def x y。

这是一个具体的例子，可以看到 fold 和 unfold 的实际效果。如果目标在战术后发生变化，我会在战术后的评论中添加新目标。还要注意 Fail progress tac 的使用，它断言执行策略 tac 根本不会影响目标。

Definition foo (b : bool) :=
  if b then 0 else 1.

Goal foo true + 1 = foo false.
Proof.
  unfold foo.
  (* 0 + 1 = 1 *)
  Fail progress fold foo.
  fold (foo true).
  (* foo true + S (foo true) = S (foo true) *)
  Fail progress fold (foo false).
  unfold foo.
  (* 0 + 1 = 1 *)
  fold (foo false).
  (* 0 + foo false = foo false *)
  fold (foo true).
  (* foo true + foo false = foo false *)
  unfold foo at 2.
  (* foo true + 1 = foo false *)

可以看到，fold foo不会做任何事情，而fold true和fold false会，当然，它也是贪婪的，任何0都会变成fold true.

在 Coq 中使用 unfold 策略然后 fold 有什么作用吗？

Does using the unfold tactic followed by fold in Coq do anything?

coq

coq-tactic