Polymodal Lattices and Polymodal Logic

A polymodal lattice is a distributive lattice carrying an n-place operator preserving top elements and certain finite meets. After exploring some of the basic properties of such structures, we investigate their freely generated instances and apply the results to the corresponding logical systems — polymodal logics — which constitute natural generalizations of the usual systems of modal logic familiar from the literature. We conclude by formulating an extension of Kripke semantics to classical polymodal logic and proving soundness and completeness theorems. Mathematics Subject Classification: 03G10, 06D99, 03B45.     

Properties of Tense Logics

Based on the results of [11] this paper delivers uniform algorithms for deciding whether a finitely axiomatizable tense logic

• has the finite model property,
• is complete with respect to Kripke semantics,
• is strongly complete with respect to Kripke semantics,
• is d-persistent,
• is r-persistent.

It is also proved that a tense logic is strongly complete iff the corresponding variety of bimodal algebras is complex, and that a tense logic is d-persistent iff it is complete and its Kripke frames form a first order definable class. From this we obtain many natural non-d-persistent tense logics whose corresponding varieties of bimodal algebras are complex. Mathematics Subject Classification: 03B45, 03B25.     

Exhibiting Wide Families of Maximal Intermediate Propositional Logics with the Disjunction Property

We provide results allowing to state, by the simple inspection of suitable classes of posets (propositional Kripke frames), that the corresponding intermediate propositional logics are maximal among the ones which satisfy the disjunction property. Starting from these results, we directly exhibit, without using the axiom of choice, the Kripke frames semantics of 2^No maximal intermediate propositional logics with the disjunction property. This improves previous evaluations, giving rise to the same conclusion but made with an essential use of the axiom of choice, of the cardinality of the set of the maximal intermediate propositional logics with the disjunction property. Mathematics Subject Classification: 03B55, 03C90.     

A note on dual‐intuitionistic logic

Dual‐intuitionistic logics are logics proposed by Czermak (1977), Goodman (1981) and Urbas (1996). It is shown in this paper that there is a correspondence between Goodman's dual‐intuitionistic logic and Nelson's constructive logic N^?.     

Relating and extending semantical approaches to possibilistic reasoning

Two main semantical approaches to possibilistic reasoning with classical propositions have been proposed in the literature. Namely, Dubois-Prade's approach known as possibilistic logic, whose semantics is based on a preference ordering in the set of possible worlds, and Ruspini's approach that we redefine and call similarity logic, which relies on the notion of similarity or resemblance between worlds. In this article we put into relation both approaches, and it is shown that the monotonic fragment of possibilistic logic can be semantically embedded into similarity logic. Furthermore, to extend possibilistic reasoning to deal with fuzzy propositions, a semantical reasoning framework, called fuzzy truth-valued logic, is also introduced and proved to capture the semantics of both possibilistic and similarity logics.     

Propositional union closed team logics

In this paper, we study several propositional team logics that are closed under unions, including propositional inclusion logic. We show that all these logics are expressively complete, and we introduce sound and complete systems of natural deduction for these logics. We also discuss the locality property and its connection with interpolation in these logics.     

Prefinitely axiomatizable modal and intermediate logics

A logic Λ bounds a property P if all proper extensions of Λ have P while Λ itself does not. We construct logics bounding finite axiomatizability and logics bounding finite model property in the lattice of intermediate logics and in the lattice of normal extensions of K4.3. MSC: 03B45, 03B55.     

The Operators of Vector Logic

Vector logic is a mathematical model of the propositional calculus in which the logical variables are represented by vectors and the logical operations by matrices. In this framework, many tautologies of classical logic are intrinsic identities between operators and, consequently, they are valid beyond the bivalued domain. The operators can be expressed as Kronecker polynomials. These polynomials allow us to show that many important tautologies of classical logic are generated from basic operators via the operations called Type I and Type II products. Finally, it is described a matrix version of the Fredkin gate that extends its properties to the many-valued domain, and it is proved that the filtered Fredkin operators are second degree Kronecker polynomials that cannot be generated by Type I or Type II products. Mathematics Subject Classification: 03B05, 03B50.     

Modal Tree-Sequents

We develop cut-free calculi of sequents for normal modal logics by using treesequents, which are trees of sequences of formulas. We introduce modal operators corresponding to the ways we move formulas along the branches of such trees, only considering fixed distance movements. Finally, we exhibit syntactic cut-elimination theorems for all the main normal modal logics. Mathematics Subject Classification: 03B45, 03F05.     

Extending possibilistic logic over Gödel logic

In this paper we present several fuzzy logics trying to capture different notions of necessity (in the sense of possibility theory) for Gödel logic formulas. Based on different characterizations of necessity measures on fuzzy sets, a group of logics with Kripke style semantics is built over a restricted language, namely, a two-level language composed of non-modal and modal formulas, the latter, moreover, not allowing for nested applications of the modal operator N. Completeness and some computational complexity results are shown.     

Fuzzy logics based on [0,1)-continuous uninorms

Axiomatizations are presented for fuzzy logics characterized by uninorms continuous on the half-open real unit interval [0,1), generalizing the continuous t-norm based approach of Hájek. Basic uninorm logic BUL is defined and completeness is established with respect to algebras with lattice reduct [0,1] whose monoid operations are uninorms continuous on [0,1). Several extensions of BUL are also introduced. In particular, Cross ratio logic CRL, is shown to be complete with respect to one special uninorm. A Gentzen-style hypersequent calculus is provided for CRL and used to establish co-NP completeness results for these logics. Research supported by Marie Curie Fellowship Grant HPMF-CT-2004-501043.     

Computational complexity of hybrid interval temporal logics

Interval logics are very expressive temporal formalisms, but reasoning with them is often undecidable or has high computational complexity. As a result, a vast number of approaches limiting their expressive power—in order to obtain better computational behaviour—have been introduced. Unfortunately, due to such restrictions, interval logics often lose referentiality, that is, the capacity to refer to specific time intervals, which is crucial for temporal representation and reasoning. The computational price that needs to be paid in order to regain referentiality is not well studied and our research aims to fill this gap. In particular we study the main interval temporal logic, called the Halpern-Shoham logic, and its low complexity modifications. To regain referentiality in these modifications, we extend the language with the hybrid machinery—nominals and satisfaction operators—and classify the obtained logics according to their computational complexity. We show that such a hybridisation often makes tractable logics intractable but not undecidable. This allows us to construct hybrid interval temporal logics which are referential as well as maintain a good compromise between expressiveness and complexity; it makes them valuable formalisms for temporal knowledge representation. We also introduce a class of models which, due to a specific interplay between the interpretation of modal operators and a structure of time, makes reasoning in interval logics computationally hard even in the absence of the hybrid machinery.     

Cut-Elimination Theorem for the Logic of Constant Domains

The logic CD is an intermediate logic (stronger than intuitionistic logic and weaker than classical logic) which exactly corresponds to the Kripke models with constant domains. It is known that the logic CD has a Gentzen-type formulation called LD (which is same as LK except that (→) and (?–) rules are replaced by the corresponding intuitionistic rules) and that the cut-elimination theorem does not hold for LD . In this paper we present a modification of LD and prove the cut-elimination theorem for it. Moreover we prove a “weak” version of cut-elimination theorem for LD , saying that all “cuts” except some special forms can be eliminated from a proof in LD . From these cut-elimination theorems we obtain some corollaries on syntactical properties of CD : fragments collapsing into intuitionistic logic. Harrop disjunction and existence properties, and a fact on the number of logical symbols in the axiom of CD . Mathematics Subject Classification : 03B55. 03F05.     

On Finite Model Property for Admissible Rules

Our investigation is concerned with the finite model property (fmp) with respect to admissible rules. We establish general sufficient conditions for absence of fmp w. r. t. admissibility which are applicable to modal logics containing K4: Theorem 3.1 says that no logic λ containing K4 with the co-cover property and of width > 2 has fmp w. r. t. admissibility. Surprisingly many, if not to say all, important modal logics of width > 2 are within the scope of this theorem–K4 itself, S4, GL, K4.1, K4.2, S4.1, S4.2, GL.2, etc. Thus the situation is completely opposite to the case of the ordinary fmp–the absolute majority of important logics have fmp, but not with respect to admissibility. As regards logics of width ≤ 2, there exists a zone for fmp w. r. t. admissibility. It is shown (Theorem 4.3) that all modal logics A of width ≤ 2 extending S4 which are not sub-logics of three special tabular logics (which is equipotent to all these λ extend a certain subframe logic defined over S4 by omission of four special frames) have fmp w.r.t. admissibility.     

CUT ELIMINATION FOR PROPOSITIONAL DYNAMIC LOGIC WITHOUT

The aim of this paper is to extend the semantic analysis of tense logic in Rescher/Urquhart [3] to propositional dynamic logic without*. For this we develop a nested sequential calculus whose axioms and rules directly reflect the steps in the semantic analysis. It is shown that this calculus, with the cut rule omitted, is complete with respect to the standard semantics. It follows that cut elimination does hold for this nested sequential calculus. MSC: 03B45.     

Infinitary S5-Epistemic Logic

It is known that a theory in S5-epistemic logic with several agents may have numerous models. This is because each such model specifies also what an agent knows about infinite intersections of events, while the expressive power of the logic is limited to finite conjunctions of formulas. We show that this asymmetry between syntax and semantics persists also when infinite conjunctions (up to some given cardinality) are permitted in the language. We develop a strengthened S5-axiomatic system for such infinitary logics, and prove a strong completeness theorem for them. Then we show that in every such logic there is always a theory with more than one model.     

Algorithmic correspondence and canonicity for non-distributive logics

We extend the theory of unified correspondence to a broad class of logics with algebraic semantics given by varieties of normal lattice expansions (LEs), also known as ‘lattices with operators’. Specifically, we introduce a syntactic definition of the class of Sahlqvist formulas and inequalities which applies uniformly to each LE-signature and is given purely in terms of the order-theoretic properties of the algebraic interpretations of the logical connectives. We also introduce the algorithm ALBA, parametric in each LE-setting, which effectively computes first-order correspondents of LE-inequalities, and is guaranteed to succeed on a wide class of inequalities (the so-called inductive inequalities) which significantly extend the Sahlqvist class. Further, we show that every inequality on which ALBA succeeds is canonical. Projecting these results on specific signatures yields state-of-the-art correspondence and canonicity theory for many well known modal expansions of classical and intuitionistic logic and for substructural logics, from classical poly-modal logics to (bi-)intuitionistic modal logics to the Lambek calculus and its extensions, the Lambek-Grishin calculus, orthologic, the logic of (not necessarily distributive) De Morgan lattices, and the multiplicative-additive fragment of linear logic.     

Quantum logics with the Riesz Interpolation Property

We study the quantum logics which satisfy the Riesz Interpolation Property. We call them the RIP logics. We observe that the class of RIP logics is considerable large—it contains all lattice quantum logics and, also, many (infinite) non‐lattice ones. We then find out that each RIP logic can be enlarged to an RIP logic with a preassigned centre. We continue, showing that the “nearly” Boolean RIP logics must be Boolean algebras. In a somewhat surprising contrast to this, we finally show that the attempt for the σ‐complete formulation of this result fails: We show by constructing an example that there is a non‐Boolean nearly Boolean σ‐RIP logic. As a result, there are interesting σ‐RIP logics which are intrinsically close to Boolean σ‐algebras. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)