Constructive Logic with Strong Negation is a Substructural Logic. I

The goal of this two-part series of papers is to show that constructive logic with strong negation N is definitionally equivalent to a certain axiomatic extension NFL _ew of the substructural logic FL _ew . In this paper, it is shown that the equivalent variety semantics of N (namely, the variety of Nelson algebras) and the equivalent variety semantics of NFL _ew (namely, a certain variety of FL _ew -algebras) are term equivalent. This answers a longstanding question of Nelson [30]. Extensive use is made of the automated theorem-prover Prover9 in order to establish the result. The main result of this paper is exploited in Part II of this series [40] to show that the deductive systems N and NFL _ew are definitionally equivalent, and hence that constructive logic with strong negation is a substructural logic over FL _ew . Presented by Heinrich Wansing     

A First Order Nonmonotonic Extension of Constructive Logic

Certain extensions of Nelson's constructive logic N with strong negation have recently become important in arti.cial intelligence and nonmonotonic reasoning, since they yield a logical foundation for answer set programming (ASP). In this paper we look at some extensions of Nelson's .rst-order logic as a basis for de.ning nonmonotonic inference relations that underlie the answer set programming semantics. The extensions we consider are those based on 2-element, here-and-there Kripke frames. In particular, we prove completeness for .rst-order here-and-there logics, and their minimal strong negation extensions, for both constant and varying domains. We choose the constant domain version, which we denote by QN^c₅, as a basis for de.ning a .rst-order nonmonotonic extension called equilibrium logic. We establish several metatheoretic properties of QN^c₅, including Skolem forms and Herbrand theorems and Interpolation, and show that the .rst-oder version of equilibrium logic can be used as a foundation for answer set inference.     

AI,ME AND LEWIS (ABELIAN IMPLICATION,MATERIAL EQUIVALENCE AND C I LEWIS 1920)

C I Lewis showed up Down Under in 2005, in e-mails initiated by Allen Hazen of Melbourne. Their topic was the system Hazen called FL (a Funny Logic), axiomatized in passing in Lewis 1921. I show that FL is the system MEN of material equivalence with negation. But negation plays no special role in MEN. Symbolizing equivalence with → and defining ∼A inferentially as A→f, the theorems of MEN are just those of the underlying theory ME of pure material equivalence. This accords with the treatment of negation in the Abelian l-group logic A of Meyer and Slaney (Abelian logic. Abstract, Journal of Symbolic Logic 46, 425–426, 1981), which also defines ∼A inferentially with no special conditions on f. The paper then concentrates on the pure implicational part AI of A, the simple logic of Abelian groups. The integers Z were known to be characteristic for AI, with every non-theorem B refutable mod some Zn for finite n. Noted here is that AI is pre-tabular, having the Scroggs property that every proper extension SI of AI, closed under substitution and detachment, has some finite Zn as its characteristic matrix. In particular FL is the extension for which n = 2 (Lewis, The structure of logic and its relation to other systems. The Journal of Philosophy 18, 505–516, 1921; Meyer and Slaney, Abelian logic. Abstract. Journal of Symbolic Logic 46, 425–426, 1981; This is an abstract of the much longer paper finally published in 1989 in G. G. Priest, R. Routley and J. Norman, eds., Paraconsistent logic: essays on the inconsistent, Philosophica Verlag, Munich, pp. 245–288, 1989). Meyer was supported in this work as a Visiting Fellow in the College of Engineering and Computer Science, ANU.     

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     

The Basic Constructive Logic for a Weak Sense of Consistency defined with a Propositional Falsity Constant

The logic B_Kc1 is the basic constructive logic in the ternaryrelational semantics (without a set of designated points) adequateto consistency understood as the absence of the negation ofany theorem. Negation is introduced in B_Kc1 with a negationconnective. The aim of this paper is to define the logic B_Kc1F.In this logic negation is introduced via a propositional falsityconstant. We prove that B_Kc1 and B_Kc1F are definitionally equivalent.     

Negation in the Context of Gaggle Theory

We study an application of gaggle theory to unary negative modal operators. First we treat negation as impossibility and get a minimal logic system Ki that has a perp semantics. Dunn's kite of different negations can be dealt with in the extensions of this basic logic K_i. Next we treat negation as “unnecessity” and use a characteristic semantics for different negations in a kite which is dual to Dunn's original one. K_u is the minimal logic that has a characteristic semantics. We also show that Shramko's falsification logic FL can be incorporated into some extension of this basic logic K_u. Finally, we unite the two basic logics K_i and K_u together to get a negative modal logic K_-, which is dual to the positive modal logic K₊ in [7]. Shramko has suggested an extension of Dunn's kite and also a dual version in [12]. He also suggested combining them into a “united” kite. We give a united semantics for this united kite of negations.     

On a Contraction-Less Intuitionistic Propositional Logic with Conjunction and Fusion

In this paper we prove the equivalence between the Gentzen system G _LJ*\c , obtained by deleting the contraction rule from the sequent calculus LJ* (which is a redundant version of LJ), the deductive system IPC*\c and the equational system associated with the variety RL of residuated lattices. This means that the variety RL is the equivalent algebraic semantics for both systems G _LJ*\c in the sense of [18] and [4], respectively. The equivalence between G _LJ*\c and IPC*\c is a strengthening of a result obtained by H. Ono and Y. Komori [14, Corollary 2.8.1] and the equivalence between G _LJ*\c and the equational system associated with the variety RL of residuated lattices is a strengthening of a result obtained by P.M. Idziak [13, Theorem 1].An axiomatization of the restriction of IPC*\c to the formulas whose main connective is the implication connective is obtained by using an interpretation of G _LJ*\c in IPC*\c.     

Investigation into Combinatory Systems with Dual Combinators

Combinatory logic is known to be related to substructural logics. Algebraic considerations of the latter, in particular, algebraic considerations of two distinct implications (, ), led to the introduction of dual combinators in Dunn & Meyer 1997. Dual combinators are "mirror images" of the usual combinators and as such do not constitute an interesting subject of investigation by themselves. However, when combined with the usual combinators (e.g., in order to recover associativity in a sequent calculus), the whole system exhibits new features. A dual combinatory system with weak equality typically lacks the Church-Rosser property, and in general it is inconsistent. In many subsystems terms "unexpectedly" turn out to be weakly equivalent. The paper is a preliminary attempt to investigate some of these issues, as well as, briefly compare function application in symmetric -calculus (cf. Barbanera & Berardi 1996) and dual combinatory logic.     

Algebras of Intervals and a Logic of Conditional Assertions

Intervals in boolean algebras enter into the study of conditional assertions (or events) in two ways: directly, either from intuitive arguments or from Goodman, Nguyen and Walker's representation theorem, as suitable mathematical entities to bear conditional probabilities, or indirectly, via a representation theorem for the family of algebras associated with de Finetti's three-valued logic of conditional assertions/events. Further representation theorems forge a connection with rough sets. The representation theorems and an equivalent of the boolean prime ideal theorem yield an algebraic completeness theorem for the three-valued logic. This in turn leads to a Henkin-style completeness theorem. Adequacy with respect to a family of Kripke models for de Finetti's logic, ukasiewicz's three-valued logic and Priest's Logic of Paradox is demonstrated. The extension to first-order yields a short proof of adequacy for Körner's logic of inexact predicates.     

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.     

Priestley Duality for Paraconsistent Nelson’s Logic

The variety of N4^{^}{{\bf N4}^\perp}-lattices provides an algebraic semantics for the logic N4^{^}{{\bf N4}^\perp} , a version of Nelson’s logic combining paraconsistent strong negation and explosive intuitionistic negation. In this paper we construct the Priestley duality for the category of N4^{^}{{\bf N4}^\perp}-lattices and their homomorphisms. The obtained duality naturally extends the Priestley duality for Nelson algebras constructed by R. Cignoli and A. Sendlewski.     

Proof Systems Combining Classical and Paraconsistent Negations

New propositional and first-order paraconsistent logics (called L _ω and FL _ω , respectively) are introduced as Gentzen-type sequent calculi with classical and paraconsistent negations. The embedding theorems of L _ω and FL _ω into propositional (first-order, respectively) classical logic are shown, and the completeness theorems with respect to simple semantics for L _ω and FL _ω are proved. The cut-elimination theorems for L _ω and FL _ω are shown using both syntactical ways via the embedding theorems and semantical ways via the completeness theorems. Presented by Yaroslav Shramko and Heinrich Wansing     

Dual Intuitionistic Logic and a Variety of Negations: The Logic of Scientific Research

We consider a logic which is semantically dual (in some precise sense of the term) to intuitionistic. This logic can be labeled as “falsification logic”: it embodies the Popperian methodology of scientific discovery. Whereas intuitionistic logic deals with constructive truth and non-constructive falsity, and Nelson's logic takes both truth and falsity as constructive notions, in the falsification logic truth is essentially non-constructive as opposed to falsity that is conceived constructively. We also briefly clarify the relationships of our falsification logic to some other logical systems.     

Bounded contraction and Gentzen-style formulation of Łukasiewicz logics

In this paper, we consider multiplicative-additive fragments of affine propositional classical linear logic extended with n-contraction. To be specific, n-contraction (n 2) is a version of the contraction rule where (n+ 1) occurrences of a formula may be contracted to n occurrences. We show that expansions of the linear models for (n + 1)- valued ukasiewicz logic are models for the multiplicative-additive classical linear logic, its affine version and their extensions with n-contraction. We prove the finite axiomatizability for the classes of finite models, as well as for the class of infinite linear models based on the set of rational numbers in the interval [0, 1]. The axiomatizations obtained in a Gentzen-style formulation are equivalent to finite and infinite-valued ukasiewicz logics.Presented by Jan Zygmunt     

Gentzen-Type Methods for Bilattice Negation

A general Gentzen-style framework for handling both bilattice (or strong) negation and usual negation is introduced based on the characterization of negation by a modal-like operator. This framework is regarded as an extension, generalization or re- finement of not only bilattice logics and logics with strong negation, but also traditional logics including classical logic LK, classical modal logic S4 and classical linear logic CL. Cut-elimination theorems are proved for a variety of proposed sequent calculi including CLS (a conservative extension of CL) and CLS_cw (a conservative extension of some bilattice logics, LK and S4). Completeness theorems are given for these calculi with respect to phase semantics, for SLK (a conservative extension and fragment of LK and CLS_cw, respectively) with respect to a classical-like semantics, and for SS4 (a conservative extension and fragment of S4 and CLScw, respectively) with respect to a Kripke-type semantics. The proposed framework allows for an embedding of the proposed calculi into LK, S4 and CL.     

Embedding Logics into Product Logic

We construct a faithful interpretation of ukasiewicz's logic in product logic (both propositional and predicate). Using known facts it follows that the product predicate logic is not recursively axiomatizable.We prove a completeness theorem for product logic extended by a unary connective of Baaz [1]. We show that Gödel's logic is a sublogic of this extended product logic.We also prove NP-completeness of the set of propositional formulas satisfiable in product logic (resp. in Gödel's logic).     

An encompassing framework for Paraconsistent Logic Programs

We propose a framework which extends Antitonic Logic Programs [Damásio and Pereira, in: Proc. 6th Int. Conf. on Logic Programming and Nonmonotonic Reasoning, Springer, 2001, p. 748] to an arbitrary complete bilattice of truth-values, where belief and doubt are explicitly represented. Inspired by Ginsberg and Fitting's bilattice approaches, this framework allows a precise definition of important operators found in logic programming, such as explicit and default negation. In particular, it leads to a natural semantical integration of explicit and default negation through the Coherence Principle [Pereira and Alferes, in: European Conference on Artificial Intelligence, 1992, p. 102], according to which explicit negation entails default negation. We then define Coherent Answer Sets, and the Paraconsistent Well-founded Model semantics, generalizing many paraconsistent semantics for logic programs. In particular, Paraconsistent Well-Founded Semantics with eXplicit negation (WFSX_p) [Alferes et al., J. Automated Reas. 14 (1) (1995) 93–147; Damásio, PhD thesis, 1996]. The framework is an extension of Antitonic Logic Programs for most cases, and is general enough to capture Probabilistic Deductive Databases, Possibilistic Logic Programming, Hybrid Probabilistic Logic Programs, and Fuzzy Logic Programming. Thus, we have a powerful mathematical formalism for dealing simultaneously with default, paraconsistency, and uncertainty reasoning. Results are provided about how our semantical framework deals with inconsistent information and with its propagation by the rules of the program.     

Negative Equivalence of Extensions of Minimal Logic

Two logics L₁ and L₂ are negatively equivalent if for any set of formulas X and any negated formula ¬, ¬ can be deduced from the set of hypotheses X in L₁ if and only if it can be done in L₂. This article is devoted to the investigation of negative equivalence relation in the class of extensions of minimal logic.The author acknowledges support by the Alexander von Humboldt-StiftungPresented by Jacek Malinowski     

Choice and Logic

There is a little known paradox the solution to which is a guide to a much more thoroughgoing solution to a whole range of classic paradoxes. This is shown in this paper with respect to Berrys Paradox, Heterologicality, Russells Paradox, and the Paradox of Predication, also the Liar and the Strengthened Liar, using primarily the epsilon calculus. The solutions, however, show not only that the first-order predicate calculus derived from Frege is inadequate as a basis for a clear science, and should be replaced with Hilbert and Bernays conservative extension. Standard second-order logic, and quantified propositional logic also must be substantially modified, to incorporate, in the first place, nominalizations of predicates, and whole sentences. And further modifications must be made, so as to insist that predicates are parts of sentences rather than forms of them, and that truth is a property of propositions rather than their sentential expressions. In all, a thorough reworking of what has been called logic in recent years must be undertaken, to make it more fit for use.Portions of this paper have previously been published in Logical Studies, vol. 9, http://www.logic.ru/LogStud/09/No9-06.html, and the Australasian Journal of Logic, vol. 2, http://www.philosophy.unimelb.edu.au/ajl/2004/2004_4.pdf.     

On an Intuitionistic Modal Logic

In this paper we consider an intuitionistic variant of the modal logic S4 (which we call IS4). The novelty of this paper is that we place particular importance on the natural deduction formulation of IS4— our formulation has several important metatheoretic properties. In addition, we study models of IS4— not in the framework of Kirpke semantics, but in the more general framework of category theory. This allows not only a more abstract definition of a whole class of models but also a means of modelling proofs as well as provability.