知识表示中的逻辑编程：有限递归程序与工具探索

# 知识表示中的逻辑编程：有限递归程序与工具探索 ## 1. ID - 逻辑与知识表示 ID - 逻辑在知识表示领域有着重要的地位。在 ID - 逻辑理论中，对于给定的实例 \(I \in Inst_{\sigma'}\)，实例 \(K \in Inst_{\sigma}\) 若要成为 \(T\) 的 \(I\) - 模型，需要满足 \(K\) 是 \(T'\) 的 \(I\) - 模型，并且 \(K|_{\sigma_{def}}\) 是程序 \(T'' \cup K|_{\sigma \setminus \sigma_{def}}\) 的完全有根模型。简单来说，要得到 ID - 逻辑理论 \(T\) 的 \(I\) - 模型，我们需要猜测 \(\sigma\) 中所有关系符号的扩展（保持 \(\sigma'\) 中关系符号的扩展按 \(I\) 指定，且不引入新常量），然后验证 \(\sigma_{def}\) 中关系符号的扩展在有根语义下由程序 \(T''\) 和不在 \(\sigma_{def}\) 中的关系符号的扩展完全确定。 ID - 逻辑（在语言中无函数符号的限制下）与（非析取）回答集编程具有相同的表达能力。不过，它的语义更简单，因为它依赖于约束和定义这两个直观的概念，所以在知识表示应用方面有很大的潜力。 ## 2. 回答集编程工具 回答集编程由于有效的计算工具而逐渐变得重要，这些工具足以处理几类“工业级”问题。处理回答集程序的一般方法包括两个步骤： 1. **接地（Grounding）**：将带有变量的输入程序实例化并简化为命题程序。 2. **求解（Solving）**：计算步骤（1）得到的程序的回答集。接地步骤的设计是为了能在步骤（2）中恢复原始程序的所有回答集。 以下是一些常见的工具： |工具名称|网址|特点| | ---- | ---- | ---- | |lparse/smodels|www.tcs.hut.fi/Software/smodels/|最早使回答集编程实用化的尝试，lparse 是求解器开发者最常用的接地器，smodels 是最具竞争力的求解器之一| |dlv 系统|www.dbai.tuwien.ac.at/proj/dlv/|提供集成的接地器和求解器包，能计算带聚合的析取程序的回答集，有 SQL、继承、规划、溯因和诊断等前端，是目前最灵活的回答集编程系统| |gringo|gringo.sourceforge.net/|接地器领域的新成员| |clasp|www.cs.uni - potsdam.de/clasp/|在第一届回答集编程竞赛中表现出色，赢得两项赛事| |pbmodels|www.cs.uky.edu/ai/pbmodels/|表现良好的求解器| |cmodels|www.cs.utexas.edu/users/tag/cmodels.html|表现良好的求解器| |gnt|www.tcs.hut.fi/Software/gnt/|表现良好的求解器| |assat| - |开创了使用循环公式将回答集计算简化为命题可满足性的思路| |psgrnd|www.cs.uky.edu/ai/aspps/|能处理一阶组件为子句形式（可能带权重原子）且逻辑程序组件为 Horn 程序的 ID - 逻辑理论的接地器| |aspps|www.cs.uky.edu/ai/aspps/|用于计算满足上述限制的接地 ID - 逻辑理论的回答集的求解器| |MXG|www.cs.sfu.ca/research/groups/mxp/mxg/|用于接地和计算 ID - 逻辑理论模型的集成软件包| |GidL/MidL 包|www.cs.kuleuven.be/∼dtai/krr/software/idp.html|用于 ID - 逻辑理论的接地（GidL）和模型生成（MidL）| 下面是处理回答集程序的流程 mermaid 图： ```mermaid graph LR A[输入带变量的程序] --> B[接地] B --> C[命题程序] C --> D[求解] D --> E[ ```