We generalize and extend the class of Sahlqvist formulae in arbitrary polyadic modal languages, to the class of so called inductive formulae. To introduce them we use a representation of modal polyadic languages in a combinatorial style and thus, in particular, develop what we believe to be a better syntactic approach to elementary canonical formulae altogether. By generalizing the method of minimal valuations à la Sahlqvist–van Benthem and the topological approach of Sambin and Vaccaro we prove that all inductive formulae (...) are elementary canonical and thus extend Sahlqvist’s theorem over them. In particular, we give a simple example of an inductive formula which is not frame-equivalent to any Sahlqvist formula. Then, after a deeper analysis of the inductive formulae as set-theoretic operators in descriptive and Kripke frames, we establish a somewhat stronger model-theoretic characterization of these formulae in terms of a suitable equivalence to syntactically simpler formulae in the extension of the language with reversive modalities. Lastly, we study and characterize the elementary canonical formulae in reversive languages with nominals, where the relevant notion of persistence is with respect to discrete frames. (shrink)
Mereotopology is an extension of mereology with some relations of topological nature like contact. An algebraic counterpart of mereotopology is the notion of contact algebra which is a Boolean algebra whose elements are considered to denote spatial regions, extended with a binary relation of contact between regions. Although the language of contact algebra is quite expressive to define many useful mereological relations and mereotopological relations, there are, however, some interesting mereotopological relations which are not definable in it. Such are, for (...) instance, the relation of n-ary contact, internal connectedness and some others. To overcome this disadvantage, we introduce a generalisation of contact algebra, replacing the contact with a binary relation between finite sets of regions and a region, satisfying some formal properties of Tarski consequence relation. The obtained system is called sequent algebra, considered as an algebraic counterpart of a new mereotopology. We develop the topological representation theory for sequent algebras showing in this way certain correspondence between point-free and point-based models of space. As a by-product, we show how one logical relation in nature notion, Tarski consequence relation, may have also certain spatial meaning. (shrink)
Constructive logic with Nelson negation is an extension of the intuitionistic logic with a special type of negation expressing some features of constructive falsity and refutation by counterexample. In this paper we generalize this logic weakening maximally the underlying intuitionistic negation. The resulting system, called subminimal logic with Nelson negation, is studied by means of a kind of algebras called generalized N-lattices. We show that generalized N-lattices admit representation formalizing the intuitive idea of refutation by means of counterexamples giving in (...) this way a counterexample semantics of the logic in question and some of its natural extensions. Among the extensions which are near to the intuitionistic logic are the minimal logic with Nelson negation which is an extension of the Johansson's minimal logic with Nelson negation and its in a sense dual version — the co-minimal logic with Nelson negation. Among the extensions near to the classical logic are the well known 3-valued logic of Lukasiewicz, two 12-valued logics and one 48-valued logic. Standard questions for all these logics — decidability, Kripke-style semantics, complete axiomatizability, conservativeness are studied. At the end of the paper extensions based on a new connective of self-dual conjunction and an analog of the Lukasiewicz middle value ½ have also been considered. (shrink)
The paper is devoted to the contributions of Helena Rasiowa to the theory of non-classical negation. The main results of Rasiowa in this area concerns–constructive logic with strong (Nelson) negation.
We propose a generalization of Sahlqvist formulae to polyadic modal languages by representing modal polyadic languages in a combinatorial style and thus, in particular, developing what we believe to be the right approach to Sahlqvist formulae at all. The class of polyadic Sahlqvist formulae PSF defined here expands essentially the so far known one. We prove first-order definability and canonicity for the class PSF.
Four known three-valued logics are formulated axiomatically and several completeness theorems with respect to nonstandard intuitive semantics, connected with the notions of information, contrariety and subcontrariety is given.
This paper is a continuation of [VAK 01]. The notion of local connection algebra, based on the primitive notions of connection and boundedness, is introduced. It is slightly different but equivalent to Roeper's notion of region-based topology [ROE 97]. The similarity between the local proximity spaces of Leader [LEA 67] and local connection algebras is emphasized. Machinery, analogous to that introduced by Efremovi?c [EFR 51],[EFR 52], Smirnov [SMI 52] and Leader [LEA 67] for proximity and local proximity spaces, is developed. (...) This permits us to give new proximity-type models of local connection algebras, to obtain a representation theorem for such algebras and to give a new shorter proof of the main theorem of Roeper's paper [ROE 97]. Finally, the notion of MVD-algebra is introduced. It is similar to Mormann's notion of enriched Boolean algebra [MOR 98], based on a single mereological relation of interior parthood. It is shown that MVD-algebras are equivalent to local connection algebras. This means that the connection relation and boundedness can be incorporated into one, mereological in nature relation. In this way a formalization of the Whiteheadian theory of space based on a single mereological relation is obtained. (shrink)
We propose a generalization of Sahlqvist formulas to polyadic modal languages by representing such languages in a combinatorial PDL style and thus, in particular, developing what we believe to be the right syntactic approach to Sahlqvist formulas at all. The class of polyadic Sahlqvist formulas PSF defined here expands essentially the so far known one. We prove first-order definability and canonicity for the class PSF.
Hyperboolean algebras are Boolean algebras with operators, constructed as algebras of complexes (or, power structures) of Boolean algebras. They provide an algebraic semantics for a modal logic (called here a {\em hyperboolean modal logic}) with a Kripke semantics accordingly based on frames in which the worlds are elements of Boolean algebras and the relations correspond to the Boolean operations. We introduce the hyperboolean modal logic, give a complete axiomatization of it, and show that it lacks the finite model property. The (...) method of axiomatization hinges upon the fact that a "difference" operator is definable in hyperboolean algebras, and makes use of additional non-Hilbert-style rules. Finally, we discuss a number of open questions and directions for further research. (shrink)
In terms of validity in Kripke frames, a modal formula expresses a universal monadic second-order condition. Those modal formulae which are equivalent to first-order conditions are called elementary. Modal formulae which have a certain persistence property which implies their validity in all canonical frames of modal logics axiomatized with them, and therefore their completeness, are called canonical. This is a survey of a recent and ongoing study of the class of elementary and canonical modal formulae. We summarize main ideas and (...) results, and outline further research perspectives. (shrink)
The previously introduced algorithm \sqema\ computes first-order frame equivalents for modal formulae and also proves their canonicity. Here we extend \sqema\ with an additional rule based on a recursive version of Ackermann's lemma, which enables the algorithm to compute local frame equivalents of modal formulae in the extension of first-order logic with monadic least fixed-points \mffo. This computation operates by transforming input formulae into locally frame equivalent ones in the pure fragment of the hybrid mu-calculus. In particular, we prove that (...) the recursive extension of \sqema\ succeeds on the class of `recursive formulae'. We also show that a certain version of this algorithm guarantees the canonicity of the formulae on which it succeeds. (shrink)
We present a system of relational syllogistic, based on classical propositional logic, having primitives of the following form: $$\begin{array}{ll}\mathbf{Some}\, a \,{\rm are} \,R-{\rm related}\, {\rm to}\, \mathbf{some} \,b;\\ \mathbf{Some}\, a \,{\rm are}\,R-{\rm related}\, {\rm to}\, \mathbf{all}\, b;\\ \mathbf{All}\, a\, {\rm are}\,R-{\rm related}\, {\rm to}\, \mathbf{some}\, b;\\ \mathbf{All}\, a\, {\rm are}\,R-{\rm related}\, {\rm to}\, \mathbf{all} \,b.\end{array}$$ Such primitives formalize sentences from natural language like ‘ All students read some textbooks’. Here a, b denote arbitrary sets (of objects), and R denotes an (...) arbitrary binary relation between objects. The language of the logic contains only variables denoting sets, determining the class of set terms, and variables denoting binary relations between objects, determining the class of relational terms. Both classes of terms are closed under the standard Boolean operations. The set of relational terms is also closed under taking the converse of a relation. The results of the paper are the completeness theorem with respect to the intended semantics and the computational complexity of the satisfiability problem. (shrink)
In this paper, intuitionistic modal logics which do not admit the law of the excluded middle are studied. The main result is that there exista a continuum of such logics.
The aim of this paper is to give new kinds of modal logics suitable for reasoning about regions in discrete spaces. We call them dynamic logics of the region-based theory of discrete spaces. These modal logics are linguistic restrictions of propositional dynamic logic with the global diamond E. Their formulas are equivalent to Boolean combinations of modal formulas like E where A and B are Boolean terms and α is a relational term. Examining what we can say about dynamic models (...) when we use formulas to describe them, we successively address the axiomatization/completeness issue and the decidability/complexity issue of our dynamic logics of the region-based theory of discrete spaces. (shrink)
In this paper we show how modal logic can be applied in the axiomatizations of some dynamic ontologies. As an example we consider the case of mereotopology, which is an extension of mereology with some relations of topological nature like contact relation. We show that in the modal extension of mereotopology we may define some new mereological and mereotopological relations with dynamic nature like stable part-of and stable contact. In some sense such “stable” relations can be considered as approximations of (...) the “essential relations” in the domain of mereotopology. (shrink)
In terms of validity in Kripke frames, a modal formula expresses a universal monadic second-order condition. Those modal formulae which are equivalent to first-order conditions are called \emph{elementary}. Modal formulae which have a certain persistence property which implies their validity in all canonical frames of modal logics axiomatized with them, and therefore their completeness, are called \emph{canonical}. This is a survey of a recent and ongoing study of the class of elementary and canonical modal formulae. We summarize main ideas and (...) results, and outline further research perspectives. (shrink)
This paper is devoted to the complete axiomatization of dynamic extensions of arrow logic based on a restriction of propositional dynamic logic with intersection. Our deductive systems contain an unorthodox inference rule: the inference rule of intersection. The proof of the completeness of our deductive systems uses the technique of the canonical model.
ABSTRACT The notion of n-dimensional arrow structure is introduced, which for n = 2 coincides with the notion of directed multi-graph. In part I of the paper several first-order and modal languages connected with arrow structures are studied and their expressive power is compared. Part II is devoted to the axiomatization of some arrow logics. At the end some further perspectives of ?arrow approach? are discussed.
A duality between Pawlak's knowledge representation systems and certain information systems of logical type, called bi-consequence systems is established. As an application a first-order characterization of some informational relations is given and a completeness theorem for the corresponding modal logic INF is proved. It is shown that INF possesses finite model property and hence is decidable.
We study the general problem of axiomatizing structures in the framework of modal logic and present a uniform method for complete axiomatization of the modal logics determined by a large family of classes of structures of any signature.
We study the general problem of axiomatizing structures in the framework of modal logic and present a uniform method for complete axiomatization of the modal logics determined by a large family of classes of structures of any signature.
The main results of the paper are the following: For each monadic prepositional formula which is classically true but not intuitionistically so, there is a continuum of intuitionistic monotone modal logics L such that L+ is inconsistent.There exists a consistent intuitionistic monotone modal logic L such that for any formula of the kind mentioned above the logic L+ is inconsistent.
A new modal logic containing four dynamic modalities with the following informal reading is introduced: $${\square^\forall}$$ – always necessary , $${\square^\exists}$$ – sometimes necessary , and their duals – $${\diamondsuit^\forall}$$ – always possibly , and $${\diamondsuit^\exists}$$ – sometimes possibly . We present a complete axiomatization with respect to the intended formal semantics and prove decidability via fmp.