伊莎贝尔的不等式推理

Question

我有以下简单证明：

lemma
    fixes a b n :: nat
    assumes a: "a > n" "b > n"
    shows "a*b > n*n"
proof -
    from assms show "a*b > n*n" by(simp_all add: field_simps)  ERROR
qed

在证明状态下，伊莎贝尔说：

Successful attempt to solve goal by exported rule: n * n < a * b

但是然后：

Failed to apply initial proof method⌂: using this: n < a n < b goal (1 subgoal): 1. n * n < a * b

问题是什么？。实际上我对实际的单个步骤感兴趣，所以我想伊莎贝尔可以告诉我方法。

Answer 1

field_simps 适合重新排列术语，但不适合这种推理。当你想证明这样的事情时，你通常需要一个好的规则；在这种情况下，关于（严格的）不等式和乘法。

如果你有一些看起来微不足道的东西，但你不知道如何准确地证明它and/or你不知道伊莎贝尔的相关事实是什么，sledgehammer通常会有帮助:

from assms show "a*b > n*n"
  sledgehammer

  > Sledgehammering... 
  > Proof found... 
  > "cvc4": Try this:
  >   by (metis (no_types, lifting) dual_order.strict_trans gr_implies_not_zero 
  >         linorder_neqE_nat mult.commute nat_0_less_mult_iff 
  >         nat_mult_less_cancel1) (796 ms)

sledgehammer 发现的证明的问题在于，如您所见，它们通常冗长、缓慢，而且不是很有启发性。在维护方面，它们也有些脆弱 w.r.t。背景理论的变化。尽管如此，它仍然是一个很好的起点，您通常可以从大锤证明（例如 nat_mult_less_cancel1 此处）中为您的证明阅读相关事实。

另一种查找相关事实的方法是 find_theorems 命令，或者等效地，Isabelle/jEdit IDE 中的查询面板。如果你这样做

find_theorems "_ * _ > _ * _"

或者，等效地，在“查询”面板中输入 _ * _ > _ * _，您将获得大量输出以供通读，但一些相关事实隐藏在该输出的末尾，例如mult_strict_mono':

thm mult_strict_mono'
> ?a < ?b ⟹ ?c < ?d ⟹ 0 ≤ ?a ⟹ 0 ≤ ?c ⟹ ?a * ?c < ?b * ?d

你的证明看起来像这样：

from assms show "a*b > n*n"
  by (rule mult_strict_mono') simp_all

simp_all只是解除了剩余的证明义务n ≥ 0。

哦，顺便说一句：你得到 Successful attempt to solve goal 但随后出现错误消息的事实是交互式 Isabelle 的非线性特性的结果：当你写 by 时，证明尝试被分叉到后台，随后证明文件的处理继续进行，就好像证明已经成功一样。这是为了允许并行化并允许用户继续处理文档，即使某些证明已损坏。

Successful attempt 消息来自在 show 之后调用的 Isabelle 部分，该部分看到 a*b > n*n 的成功（但仍未决）证明。但是，您随后会立即从 by (simp_all …) 中收到一条错误消息，指出证明方法失败。在批处理模式下，这样的故障比较剧烈（也比较明显）。

伊莎贝尔的不等式推理

Inequality reasoning in Isabelle

formal-methods

theorem-proving

isabelle