This paper explores relational syllogistic logics, a family of logical systems related to reasoning about relations in extensions of the classical syllogistic. These are all decidable logical systems. We prove completeness theorems and complexity results for a natural subfamily of relational syllogistic logics, parametrized by constructors for terms and for sentences.
This paper is similar in spirit to @cite_9 , which also considered completeness and complexity results for decidable languages extending the basic syllogistic logic @math . In fact, the largest language of this paper, @math , is essentially equivalent to the largest language considered in @cite_9 , called @math there (see Propositions and below). But there are several differences between the other languages in @cite_9 and in this paper. First, @cite_9 allowed for complemented , contrary to what we do here. Second, @cite_9 also explored logical systems where the two terms in sentences like @math were not treated the same. For example, in two systems there, the subject noun phrase @math was required to be (negated) atomic. Third, we allow nested terms, which are not part of the syntax in @cite_9 . The upshot is that there is no overlap in the technical results from @cite_9 and this paper, except for the result on @math which we quote in .
@cite_9
2115133449
The Aristotelian syllogistic cannot account for the validity of certain inferences involving relational facts. In this paper, we investigate the prospects for providing a relational syllogistic. We identify several fragments based on (a) whether negation is permitted on all nouns, including those in the subject of a sentence; and (b) whether the subject noun phrase may contain a relative clause. The logics we present are extensions of the classical syllogistic, and we pay special attention to the question of whether reductio ad absurdum is needed. Thus our main goal is to derive results on the existence (or non-existence) of syllogistic proof systems for relational fragments. We also determine the computational complexity of all our fragments. S