Online research in philosophy

The logical flow graphs of sequent calculus proofs might contain oriented cycles. For the predicate calculus the elimination of cycles might be non-elementary and this was shown in [Car96]. For the propositional calculus, we prove that if a proof of k lines contains n cycles then there exists an acyclic proof with O(k n+l ) lines. In particular, there is a polynomial time algorithm which eliminates cycles from a proof. These results are motivated by the search for general methods on proving lower bounds on proof size and by the design of more efficient heuristic algorithms for proof search.

Deep inference is a natural generalisation of the one-sided sequent calculus where rules are allowed to apply deeply inside formulas, much like rewrite rules in term rewriting. This freedom in applying inference rules allows to express logical systems that are difficult or impossible to express in the cut-free sequent calculus and it also allows for a more fine-grained analysis of derivations than the sequent calculus. However, the same freedom also makes it harder to carry out this analysis, in particular it is harder to design cut elimination procedures. In this paper we see a cut elimination procedure for a deep inference system for classical predicate logic. As a consequence we derive Herbrand's Theorem, which we express as a factorisation of derivations.

Consider the set of tautologies of the classical propositional calculus containing no connective other than and, or, and not. Consider the subset of this set containing tautologies in exactlyn propositional variables. This paper provides a method for determining the number of equivalence classes of each such subset modulo equivalence in the infinite-valued Lukasiewicz propositional calculus.

The aim of this paper is to apply properties of the double dual endofunctor on the category of bounded distributive lattices and some extensions thereof to obtain completeness of certain non-classical propositional logics in a unified way. In particular, we obtain completeness theorems for Moisil calculus, n-valued Łukasiewicz calculus and Nelson calculus. Furthermore we show some conservativeness results by these methods.

S. Jakowski introduced the discussive prepositional calculus D 2as a basis for a logic which could be used as underlying logic of inconsistent but nontrivial theories (see, for example, N. C. A. da Costa and L. Dubikajtis, On Jakowski's discussive logic, in Non-Classical Logic, Model Theory and Computability, A. I. Arruda, N. C. A da Costa and R. Chuaqui edts., North-Holland, Amsterdam, 1977, 37–56). D 2has afterwards been extended to a first-order predicate calculus and to a higher-order logic (cf. the quoted paper). In this paper we present a natural version of D 2, in the sense of Jakowski and Gentzen; as a consequence, we suggest a new formulation of the discussive predicate calculus (with equality). A semantics for the new calculus is also presented.

In classical propositional calculus for each proposition A(p) the following holds: $\vdash A(p) \leftrightarrow A^3(p)$ . In this paper we consider what remains of this in the intuitionistic case. It turns out that for each proposition A(p) the following holds: there is an n ∈ N such that $\vdash A^n(p) \leftrightarrow A^{n + 2}(p)$ . As a byproduct of the proof we give some theorems which may be useful elsewhere in propositional calculus.

Four consequence operators based on hypergraph satisfiability are defined. Their properties are explored and interconnections are displayed. Finally their relation to the case of the Classical Propositional Calculus is shown.

Introduction -- The concept of logical consequence -- Tarski's characterization of the common concept of logical consequence -- The logical consequence relation has a modal element -- The logical consequence relation is formal -- The logical consequence relation is A priori -- Logical and non-logical terminology -- The meanings of logical terms explained in terms of their semantic properties -- The meanings of logical terms explained in terms of their inferential properties -- Model-theoretic and deductive-theoretic conceptions of logic -- Linguistic preliminaries : the language M -- Syntax of M -- The definition of a well formed formula of M -- Semantics for M -- The sentential connectives are defined -- The notion of satisfaction is introduced and the quantifiers are defined -- Model-theoretic consequence -- Truth in a structure -- Satisfaction revisited -- Formalized definition of truth -- Model-theoretic consequence defined -- The model-theoretic definition and the concept of logical consequence -- Does the model theoretic consequence relation reflect the salient features of the common concept of logical consequence? -- What is a logical constant? -- Deductive consequence -- Deductive system n -- The deductive theoretic definition and the concept of logical consequence -- Tarski's criticism of the deductive theoretic definition -- Is N a correct deductive system?

Hilbert's ε-calculus is based on an extension of the language of predicate logic by a term-forming operator ex. Two fundamental results about the ε-calculus, the first and second epsilon theorem, play a rôle similar to that which the cut-elimination theorem plays in sequent calculus. In particular, Herbrand's Theorem is a consequence of the epsilon theorems. The paper investigates the epsilon theorems and the complexity of the elimination procedure underlying their proof, as well as the length of Herbrand disjunctions of existential theorems obtained by this elimination procedure.

We provide a constructive, direct, and simple proof of the completeness of the cut-free part of the hypersequential calculus for G¨odel logic (thereby proving both completeness of the calculus for its standard semantics, and the admissibility of the cut rule in the full calculus). We then extend the results and proofs to derivations from assumptions, showing that such derivations can be confined to those in which cuts are made only on formulas which occur in the assumptions.