Online research in philosophy

We extend the language of the classical syllogisms with the sentence-forms “At most 1 p is a q” and “More than 1 p is a q”. We show that the resulting logic does not admit a finite set of syllogism-like rules whose associated derivation relation is sound and complete, even when reductio ad absurdum is allowed.

This paper undertakes a re-examination of Sir William Hamilton’s doctrine of the quantification of the predicate . Hamilton’s doctrine comprises two theses. First, the predicates of traditional syllogistic sentence-forms contain implicit existential quantifiers, so that, for example, All p is q is to be understood as All p is some q . Second, these implicit quantifiers can be meaningfully dualized to yield novel sentence-forms, such as, for example, All p is all q . Hamilton attempted to provide a deductive system (...) for his language, along the lines of the classical syllogisms. We show, using techniques unavailable to Hamilton, that such a system does exist, though with qualifications that distinguish it from its classical counterpart. (shrink)

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. (shrink)

The satisfiability and finite satisfiability problems for the two-variable fragment of first-order logic with counting quantifiers are both in NEXPTIME, even when counting quantifiers are coded succinctly.

By a fragment of a natural language we mean a subset of thatlanguage equipped with semantics which translate its sentences intosome formal system such as first-order logic. The familiar conceptsof satisfiability and entailment can be defined for anysuch fragment in a natural way. The question therefore arises, for anygiven fragment of a natural language, as to the computational complexityof determining satisfiability and entailment within that fragment. Wepresent a series of fragments of English for which the satisfiabilityproblem is polynomial, NP-complete, EXPTIME-complete,NEXPTIME-complete (...) and undecidable. Thus, this paper represents a casestudy in how to approach the problem of determining the logicalcomplexity of various natural language constructions. In addition, wedraw some general conclusions about the relationship between naturallanguage and formal logic. (shrink)

Controlled languages are regimented fragments of natural languagedesigned to make the processing of natural language more efficient andreliable. This paper defines a controlled language, E2V, whose principalgrammatical resources include determiners, relative clauses, reflexivesand pronouns. We provide a formal syntax and semantics for E2V, in whichanaphoric ambiguities are resolved in a linguistically natural way. Weshow that the expressive power of E2V is equal to that of thetwo-variable fragment of first-order logic. It follows that the problemof determining the satisfiability of a set (...) of E2V sentences is NEXPTIMEcomplete. We show that E2V can be extended in various ways withoutcompromising these complexity results; however, relaxing our policy onanaphora resolution renders the satisfiability problem for E2Vundecidable. Finally, we argue that our results have a bearing on thebroader philosophical issue of the relationship between natural andformal languages. (shrink)

A region-based model of physical space is one in which the primitive spatial entities are regions, rather than points, and in which the primitive spatial relations take regions, rather than points, as their relata. Historically, the most intensively investigated region-based models are those whose primitive relations are topological in character; and the study of the topology of physical space from a region-based perspective has come to be called mereotopology. This paper concentrates on a mereotopological formalism originally introduced by Whitehead, (...) which employs a single primitive binary relation C(x,y) (read: x is in contact with y). Thus, in this formalism, all topological facts supervene on facts about contact. Because of its potential application to theories of qualitative spatial reasoning, Whitehead's primitive has recently been the subject of scrutiny from within the Artificial Intelligence community. Various results regarding the mereotopology of the Euclidean plane have been obtained, settling such issues as expressive power, axiomatization and the existence of alternative models. The contribution of the present paper is to extend some of these results to the mereotopology of three-dimensional Euclidean space. Specifically, we show that, in a first-order setting where variables range over tame subsets of R 3, Whitehead's primitive is maximally expressive for topological relations; and we deduce a corollary constraining the possible region-based models of the space we inhabit. (shrink)