一阶逻辑中的扩展子句消去原则

宁欣然; 徐扬; 何星星

doi:10.3969/j.issn.0258-2724.20180974

一阶逻辑中的扩展子句消去原则

doi: 10.3969/j.issn.0258-2724.20180974

宁欣然^1,2,,
徐扬^1,3,
何星星^1,3

基金项目: 国家自然科学基金（1673320）；中央高校基本科研业务费专项资金（2682018ZT10）

详细信息

作者简介:
宁欣然（1990—），女，博士研究生，研究方向为自动推理、人工智能，E-mail：xinxinran@my.swjtu.edu.cn

中图分类号: V221.3
计量
- 文章访问数: 542
- HTML全文浏览量: 233
- PDF下载量: 12
- 被引次数: 0
出版历程
- 收稿日期: 2018-11-27
- 修回日期: 2019-06-18
- 网络出版日期: 2020-03-30
- 刊出日期: 2020-06-01

Extended Unifying Principle of Clause Elimination in First-Order Logic

NING Xinran^{1,2
,},
XU Yang^1,3,
HE Xingxing^1,3

摘要

摘要: 对于一阶逻辑定理证明器，子句集化简一直是必不可少的步骤，这将有助于提高后续一阶逻辑定理证明器的证明效率. 针对子句冗余性的判断，提出了一种评估子句冗余性的原则：集合蕴涵模归结原则. 并且证明了该原则在不带等词一阶逻辑上的可靠性，根据该原则删除子句，不会影响原始子句集的不可满足性或者可满足性. 此外，依据该原则提出了两种新型的一阶逻辑预处理方法：集合归结包含消去（set resolution subsumption, SRSE）方法和集合归结不对称恒真消去（set resolution asymmetric tautology elimination, SRATE）方法，并证明了这两种子句消去方法在不带等词一阶逻辑子句集上的可靠性. 最后在理论上比较了SRSE方法和归结包含消去（sesolution subsumption elimination, RSE）方法以及SRATE方法和归结不对称恒真（sesolution asymmetric tautology elimination, RATE）方法之间的有效性，结果表明SRSE方法和SRATE方法分别比RSE方法和RATE方法更为有效.
- 集合蕴涵模归结 /
- 一阶逻辑 /
- 蕴涵模归结 /
- 子句消去方法 /
- 预处理方法
Abstract: Simplifications are indispensable steps of first-order theorem proving, which can enhance the proving efficiency of first-order theorem provers. Set implication modulo resolution, a principle of identifying the redundancy property of clauses, is proposed. The soundness of this principle in first-order logic without equality is proved, which means that eliminating clauses according to the principle has not effect on the unsatisfiability or satisfiability of original formulas. In addition, two novel preprocessing methods in first-order theorem proving are developed given the principle of set implication modulo resolution, i.e., set resolution subsumption elimination (SRSE) and set resolution asymmetric tautology elimination (SRATE). The soundness of the two clause elimination methods is also demonstrated. Finally, the effectiveness is theoretically compared between SRSE and resolution subsumption elimination (RSE) and between SRATE and resolution asymmetric tautology elimination (RATE), which shows SRSE and SRATE are more effective than RSE and RATE, respectively.
- set implication modulo resolution /
- first-order logic /
- implication modulo resolution /
- clause elimination method /
- preprocessing technique

HTML全文

参考文献(21)

MENEGUZZI F, TELANG P, SINGH M. A first-order formalization of commitments and goals for planning[C]//Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence. Bellevue: AAAI Press, 2013: 697-703.

MORITOMO A, HAMAGUCHI K, KASHIWABARA T. Validity checking for quantifier-free first-order logic with equality using substitution of boolean formulas[C]//International Symposium on Automated Technology for Verification and Analysis 2004, Lecture Notes in Computer Science. Berlin: Springer, 2004: 108-119.

BECKERT B, HAHNLE R. Reasoning and verification:state of the art and current trends[J]. IEEE Intelligent Systems, 2014, 29(1): 20-29. doi: 10.1109/MIS.2014.3

GRUNINGER M, HULL R, MCILRAITHS A. Short overview of flows: a first-order logic ontology for web services[C]//Bulletin of the IEEE Computer Society Technical Committee on Data Engineering. [S.l.]: IEEE, 2008: 3-7.

WITHERELL P, KRISHNAMURTY S, GROSSE I, et al. Improved knowledge management through first-order logic in engineering design ontologies[J]. Creativity:Simulation,Stimulation,and Studies, 2010, 24(2): 245-257.

WANG Zhenghao, YAN Shengquan, WANG Huaming, et al. An overview of Microsoft deep QA system on stanford web questions benchmark[R]. Washington D. C.: Microsoft, 2014.

HODER K, VORONKOV A. Sine qua non for large theory reasoning[C]//Automated Deduction-CADE-23. [S.l.]: CADE, 2011: 299-314.

ALAMA J, HESKES, T, KUHLWEIN D, et al. Premise selection for mathematics by corpus analysis and kernel methods[J]. Journal of Automated Reasoning, 2014, 52: 191-213. doi: 10.1007/s10817-013-9286-5

KHASIDASHVILI Z, KOROVIN K. Predicate elimination for preprocessing in first-order theorem proving[C]//International Conference on Theory and Applications of Satisfiability Testing, Lecture Notes in Computer Science. [S.l.]: SAT, 2016: 361-372.

KIESL B, SUDA M, SEIDL M. et al. Blocked clauses in first-order logic[C/OL]//Proceedings of the 21st International Conference on Logic for Programming, Artificial Intelligence and Reasoning (LPAR-21). [2018-09-20]. https://arxiv.org/pdf/1702. 00847.pdf.

NING Xinran, XU Yang; WU Guanfeng, et al. Set-blocked clause and extended set-blocked clause in first-order logic[J]. Symmetry, 2018, 10: 533-1-533-15.

BLOCKEEL H. Identifying non-redundant literals in clauses with uniqueness propagation[C]//The 26th International Conference on Inductive Logic Programming. [S.l.]: Springer, 2017: 8-13.

PIOTROWSKI P, URBAN J. ATPboost: learning premise selection in binary setting with ATP feedback[EB/OL]. [2018-2-15]. https://arxiv.org/abs/1802.03375?context=stat.

KUHLWEIN D, BLANCHETTE J. C. A survey of axiom selection as a machine learning problem[R]. Infinity, Computability and Metamathematics: Festschrift celebrating the 60th birthdays of Peter Koepke and Philip Welch. London: [s.n.], 2014.

陈青山,徐扬,何星星. 利用逻辑演绎求解SAT问题的启发式完全算法[J]. 西南交通大学学报,2017,52(6): 1224-1232. doi: 10.3969/j.issn.0258-2724.2017.06.025

CHEN Qingshan, XU Yang, HE Xingxing. Heuristic complete algorithm for SAT problem by using logical deduction[J]. Journal of Southwest Jiaotong University, 2017, 52(6): 1224-1232. doi: 10.3969/j.issn.0258-2724.2017.06.025

KIESL B, SUDA M. A unifying principle for clause elimination in first-order logic[C]//International Conference on Automated Deduction, Lecture Notes in Computer Science. [S.l.]: Springer, 2017: 274-290.

HEULE M J H, JARVISALO M, BIERE A. Covered clause elimination[C]//Short Papers for the 17th International Conference on Logic for Programming, Artificial intelligence, and Reasoning (LPAR-17-short). Yogyakarta: [s.n.], 2010, 13: 41-46.

HEULE M J H, JARVISALO M, BIERE A. Clause elimination procedures for CNF formulas[C]//Proceedings of the 17th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR-17). [S.l.]: Springer, 2010: 357-371

JARVISALO M, HEULE M J H, BIERE A. Inprocessing rules[C]//International Joint Conference on Automated Reasoning. [S.l.]: Springer, 2012: 355-370

刘叙华. 基于归结方法的自动推理[M]. 北京: 科学出版社, 1994.

HEULE M J H, SEIDL M, BIERE A. Solution validation and extraction for QBF preprocessing[J]. Journal of Automated Reasoning, 2017, 58: 1-29. doi: 10.1007/s10817-016-9394-0

施引文献

附加材料(0)

访问统计

点击查看大图

计量

文章访问数: 542
HTML全文浏览量: 233
PDF下载量: 12
被引次数: 0

一阶逻辑中的扩展子句消去原则

doi: 10.3969/j.issn.0258-2724.20180974

作者简介: 宁欣然（1990—），女，博士研究生，研究方向为自动推理、人工智能，E-mail：xinxinran@my.swjtu.edu.cn

计量

出版历程

Extended Unifying Principle of Clause Elimination in First-Order Logic

计量

出版历程

目录

作者简介:
宁欣然（1990—），女，博士研究生，研究方向为自动推理、人工智能，E-mail：xinxinran@my.swjtu.edu.cn