ssreflect：初等代数简化

Question

有这个引理

Lemma my_lemma n : n %/ 4 * 4 + n %% 4 * 5 - n %% 4 * 4 = n.
Proof.
  (* ? *)
  (* n %/ 4 * 4 + n %% 4 = n. *)
  symmetry. apply: divn_eq n 4.
Qed.

如何将 n %% 4 * 5 - n %% 4 * 4 转换为 n %% 4？那就小菜一碟了。

Answer 1

为了解决这个问题，ssreflect 中的惯用方法是使用手头所有关于算术的定理进行重写。这需要一点搜索。我建议你广泛使用 Search 命令。

第一个障碍是您的公式包含 (A + B - C)，这与 (A + (B - C)) 不同，因为 t运行减法的特殊行为。要在两者之间进行转换，您可以查找定理。我输入了以下 Search 命令。

Search (_ + _ - _).

在列出的定理中，我对addnBA（加法和减法之间的关联性）感到满意，但是这个引理有一个附加条件，我想先证明它。所以我使用下面的重写命令。

rewrite -addnBA; last first.

这里我想把比较中的乘法分解出来。我使用以下 Search 命令寻找包含此模式的定理。

搜索 _ (_ * _ <= _ * _)。

请注意这个Search命令中的第一个_模式，它很重要，如果你不包括它，只会列出一些有趣的定理，而我们想要的不会出现。我要的是leq_mul2l

我按以下方式执行此证明：

by rewrite leq_mul2l orbC.

在 rewrite leq_mul2l 之后的语句是一个 _ || _ 语句（布尔析取），右侧显然是真模计算（在 ssreflect 中），通过交换这个布尔析取,我做的目的是为了不费吹灰之力直接解决目标

现在，我们来看看乘法对减法的分配性。这里的搜索命令使用起来比较棘手，因为分配律是用关键字处理的。

Search (_ * (_ - _)).

没有提供任何有用的结果，但 ssrnat 中有关于命名模式的有用文档。它告诉我们，当减法是二次运算时，那么定理名中很可能出现B。这里我们想要一个关于自然数的定理，所以它应该在ssrnat中，所以我尝试以下。

Search "B" in ssrnat.

这告诉我，有些定理的陈述依赖于 left_distributive 和 right_distributive 等概念。您可以通过打印来理解这些概念。

Print right_distributive.

在长运行中，你往往会记住你经常使用的定理名称，所以在我的例子中，我知道我要使用mulnBr，因为减法是在乘法的权利，我们正在处理自然数。 math-comp 库的设计非常注重命名的规律性。

那么我们现在可以通过以下方式完成修改：

rewrite -mulnBr muln1.

你终于可以应用你想应用的引理了。

完整脚本如下：

Lemma my_lemma n : n %/ 4 * 4 + n %% 4 * 5 - n %% 4 * 4 = n.
Proof.
symmetry.
rewrite -addnBA; last first.
  by rewrite leq_mul2l orbC.
rewrite -mulnBr muln1.
apply: divn_eq n 4.
Qed.

ssreflect：初等代数简化

ssreflect: elementary algebraic simplification

coq

ssreflect