On the Complexity of Nonassociative Lambek Calculus with Unit

Nonassociative Lambek Calculus (NL) is a syntactic calculus of types introduced by Lambek [8]. The polynomial time decidability of NL was established by de Groote and Lamarche [4]. Buszkowski [3] showed that systems of NL with finitely many assumptions are decidable in polynomial time and generate context-free languages; actually the P-TIME complexity is established for the consequence relation of NL. Adapting the method of Buszkowski [3] we prove an analogous result for Nonassociative Lambek Calculus with unit (NL1). Moreover, we show that any Lambek grammar based on NL1 (with assumptions) can be transformed into an equivalent context-free grammar in polynomial time.     

Filter distributive logics

The present paper is thought as a formal study of distributive closure systems which arise in the domain of sentential logics. Special stress is laid on the notion of a C-filter, playing the role analogous to that of a congruence in universal algebra. A sentential logic C is called filter distributive if the lattice of C-filters in every algebra similar to the language of C is distributive. Theorem IV.2 in Section IV gives a method of axiomatization of those filter distributive logics for which the class Matr (C) _prime of C-prime matrices (models) is axiomatizable. In Section V, the attention is focused on axiomatic strengthenings of filter distributive logics. The theorems placed there may be regarded, to some extent, as the matrix counterparts of Baker's well-known theorem from universal algebra [9, § 62, Theorem 2].The contents of this paper were presented in a talk at the 7th International Congress of Logic, Methodology and Philosophy of Science held at Salzburg, Austria, in July 1983. In abstracted form the paper was published in Abstracts of the 7th Congress, Vol. 2, pp. 39– 42. We take this opportunity to thank Professor Paul Weingartner and Doctor Georg Dorn from Salzburg for their (not fulfilled) wish to publish the present version in a special volume containing a selection of contributions to the 7th Congress.     

Basic properties of the equivalence

In this paper we investigate some basic semantic and syntactic conditions characterizing the equivalence connective. In particular we define three basic classes of algebras: the class of weak equivalential algebras, the class of equivalential algebras and the class of regular equivalential algebras (see [12]).Weak equivalential algebras can be used to study purely equivalential fragments of relevant logics and strict equivalential fragments of some modal logics (for investigations of strict implicational fragments of modal logics see [20]). Equivalential algebras are suitable to study purely equivalential fragment of BCI and BCK logic (see [21], p. 316). A subclass of the class of regular equivalential algebras is suitable to study equivalential fragments of ukasiewicz logics. Some subvarieties of the class of regular equivalential algebras provide natural semantics for equivalential fragments of the intuitionistic prepositional logic and various intermediate logics (see [13]).The last chapter is a selection of research problems which in the author's opinion are worth to be solved.     

Equivalential logics (II)

In the first section logics with an algebraic semantics are investigated. Section 2 is devoted to subdirect products of matrices. There, among others we give the matrix counterpart of a theorem of Jónsson from universal algebra. Some positive results concerning logics with, finite degrees of maximality are presented in Section 3.     

Equivalential logics (I)

The class of equivalential logics comprises all implicative logics in the sense of Rasiowa [9], Suszko's logicSCI and many Others. Roughly speaking, a logic is equivalential iff the greatest strict congruences in its matrices (models) are determined by polynomials. The present paper is the first part of the survey in which systematic investigations into this class of logics are undertaken. Using results given in [3] and general theorems from the theory of quasi-varieties of models [5] we give a characterization of all simpleC-matrices for any equivalential logicC (Theorem I.14). In corollaries we give necessary and sufficient conditions for the class of all simple models for a given equivalential logic to be closed under free products (Theorem I.18). Theorem I.17 can be generalized as follows:For any equivalential logic C, clauses (i), (iii)and (v),formulated in Th.I.17,are equivalent.     

A deduction theorem schema for deductive systems of propositional logics

We propose a new schema for the deduction theorem and prove that the deductive system S of a prepositional logic L fulfills the proposed schema if and only if there exists a finite set A(p, q) of propositional formulae involving only prepositional letters p and q such that A(p, p) L and p, A(p, q) _s q.     

S. A. Janovskaja

With the passing of S. A. Janovskaja, contemporary Soviet philosophy has lost one of its leading experts in logic and in combining creativity with survival.