• ISSN 0258-2724
  • CN 51-1277/U
  • EI Compendex
  • Scopus 收录
  • 全国中文核心期刊
  • 中国科技论文统计源期刊
  • 中国科学引文数据库来源期刊

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

宁欣然 徐扬 何星星

宁欣然, 徐扬, 何星星. 一阶逻辑中的扩展子句消去原则[J]. 西南交通大学学报, 2020, 55(3): 588-595. doi: 10.3969/j.issn.0258-2724.20180974
引用本文: 宁欣然, 徐扬, 何星星. 一阶逻辑中的扩展子句消去原则[J]. 西南交通大学学报, 2020, 55(3): 588-595. doi: 10.3969/j.issn.0258-2724.20180974
NING Xinran, XU Yang, HE Xingxing. Extended Unifying Principle of Clause Elimination in First-Order Logic[J]. Journal of Southwest Jiaotong University, 2020, 55(3): 588-595. doi: 10.3969/j.issn.0258-2724.20180974
Citation: NING Xinran, XU Yang, HE Xingxing. Extended Unifying Principle of Clause Elimination in First-Order Logic[J]. Journal of Southwest Jiaotong University, 2020, 55(3): 588-595. doi: 10.3969/j.issn.0258-2724.20180974

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

doi: 10.3969/j.issn.0258-2724.20180974
基金项目: 国家自然科学基金(1673320);中央高校基本科研业务费专项资金(2682018ZT10)
详细信息
    作者简介:

    宁欣然(1990—),女,博士研究生,研究方向为自动推理、人工智能,E-mail:xinxinran@my.swjtu.edu.cn

  • 中图分类号: V221.3

Extended Unifying Principle of Clause Elimination in First-Order Logic

  • 摘要: 对于一阶逻辑定理证明器,子句集化简一直是必不可少的步骤,这将有助于提高后续一阶逻辑定理证明器的证明效率. 针对子句冗余性的判断,提出了一种评估子句冗余性的原则:集合蕴涵模归结原则. 并且证明了该原则在不带等词一阶逻辑上的可靠性,根据该原则删除子句,不会影响原始子句集的不可满足性或者可满足性. 此外,依据该原则提出了两种新型的一阶逻辑预处理方法:集合归结包含消去(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方法更为有效.

     

  • 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
  • 加载中
计量
  • 文章访问数:  530
  • HTML全文浏览量:  224
  • PDF下载量:  12
  • 被引次数: 0
出版历程
  • 收稿日期:  2018-11-27
  • 修回日期:  2019-06-18
  • 网络出版日期:  2020-03-30
  • 刊出日期:  2020-06-01

目录

    /

    返回文章
    返回