arXiv:2608.09190cs.AIcs.LO2026-08被引 1

让一阶推理过程保留结构并量化不确定性,支持不完全搜索结果的可信报告。

Structure-Preserving Uncertainty Propagation in First-Order Proof Search

  • 通过保留证明历史,动态重构不确定前提的概率
  • 在中间原子处合并正负支持,精确计算例外条件的置信度
  • 适用于需要可解释性与可靠性验证的逻辑推理系统

GK 是一种以查询为导向的一阶定理证明器,扩展了传统基于归结的证明搜索,引入显式的正负断言、数值置信度及带异常处理的优先默认规则。它直接处理非基元子句,包括等式和函数项。候选证明通过有界一阶搜索获得;默认规则的异常条件通过进一步有界的搜索验证,递归检查依赖于其他默认规则的异常。该方法避免了全局有限接地的需求,同时允许报告不完整的搜索。本文在此框架中加入结构保持的定量报告机制。利用保留的证明历史进行两项计算:第一,重建每个证明所用的不确定基元,并计算至少一个保留证明可用的概率,不重复计数共享前提;第二,在支持传播至后续规则前,对中间原子的正负支持进行合并;相同计算也用于评估单个规则应用的不确定异常条件。报告分别包含正支持、负支持、冲突、无知状态,并能识别检测到的不完整计算或回退。实现可在证明搜索后执行有界重构与依赖遍历,仍无需全局接地。分析示例与独立模拟器在指定片段上复现了参考计算。与概率逻辑、概率ASP、默认逻辑及目标导向ASP的对比揭示了一致情况、语义差异、不可翻译项及不完整计算。

原文摘要 · Abstract (English)

GK is a query-directed first-order prover that extends ordinary resolution-based proof search with explicit positive and negative claims, numerical confidence values, and prioritized default rules with exceptions. It works directly with non-ground clauses, including equality and function terms. Candidate proofs are found by bounded first-order proof search; exception conditions of defaults are checked by further bounded searches, recursively when exceptions themselves depend on defaults. This avoids requiring a finite global grounding, while allowing incomplete searches to be reported as such. This paper adds structure-preserving quantitative reporting to that framework. Retained proof histories are used in two calculations. The first reconstructs the uncertain ground premises used by each proof and computes the probability that at least one retained proof is available, without counting shared premises independently. The second resolves positive and negative support at intermediate atoms before that support is propagated through later rules; the same calculation evaluates uncertain exception conditions for individual rule applications. Reports separate positive support, negative support, conflict, and ignorance and identify detected incomplete calculations or fallbacks. The implementation performs bounded reconstruction and dependency traversal after proof search and still requires no global grounding. Analytic examples and independent simulators reproduce the reference calculations on their stated fragments. Comparisons with probabilistic logic, probabilistic ASP, default logic, and goal-directed ASP identify cases of agreement, semantic difference, unsupported translation, and incomplete computation.

逻辑推理不确定性证明搜索形式化验证

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。