证明助手中的认证计算
Certified calculations in a proof assistant
手动或由计算机代数系统执行的符号计算可能有错误或仅在某些假设条件下成立。一个经典的例子是 sqrt(x^2) == x 这在一般情况下是不正确的，但如果 x 是实数且非负则它确实成立。
是否有使用 Coq、Isabelle、HOL、Metamath 或其他证明 assistants/checkers 证明符号计算正确性的示例？特别是，我对微积分和线性代数示例感兴趣，例如求解定积分或不定积分、微分方程和矩阵方程。
更新：
更具体地说，知道是否有微积分和线性代数中的本科作业可以正式解决（可能在证明助手的帮助下）以便解决方案可以由证明检查器自动验证的示例会很有趣.精益的一个非常简单的示例分配是 here.
我唯一想到的是 Isabelle/HOL 可以重放 SMT 证明（例如由 Z3 或 CVC4 生成），例如涉及整数和实数算术。对于计算机代数系统，我不知道有任何可比较的例子。
问题在于，计算机代数系统的设置方式往往无法输出详细的简化证明——如果他们能够做到这一点，人们可以尝试在定理证明器中重放它.但它必须超越纯粹的等式推理，因为许多规则（例如你的例子）需要证明不等式作为先决条件。
如果计算机代数系统能够将它们的计算轨迹输出为使用的重写规则列表，包括如何证明它们的每个先决条件，原则上可以在定理证明器中重播这样的轨迹 –但这当然需要 CAS 使用的每条规则在定理证明器中都有相应的规则（这大致就是重放 SMT 证明在 Isabelle 中的工作方式）。但是，我不知道有这样的项目。
另一方面，有各种示例使用 CAS 来计算一些易于验证（但难以计算）的结果，例如分解一个多项式，分离出一个实数多项式的根，Wilf-Zeilberger 见证，然后在定理证明器中验证这确实是一个有效结果。但是，这并不涉及证明CAS的计算过程，只是结果。
对于 Coq 证明助手，有几个库可以提供帮助。 Coquelicot (https://gitlab.inria.fr/coquelicot/coquelicot). The Coquelicot team made an exercise and participated in the French baccalauréat - I would say comparable more to a college than a high school math exam - and finished proofs for a good part of the exercises. The proofs can be found in the examples here (https://gitlab.inria.fr/coquelicot/coquelicot/-/tree/master/examples) 非常符合您的要求。我想过把习题和答案翻译成英文。
但这是几年前的事了，同时也有针对特定应用程序的非常强大的工具。例如。有 coq-interval (https://gitlab.inria.fr/coqinterval/interval)，它完全自动地对相当复杂的不等式进行 Coq 证明，比如高阶多项式在特定区间内与具有特定最大偏差的正弦函数匹配。它通过泰勒分解和计算残差的上限来做到这一点。它还可以对范围广泛的数值积分进行错误证明。最近添加的一项新功能是能够绘制经过验证的正确图。
在 Coq 中证明无限精度实数和浮点计算之间的误差的工具是 Gappa (https://gitlab.inria.fr/gappa/gappa)。
另一个非常有趣的 Coq 开发是 CoRN (https://github.com/coq-community/corn)，它是 Coq 中构造实数的形式化。构造实数是可以计算的真实实数。本质上，构造实数是一种算法，可以将数字计算到任何所需的精度，并证明该算法收敛。可以证明这样的数满足实数的所有常见性质。构造实数的一个有趣的副作用是它们只需要 LPO 作为公理，而在经典实数中实数本身的存在就是一个公理。你在 CoRN 中做的任何计算，比如 pi>3，都会自动被证明是正确的。
所有这些工具都包含在 Coq 平台中，这是 Coq 证明助手的一个通用发行版。
还有更多，而且还在稳步增加。我想说的是，在不久的将来，我们就会拥有一个可用且经过验证的正确 CAS。
出于演示目的，我准备了一个小的“假练习”，既可以说明验证计算的意义，也可以说明 Coq 中可用的最图形化的方法（这显示了您可以在 11 月 17 日完成的一些事情）。 2021).
可以在github github.com:ybertot/osxp_demos_coq, especially the file sin_properties.v上看到。
演示遵循以下路径：
证明我们可以自动陈述和证明给出 PI 的“安全近似值”的陈述（这是 Coq 库中数学常数的名称）。
证明 Coq 可以用来绘制一个已知的数学函数，在本例中是 sin 介于 0 和 PI 之间的函数。这依赖于与 gnuplot 的连接以进行图形显示。恐怕 gnuplot 不会被包含在 M. Soegtrop 在另一个答案中提到的 Coq 平台中。
表明我们也可以使用 Coq 绘制函数 sin(1/x)
（该图实际上作为 pdf file 保存在 github 存储库中）
表明在这种情况下，通用函数绘图仪实际上 returns 是一个误导性结果（通用函数绘图仪是 gnuplot）。
github 存储库 as a pdf file.
中也给出了误导性情节
下一步是证明我们可以证明某些计算的区间保证，有时会自动使用 interval 策略，有时 interval 策略无法得出结论.这里重要的一点是，命令无法得出结论，而不是给出一个不可信的答案。当这种情况发生时，用户可以依靠知识和数学推理来获得想要的结果。该演示演示如何证明对于特定范围内的任何 x，sin 函数保证具有正值。
下一步是证明sin x < x对于每个正数x，它表明数学推理可以依赖于各种数学技巧：
- 将区间分解为两部分，
- 使用中值定理，
- 计算
x - sin x 的导数（这可以在 Coq 中自动完成），
- 根据已知
cos 在 0 和 PI 之间严格递减的事实。
这只是一个简短的演示，还旨在解释定理证明器与袖珍计算器的使用方式有何不同，因为仅返回近似值而不限定数学公式的值是一个过程真的不可信。
原题还包括计算积分的问题。 interval 包也包含这方面的设施。
手动或由计算机代数系统执行的符号计算可能有错误或仅在某些假设条件下成立。一个经典的例子是 sqrt(x^2) == x 这在一般情况下是不正确的，但如果 x 是实数且非负则它确实成立。
是否有使用 Coq、Isabelle、HOL、Metamath 或其他证明 assistants/checkers 证明符号计算正确性的示例？特别是，我对微积分和线性代数示例感兴趣，例如求解定积分或不定积分、微分方程和矩阵方程。
更新： 更具体地说，知道是否有微积分和线性代数中的本科作业可以正式解决（可能在证明助手的帮助下）以便解决方案可以由证明检查器自动验证的示例会很有趣.精益的一个非常简单的示例分配是 here.
我唯一想到的是 Isabelle/HOL 可以重放 SMT 证明（例如由 Z3 或 CVC4 生成），例如涉及整数和实数算术。对于计算机代数系统，我不知道有任何可比较的例子。
问题在于，计算机代数系统的设置方式往往无法输出详细的简化证明——如果他们能够做到这一点，人们可以尝试在定理证明器中重放它.但它必须超越纯粹的等式推理，因为许多规则（例如你的例子）需要证明不等式作为先决条件。
如果计算机代数系统能够将它们的计算轨迹输出为使用的重写规则列表，包括如何证明它们的每个先决条件，原则上可以在定理证明器中重播这样的轨迹 –但这当然需要 CAS 使用的每条规则在定理证明器中都有相应的规则（这大致就是重放 SMT 证明在 Isabelle 中的工作方式）。但是，我不知道有这样的项目。
另一方面，有各种示例使用 CAS 来计算一些易于验证（但难以计算）的结果，例如分解一个多项式，分离出一个实数多项式的根，Wilf-Zeilberger 见证，然后在定理证明器中验证这确实是一个有效结果。但是，这并不涉及证明CAS的计算过程，只是结果。
对于 Coq 证明助手，有几个库可以提供帮助。 Coquelicot (https://gitlab.inria.fr/coquelicot/coquelicot). The Coquelicot team made an exercise and participated in the French baccalauréat - I would say comparable more to a college than a high school math exam - and finished proofs for a good part of the exercises. The proofs can be found in the examples here (https://gitlab.inria.fr/coquelicot/coquelicot/-/tree/master/examples) 非常符合您的要求。我想过把习题和答案翻译成英文。
但这是几年前的事了，同时也有针对特定应用程序的非常强大的工具。例如。有 coq-interval (https://gitlab.inria.fr/coqinterval/interval)，它完全自动地对相当复杂的不等式进行 Coq 证明，比如高阶多项式在特定区间内与具有特定最大偏差的正弦函数匹配。它通过泰勒分解和计算残差的上限来做到这一点。它还可以对范围广泛的数值积分进行错误证明。最近添加的一项新功能是能够绘制经过验证的正确图。
在 Coq 中证明无限精度实数和浮点计算之间的误差的工具是 Gappa (https://gitlab.inria.fr/gappa/gappa)。
另一个非常有趣的 Coq 开发是 CoRN (https://github.com/coq-community/corn)，它是 Coq 中构造实数的形式化。构造实数是可以计算的真实实数。本质上，构造实数是一种算法，可以将数字计算到任何所需的精度，并证明该算法收敛。可以证明这样的数满足实数的所有常见性质。构造实数的一个有趣的副作用是它们只需要 LPO 作为公理，而在经典实数中实数本身的存在就是一个公理。你在 CoRN 中做的任何计算，比如 pi>3，都会自动被证明是正确的。
所有这些工具都包含在 Coq 平台中，这是 Coq 证明助手的一个通用发行版。
还有更多，而且还在稳步增加。我想说的是，在不久的将来，我们就会拥有一个可用且经过验证的正确 CAS。
出于演示目的，我准备了一个小的“假练习”，既可以说明验证计算的意义，也可以说明 Coq 中可用的最图形化的方法（这显示了您可以在 11 月 17 日完成的一些事情）。 2021).
可以在github github.com:ybertot/osxp_demos_coq, especially the file sin_properties.v上看到。
演示遵循以下路径：
证明我们可以自动陈述和证明给出 PI 的“安全近似值”的陈述（这是 Coq 库中数学常数的名称）。
证明 Coq 可以用来绘制一个已知的数学函数，在本例中是
sin介于 0 和 PI 之间的函数。这依赖于与gnuplot的连接以进行图形显示。恐怕gnuplot不会被包含在 M. Soegtrop 在另一个答案中提到的 Coq 平台中。表明我们也可以使用 Coq 绘制函数
sin(1/x)表明在这种情况下，通用函数绘图仪实际上 returns 是一个误导性结果（通用函数绘图仪是
中也给出了误导性情节gnuplot）。下一步是证明我们可以证明某些计算的区间保证，有时会自动使用
interval策略，有时interval策略无法得出结论.这里重要的一点是，命令无法得出结论，而不是给出一个不可信的答案。当这种情况发生时，用户可以依靠知识和数学推理来获得想要的结果。该演示演示如何证明对于特定范围内的任何x，sin函数保证具有正值。下一步是证明
sin x < x对于每个正数x，它表明数学推理可以依赖于各种数学技巧：- 将区间分解为两部分，
- 使用中值定理，
- 计算
x - sin x的导数（这可以在 Coq 中自动完成）， - 根据已知
cos在 0 和 PI 之间严格递减的事实。
这只是一个简短的演示，还旨在解释定理证明器与袖珍计算器的使用方式有何不同，因为仅返回近似值而不限定数学公式的值是一个过程真的不可信。
原题还包括计算积分的问题。 interval 包也包含这方面的设施。