如何证明递归函数有一定的价值

Question

这是一个简单的函数和一个引理：

fun count_from where
  "count_from y 0 = []"
| "count_from y (Suc x) = y # count_from (Suc y) x"

lemma "count_from 3 5 = [3,4,5,6,7]"

这只是一个例子。真正的功能比较复杂

你能建议如何证明这样的引理吗？

我使用尾递归重新定义了函数并证明了引理如下：

fun count_from2 where
  "count_from2 y 0 ys = ys"
| "count_from2 y (Suc x) ys = count_from2 (Suc y) x (ys @ [y])"

lemma "count_from2 3 5 [] = xs ⟹ xs = [3,4,5,6,7]"
  apply (erule count_from2.elims)
  apply simp
  apply (drule_tac s="xs" in sym)
  apply (erule count_from2.elims)
  apply simp
  apply (drule_tac s="xs" in sym)
  apply (erule count_from2.elims)
  apply simp
  apply (drule_tac s="xs" in sym)
  apply (erule count_from2.elims)
  by auto

当然这不是一个合适的解决方案。

我有几个问题：

是否更喜欢使用尾递归来定义函数？它通常会简化定理证明吗？
为什么不能应用函数简化规则（count_from.simps 或 count_from2.simps）？
我是否应该定义一个引入规则来证明第一个引理？
是否可以应用函数归纳规则来证明这样的引理？

Answer 1

您的问题最好表述为“我如何评估递归定义的函数并将该评估作为定理？”

答案是通常简化器应该在评估方面做得很好。这里的问题是像 1、2、3 这样的数字使用自然数的二进制表示，而函数是由 0 和 Suc 上的模式匹配定义的。这就是您的 simps 无法应用的原因：它们仅匹配 count_from ?y 0 或 count_from ?y (Suc ?x) 形式的条款，而 count_from 3 5 两者都不是。

你可以做的是使用定理集合eval_nat_numeral，它只是将数字如 1、2、3 重写为后继符号：

lemma "count_from 3 5 = [3,4,5,6,7]"
  by (simp add: eval_nat_numeral)

另一种可能性是 code_simp 和 eval 证明方法，它们试图通过评估并检查你是否得到 True 来证明某种意义上“可执行”的陈述。他们在这里都工作得很好：

lemma "count_from 3 5 = [3,4,5,6,7]"
  by code_simp

两者之间的区别在于 code_simp 使用简化器，它为您提供了通过 Isabelle 内核的“适当”证明（但对于更大的示例，这可能非常慢），而 eval 使用代码生成器作为受信任的 oracle，因此可能不太值得信赖（尽管我在实践中从未见过问题）但速度更快。

至于你的其他问题：不，我不明白归纳法在这里是如何应用的。我不知道定义引入规则是什么意思（它们看起来像什么？）。尾递归在证明事物方面并没有真正的优势——事实上，如果你“人为地”使函数定义成为尾递归的，就像你为 count_from2 所做的那样，你实际上会使事情变得稍微困难一些，因为任何属性你想要证明然后需要额外的概括，然后才能通过归纳法证明它们。一个典型的例子是正常 vs 尾递归列表反转（我想你可以在“编程和证明”教程中找到它）。

另请注意，与您的 count_from 非常相似的函数已存在于库中：它称为 upt :: nat ⇒ nat ⇒ nat list 并具有 [a..<b] 形式的自定义语法。它以升序为您提供 a 和 b-1 之间的自然数列表。最好查看“主要内容”文档以了解内容。

如何证明递归函数有一定的价值

How to prove that a recursive function has some value

isabelle