Formulas for computing the number of Df2-algebra structures that can be defined over Bn, where Bn is the Boolean algebra with n atoms, as well as the fine spectrum of Df2 are obtained. Properties of the lattice of all subvarieties of Df2, (Df 2), are exhibited. In particular, the poset Sifin(Df2) is described.

It is known that classical logic CL is the single maximal consistent logic over intuitionistic logic Int, which is moreover the single one even over the substructural logic FLew. On the other hand, if we consider maximal consistent logics over a weaker logic, there may be uncountablymany of them. Since the subvariety lattice of a given variety V of residuated lattices is dually isomorphic to the lattice of logics over the corresponding substructural logic L(V), the number of maximal consistent logics is equal to the number of minimal subvarieties of the subvariety lattice of V. Tsinakis and Wille have shown that there exist uncountably many atoms in the subvariety lattice of the variety of involutive residuated lattices. In the present paper, we will show that while there exist uncountably many atoms in the subvariety lattice of the variety of bounded representable involutive residuated lattices with mingle axiom x2 ≤ x, only two atoms exist in the subvariety lattice of the variety of bounded representable involutive residuated lattices with the idempotency x = x2.

The notion of “sequences” is fundamental to practical reasoning in computer science, because it can appropriately represent “data (information) sequences”, “program (execution) sequences”, “action sequences”, “time sequences”, “trees”, “orders” etc. The aim of this paper is thus to provide a basic logic for reasoning with sequences. A propositional modal logic LS of sequences is introduced as a Gentzen-type sequent calculus by extending Gentzen’s LK for classical propositional logic. The completeness theorem with respect to a sequence-indexed semantics for LS is proved, and the cut-elimination theorem for LS is shown. Moreover, a first-order modal logic FLS of sequences, which is a first-order extension of LS, is introduced. The completeness theorem with respect to a first-order sequence-indexed semantics for FLS is proved, and the cut-elimination theorem for FLS is shown. LS and the monadic fragment of FLS are shown to be decidable.

Interpretability logic is a modal description of the interpretability predicate. The modal system IL is an extension of the provability logic GL (Gödel–Löb). Bisimulation quotients and largest bisimulations have been well studied for Kripke models. We examine interpretability logic and consider how these results extend to Veltman models.

In [4, Definition 8.1], some important subvarieties of the variety SH of semi-Heyting algebras are defined. The purpose of this paper is to introduce and investigate the subvariety ISSH of SH, characterized by the identity(0 - 1)* v (0 - 1)** = 11. We prove that ISSH contains all the subvarieties introduced by Sankappanavar and it is in fact the least subvariety of SH with this property. We also determine the sublattice generated by the subvarieties introduced in [4, Definition 8.1] within the lattice of subvarieties of semi-Heyting algebras.

This paper presents a complete classification of the complexity of the SAT and equivalence problems for two-element algebras. Cases of terms and polynomials are considered. We show that for any fixed two-element algebra the considered SAT problems are either in P or NP-complete and the equivalence problems are either in P or coNP-complete. We show that the complexity of the considered problems, parametrized by an algebra, are determined by the clone of term operations of the algebra and does not depend on generating functions for the clone.

This paper studies some properties of the so-called semilattice-based logics (which are defined in a standard way using only the order relation from a variety of algebras that have a semilattice reduct with maximum) under the assumption that its companion assertional logic (defined from the same variety of algebras using the top element as representing truth) is algebraizable. This describes a very common situation, and the conclusion of the paper is that these semilattice-based logics exhibit some of the good behaviour of protoalgebraic logics, without being necessarily so. The main result is that all these logics have enough Leibniz filters, a fact previously known in the literature to occur only for protoalgebraic logics. Another significant result is that the two companion logics coincide if and only if one of them enjoys the characteristic property of the other, that is, if and only if the semilattice-based logic is algebraizable, and if and only if its assertional companion is selfextensional. When these conditions are met, then the (unique) logic is finitely, regularly and strongly algebraizable and fully Fregean; this places it at some of the highest ranks in both the Leibniz hierarchy and the Frege hierarchy.

We describe properties of simply axiomatized modal logics, which are called pseudo-Euclidean modal logics. We will then give a complete description of the inclusion relationship among these logics by showing inclusion relationships for pairs of their logics with fixed m and n.