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.