Rough Sets and 3-Valued Logics

In the paper we explore the idea of describing Pawlak’s rough sets using three-valued logic, whereby the value t corresponds to the positive region of a set, the value f — to the negative region, and the undefined value u — to the border of the set. Due to the properties of the above regions in rough set theory, the semantics of the logic is described using a non-deterministic matrix (Nmatrix). With the strong semantics, where only the value t is treated as designated, the above logic is a “common denominator” for Kleene and Łukasiewicz 3-valued logics, which represent its two different “determinizations”. In turn, the weak semantics—where both t and u are treated as designated—represents such a “common denominator” for two major 3-valued paraconsistent logics. We give sound and complete, cut-free sequent calculi for both versions of the logic generated by the rough set Nmatrix. Then we derive from these calculi sequent calculi with the same properties for the various “determinizations” of those two versions of the logic (including Łukasiewicz 3-valued logic). Finally, we show how to embed the four above-mentioned determinizations in extensions of the basic rough set logics obtained by adding to those logics a special two-valued “definedness” or “crispness” operator.     

Nelson's Negation on the Base of Weaker Versions of Intuitionistic Negation

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.     

SUPERVALUATION FIXED-POINT LOGICS OF TRUTH

Michael Kremer defines fixed-point logics of truth based on Saul Kripke’s fixed point semantics for languages expressing their own truth concepts. Kremer axiomatizes the strong Kleene fixed-point logic of truth and the weak Kleene fixed-point logic of truth, but leaves the axiomatizability question open for the supervaluation fixed-point logic of truth and its variants. We show that the principal supervaluation fixed point logic of truth, when thought of as consequence relation, is highly complex: it is not even analytic. We also consider variants, engendered by a stronger notion of ‘fixed point’, and by variant supervaluation schemes. A ‘logic’ is often thought of, not as a consequence relation, but as a set of sentences – the sentences true on each interpretation. We axiomatize the supervaluation fixed-point logics so conceived.     

Equivalential and algebraizable logics

The notion of an algebraizable logic in the sense of Blok and Pigozzi [3] is generalized to that of a possibly infinitely algebraizable, for short, p.i.-algebraizable logic by admitting infinite sets of equivalence formulas and defining equations. An example of the new class is given. Many ideas of this paper have been present in [3] and [4]. By a consequent matrix semantics approach the theory of algebraizable and p.i.-algebraizable logics is developed in a different way. It is related to the theory of equivalential logics in the sense of Prucnal and Wroski [18], and it is extended to nonfinitary logics. The main result states that a logic is algebraizable (p.i.-algebraizable) iff it is finitely equivalential (equivalential) and the truth predicate in the reduced matrix models is equationally definable.Most of the results of the present and a forthcoming paper originally appeared in [13].Presented by Wolfgang Rautenberg     

Maximal and Premaximal Paraconsistency in the Framework of Three-Valued Semantics

Maximality is a desirable property of paraconsistent logics, motivated by the aspiration to tolerate inconsistencies, but at the same time retain from classical logic as much as possible. In this paper we introduce the strongest possible notion of maximal paraconsistency, and investigate it in the context of logics that are based on deterministic or non-deterministic three-valued matrices. We show that all reasonable paraconsistent logics based on three-valued deterministic matrices are maximal in our strong sense. This applies to practically all three-valued paraconsistent logics that have been considered in the literature, including a large family of logics which were developed by da Costa’s school. Then we show that in contrast, paraconsistent logics based on three-valued properly nondeterministic matrices are not maximal, except for a few special cases (which are fully characterized). However, these non-deterministic matrices are useful for representing in a clear and concise way the vast variety of the (deterministic) three-valued maximally paraconsistent matrices. The corresponding weaker notion of maximality, called premaximal paraconsistency, captures the “core” of maximal paraconsistency of all possible paraconsistent determinizations of a non-deterministic matrix, thus representing what is really essential for their maximal paraconsistency.     

Combinator Logics

Combinator logics are a broad family of substructual logics that are formed by extending the basic relevant logic B with axioms that correspond closely to the reduction rules of proper combinators in combinatory logic. In the Routley-Meyer relational semantics for relevant logic each such combinator logic is characterized by the class of frames that meet a first-order condition that also directly corresponds to the same combinator's reduction rule. A second family of logics is also introduced that extends B with the addition of propositional constants that correspond to combinators. These are characterized by relational frames that meet first-order conditions that reflect the structures of the combinators themselves.     

Dual Equivalent Two-valued Under-determined and Over-determined Interpretations for Łukasiewicz’s 3-valued Logic Ł3

?ukasiewicz three-valued logic ?3 is often understood as the set of all 3-valued valid formulas according to ?ukasiewicz’s 3-valued matrices. Following Wojcicki, in addition, we shall consider two alternative interpretations of ?3: “well-determined” ?3a and “truth-preserving” ?3b defined by two different consequence relations on the 3-valued matrices. The aim of this paper is to provide (by using Dunn semantics) dual equivalent two-valued under-determined and over-determined interpretations for ?3, ?3a and ?3b. The logic ?3 is axiomatized as an extension of Routley and Meyer’s basic positive logic following Brady’s strategy for axiomatizing many-valued logics by employing two-valued under-determined or over-determined interpretations. Finally, it is proved that “well determined” ?ukasiewicz logics are paraconsistent.     

On Modal Logics of Partial Recursive Functions

The classical propositional logic is known to be sound and complete with respect to the set semantics that interprets connectives as set operations. The paper extends propositional language by a new binary modality that corresponds to partial recursive function type constructor under the above interpretation. The cases of deterministic and non-deterministic functions are considered and for both of them semantically complete modal logics are described and decidability of these logics is established. Presented by Melvin Fitting     

The Classification of Propositional Calculi

We discuss Smirnovs problem of finding a common background for classifying implicational logics. We formulate and solve the problem of extending, in an appropriate way, an implicational fragment H of the intuitionistic propositional logic to an implicational fragment TV of the classical propositional logic. As a result we obtain logical constructions having the form of Boolean lattices whose elements are implicational logics. In this way, whole classes of new logics can be obtained. We also consider the transition from implicational logics to full logics. On the base of the lattices constructed, we formulate the main classification principles for propositional logics.     

Coinductive models and normal forms for modal logics (or how we learned to stop worrying and love coinduction)

We present a coinductive definition of models for modal logics and show that it provides a homogeneous framework in which it is possible to include different modal languages ranging from classical modalities to operators from hybrid and memory logics. Moreover, results that had to be proved separately for each different language—but whose proofs were known to be mere routine—now can be proved in a general way. We show, for example, that we can have a unique definition of bisimulation for all these languages, and prove a single invariance-under-bisimulation theorem.We then use the new framework to investigate normal forms for modal logics. The normal form we introduce may have a smaller modal depth than the original formula, and it is inspired by global modalities like the universal modality and the satisfiability operator from hybrid logics. These modalities can be extracted from under the scope of other operators. We provide a general definition of extractable modalities and show how to compute extracted normal forms. As it is the case with other classical normal forms—e.g., the conjunctive normal form of propositional logic—the extracted normal form of a formula can be exponentially bigger than the original formula, if we require the two formulas to be equivalent. If we only require equi-satisfiability, then every modal formula has an extracted normal form which is only polynomially bigger than the original formula, and it can be computed in polynomial time.     

Leibniz Filters Revisited

Leibniz filters play a prominent role in the theory of protoalgebraic logics. In [3] the problem of the definability of Leibniz filters is considered. Here we study the definability of Leibniz filters with parameters. The main result of the paper says that a protoalgebraic logic S has its strong version weakly algebraizable iff it has its Leibniz filters explicitly definable with parameters.     

Glivenko Type Theorems for Intuitionistic Modal Logics

In this article we deal with Glivenko type theorems for intuitionistic modal logics over Prior's MIPC. We examine the problems which appear in proving Glivenko type theorems when passing from the intuitionistic propositional logic Intto MIPC. As a result we obtain two different versions of Glivenko's theorem for logics over MIPC. Since MIPCcan be thought of as a one-variable fragment of the intuitionistic predicate logic Q-Int, one of the versions of Glivenko's theorem for logics over MIPCis closely related to that for intermediate predicate logics obtained by Umezawa [27] and Gabbay [15]. Another one is rather surprising.     

Fuzzy Topology and Łukasiewicz Logics from the Viewpoint of Duality Theory

This paper explores relationships between many-valued logic and fuzzy topology from the viewpoint of duality theory. We first show a fuzzy topological duality for the algebras of ?ukasiewicz n-valued logic with truth constants, which generalizes Stone duality for Boolean algebras to the n-valued case via fuzzy topology. Then, based on this duality, we show a fuzzy topological duality for the algebras of modal ?ukasiewicz n-valued logic with truth constants, which generalizes Jónsson-Tarski duality for modal algebras to the n-valued case via fuzzy topology. We emphasize that fuzzy topological spaces naturally arise as spectrums of algebras of many-valued logics.     

On Intermediate Predicate Logics of some Finite Kripke Frames,I. Levelwise Uniform Trees

An intermediate predicate logic L is called finite iff it is characterized by a finite partially ordered set M, i.e., iff L is the logic of the class of all predicate Kripke frames based on M. In this paper we study axiomatizability of logics of this kind. Namely, we consider logics characterized by finite trees M of a certain type (levelwise uniform trees) and establish the finite axiomatizability criterion for this case.     

Combinatory Logic and the Semantics of Substructural Logics

The results of this paper extend some of the intimate relations that are known to obtain between combinatory logic and certain substructural logics to establish a general characterization theorem that applies to a very broad family of such logics. In particular, I demonstrate that, for every combinator X, if LX is the logic that results by adding the set of types assigned to X (in an appropriate type assignment system, TAS) as axioms to the basic positive relevant logic B∘T, then LX is sound and complete with respect to the class of frames in the Routley-Meyer relational semantics for relevant and substructural logics that meet a first-order condition that corresponds in a very direct way to the structure of the combinator X itself. Presented by Rob Goldblatt     

Characterizing Equivalential and Algebraizable Logics by the Leibniz Operator

In [14] we used the term finitely algebraizable for algebraizable logics in the sense of Blok and Pigozzi [2] and we introduced possibly infinitely algebraizable, for short, p.i.-algebraizable logics. In the present paper, we characterize the hierarchy of protoalgebraic, equivalential, finitely equivalential, p.i.-algebraizable, and finitely algebraizable logics by properties of the Leibniz operator. A Beth-style definability result yields that finitely equivalential and finitely algebraizable as well as equivalential and p.i.-algebraizable logics can be distinguished by injectivity of the Leibniz operator. Thus, from a characterization of equivalential logics we obtain a new short proof of the main result of [2] that a finitary logic is finitely algebraizable iff the Leibniz operator is injective and preserves unions of directed systems. It is generalized to nonfinitary logics. We characterize equivalential and, by adding injectivity, p.i.-algebraizable logics.     

Some Useful 16-Valued Logics: How a Computer Network Should Think

In Belnaps useful 4-valued logic, the set 2={T,F} of classical truth values is generalized to the set 4=(2)={,{T},{F},{T,F}}. In the present paper, we argue in favor of extending this process to the set 16=(4) (and beyond). It turns out that this generalization is well-motivated and leads from the bilattice FOUR₂ with an information and a truth-and-falsity ordering to another algebraic structure, namely the trilattice SIXTEEN₃ with an information ordering together with a truth ordering and a (distinct) falsity ordering. Interestingly, the logics generated separately by the algebraic operations under the truth order and under the falsity order in SIXTEEN₃ coincide with the logic of FOUR₂, namely first degree entailment. This observation may be taken as a further indication of the significance of first degree entailment. In the present setting, however, it becomes rather natural to consider also logical systems in the language obtained by combining the vocabulary of the logic of the truth order and the falsity order. We semantically define the logics of the two orderings in the extended language and in both cases axiomatize a certain fragment comprising three unary operations: a negation, an involution, and their combination. We also suggest two other definitions of logics in the full language, including a bi-consequence system. In other words, in addition to presenting first degree entailment as a useful 16-valued logic, we define further useful 16-valued logics for reasoning about truth and (non-)falsity. We expect these logics to be an interesting and useful instrument in information processing, especially when we deal with a net of hierarchically interconnected computers. We also briefly discuss Arielis and Avrons notion of a logical bilattice and state a number of open problems for future research.Dedicated to Nuel D. Belnap on the occasion of his 75th Birthday     

Ideal Paraconsistent Logics

We define in precise terms the basic properties that an ??ideal propositional paraconsistent logic?? is expected to have, and investigate the relations between them. This leads to a precise characterization of ideal propositional paraconsistent logics. We show that every three-valued paraconsistent logic which is contained in classical logic, and has a proper implication connective, is ideal. Then we show that for every n > 2 there exists an extensive family of ideal n-valued logics, each one of which is not equivalent to any k-valued logic with k < n.     

A Loop-Free Decision Procedure for Modal Propositional Logics K4, S4 and S5

The aim of this paper is to present a loop-free decision procedure for modal propositional logics K4, S4 and S5. We prove that the procedure terminates and that it is sound and complete. The procedure is based on the method of Socratic proofs for modal logics, which is grounded in the logic of questions IEL.     

Preservation of Craig interpolation by the product of matrix logics

The product of matrix logics, possibly with additional interaction axioms, is shown to preserve a slightly relaxed notion of Craig interpolation. The result is established symbolically, capitalizing on the complete axiomatization of the product of matrix logics provided by their meet-combination. Along the way preservation of the metatheorem of deduction is also proved. The computation of the interpolant in the resulting logic is proved to be polynomially reducible to the computation of the interpolants in the two given logics. Illustrations are provided for classical, intuitionistic and modal propositional logics.