Arnon Avron

The notion of a bilattice was rst introduced by Ginsburg (see Gin]) as a general framework for a diversity of applications (such as truth maintenance systems, default inferences and others). The notion was further investigated and applied for various purposes by Fitting (see Fi1]- Fi6]). The main idea behind bilattices is to use structures in which there are two (partial) order relations, having di erent interpretations. The two relations should, of course, be connected somehow in order for the mathematical structure to be useful. It is not clear, however, what this connection should be. Ginsberg, for example, has made the connection through an extra operation of negation. Fitting, on the other hand, has investigated connections in the form of conditions on the structure (such as being interlaced { see below). These conditions are independent of the existence, or even the possibility to de ne, operations like Ginsberg's negation.* Fitting de nes, accordingly, notions like \an interlaced bilattice", \a distributive bilattice", \a bilattice with negation" and others. He does not provide, however, any de nition of the notion of bilattice itself (without an extra modi er). I was unable to nd anywhere, in fact, a de nition which will cover all the structures which were called \bilattice" in the literature

We introduce a general framework for solving the problem of a computer collecting and combining information from various sources. Unlike previous approaches to this problem, in our framework the sources are allowed to provide information about complex formulae too. This is enabled by the use of a new tool — non-deterministic logical matrices. We also consider several alternative plausible assumptions concerning the framework. These assumptions lead to various logics. We provide strongly sound and complete proof systems for all the basic logics induced in this way

A paraconsistent logic is a logic which allows non-trivial inconsistent theories. One of the oldest and best known approaches to the problem of designing useful paraconsistent logics is da Costa’s approach, which seeks to allow the use of classical logic whenever it is safe to do so, but behaves completely differently when contradictions are involved. da Costa’s approach has led to the family of Logics of Formal (In)consistency (LFIs). In this paper we provide non-deterministic semantics for a very large family of first-order LFIs (which includes da Costa’s original system..

Many efforts have been made in recent years to construct formal systems for mechanizing general mathematical reasoning. Most of these systems are based on logics which are stronger than first-order logic. However, there are good reasons to avoid using full second-order logic for this task. In this work we investigate a logic which is intermediate between FOL and SOL, and seems to be a particularly attractive alternative to both: ancestral logic. This is the logic which is obtained from FOL by augmenting it with the transitive closure operator. While the study of this logic has so far been mostly model-theoretical, this work is devoted to its proof theory. Two natural Gentzen-style proof systems for ancestral logic are presented: one for the reflexive transitive closure, and one for the non-reflexive one. We show that these systems are sound for ancestral logic and provide evidence that they indeed encompass all forms of reasoning for this logic that are used in practice. The two systems are shown to be equivalent by providing translation algorithms between them. We end with an investigation of two main proof-theoretical properties: cut elimination and constructive consistency proof.

The notion of bilattice was introduced by Ginsberg, and further examined by Fitting, as a general framework for many applications. In the present paper we develop proof systems, which correspond to bilattices in an essential way. For this goal we introduce the notion of logical bilattices. We also show how they can be used for efficient inferences from possibly inconsistent data. For this we incorporate certain ideas of Kifer and Lozinskii, which happen to suit well the context of our work. The outcome are paraconsistent logics with a lot of desirable properties.1

It is well known that every propositional logic which satisfies certain very natural conditions can be characterized semantically using a multi-valued matrix ([Los and Suszko, 1958; W´ ojcicki, 1988; Urquhart, 2001]). However, there are many important decidable logics whose characteristic matrices necessarily consist of an infinite number of truth values. In such a case it might be quite difficult to find any of these matrices, or to use one when it is found. Even in case a logic does have a finite characteristic matrix it might be difficult to discover this fact, or to find such a matrix. The deep reason for these difficulties is that in an ordinary multi-valued semantics the rules and axioms of a system should be considered as a whole, and there is no method for separately determining the semantic effects of each rule alone

Linear logic is a new logic which was recently developed by Girard in order to provide a logical basis for the study of parallelism. It is described and investigated in Gi]. Girard's presentation of his logic is not so standard. In this paper we shall provide more standard proof systems and semantics. We shall also extend part of Girard's results by investigating the consequence relations associated with Linear Logic and by proving corresponding str ong completeness theorems. Finally, we shall investigate the relation between Linear Logic and previously known systems, especially Relevance logics

An (n, k)-ary quantifier is a generalized logical connective, binding k variables and connecting n formulas. Canonical systems with (n, k)-ary quantifiers form a natural class of Gentzen-type systems which in addition to the standard axioms and structural rules have only logical rules in which exactly one occurrence of a quantifier is introduced. The semantics for these systems is provided using two-valued non-deterministic matrices, a generalization of the classical matrix. In this paper we use a constructive syntactic criterion of coherence to characterize strong cutelimination in such systems. We show that the following properties of a canonical system G with arbitrary (n, k)-ary quantifiers are equivalent: (i) G is coherent, (ii) G admits strong cut-elimination, and (iii) G has a strongly characteristic two-valued generalized non-deterministic matrix. In addition, we define simple calculi, an important subclass of canonical calculi, for which coherence is equivalent to the weaker, standard cut-elimination property.

One of the most signi cant drawbacks of classical logic is its being useless in the presence of an inconsistency. Nevertheless, the classical calculus is a very convenient framework to work with. In this work we propose means for drawing conclusions from systems that are based on classical logic, although the informationmightbe inconsistent. The idea is to detect those parts of the knowledge-base that \cause" the inconsistency, and isolate the parts that are \recoverable". We do this by temporarily switching into Ginsberg/Fitting multi-valued framework of bilattices (which is a common framework for logic programmingand nonmonotonic reasoning). Our method is conservative in the sense that it considers the contradictory data as useless and regards all the remaining information una ected. The resulting logic is nonmonotonic, paraconsistent, and a plausibility logic in the sense of Lehmann

We show that the elimination rule for the multiplicative conjunction $\wedge$ is admissible in many important multiplicative substructural logics. These include LL$_m$ and RMI$_m$ An exception is R$_m$. Let SLL$_m$ and SR$_m$ be, respectively, the systems which are obtained from LL$_m$ and R$_m$ by adding this rule as a new rule of inference. The set of theorems of SR$_m$ is a proper extension of that of R$_m$, but a proper subset of the set of theorems of RMI$_m$. Hence it still has the variable-sharing property. SR$_m$ has also the interesting property that classical logic has a strong translation into it. We next introduce general algebraic structures, called strong multiplicative structures, and prove strong soundness and completeness of SLL$_m$ relative to them. We show that in the framework of these structures, the addition of the weakening axiom to SLL$_m$ corresponds to the condition that there will be exactly one designated element, while the addition of the contraction axiom corresponds to the condition that there will be exactly one nondesignated element. Various other systems in which multiplicative conjunction functions as a true conjunction are studied, together with their algebraic counterparts.

Paradefinite logics are logics that can be used for handling contradictory or partial information. As such, paradefinite logics should be both paraconsistent and paracomplete. In this paper we consider the simplest semantic framework for introducing paradefinite logics. It consists of the four-valued matrices that expand the minimal matrix which is characteristic for first degree entailments: Dunn–Belnap matrix. We survey and study the expressive power and proof theory of the most important logics that can be developed in this framework.

We describe a method for obtaining classical logic from intuitionistic logic which does not depend on any proof system, and show that by applying it to the most important implicational relevance logics we get relevance logics with nice semantical and proof-theoretical properties. Semantically all these logics are sound and strongly complete relative to classes of structures in which all elements except one are designated. Proof-theoretically they correspond to cut-free hypersequential Gentzen-type calculi. Another major property of all these logic is that the classical implication can faithfully be translated into them

There is a long tradition (See e.g. [9, 10]) starting from [12], according to which the meaning of a connective is determined by the introduction and elimination rules which are associated with it. The supporters of this thesis usually have in mind natural deduction systems of a certain ideal type (explained in Section 3 below). Unfortunately, already the handling of classical negation requires rules which are not of that type. This problem can be solved in the framework of multiple-conclusion Gentzen-type systems (also first introduced in [12]), where instead of introduction and elimination rules there are left introduction rules and right introduction rules.

.  The paper presents a method for transforming a given sound and complete n-sequent proof system into an equivalent sound and complete system of ordinary sequents. The method is applicable to a large, central class of (generalized) finite-valued logics with the language satisfying a certain minimal expressiveness condition. The expressiveness condition decrees that the truth-value of any formula φ must be identifiable by determining whether certain formulas uniformly constructed from φ have designated values or not. The transformation preserves the general structure of proofs in the original calculus in a way ensuring preservation of the weak cut elimination theorem under the transformation. The described transformation metod is illustrated on several concrete examples of many-valued logics, including a new application to information sources logics.

We investigate two large families of logics, differing from each other by the treatment of negation. The logics in one of them are obtained from the positive fragment of classical logic (with or without a propositional constant ff for “the false”) by adding various standard Gentzen-type rules for negation. The logics in the other family are similarly obtained from LJ+, the positive fragment of intuitionistic logic (again, with or without ff). For all the systems, we provide simple semantics which is based on non-deterministic four-valued or three-valued structures, and prove soundness and completeness for all of them. We show that the role of each rule is to reduce the degree of non-determinism in the corresponding systems. We also show that all the systems considered are decidable, and our semantics can be used for the corresponding decision procedures. Most of the extensions of LJ+ (with or without ff) are shown to be conservative over the underlying logic, and it is determined which of them are not

We provide a general framework for constructing natural consequence relations for paraconsistent and plausible nonmonotonic reasoning. The framework is based on preferential systems whose preferences are based on the satisfaction of formulas in models. We show that these natural preferential In the research on paraconsistency, preferential systems systems that were originally designed for for paraconsistent reasoning fulfill a key condition (stopperedness or smoothness) from the theoretical research of nonmonotonic reasoning. Consequently, the nonmonotonic consequence relations that they induce fulfill the desired conditions of plausible consequence relations. Hence our framework encompasses different types of preferential systems that were developed from different motivations of paraconsistent reasoning and non-monotonic reasoning, and reveals an important link between them.

According to Suszko's Thesis,any multi-valued semantics for a logical system can be replaced by an equivalent bivalent one. Moreover: bivalent semantics for families of logics can frequently be developed in a modular way. On the other hand bivalent semantics usually lacks the crucial property of analycity, a property which is guaranteed for the semantics of multi-valued matrices. We show that one can get both modularity and analycity by using the semantic framework of multi-valued non-deterministic matrices. We further show that for using this framework in a constructive way it is best to view "truth-values" as information carriers, or "information-values"

Canonical Propositional Gentzen-type systems are systems which in addition to the standard axioms and structural rules have only pure logical rules with the sub-formula property, in which exactly one occurrence of a connective is introduced in the conclusion, and no other occurrence of any connective is mentioned anywhere else. In this paper we considerably generalize the notion of a “canonical system” to first-order languages and beyond. We extend the Propositional coherence criterion for the non-triviality of such systems to rules with unary quantifiers and show that it remains constructive. Then we provide semantics for such canonical systems using 2-valued non-deterministic matrices extended to languages with quantifiers, and prove that the following properties are equivalent for a canonical system G: (1) G admits Cut-Elimination, (2) G is coherent, and (3) G has a characteristic 2-valued non-deterministic matrix.

Hypersequents are finite sets of ordinary sequents. We show that multiple-conclusion sequents and single-conclusion hypersequents represent two different natural methods of switching from a single-conclusion calculus to a multiple-conclusion one. The use of multiple-conclusion sequents corresponds to using a multiplicative disjunction, while the use of single-conclusion hypersequents corresponds to using an additive one. Moreover: each of the two methods is usually based on a different natural semantic idea and accordingly leads to a different class of algebraic structures. In the cases we consider here the use of multiple-conclusion sequents corresponds to focusing the attention on structures in which there is a full symmetry between the sets of designated and antidesignated elements. The use of single-conclusion hypersequents, on the other hand, corresponds to the use of structures in which all elements except one are designated. Not surprisingly, the use of multiple-conclusion hypersequents corresponds to the use of structures which are both symmetrical and with a single nondesignated element