Arnon Avron

.  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

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.

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"

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

We provide a general investigation of Logic in which the notion of a simple consequence relation is taken to be fundamental. Our notion is more general than the usual one since we give up monotonicity and use multisets rather than sets. We use our notion for characterizing several known logics (including Linear Logic and non-monotonic logics) and for a general, semantics-independent classi cation of standard connectives via equations on consequence relations (these include Girard's \multiplicatives" and \additives"). We next investigate the standard methods for uniformly representing consequence relations: Hilbert type, Natural Deduction and Gentzen type. The advantages and disadvantages of using each system and what should be taken as..

We suggest a new framework for the Weyl-Feferman predicativist program by constructing a formal predicative set theory P ZF which resembles ZF , and is suitable for mechanization. The basic idea is that the predicatively acceptable instances of the comprehension schema are those which determine the collections they define in an absolute way, independent of the extension of the “surrounding universe”. The language of P ZF is type-free, and it reflects real mathematical practice in making an extensive use of statically defined abstract set terms. Another important feature of P ZF is that its underlying logic is ancestral logic (i.e. the extension of first-order logic with a transitive closure operation)

Around 1950, B.A. Trakhtenbrot proved an important undecidability result (known, by a pure accident, as \Trakhtenbrot's theorem"): there is no algorithm to decide, given a rst-order sentence, whether the sentence is satis able in some nite model. The result is in fact true even if we restrict ourselves to languages that has only one binary relation Tra63]. It is hardly conceivable that at that time Prof. Trakhtenbrot expected his result to in uence the development of the theory of relational databases query languages, but it did. This perhaps is not surprising in view of the following two facts: 1) The theory of relational databases is strongly rooted in logic and can easily be abstracted to make it a branch of mathematical logic. 2) The main interest in the theory of relational databases is in nite relations. In the rst section we explain those two points in more detail. Then, in section 2 of the present paper, we discuss the question: \What constitutes a reasonable query to a database?" The discussion naturally leads to a certain class of queries, known as the \domain independent" queries, as an ideal query language. At this point Trakhtenbrot's theorem appears as a major obstacle, since it easily implies that this ideal class is undecidable. Real query languages cannot be allowed to have this property. Section 3 outlines then several possible ways to circumvent this di culty. The following section explains the..

Non-deterministic matrices are multiple-valued structures in which the value assigned by a valuation to a complex formula can be chosen non-deterministically out of a certain nonempty set of options. We consider two different types of semantics which are based on Nmatrices: the dynamic one and the static one . We use the Rasiowa-Sikorski decomposition methodology to get sound and complete proof systems employing finite sets of mv-signed formulas for all propositional logics based on such structures with either of the above types of semantics. Later we demonstrate how these systems can be converted into cut-free ordinary Gentzen calculi which are also sound and complete for the corresponding non-deterministic semantics. As a by-product, we get new semantic characterizations for some well-known 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

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 logics is that the classical implication can faithfully be translated into them.

A quasi-canonical Gentzen-type system is a Gentzen-type system in which each logical rule introduces either a formula of the form , or of the form , and all the active formulas of its premises belong to the set . In this paper we investigate quasi-canonical systems in which exactly one of the two classical rules for negation is included, turning the induced logic into either a paraconsistent logic or a paracomplete logic, but not both. We provide a constructive coherence criterion for such systems, and show that a quasi-canonical system of the type we investigate is coherent iff it is strongly paraconsistent or strongly paracomplete (in a sense defined in the paper), iff it has a trivalent, non-deterministic semantics of a special type (also defined in the paper) for which it is sound and complete. Finally, we determine when a system of this sort admits cut-elimination, and provide a simple procedure for transforming one which does not into one which does.

We present a new unified framework for formalizations of axiomatic set theories of different strength, from rudimentary set theory to full ZF . It allows the use of set terms, but provides a static check of their validity. Like the inconsistent “ideal calculus” for set theory, it is essentially based on just two set-theoretical principles: extensionality and comprehension (to which we add ∈-induction and optionally the axiom of choice). Comprehension is formulated as: x ∈ {x | ϕ} ↔ ϕ, where {x | ϕ} is a legal set term of the theory. In order for {x | ϕ} to be legal, ϕ should be safe with respect to {x}, where safety is a relation between..

We show by way of example how one can provide in a lot of cases simple modular semantics for rules of inference, so that the semantics of a system is obtained by joining the semantics of its rules in the most straightforward way. Our main tool for this task is the use of finite Nmatrices, which are multi-valued structures in which the value assigned by a valuation to a complex formula can be chosen non-deterministically out of a certain nonempty set of options. The method is applied in the area of logics with a formal consistency operator (known as LFIs), allowing us to provide in a modular way effective, finite semantics for thousands of different LFIs