Isomorphism between formulae is defined with respect to categories formalizing equality of deductions in classical propositional logic and in the multiplicative fragment of classical linear propositional logic caught by proof nets. This equality is motivated by generality of deductions. Characterizations are given for pairs of isomorphic formulae, which lead to decision procedures for this isomorphism.

This article investigates Charles Peirce’s development of logical calculi for classical propositional logic in 1880–1896. Peirce’s 1880 work on the algebra of logic resulted in a successful calculus for Boolean algebra. This calculus, denoted byPC, is here presented as a sequent calculus and not as a natural deduction system. It is shown that Peirce’s aim was to presentPCas a sequent calculus. The law of distributivity, which Peirce states in 1880, is proved using Peirce’s Rule, which is (...) a residuation, inPC. The transitional systems of the algebra of the copula that Peirce develops since 1880 paved the way to the 1896 graphical system of the alpha graphs. It is shown how the rules of the alpha system reinterpret Boolean algebras, answering Peirce’s statement that logical graphs supply a new system of fundamental assumptions to logical algebra. A proof-theoretic analysis is given for the connection betweenPCand the alpha system. (shrink)

This paper studies a combined system of intuitionistic and classical propositional logic from proof-theoretic viewpoints. Based on the semantic treatment of Humberstone (J Philos Log 8:171–196, 1979) and del Cerro and Herzig (Frontiers of combining systems: FroCoS, Springer, 1996), a sequent calculus $$\textsf{G}(\textbf{C}+\textbf{J})$$ is proposed. An approximate idea of obtaining $$\textsf{G}(\textbf{C}+\textbf{J})$$ is adding rules for classical implication on top of the intuitionistic multi-succedent sequent calculus by Maehara (Nagoya Math J 7:45–64, 1954). However, in the semantic treatment, (...) some formulas do not satisfy heredity, which leads to the necessity of a restriction on the right rule for intuitionistic implication to keep the soundness of the calculus. The calculus $$\textsf{G}(\textbf{C}+\textbf{J})$$ enjoys cut elimination and Craig interpolation, whose detailed proofs are described in this paper. Cut elimination enables us to show the decidability of this combination both directly and syntactically. This paper also employs a canonical model argument to establish the strong completeness of Hilbert system $$\mathbf {C+J}$$ proposed by del Cerro and Herzig (Frontiers of combining systems: FroCoS, Springer, 1996). (shrink)

We show that the relational semantics of the Lambek calculus, both nonassociative and associative, is also sound and complete for its extension with classical propositional logic. Then, using filtrations, we obtain the finite model property for the nonassociative Lambek calculus extended with classical propositional logic.

In Schwichtenberg, Schwichtenberg fine-tuned Tait’s technique so as to provide a simplified version of Gentzen’s original cut-elimination procedure for first-order classical logic. In this note we show that, limited to the case of classical propositional logic, the Tait–Schwichtenberg algorithm allows for a further simplification. The procedure offered here is implemented on Kleene’s sequent system G4. The specific formulation of the logical rules for G4 allows us to provide bounds on the height of cut-free proofs just (...) in terms of the logical complexity of their end-sequent. (shrink)

In the paper, we apply Kooi and Tamminga’s correspondence analysis to some conventional and functionally incomplete fragments of classical propositional logic. In particular, the paper deals with the implication, disjunction, and negation fragments. Additionally, we consider an application of correspondence analysis to some connectiveless fragment with certain basic properties of the logical consequence relation only. As a result of the application, one obtains a sound and complete natural deduction system for any binary extension of each fragment in (...) question. With the focus on exclusive disjunction we comparatively study the proposed systems. Finally, we discuss Segerberg’s systems for connectiveless and negation fragments and compare them with our systems. (shrink)

In this paper we show that some versions of Dung’s abstract argumentation frames are equivalent to classical propositional logic. In fact, Dung’s attack relation is none other than the generalised Peirce–Quine dagger connective of classical logic which can generate the other connectives ${\neg, \wedge, \vee, \to}$ of classical logic. After establishing the above correspondence we offer variations of the Dung argumentation frames in parallel to variations of classical logic, such as resource (...) logics, predicate logic, etc., etc., and create resource argumentation frames, predicate argumentation frames, etc., etc. We also offer the notion of logic proof as a geometrical walk along the nodes of a Dung network and thus we are able to offer a geometrical abstraction of the notion of inference based argumentation. Thus our paper is also a contribution to the question: “What is a logical system” in as much as it integrates logic with abstract argumentation networks. (shrink)

The connectives of classical propositional logic are given an analysis in terms of necessary and sufficient conditions of acceptance and rejection, i.e. the connectives are analyzed within an expressivist bilateral meaning-is-use framework. It is explained how such a framework differs from standard inferentialist frameworks and it is argued that it is better suited to address the particular issues raised by the expressivist thesis that the meaning of a sentence is determined by the mental state that it is (...) conventionally used to express. Furthermore, it is shown that the classical requirements governing the connectives completely characterize classical logic, are conservative and separable, are in bilateral harmony, are structurally preservative with respect to the classical coordination requirements and resolve the categoricity problem. These results are taken to show that one can give an expressivist bilateral meaning-is-use analysis of the connectives that confer on them a determinate coherent classical interpretation. (shrink)

Dyrda and Prucnal gave a Hilbert-style axiomatization for the \-fragment of classical propositional logic. Their proof of completeness follows a different approach to the standard one proving the completeness of classical propositional logic. In this note, we present an alternative proof of Dyrda and Prucnal’s result following the standard arguments which prove the completeness of classical propositional logic.

In this paper, we show that the implication fragment of classical propositional logic is finitary for unification with parameters.

The introduction and elimination rules for material implication in natural deduction are not complete with respect to the implicational fragment of classical logic. A natural way to complete the system is through the addition of a new natural deduction rule corresponding to Peirce's formula → A) → A). E. Zimmermann [6] has shown how to extend Prawitz' normalization strategy to Peirce's rule: applications of Peirce's rule can be restricted to atomic conclusions. The aim of the present paper is (...) to extend Seldin's normalization strategy to Peirce's rule by showing that every derivation Π in the implicational fragment can be transformed into a derivation Π' such that no application of Peirce's rule in Π' occurs above applications of →-introduction and →-elimination. As a corollary of Seldin's normalization strategy we obtain a form of Glivenko's theorem for the classical {→}-fragment. (shrink)

Several problems arise with the Axiomatizability Theorem : Each 2-valued consequence is s.f.a . We mention in particular.

Dyrda and Prucnal gave a Hilbert-style axiomatization for the {∧,∨}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\{\wedge,\vee \}$$\end{document}-fragment of classical propositional logic. Their proof of completeness follows a different approach to the standard one proving the completeness of classical propositional logic. In this note, we present an alternative proof of Dyrda and Prucnal’s result following the standard arguments which prove the completeness of classical propositional logic.

In previous work, I introduced a complete axiomatization of classical non-tautologies based essentially on Łukasiewicz’s rejection method. The present paper provides a new, Hilbert-type axiomatization (along with related systems to axiomatize classical contradictions, non-contradictions, contingencies and non-contingencies respectively). This new system is mathematically less elegant, but the format of the inferential rules and the structure of the completeness proof possess some intrinsic interest and suggests instructive comparisons with the logic of tautologies.

In much the same way that it is possible to construct a model of hyperbolic geometry in the Euclidean plane, it is possible to model quantum logic within the classical propositional calculus.

The logical properties of the 'if-then' connective of ordinary English differ markedly from the logical properties of the material conditional of classical, two-valued logic. This becomes apparent upon examination of arguments in conversational English which involve (noncounterfactual) usages of if-then'. A nonclassical system of propositional logic is presented, whose conditional connective has logical properties approximating those of 'if-then'. This proposed system reduces, in a sense, to the classical logic. Moreover, because it is equivalent to (...) a certain nonstandard three-valued logic, its decision procedure is almost as efficient as that of the classical logic. It therefore provides a rational and convenient system in which to formalize English arguments. (shrink)

Propositional logic, also known as sentential logic and statement logic, is the branch of logic that studies ways of joining and/or modifying entire propositions, statements or sentences to form more complicated propositions, statements or sentences, as well as the logical relationships and properties that are derived from these methods of combining or altering statements. In propositional logic, the simplest statements are considered as indivisible units, and hence, propositional logic does not study (...) those logical properties and relations that depend upon parts of statements that are not themselves statements on their own, such as the subject and predicate of a statement. The most thoroughly researched branch of propositional logic is classical truth-functional propositional logic, which studies logical operators and connectives that are used to produce complex statements whose truth-value depends entirely on the truth-values of the simpler statements making them up, and in which it is assumed that every statement is either true or false and not both. However, there are other forms of propositional logic in which other truth-values are considered, or in which there is consideration of connectives that are used to produce statements whose truth-values depend not simply on the truth-values of the parts, but additional things such as their necessity, possibility or relatedness to one another. (shrink)

Bertrand Russell presented three systems of propositional logic, one first in Principles of Mathematics, University Press, Cambridge, 1903 then in “The Theory of Implication”, Routledge, New York, London, pp. 14–61, 1906) and culminating with Principia Mathematica, Cambridge University Press, Cambridge, 1910. They are each based on different primitive connectives and axioms. This paper follows “Peirce’s Law” through those systems with the aim of understanding some of the notorious peculiarities of the 1910 system and so revealing some of the (...) early history of classical propositional logic. “Peirce’s Law” is a valid formula of elementary propositional logic: [ ⊃ p] ⊃ p This sentence is not even a theorem in the 1910 system although it is one of the axioms in 1903 and is proved as a theorem in 1906. Although it is not proved in 1910, the two lemmas from the proof in 1906 occur as theorems, and Peirce’s Law could have been derived from them in a two step proof. The history of Peirce’s Law in Russell’s systems helps to reconstruct some of the history of axiomatic systems of classical propositional logic. (shrink)

The formulas-as-types isomorphism tells us that every proof and theorem, in the intuitionistic implicational logic $H_\rightarrow$, corresponds to a lambda term or combinator and its type. The algorithms of Bunder very efficiently find a lambda term inhabitant, if any, of any given type of $H_\rightarrow$ and of many of its subsystems. In most cases the search procedure has a simple bound based roughly on the length of the formula involved. Computer implementations of some of these procedures were done in (...) Dekker. In this paper we extend these methods to full classical propositional logic as well as to its various subsystems. This extension has partly been implemented by Oostdijk. (shrink)

First and foremost, this paper concerns the combination of classical propositional logic with a relevant implication. The proposed combination is simple and transparent from a proof theoretic point of view and at the same time extremely useful for relating formal logic to natural language sentences. A specific system will be presented and studied, also from a semantic point of view. The last sections of the paper contain more general considerations on combining classical propositional (...) class='Hi'>logic with a relevant logic that has all classical theorems as theorems. (shrink)

We construct a a system PLRI which is the classical propositional logic supplied with a ternary construction , interpreted as the intensional identity of statements and in the context . PLRI is a refinement of Roman Suszko’s sentential calculus with identity (SCI) whose identity connective is a binary one. We provide a Hilbert-style axiomatization of this logic and prove its soundness and completeness with respect to some algebraic models. We also show that PLRI can be used (...) to give a partial solution to the paradox of analysis. (shrink)

§1. Introduction. The classical propositional calculus has an undeserved reputation among logicians as being essentially trivial. I hope to convince the reader that it presents some of the most challenging and intriguing problems in modern logic. Although the problem of the complexity of propositional proofs is very natural, it has been investigated systematically only since the late 1960s. Interest in the problem arose from two fields connected with computers, automated theorem proving and computational complexity theory. The (...) earliest paper in the subject is a ground-breaking article by Tseitin [62], the published version of a talk given in 1966 at a Leningrad seminar. In the three decades since that talk, substantial progress has been made in determining the relative complexity of proof systems, and in proving strong lower bounds for some restricted proof systems. However, major problems remain to challenge researchers. The present paper provides a survey of the field, and of some of the techniques that have proved successful in deriving lower bounds on the complexity of proofs. A major area only touched upon here is the proof theory of bounded arithmetic and its relation to the complexity of propositional proofs. The reader is referred to the book by Buss [10] for background in bounded arithmetic. The forthcoming book by Krajíček [40] also gives a good introduction to bounded arithmetic, as well as covering most of the basic results in complexity of propositional proofs. (shrink)

We examine second order intuitionistic propositional logic, IPC². Let $F_\exists $ be the set of formulas with no universal quantification. We prove Glivenko's theorem for formulas in $F_\exists $ that is, for φ € $F_\exists $ φ is a classical tautology if and only if ¬¬φ is a tautology of IPC². We show that for each sentence φ € $F_\exists $ (without free variables), φ is a classical tautology if and only if φ is an intuitionistic (...) tautology. As a corollary we obtain a semantic argument that the quantifier V is not definable in IPC² from ⊥, V, ^, →. (shrink)

This paper shows Hilbert system (C+J)-, given by del Cerro and Herzig (1996) is semantically incomplete. This system is proposed as a proof theory for Kripke semantics for a combination of intuitionistic and classical propositional logic, which is obtained by adding the natural semantic clause of classical implication into intuitionistic Kripke semantics. Although Hilbert system (C+J)- contains intuitionistic modus ponens as a rule, it does not contain classical modus ponens. This paper gives an argument ensuring (...) that the system (C+J)- is semantically incomplete because of the absence of classical modus ponens. Our method is based on the logic of paradox, which is a paraconsistent logic proposed by Priest (1979). (shrink)

This paper presents a formalization of the classical proof of completeness in Henkin-style developed by Troelstra and van Dalen for intuitionistic logic with respect to Kripke models. The completeness proof incorporates their insights in a fresh and elegant manner that is better suited for mechanization. We discuss details of our implementation in the Lean theorem prover with emphasis on the prime extension lemma and construction of the canonical model. Our implementation is restricted to a system of intuitionistic (...) class='Hi'>propositional logic with implication, conjunction, disjunction, and falsity given in terms of a Hilbert-style axiomatization. As far as we know, our implementation is the first verified Henkin-style proof of completeness for intuitionistic logic following Troelstra and van Dalen's method in the literature. (shrink)

This paper studies the relationship between Argumentation Logic, a recently defined logic based on the study of argumentation in AI, and classical Propositional Logic. In particular, it shows that AL and PL are logically equivalent in that they have the same entailment relation from any given classically consistent theory. This equivalence follows from a correspondence between the non-acceptability of sentences in AL and Natural Deduction proofs of the complement of these sentences. The proof of this (...) equivalence uses a restricted form of ND proofs, where hypotheses in the application of the Reductio of Absurdum inference rule are required to be “relevant” to the absurdity derived in the rule. The paper also discusses how the argumentative re-interpretation of PL could help control the application of ex-falso quodlibet in the presence of inconsistencies. (shrink)

This paper is a survey of results concerning embeddings of intuitionistic propositional logic and its extensions into various classical modal systems.

A logic-enriched type theory is a type theory extended with a primitive mechanism for forming and proving propositions. We construct two LTTs, named and , which we claim correspond closely to the classical predicative systems of second order arithmetic and . We justify this claim by translating each second order system into the corresponding LTT, and proving that these translations are conservative. This is part of an ongoing research project to investigate how LTTs may be used to formalise (...) different approaches to the foundations of mathematics.The two LTTs we construct are subsystems of the logic-enriched type theory , which is intended to formalise the classical predicative foundation presented by Herman Weyl in his monograph Das Kontinuum. The system has also been claimed to correspond to Weyl’s foundation. By casting and as LTTs, we are able to compare them with . It is a consequence of the work in this paper that is strictly stronger than .The conservativity proof makes use of a novel technique for proving one LTT conservative over another, involving defining an interpretation of the stronger system out of the expressions of the weaker. This technique should be applicable in a wide variety of different cases outside the present work. (shrink)

In the paper we consider complexity of intuitionistic propositional logic and its natural fragments such as implicative fragment, finite-variable fragments, and some others. Most facts we mention here are known and obtained by logicians from different countries and in different time since 1920s; we present these results together to see the whole picture.

Automated reasoning issues are addressed for a finite lattice-valued propositional logic LnP(X) with truth-values in a finite lattice-valued logical algebraic structure—lattice implication algebra. We investigate extended strategies and rules from classical logic to LnP(X) to simplify the procedure in the semantic level for testing the satisfiability of formulas in LnP(X) at a certain truth-value level α (α-satisfiability) while keeping the role of truth constant formula played in LnP(X). We propose a lock resolution method at a certain (...) truth-value level α (α-lock resolution) in LnP(X) and have proved its theorems of soundness and weak completeness, respectively. We provide more efficient resolution based automated reasoning in LnP(X) and key supports for α-resolution-based automated reasoning approaches and algorithms in lattice based linguistic truth-valued logic. (shrink)

Modern methodology furnishes two partly competitive and partly complementary views on structure of the development of scientific investigation. According to the first view the development of science consists in enlargement of the set of empirical theorems; according to the other it consists, rather, in the narrowing of the set of possible theoretical hypotheses. A particular kind of assertion is associated with each of these views. The first is associated with the relation of assertion expressed in the statement: “the state α (...) of scientific investigationB forces us to accept the statement Τ”. The other view is associated with the relation of assertion expressed in the statement: “the state α of scientific investigationB admits the acceptance of the statement Τ”. Under a suitable definition of forcing we obtain the conclusion that intuitionistic logic is the class of only those formulas which we are forced to accept by every state of every scientific investigation. The notion of admission under a certain definition analogically leads to intuitionistic logic; on the other hand in the case of another, more natural definition, it leads to justification of a certain system of strict implication which is stronger than Lewis’ system S4 and which overlaps system S5.It can be said that assuming quite a natural definition of admission this system contains only those formulas the acceptance of which is admitted by every state of every scientific investigation. (shrink)