Coq 中的析取交换性

Question

我想要一个 Ltac 策略来完成析取交换性的工作。主要是，如果我在假设 H 的某处有子项 P \/ Q，Ltac Com H 会将 Q \/ P 作为另一个假设添加到上下文中。

我试过通过公理和 apply它提供交换规则；但它只适用于简单的假设，例如在 R -> (P \/ Q) 中失败；它应该添加到上下文的位置 R -> (Q \/ P).

Answer 1

您可以使用 setoid 重写库，它允许您使用相等关系以外的关系进行重写。以下代码段显示了如何在假设中将 A \/ B 替换为 B \/ A：

Require Import Setoid.

Variables A B C : Prop.

Goal ~ (A \/ B -> C).
intros H.
rewrite or_comm in H.
Abort.

要实现你想要的策略，我们只需要复制假设并在其中重写。请注意 fresh 策略的使用，它会生成一个新的假设名称。

Ltac Comm H :=
  let H' := fresh "H" in
  pose proof H as H';
  rewrite or_comm in H'.

这是 Comm 的实际演示。

Goal ~ (A \/ B -> C).
intros H.
Comm H.
Abort.

Edit Coq manual 有一个关于 setoid 重写的部分。粗略地说，你可以在一个假设中用any关系重写R，前提是你证明那个假设中出现的操作与该关系兼容。例如，如果我们将 R 设为 <->，上面的重写是有效的，因为标准库中的引理表明逻辑等价性受到蕴涵的尊重。

注意我通常建议不要让 Coq 自己命名假设：这些名称往往非常不稳定，这通常会导致证明脚本中断。根据经验，如果您正在编写完全自动化的证明脚本，您应该让 Coq 自己选择名称，这些脚本从不引用自动选择的名称。这是避免此问题的 Comm 的另一个版本。

Ltac Comm' H H' :=
  pose proof H as H';
  rewrite or_comm in H'.

Goal ~ (A \/ B -> C).
intros H.
Comm H H'.
Abort.

Disjunction Commutavity in Coq