Skip Navigation



Logic Journal of IGPL Advance Access published online on September 18, 2009
Logic Journal of IGPL, doi:10.1093/jigpal/jzp053
This Article
Right arrow Abstract Freely available
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Cowen, R.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© The Author 2009. Published by Oxford University Press. All rights reserved. For Permissions, please email: journals.permissions@oxfordjournals.org

Generalized Davis-Putnam and satisfiability problems in mathematics

Robert Cowen

Department of Mathematics, Queens College, CUNY.
E-mail: robert.cowen{at}gmail.com

The well-known Davis-Putnam Procedure used to decide the Sat Problem in Logic is shown to be combinatorial in nature and thus directly applicable to solving various Mathematical "Satisfiability" Problems.

Key Words: Davis-Putnam • satisfiability

Received for publication 9 July 2009.

References

    [1]  Cowen R. Some connections between set theory and computer science. Lecture Notes in Computer Science (1993) 713:14–22.[CrossRef]

    [2]  Cowen R, Property S. Reports on Math. Logic (2001) 35:61–74.

    [3]  Cowen R. Combinatorial analytic tableaux. Reports on Math. Logic (1993) 27:29–39.

    [4]  Cowen R, Kolany A. Davis-Putnam style rules for deciding Property S. Fund. Inform. 79(1–2):5–15.

    [5]  Davis M, Longemann G, Loveland D. A machine program for theorem proving. Communications of the ACM (1962) 5:394–397.[CrossRef][Web of Science]

    [6]  Davis M, Putnam H. A computing procedure for quantification theory. J. of the ACM (1960) 7:201–215.[CrossRef]

    [7]  Schrijver A. The dependence of some some logical axioms on disjoint transversals and linked systems. Colloq. Math. (1978) 39:191–199.

    [8]  Erdös P. On a combinatorial problem. Nordisk Mat. Tidskr. (1963) 11:5–10.

    [9]  Erdös PL. Some generalizations of Property B and the splitting property. Annals of Combinatorics (1999) 3:53–59.[CrossRef]

    [10]  Graham R, Rothschild BL, Spencer JH. Ramsey Theory (1990) 2nd. New York: Wiley Interscience.

    [11]  Kolany A. Satis ability on hypergraphs. Studia Logica (1993) 52:393–404.[CrossRef]

    [12]  Miller EW. On a property of families of sets. Comptes Rendus Varsovic (1937) 30:31–38.

    [13]  Stein SK. B-sets and planar maps. Paci c J. Math. (1971) 37:217–224.

    [14]  Steiner Triple System, Wofram MathWorld, http://mathworld.wolfram.com/SteinerTripleSystem.html.

    [15]  Woodall DR. Property B and the four-colour problem, in Combinatorics. Welsh DJ, Woodall DR, eds. (1972) IMA.


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?



This Article
Right arrow Abstract Freely available
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Cowen, R.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?