由一阶逻辑公式得到命题逻辑可满足性问题实例
作者:
基金项目:

Supported by the National Science Fund for Distinguished Young Scholars of China under Grant No.60125207 (国家杰出青年科学基金)


Generating SAT Instances from First-Order Formulas
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [12]
  • |
  • 相似文献 [20]
  • |
  • 引证文献
  • | |
  • 文章评论
    摘要:

    命题逻辑可满足性(SAT)问题是计算机科学中的一个重要问题.近年来许多学者在这方面进行了大量的研究,提出了不少有效的算法.但是,很多实际问题如果用一组一阶逻辑公式来描述,往往更为自然.当解释的论域是一个固定大小的有限集合时,一阶逻辑公式的可满足性问题可以等价地归约为SAT问题.为了利用现有的高效SAT工具,提出了一种从一阶逻辑公式生成SAT问题实例的算法,并描述了一个自动的转换工具,给出了相应的实验结果.还讨论了通过增加公式来消除同构从而减小搜索空间的一些方法.实验表明,这一算法是有效的,可以用来解决数学研究和实际应用中的许多问题.

    Abstract:

    To solve the satisfiability (SAT) problem in propositional logic, many algorithms have been proposed in recent years. However, practical problems are often more naturally described as satisfying a set of first-order formulas. When the domain of interpretation is finite and its size is a fixed positive integer, the satisfiability problem in the first-order logic can be reduced to SAT. To facilitate the use of SAT solvers, this paper presents an algorithm for generating SAT instances from first-order clauses, and describes an automatic tool performing the transformation, together with some experimental results. Several different ways of adding formulas are also discussed to eliminate symmetries, which will reduce the search space. Experiments show that the algorithm is effective and can be used to solve many problems in mathematics and real-world applications.

    参考文献
    [1]Zhang H, SATO: An efficient propositional prover. In: McCune W, ed. Proc. of the 14th Int'l Conf. on Automated Deduction (CADE-14). LNAI 1249, 1997. 272-275.
    [2]Selman B, Kautz H, Cohen B. Noise strategies for improving local search. In: Proc. of the 12th National Conf. on Artificial Intelligence (AAAI'94). 1994. 337-343.
    [3]Moskewicz M, et al. Chaff: Engineering an efficient SAT solver. In: Proc. of the 38th Design Automation Conf. Las Vegas, 2001. 530-535.
    [4]Shutter C, Sutcliffe G. The TPTP problem library (TPTP v2.2.0). Technical Report 99/02, James Cook University, Townsville, 1999.
    [5]McCune W, MACE 2.0 reference manual and guide. Technical Memo ANL/MCS-TM-249, Argonne National Laboratory, 2001.
    [6]Slaney J, FINDER: Finite domain enumerator, system description. In: Bundy A, ed. Proc. of the 12th Int'l Conf. on Automated Deduction (CADE-12). LNCS 814, 1994. 798-801.
    [7]Zhang J, Zhang H. SEM: A system for enumerating models. In: Mellish CS, ed. Proc. of the 14th Int'l Joint Conf. on Artificial Intelligence (IJCAI). 1995. 298-303.
    [8]Fujita M, Slaney J, Bennett F. Automatic generation of some results in finite algebra. In: Bajcsy R, ed. Proc. of the 13th Int'l Joint Conf. on Artificial Intelligence (IJCAI). 1993. 52-57.
    [9]Zhang J. Automatic symmetry breaking method combined with SAT. In: Proc. of the 16th ACM Symp. on Applied Computing. Las Vegas, 2001. 17-21.
    [10]Zhang J. Problems on the generation of finite models. In: Bundy A, ed. Proc. of the 12th Int'l Conf. on Automated Deduction (CADE-12). LNAI 814, 1994. 753-757.
    [11]McCune W. Automatic proofs and counterexamples for some ortholattice identities. Information Processing Letters, 1998,65(6): 285-291.
    [12]Kim S, Zhang H. ModGen: Theorem proving by model generation. In: Proc. of the 12th National Conf. on Artificial Intelligence (AAAI'94). 1994. 162-167.
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

黄拙,张健.由一阶逻辑公式得到命题逻辑可满足性问题实例.软件学报,2005,16(3):327-335

复制
分享
文章指标
  • 点击次数:5697
  • 下载次数: 6068
  • HTML阅读次数: 0
  • 引用次数: 0
历史
  • 收稿日期:2003-09-17
  • 最后修改日期:2004-01-08
文章二维码
您是第19867246位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号