编辑“︁Lean决策过程”︁

= Lean决策过程 =

== 介绍 ==

在Lean定理证明器中，'''决策过程'''（Decision Procedures）是一类能够自动判断特定逻辑命题真伪的算法。这些过程是自动化证明的核心工具，能够高效处理命题逻辑、线性算术、等式理论等子领域的问题。对于初学者而言，理解决策过程有助于掌握Lean的自动化能力；对于高级用户，深入原理可优化证明策略的调用方式。

决策过程的核心特征是：
* '''完全性'''：对于其适用的问题类，总能返回确定答案（真/假）。
* '''高效性'''：通常基于多项式时间或特定启发式算法。
* '''领域特定'''：如`omega`用于线性整数算术，`cc`用于等价关系推理。

== 基础决策过程类型 ==

=== 命题逻辑（SAT求解） ===
Lean内置的`tauto`策略实现了命题逻辑的决策过程：

<syntaxhighlight lang="lean">
example (p q : Prop) : p ∧ q → q ∧ p := by
  tauto  -- 自动处理命题逻辑连接词
</syntaxhighlight>

输出结果：目标被自动证明。

=== 线性算术（Omega算法） ===
`omega`策略处理线性整数算术的不等式：

<syntaxhighlight lang="lean">
example (x y : ℤ) : 2 * x + 1 ≤ 2 * y → x ≤ y := by
  omega  -- 自动解决整数线性关系
</syntaxhighlight>

=== 等价关系（Congruence Closure） ===
`cc`策略处理基于等价关系的推理：

<syntaxhighlight lang="lean">
example (a b c : α) (f : α → α) : a = b → b = c → f a = f c := by
  cc  -- 通过等价闭包自动推导
</syntaxhighlight>

== 决策过程的工作原理 ==

<mermaid>
graph TD
    A[输入命题] --> B{语法分析}
    B -->|符合语法| C[转换为内部形式]
    B -->|不符合| D[报错]
    C --> E[应用特定决策算法]
    E --> F{可判定?}
    F -->|是| G[返回真/假]
    F -->|否| H[返回未知]
</mermaid>

数学表示：对于理论<math>T</math>，决策过程是函数<math>DP_T : Formula \to \{\top, \bot\}</math>满足：
<math>
\forall \phi \in Formula, DP_T(\phi) = \top \iff T \vdash \phi
</math>

== 高级应用案例 ==

=== 组合决策过程 ===
通过`by_cases`结合多个决策过程：

<syntaxhighlight lang="lean">
example (p q : Prop) (n : ℤ) : (p ∨ q) ∧ (¬q ∨ p) ∧ (n ≥ 0 ∨ n ≤ 0) := by
  apply And.intro
  · tauto  -- 处理命题部分
  · omega  -- 处理算术部分
</syntaxhighlight>

=== 自定义决策过程 ===
利用`meta`编程扩展决策过程（高级技巧）：

<syntaxhighlight lang="lean">
meta def my_decision (e : expr) : tactic unit :=
/- 自定义决策逻辑 -/
</syntaxhighlight>

== 性能优化建议 ==

1. '''作用域限制'''：用`only`限定决策过程的作用域
   <syntaxhighlight lang="lean">
   omega only [x, y]  -- 仅处理涉及x,y的约束
   </syntaxhighlight>

2. '''提前过滤'''：先使用`intros`减少命题复杂度

3. '''过程组合'''：按`<;>`序列组合策略，如`tauto <;> omega`

== 常见问题 ==

{| class="wikitable"
|-
! 问题 !! 解决方案
|-
| 过程超时 || 添加`maxDepth`参数限制搜索深度
|-
| 无法识别的语法 || 检查是否符合决策过程的输入语法要求
|-
| 意外成功 || 确认是否误用了过于强大的决策过程
|}

== 延伸阅读 ==

* 决策过程的完备性理论
* Nelson-Oppen组合框架
* DPLL(T)现代SMT求解架构

该内容覆盖了从基础使用到原理分析的完整知识链，通过代码示例和可视化图表帮助不同层次的读者理解Lean决策过程的工作机制与应用技巧。

[[Category:计算机科学]]
[[Category:Lean]]
[[Category:Lean高级证明技术]]