Hostname: page-component-6bf8c574d5-gr6zb Total loading time: 0 Render date: 2025-02-23T21:11:43.324Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Computational Complexity of the Numerically Definite Syllogistic and Related Logics

Published online by Cambridge University Press:  15 January 2014

Ian Pratt-Hartmann
Ian Pratt-Hartmann*
Affiliation:
School of Computer Science, University of Manchester, Manchester M13 9PL, UKE-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

The numerically definite syllogistic is the fragment of English obtained by extending the language of the classical syllogism with numerical quantifiers. The numerically definite relational syllogistic is the fragment of English obtained by extending the numerically definite syllogistic with predicates involving transitive verbs. This paper investigates the computational complexity of the satisfiability problem for these fragments. We show that the satisfiability problem (= finite satisfiability problem) for the numerically definite syllogistic is strongly NP-complete, and that the satisfiability problem (= finite satisfiability problem) for the numerically definite relational syllogistic is NEXPTIME-complete, but perhaps not strongly so. We discuss the related problem of probabilistic (propositional) satisfiability, and thereby demonstrate the incompleteness of some proof-systems that have been proposed for the numerically definite syllogistic.

Type
Research Article
Information
Bulletin of Symbolic Logic , Volume 14 , Issue 1 , March 2008 , pp. 1 - 28
Copyright
Copyright © Association for Symbolic Logic 2008

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1] Boole, G., Of propositions numerically definite, Transactions of the Cambridge Philosophical Society, vol. XI (1868), no. II.Google Scholar
[2] Boole, G., Collected logical works: Studies in logic and probability, vol. 1, Open Court, La Salle, IL, 1952.Google Scholar
[3] Borosh, I. and Treybig, L., Bounds on the positive integral solutions of linear Diophantine equations, Proceedings of the American Mathematical Society, vol. 55 (1976), no. 2, pp. 299–304.Google Scholar
[4] de Morgan, A., Formal logic: or, the calculus of inference, necessary and probable, Taylor and Walton, London, 1847.Google Scholar
[5] Eisenbrand, F. and Shmonina, G., Carathéodory bounds for integer cones, Operations Research Letters, vol. 34 (2006), no. 5, pp. 564–568.Google Scholar
[6] Georgakopoulos, G., Kavvadias, D., and Papadimitriou, C., Probabilistic satisfiability, Journal of Complexity, vol. 4 (1988), no. 1, pp. 1–11.Google Scholar
[7] Grattan-Guinness, I., The search for mathematical roots, 1870-1940 : logics, set theories and the foundations of mathematics from Cantor through Russell to Gödel, Princeton University Press, Princeton, N.J., 2000.Google Scholar
[8] Hacker, E. and Parry, W., Pure numerical Boolean syllogisms, Notre Dame Journal of Formal Logic, vol. 8 (1967), no. 4, pp. 321–324.Google Scholar
[9] Jevons, W., On a general system of numerically definite reasoning, Memoirs of the Manchester Literary and Philosophical Society (3rd Series), vol. 4 (1871), pp. 330–352.Google Scholar
[10] Jevons, W., Pure logic and other minor works, Macmillan, London, 1890.Google Scholar
[11] Kazakov, Y., A polynomial translation from the two-variable guarded fragment with number restrictions to the guarded fragment, Proceedings, 9th European Conference on Logics in Artificial Intelligence (JELIA 2004) (Alferes, J. and Leite, J., editors), Lecture Notes in Artificial Intelligence, vol. 3229, Springer, Berlin, 2004, pp. 372–384.Google Scholar
[12] Kuncak, V. and Rinard, M., Towards efficient satisfiability checking for Boolean algebra with Presburger arithmetic, Proceedings, 21st International Conference on Automated Deduction (CADE-21) (Pfenning, F., editor), Lecture Notes in Computer Science, vol. 4603, Springer, Berlin, 2007, pp. 215–230.CrossRefGoogle Scholar
[13] Murphree, W., The numerical syllogism and existential presupposition, Notre Dame Journal of Formal Logic, vol. 38 (1997), no. 1, pp. 49–64.Google Scholar
[14] Murphree, W., Numerical term logic, Notre Dame Journal of Formal Logic, vol. 39 (1998), no. 3, pp. 346–362.CrossRefGoogle Scholar
[15] Pacholski, L., Szwast, W., and Tendera, L., Complexity results for first-order twovariable logic with counting, SIAM Journal on Computing, vol. 29 (1999), no. 4, pp. 1083–1117.Google Scholar
[16] Paris, J., The uncertain reasoner's companion, Cambridge University Press, Cambridge, 1994.Google Scholar
[17] Peterson, P., Complexly fractionated syllogistic quantifiers, Notre Dame Journal of Formal Logic, vol. 20 (1979), no. 1, pp. 155–179.Google Scholar
[18] Peterson, P., On the logic of “few”, “many” and “most”, Journal of Philosophical Logic, vol. 20 (1991), no. 3, pp. 287–313.Google Scholar
[19] Pratt-Hartmann, I., Complexity of the two-variable fragment with counting quantifiers, Journal of Logic, Language and Information, vol. 14 (2005), pp. 369–395.Google Scholar
[20] Pratt-Hartmann, I., Complexity of the guarded two-variable fragment with counting quantifiers, Journal of Logic and Computation, vol. 17 (2007), pp. 133–155.CrossRefGoogle Scholar
[21] Pratt-Hartmann, I. and Third, A., More fragments of language: the case of ditransitive verbs, Notre Dame Journal of Formal Logic, vol. 47 (2006), no. 2, pp. 151–177.Google Scholar
[22] Tobies, S., PSPACE reasoning for graded modal logics, Journal of Logic and Computation, vol. 11 (2001), no. 1, pp. 85–106.Google Scholar