39 found
Order:
  1.  23
    Unsound Inferences Make Proofs Shorter.Juan P. Aguilera & Matthias Baaz - 2019 - Journal of Symbolic Logic 84 (1):102-122.
    We give examples of calculi that extend Gentzen’s sequent calculusLKby unsound quantifier inferences in such a way that derivations lead only to true sequents, and proofs therein are nonelementarily shorter thanLK-proofs.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  2.  62
    First-Order Gödel Logics.Richard Zach, Matthias Baaz & Norbert Preining - 2007 - Annals of Pure and Applied Logic 147 (1):23-47.
    First-order Gödel logics are a family of finite- or infinite-valued logics where the sets of truth values V are closed subsets of [0,1] containing both 0 and 1. Different such sets V in general determine different Gödel logics GV (sets of those formulas which evaluate to 1 in every interpretation into V). It is shown that GV is axiomatizable iff V is finite, V is uncountable with 0 isolated in V, or every neighborhood of 0 in V is uncountable. Complete (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   16 citations  
  3. Systematic Construction of Natural Deduction Systems for Many-Valued Logics.Matthias Baaz, Christian G. Fermüller & Richard Zach - 1993 - In Proceedings of The Twenty-Third International Symposium on Multiple-Valued Logic, 1993. Los Alamitos, CA: IEEE Press. pp. 208-213.
    A construction principle for natural deduction systems for arbitrary, finitely-many-valued first order logics is exhibited. These systems are systematically obtained from sequent calculi, which in turn can be automatically extracted from the truth tables of the logics under consideration. Soundness and cut-free completeness of these sequent calculi translate into soundness, completeness, and normal-form theorems for natural deduction systems.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   12 citations  
  4. Labeled Calculi and Finite-Valued Logics.Matthias Baaz, Christian G. Fermüller, Gernot Salzer & Richard Zach - 1998 - Studia Logica 61 (1):7-33.
    A general class of labeled sequent calculi is investigated, and necessary and sufficient conditions are given for when such a calculus is sound and complete for a finite -valued logic if the labels are interpreted as sets of truth values. Furthermore, it is shown that any finite -valued logic can be given an axiomatization by such a labeled calculus using arbitrary "systems of signs," i.e., of sets of truth values, as labels. The number of labels needed is logarithmic in the (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   16 citations  
  5.  77
    Elimination of Cuts in First-Order Finite-Valued Logics.Matthias Baaz, Christian G. Fermüller & Richard Zach - 1993 - Journal of Information Processing and Cybernetics EIK 29 (6):333-355.
    A uniform construction for sequent calculi for finite-valued first-order logics with distribution quantifiers is exhibited. Completeness, cut-elimination and midsequent theorems are established. As an application, an analog of Herbrand’s theorem for the four-valued knowledge-representation logic of Belnap and Ginsberg is presented. It is indicated how this theorem can be used for reasoning about knowledge bases with incomplete and inconsistent information.
    Direct download  
     
    Export citation  
     
    Bookmark   11 citations  
  6.  21
    Interpolation in Fuzzy Logic.Matthias Baaz & Helmut Veith - 1999 - Archive for Mathematical Logic 38 (7):461-489.
    We investigate interpolation properties of many-valued propositional logics related to continuous t-norms. In case of failure of interpolation, we characterize the minimal interpolating extensions of the languages. For finite-valued logics, we count the number of interpolating extensions by Fibonacci sequences.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   12 citations  
  7.  61
    Gentzen Calculi for the Existence Predicate.Matthias Baaz & Rosalie Iemhoff - 2006 - Studia Logica 82 (1):7-23.
    We introduce Gentzen calculi for intuitionistic logic extended with an existence predicate. Such a logic was first introduced by Dana Scott, who provided a proof system for it in Hilbert style. We prove that the Gentzen calculus has cut elimination in so far that all cuts can be restricted to very simple ones. Applications of this logic to Skolemization, truth value logics and linear frames are also discussed.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  8. Compact Propositional Gödel Logics.Matthias Baaz & Richard Zach - 1998 - In 28th IEEE International Symposium on Multiple-Valued Logic, 1998. Proceedings. Los Alamitos: IEEE Press. pp. 108-113.
    Entailment in propositional Gödel logics can be defined in a natural way. While all infinite sets of truth values yield the same sets of tautologies, the entailment relations differ. It is shown that there is a rich structure of infinite-valued Gödel logics, only one of which is compact. It is also shown that the compact infinite-valued Gödel logic is the only one which interpolates, and the only one with an r.e. entailment relation.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  9.  92
    Dual Systems of Sequents and Tableaux for Many-Valued Logics.Matthias Baaz, Christian G. Fermüller & Richard Zach - 1993 - Bulletin of the EATCS 51:192-197.
    The aim of this paper is to emphasize the fact that for all finitely-many-valued logics there is a completely systematic relation between sequent calculi and tableau systems. More importantly, we show that for both of these systems there are al- ways two dual proof sytems (not just only two ways to interpret the calculi). This phenomenon may easily escape one’s attention since in the classical (two-valued) case the two systems coincide. (In two-valued logic the assignment of a truth value and (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  10.  15
    Cut Normal Forms and Proof Complexity.Matthias Baaz & Alexander Leitsch - 1999 - Annals of Pure and Applied Logic 97 (1-3):127-177.
    Statman and Orevkov independently proved that cut-elimination is of nonelementary complexity. Although their worst-case sequences are mathematically different the syntax of the corresponding cut formulas is of striking similarity. This leads to the main question of this paper: to what extent is it possible to restrict the syntax of formulas and — at the same time—keep their power as cut formulas in a proof? We give a detailed analysis of this problem for negation normal form , prenex normal form and (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   7 citations  
  11. Hypersequents and the Proof Theory of Intuitionistic Fuzzy Logic.Matthias Baaz & Richard Zach - 2000 - In Peter G. Clote & Helmut Schwichtenberg (eds.), Computer Science Logic. 14th International Workshop, CSL 2000. Berlin: Springer. pp. 187– 201.
    Takeuti and Titani have introduced and investigated a logic they called intuitionistic fuzzy logic. This logic is characterized as the first-order Gödel logic based on the truth value set [0,1]. The logic is known to be axiomatizable, but no deduction system amenable to proof-theoretic, and hence, computational treatment, has been known. Such a system is presented here, based on previous work on hypersequent calculi for propositional Gödel logics by Avron. It is shown that the system is sound and complete, and (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  12. Quantified Propositional Gödel Logics.Matthias Baaz, Agata Ciabattoni & Richard Zach - 2000 - In Andrei Voronkov & Michel Parigot (eds.), Logic for Programming and Automated Reasoning. 7th International Conference, LPAR 2000. Berlin: Springer. pp. 240-256.
    It is shown that Gqp↑, the quantified propositional Gödel logic based on the truth-value set V↑ = {1 - 1/n : n≥1}∪{1}, is decidable. This result is obtained by reduction to Büchi's theory S1S. An alternative proof based on elimination of quantifiers is also given, which yields both an axiomatization and a characterization of Gqp↑ as the intersection of all finite-valued quantified propositional Gödel logics.
    Direct download  
     
    Export citation  
     
    Bookmark   3 citations  
  13.  56
    On the Complexity of Proof Deskolemization.Matthias Baaz, Stefan Hetzl & Daniel Weller - 2012 - Journal of Symbolic Logic 77 (2):669-686.
    We consider the following problem: Given a proof of the Skolemization of a formula F, what is the length of the shortest proof of F? For the restriction of this question to cut-free proofs we prove corresponding exponential upper and lower bounds.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  14.  9
    Complexity of T-Tautologies.Matthias Baaz, Petr Hájek, Franco Montagna & Helmut Veith - 2001 - Annals of Pure and Applied Logic 113 (1-3):3-11.
    A t-tautology is a propositional formula which is a tautology in all fuzzy logics defined by continuous triangular norms. In this paper we show that the problem of recognizing t-tautologies is coNP complete, and thus decidable.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  15.  9
    On the Non-Confluence of Cut-Elimination.Matthias Baaz & Stefan Hetzl - 2011 - Journal of Symbolic Logic 76 (1):313 - 340.
    We study cut-elimination in first-order classical logic. We construct a sequence of polynomial-length proofs having a non-elementary number of different cut-free normal forms. These normal forms are different in a strong sense: they not only represent different Herbrand-disjunctions but also differ in their propositional structure. This result illustrates that the constructive content of a proof in classical logic is not uniquely determined but rather depends on the chosen method for extracting it.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  16.  23
    On Skolemization in Constructive Theories.Matthias Baaz & Rosalie Iemhoff - 2008 - Journal of Symbolic Logic 73 (3):969-998.
    In this paper a method for the replacement, in formulas, of strong quantifiers by functions is introduced that can be considered as an alternative to Skolemization in the setting of constructive theories. A constructive extension of intuitionistic predicate logic that captures the notions of preorder and existence is introduced and the method, orderization, is shown to be sound and complete with respect to this logic. This implies an analogue of Herbrand's theorem for intuitionistic logic. The orderization method is applied to (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  17. Completeness of a First-Order Temporal Logic with Time-Gaps.Matthias Baaz, Alexander Leitsch & Richard Zach - 1996 - Theoretical Computer Science 160 (1-2):241-270.
    The first-order temporal logics with □ and ○ of time structures isomorphic to ω (discrete linear time) and trees of ω-segments (linear time with branching gaps) and some of its fragments are compared: the first is not recursively axiomatizable. For the second, a cut-free complete sequent calculus is given, and from this, a resolution system is derived by the method of Maslov.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  18.  21
    The Skolemization of Existential Quantifiers in Intuitionistic Logic.Matthias Baaz & Rosalie Iemhoff - 2006 - Annals of Pure and Applied Logic 142 (1):269-295.
    In this paper an alternative Skolemization method is introduced that, for a large class of formulas, is sound and complete with respect to intuitionistic logic. This class extends the class of formulas for which standard Skolemization is sound and complete and includes all formulas in which all strong quantifiers are existential. The method makes use of an existence predicate first introduced by Dana Scott.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  19.  47
    Embedding Logics Into Product Logic.Matthias Baaz, Petr Hájek, David Švejda & Jan Krajíček - 1998 - Studia Logica 61 (1):35-47.
    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.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  20.  52
    Kurt Gödel and the Foundations of Mathematics: Horizons of Truth.Matthias Baaz (ed.) - 2011 - Cambridge University Press.
    Machine generated contents note: Part I. Historical Context - Gödel's Contributions and Accomplishments: 1. The impact of Gödel's incompleteness theorems on mathematics Angus Macintyre; 2. Logical hygiene, foundations, and abstractions: diversity among aspects and options Georg Kreisel; 3. The reception of Gödel's 1931 incompletabilty theorems by mathematicians, and some logicians, to the early 1960s Ivor Grattan-Guinness; 4. 'Dozent Gödel will not lecture' Karl Sigmund; 5. Gödel's thesis: an appreciation Juliette C. Kennedy; 6. Lieber Herr Bernays!, Lieber Herr Gödel! Gödel on (...)
    Direct download  
     
    Export citation  
     
    Bookmark   1 citation  
  21. Short Proofs of Tautologies Using the Schema of Equivalence.Matthias Baaz & Richard Zach - 1994 - In Egon Börger, Yuri Gurevich & Karl Meinke (eds.), Computer Science Logic. 7th Workshop, CSL '93, Swansea. Selected Papers. Berlin: Springer. pp. 33-35.
    It is shown how the schema of equivalence can be used to obtain short proofs of tautologies A , where the depth of proofs is linear in the number of variables in A .
    Direct download (2 more)  
    Translate
     
     
    Export citation  
     
    Bookmark   1 citation  
  22.  14
    Complexity of Resolution Proofs and Function Introduction.Matthias Baaz & Alexander Leitsch - 1992 - Annals of Pure and Applied Logic 57 (3):181-215.
    The length of resolution proofs is investigated, relative to the model-theoretic measure of Herband complexity. A concept of resolution deduction is introduced which is somewhat more general than the classical concepts. It is shown that proof complexity is exponential in terms of Herband complexity and that this bound is tight. The concept of R-deduction is extended to FR-deduction, where, besides resolution, a function introduction rule is allowed. As an example, consider the clause P Q: conclude P) Q, where a, f (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  23.  13
    Generalizing Theorems in Real Closed Fields.Matthias Baaz & Richard Zach - 1995 - Annals of Pure and Applied Logic 75 (1-2):3-23.
    Jan Krajíček posed the following problem: Is there is a generalization result in the theory of real closed fields of the form: If A is provable in length k for all n ϵ ω , then A is provable? It is argued that the answer to this question depends on the particular formulation of the “theory of real closed fields.” Four distinct formulations are investigated with respect to their generalization behavior. It is shown that there is a positive answer to (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  24.  15
    Note on Witnessed Gödel Logics with Delta.Matthias Baaz & Oliver Fasching - 2010 - Annals of Pure and Applied Logic 161 (2):121-127.
    Witnessed Gödel logics are based on the interpretation of () by minimum instead of supremum . Witnessed Gödel logics appear for many practical purposes more suited than usual Gödel logics as the occurrence of proper infima/suprema is practically irrelevant. In this note we characterize witnessed Gödel logics with absoluteness operator w.r.t. witnessed Gödel logics using a uniform translation.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  25. Approximating Propositional Calculi by Finite-Valued Logics.Matthias Baaz & Richard Zach - 1994 - In 24th International Symposium on Multiple-valued Logic, 1994. Proceedings. Los Alamitos: IEEE Press. pp. 257–263.
    The problem of approximating a propositional calculus is to find many-valued logics which are sound for the calculus (i.e., all theorems of the calculus are tautologies) with as few tautologies as possible. This has potential applications for representing (computationally complex) logics used in AI by (computationally easy) many-valued logics. It is investigated how far this method can be carried using (1) one or (2) an infinite sequence of many-valued logics. It is shown that the optimal candidate matrices for (1) can (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  26. Algorithmic Structuring of Cut-Free Proofs.Matthias Baaz & Richard Zach - 1993 - In Egon Börger, Hans Kleine Büning, Gerhard Jäger, Simone Martini & Michael M. Richter (eds.), Computer Science Logic. CSL’92, San Miniato, Italy. Selected Papers. Berlin: Springer. pp. 29–42.
    The problem of algorithmic structuring of proofs in the sequent calculi LK and LKB ( LK where blocks of quantifiers can be introduced in one step) is investigated, where a distinction is made between linear proofs and proofs in tree form. In this framework, structuring coincides with the introduction of cuts into a proof. The algorithmic solvability of this problem can be reduced to the question of k-l-compressibility: "Given a proof of length k , and l ≤ k : Is (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  27. Completeness of a Hypersequent Calculus for Some First-Order Gödel Logics with Delta.Matthias Baaz, Norbert Preining & Richard Zach - 2006 - In 36th International Symposium on Multiple-valued Logic. May 2006, Singapore. Proceedings. Los Alamitos: IEEE Press.
    All first-order Gödel logics G_V with globalization operator based on truth value sets V C [0,1] where 0 and 1 lie in the perfect kernel of V are axiomatized by Ciabattoni’s hypersequent calculus HGIF.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  28.  5
    Controlling Witnesses.Matthias Baaz - 2005 - Annals of Pure and Applied Logic 136 (1-2):22-29.
    This paper presents a translation which allows one to describe constructive provability within classical first-order logic.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  29. Effective Finite-Valued Approximations of General Propositional Logics.Matthias Baaz & Richard Zach - 2008 - In Arnon Avron, Nachum Dershowitz & Alexander Rabinovich (eds.), Pillars of Computer Science: Essays Dedicated to Boris (Boaz) Trakhtenbrot on the Occasion of His 85th Birthday. Berlin: Springer. pp. 107–129.
    Propositional logics in general, considered as a set of sentences, can be undecidable even if they have “nice” representations, e.g., are given by a calculus. Even decidable propositional logics can be computationally complex (e.g., already intuitionistic logic is PSPACE-complete). On the other hand, finite-valued logics are computationally relatively simple—at worst NP. Moreover, finite-valued semantics are simple, and general methods for theorem proving exist. This raises the question to what extent and under what circumstances propositional logics represented in various ways can (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  30.  2
    Foreword.Matthias Baaz - 2009 - Annals of Pure and Applied Logic 157 (2-3):63.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  31.  2
    Foreword.Matthias Baaz - 2012 - Annals of Pure and Applied Logic 163 (11):1447.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  32.  21
    Generalizing Proofs in Monadic Languages.Matthias Baaz & Piotr Wojtylak - 2008 - Annals of Pure and Applied Logic 154 (2):71-138.
    This paper develops a proof theory for logical forms of proofs in the case of monadic languages. Among the consequences are different kinds of generalization of proofs in various schematic proof systems. The results use suitable relations between logical properties of partial proof data and algebraic properties of corresponding sets of linear diophantine equations.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  33.  19
    Herbrand's Theorem and Term Induction.Matthias Baaz & Georg Moser - 2006 - Archive for Mathematical Logic 45 (4):447-503.
    We study the formal first order system TIND in the standard language of Gentzen's LK . TIND extends LK by the purely logical rule of term-induction, that is a restricted induction principle, deriving numerals instead of arbitrary terms. This rule may be conceived as the logical image of full induction.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  34. Incompleteness of a First-Order Gödel Logic and Some Temporal Logics of Programs.Matthias Baaz, Alexander Leitsch & Richard Zach - 1996 - In Hans Kleine Büning (ed.), Computer Science Logic. CSL 1995. Selected Papers. Berlin: Springer. pp. 1--15.
    It is shown that the infinite-valued first-order Gödel logic G° based on the set of truth values {1/k: k ε w {0}} U {0} is not r.e. The logic G° is the same as that obtained from the Kripke semantics for first-order intuitionistic logic with constant domains and where the order structure of the model is linear. From this, the unaxiomatizability of Kröger's temporal logic of programs (even of the fragment without the nexttime operator O) and of the authors' temporal (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  35.  32
    Note on Generalizing Theorems in Algebraically Closed Fields.Matthias Baaz & Richard Zach - 1998 - Archive for Mathematical Logic 37 (5-6):297-307.
    The generalization properties of algebraically closed fields $ACF_p$ of characteristic $p > 0$ and $ACF_0$ of characteristic 0 are investigated in the sequent calculus with blocks of quantifiers. It is shown that $ACF_p$ admits finite term bases, and $ACF_0$ admits term bases with primality constraints. From these results the analogs of Kreisel's Conjecture for these theories follow: If for some $k$ , $A(1 + \cdots + 1)$ ( $n$ 1's) is provable in $k$ steps, then $(\forall x)A(x)$ is provable.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  36.  10
    On the Classification of First Order Gödel Logics.Matthias Baaz & Norbert Preining - 2019 - Annals of Pure and Applied Logic 170 (1):36-57.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  37.  17
    Skolemization in Intermediate Logics with the Finite Model Property.Matthias Baaz & Rosalie Iemhoff - 2016 - Logic Journal of the IGPL 24 (3):224-237.
  38.  46
    The Axiom of Choice in Quantum Theory.Norbert Brunner, Karl Svozil & Matthias Baaz - 1996 - Mathematical Logic Quarterly 42 (1):319-340.
    We construct peculiar Hilbert spaces from counterexamples to the axiom of choice. We identify the intrinsically effective Hamiltonians with those observables of quantum theory which may coexist with such spaces. Here a self adjoint operator is intrinsically effective if and only if the Schrödinger equation of its generated semigroup is soluble by means of eigenfunction series expansions.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark  
  39.  7
    Monotone Operators on Gödel Logic.Oliver Fasching & Matthias Baaz - 2014 - Archive for Mathematical Logic 53 (3-4):261-284.
    We consider an extension of Gödel logic by a unary operator that enables the addition of non-negative reals to truth-values. Although its propositional fragment has a simple proof system, first-order validity is Π2-hard. We explain the close connection to Scarpellini’s result on Π2-hardness of Łukasiewicz’s logic.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark