Adding Guarded Constructions to the Syllogistic

The relational syllogistic extends the classical syllogistic by allowing predicate phrases of the forms “rs every q”, “rs some q” and their negations, where q is a common (count) noun and r a transitive verb. It is known that both the classical and relational syllogistic admit a finite set of syllogism-like rules whose associated derivation relation is sound and complete (the latter only when reductio ad absurdum is allowed). In this article, we extend the classical and relational syllogistic by allowing ‘guarded’ predicate phrases of the form “rs only qs”, and their negations. We show that, in both cases, the resulting logic is PSPACE-complete. It follows, on the assumption that NPTIME is not equal to PSPACE, that neither extension admits a finite set of syllogism-like rules whose associated derivation relation is sound and complete, even when reductio ad absurdum is allowed. We also show that further extending these systems with noun-complementation in sentence-subjects results in logics which are EXPTIME-complete.