The main theorem says that a consequence operator is an effective part of the consequence operator for the classical prepositional calculus iff it is a consequence operator for a logic satisfying the compactness theorem, and in which every finitely axiomatizable theory is decidable.

We introduce two Gentzen-style sequent calculus axiomatizations for conservative extensions of basic propositional logic. Our first axiomatization is an ipmrovement of, in the sense that it has a kind of the subformula property and is a slight modification of. In this system the cut rule is eliminated. The second axiomatization is a classical conservative extension of basic propositional logic. Using these axiomatizations, we prove interpolation theorems for basic propositional logic.

We explore the technical details and historical evolution of Charles Peirce's articulation of a truth table in 1893, against the background of his investigation into the truth-functional analysis of propositions involving implication. In 1997, John Shosky discovered, on the verso of a page of the typed transcript of Bertrand Russell's 1912 lecture on ?The Philosophy of Logical Atomism? truth table matrices. The matrix for negation is Russell's, alongside of which is the matrix for material implication in the hand of Ludwig (...) Wittgenstein. It is shown that an unpublished manuscript identified as composed by Peirce in 1893 includes a truth table matrix that is equivalent to the matrix for material implication discovered by John Shosky. An unpublished manuscript by Peirce identified as having been composed in 1883?1884 in connection with the composition of Peirce's ?On the Algebra of Logic: A Contribution to the Philosophy of Notation? that appeared in the American Journal of Mathematics in 1885 includes an example of an indirect truth table for the conditional. (shrink)

In this paper I argue that a truth functional account of conditional statements ‘if A then B’ not only is inadequate, but that it eliminates the very conditionality expressed by ‘if’. Focusing only on the truth-values of the statements ‘A’ and ‘B’ and different combinations of these, one is bound to miss out on the conditional relation expressed between them. But this is not a flaw only of truth functionality and the material conditional. All approaches that try to treat conditionals (...) as mere functions of their antecedents and consequents will end up in some sort of logical atomism where causal matters simply are reduced to the joint occurrence of A and B. What we need is a non-extensional approach to conditionals that can account for hypotheticality, potentiality, and dependency, none of which can be understood by looking to the antecedent or consequent per se. (shrink)

In this paper I present some of Robert N. McLaughlin's critique of a truth functional approach to conditionals as it appears in his book On the Logic of Ordinary Conditionals. Based on his criticism I argue that the basic principles of logic together amount to epistemological and metaphysical implications that can only be accepted from a logical atomist perspective. Attempts to account for conditional relations within this philosophical framework will necessarily fail. I thus argue that it is not truth functionality (...) as such that is the problem, but the philosophical foundation of modern logic. (shrink)

El objetivo de este artículo es proponer un método de traducción de tablas de verdad a reglas de inferencia, para la lógica proposicional, que sea tan directo como el tradicional método inverso (de reglas a tablas). Este método, además, permitirá resolver de manera elegante el viejo problema, formulado originalmente por Prior en 1960, de determinar qué reglas de inferencia definen un conectivo. /// This article aims at setting forth a method to translate truth tables into inference rules, in propositional logic, (...) which is as straightforward as the traditional inverse method (from rules to tables). Besides, this method allows for an elegant solution of Prior's (1960) problem of determining when a set of inferential rules succeeds or fails in defining a logical operator. (shrink)

INTRODUCTION The main purpose of this work is to provide an English translation of and commentary on a recently published Arabic text dealing with conditional propositions and syllogisms. The text is that of Avicenna (Abu 'All ibn Sina, ...

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. (shrink)

Most instantiations of the inference ‘y; so if x, y’ seem intuitively odd, a phenomenon known as one of the paradoxes of the material conditional. A common explanation of the oddity, endorsed by Mental Model theory, is based on the intuition that the conclusion of the inference throws away semantic information. We build on this explanation to identify two joint conditions under which the inference becomes acceptable: (a) the truth of x has bearings on the relevance of asserting y; and (...) (b) the speaker can reasonably be expected not to be in a position to assume that x is false. We show that this dual pragmatic criterion makes accurate predictions, and contrast it with the criterion defined by the mental model theory of conditionals, which we show to be inadequate. (shrink)

This is part two of a complete exposition of Logic, in which there is a radically new synthesis of Aristotelian-Scholastic Logic with modern Logic. Part II is the presentation of the theory of propositions. Simple, composite, atomic, compound, modal, and tensed propositions are all examined. Valid consequences and propositional logical identities are rigorously proven. Modal logic is rigorously defined and proven. This is the first work of Logic known to unite Aristotelian logic and modern logic using scholastic logic as the (...) instrument. (shrink)

Clear, comprehensive, intermediate introduction to logical languages, applications of symbolic logic to physics, mathematics, biology.

I have shown (to my satisfaction) that Leibniz's final attempt at a generalized syllogistico-propositional calculus in the Generales Inquisitiones was pretty successful. The calculus includes the truth-table semantics for the propositional calculus. It contains an unorthodox view of conjunction. It offers a plethora of very important logical principles. These deserve to be called a set of fundamentals of logical form. Aside from some imprecisions and redundancies the system is a good systematization of propositional logic, its semantics, and a correct account (...) of general syllogistics. For 1686 it was quite an accomplishment. It is a pity that Leibniz himself did not fully appreciate what he had achieved. It does seem to me that this was due in part, as the Kneales urge (Note 4), to his having kept the focus of his attention on traditional syllogistics. It is a great pity that he did not polish GI 195–200 for publication. The publication of GI 195, 198, and 200 would have most likely promoted further research. MAJR- Humanities, Social Sciences and Law. (shrink)

We give resource bounded versions of the Completeness Theorem for propositional and predicate logic. For example, it is well known that every computable consistent propositional theory has a computable complete consistent extension. We show that, when length is measured relative to the binary representation of natural numbers and formulas, every polynomial time decidable propositional theory has an exponential time (EXPTIME) complete consistent extension whereas there is a nondeterministic polynomial time (NP) decidable theory which has no polynomial time complete consistent extension (...) when length is measured relative to the binary representation of natural numbers and formulas. It is well known that a propositional theory is axiomatizable (respectively decidable) if and only if it may be represented as the set of infinite paths through a computable tree (respectively a computable tree with no dead ends). We show that any polynomial time decidable theory may be represented as the set of paths through a polynomial time decidable tree. On the other hand, the statement that every polynomial time decidable, relative to the tally representation of natural numbers and formulas, is equivalent to P = NP. For predicate logic, we develop a complexity theoretic version of the Henkin construction to prove a complexity theoretic version of the Completeness Theorem. Our results imply that that any polynomial space decidable theory △ possesses a polynomial space computable model which is exponential space decidable and thus △ has an exponential space complete consistent extension. Similar results are obtained for other notions of complexity. (shrink)

This book contains an introduction to symbolic logic and a thorough discussion of mechanical theorem proving and its applications. The book consists of three major parts. Chapters 2 and 3 constitute an introduction to symbolic logic. Chapters 4–9 introduce several techniques in mechanical theorem proving, and Chapters 10 an 11 show how theorem proving can be applied to various areas such as question answering, problem solving, program analysis, and program synthesis.

This introduction to the basic forms of deductive inference as evaluated by methods of modern symbolic logic is de­signed for sophomore-junior-level stu­dents ready to specialize in the study of deductive logic. It can be used also for an introductory logic course. The inde­pendence of many sections allows the instructor utmost flexibility. The text consists of eight chapters, the first six of which are designed to intro­duce the student to basic topics of sen­tence and predicate logic. The last two chapters extend (...) the procedures of the first six to alethic modal logic, the logic of imperatives, and deontic logic. Throughout the text there is an attempt to relate symbolic techniques to issues in the philosophy of logic. (shrink)

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)

Logic forms the basis of mathematics and is a fundamental part of any mathematics course. This book provides students with a clear and accessible introduction to this important subject, using the concept of model as the main focus and covering a wide area of logic. The chapters of the book cover propositional calculus, boolean algebras, predicate calculus and completelness theorems with answeres to all of the excercises and the end of the volume. This is an ideal introduction to mathematics and (...) logic for the advanced undergraduate student. (shrink)

We present a series of arguments for logical nativism, focusing mainly on the meaning of disjunction in human languages. We propose that all human languages are logical in the sense that the meaning of linguistic expressions corresponding to disjunction (e.g. English or , Chinese huozhe, Japanese ka ) conform to the meaning of the logical operator in classical logic, inclusive- or . It is highly implausible, we argue, that children acquire the (logical) meaning of disjunction by observing how adults use (...) disjunction. Findings from studies of child language acquisition and from cross-linguistic research invite the conclusion that children do not learn to be logical—it comes naturally to them. (shrink)

This article advances the view that propositional logic can and should be taught within general education logic courses in ways that emphasizes its practical usefulness, much beyond what commonly occurs in logic textbooks. Discussion and examples of this relevance include database searching, understanding structured documents, and integrating concepts of proof construction with argument analysis. The underlying rationale for this approach is shown to have import for questions concerning the design of logic courses, textbooks, and the general education curriculum, particularly the (...) sequencing of formal and informal logic courses. (shrink)

The first known statements of the deduction theorems for the first-order predicate calculus and the classical sentential logic are due to Herbrand [8] and Tarski [14], respectively. The present paper contains an analysis of closure spaces associated with those sentential logics which admit various deduction theorems. For purely algebraic reasons it is convenient to view deduction theorems in a more general form: given a sentential logic C (identified with a structural consequence operation) in a sentential language I, a quite arbitrary (...) set P of formulas of I built up with at most two distinct sentential variables p and q is called a uniform deduction theorem scheme for C if it satisfies the following condition: for every set X of formulas of I and for any formulas and , C(X{{a}}) iff P(, ) AC(X). [P(, ) denotes the set of formulas which result by the simultaneous substitution of for p and for q in all formulas in P]. The above definition encompasses many particular formulations of theorems considered in the literature to be deduction theorems. Theorem 1.3 gives necessary and sufficient conditions for a logic to have a uniform deduction theorem scheme. Then, given a sentential logic C with a uniform deduction theorem scheme, the lattices of deductive filters on the algebras A similar to the language of C are investigated. It is shown that the join-semilattice of finitely generated (= compact) deductive filters on each algebra A is dually Brouwerian. (shrink)

We propose a new schema for the deduction theorem and prove that the deductive system S of a prepositional logic L fulfills the proposed schema if and only if there exists a finite set A(p, q) of propositional formulae involving only prepositional letters p and q such that A(p, p) L and p, A(p, q) s q.

We give a direct, purely arithmetical and elementary proof of the strong normalization of the cut-elimination procedure for full (i.e., in presence of all the usual connectives) classical natural deduction.

This article features long-sought proofs with intriguing properties (such as the absence of double negation and the avoidance of lemmas that appeared to be indispensable), and it features the automated methods for finding them. The theorems of concern are taken from various areas of logic that include two-valued sentential (or propositional) calculus and infinite-valued sentential calculus. Many of the proofs (in effect) answer questions that had remained open for decades, questions focusing on axiomatic proofs. The approaches we take are of (...) added interest in that all rely heavily on the use of a single program that offers logical reasoning, William McCune's automated reasoning program OTTER. The nature of the successes and approaches suggests that this program offers researchers a valuable automated assistant. This article has three main components. First, in view of the interdisciplinary nature of the audience, we discuss the means for using the program in question (OTTER), which flags, parameters, and lists have which effects, and how the proofs it finds are easily read. Second, because of the variety of proofs that we have found and their significance, we discuss them in a manner that permits comparison with the literature. Among those proofs, we offer a proof shorter than that given by Meredith and Prior in their treatment of ukasiewicz's shortest single axiom for the implicational fragment of two-valued sentential calculus, and we offer a proof for the ukasiewicz 23-letter single axiom for the full calculus. Third, with the intent of producing a fruitful dialogue, we pose questions concerning the properties of proofs and, even more pressing, invite questions similar to those this article answers. (shrink)

As with mathematics, logic is easier to do if its symbols and their rules are better. In a graphic way, the logic symbols introduced in thís paper show their truth-table values, their composite truth-functions, and how to say them as either ?or? or ?if ? then? propositions. Simple rules make the converse, add or remove negations, and resolve propositions.

This essay provides an intuitive technique that illustrates why a conditional must be true when the antecedent is false and the consequent is either true or false. Other techniques for explaining the conditional’s truth table are unsatisfactory.

We can think of functional completeness in systems of propositional logic as a form of expressive completeness: while every logical constant in such system expresses a truth-function of finitely many arguments, functional completeness garantees that every truth-function of finitely many arguments can be expressed with the constants in the system. From this point of view, a functionnaly complete system of propositionnal logic can thus be seen as one where no logical constant is missing. Can a similar question be formulated for (...) quantified first-order logics ? How to make sense of the question whether, e.g., ordinary first-order logic is "functionaly" complete or have no logical constant missing ? In this note, we build on a suggestive proposal made by Bonnay(2006) and shows that it is equivalent to the criterion that a first-order logic L be functionaly complete if and only if every class of structures closed under L-elementary equivalence is L-elementary. Ordinary first-order logic is not complete in this sense. We raise the question whether any logic can be. -/- . (shrink)

Natural deduction systems were motivated by the desire to define the meaning of each connective by specifying how it is introduced and eliminated from inference. In one sense, this attempt fails, for it is well known that propositional logic rules (however formulated) underdetermine the classical truth tables. Natural deduction rules are too weak to enforce the intended readings of the connectives; they allow non-standard models. Two reactions to this phenomenon appear in the literature. One is to try to restore the (...) standard readings, for example by adopting sequent rules with multiple conclusions. Another is to explore what readings the natural deduction rules do enforce. When the notion of a model of a rule is generalized, it is found that natural deduction rules express “intuitionistic” readings of their connectives. A third approach is presented here. The intuitionistic readings emerge when models of rules are defined globally, but the notion of a local model of a rule is also natural. Using this benchmark, natural deduction rules enforce exactly the classical readings of the connectives, while this is not true of axiomatic systems. This vindicates the historical motivation for natural deduction rules. One odd consequence of using the local model benchmark is that some systems of propositional logic are not complete for the semantics that their rules express. Parallels are drawn with incompleteness results in modal logic to help make sense of this. (shrink)

Claims that necessary and sufficient conditions are not converse relations are discussed, as well as the related claim that If A, then B is not equivalent to A only if B . The analysis of alleged counterexamples has shown, among other things, how necessary and sufficient conditions should be understood, especially in the case of causal conditions, and the importance of distinguishing sufficient-cause conditionals from necessary-cause conditionals. It is concluded that necessary and sufficient conditions, adequately interpreted, are converse relations in (...) all cases. (shrink)

The approach used by Boole in Mathematical analysis of logic to develop propositional logic was based on the idea of ?cases? or ?conjunctures of circumstances?. But this was dropped in Laws of thought in favor of one which Boole considered to be more satisfactory, that of using the notion of ?time for which a proposition is true?. We show that, when suitable clarifications and corrections are made, the earlier approach? which accords with modern logic in eschewing the extraneous notion of (...) time?is indeed a viable one. (shrink)

Intuitionists and classical logicians use in common a large number of the logical axioms, even though they supposedly mean different things by the logical connectives and quantifiers — conquans for short. But Wittgenstein says The meaning of a word is its use in the language. We prove that in a definite sense the intuitionistic axioms do indeed characterize the logical conquans, both for the intuitionist and the classical logician.

This is a basic logic text for first-time logic students. Custom-made texts from the chapters is an option as well. And there is a website to go with text too: http://www.poweroflogic.com/cgi/menu.cgi .

The interplay of introduction and elimination rules for propositional connectives is often seen as suggesting a distinguished role for intuitionistic logic. We prove three formal results concerning intuitionistic propositional logic that bear on that perspective, and discuss their significance. First, for a range of connectives including both negation and the falsum, there are no classically or intuitionistically correct introduction rules. Second, irrespective of the choice of negation or the falsum as a primitive connective, classical and intuitionistic consequence satisfy exactly the (...) same structural, introduction, and elimination (briefly, elementary) rules. Third, for falsum as primitive only, intuitionistic consequence is the least consequence relation that satisfies all classically correct elementary rules. (shrink)

Classical logic rests on the assumption that there are two mutually exclusive and jointly exhaustive truth values. This assumption has always been surrounded by philosophical controversy. Doubts have been raised about its legitimacy, and hence about the legitimacy of classical logic. Usually, the assumption is stated in the form of a general principle, namely the principle that every proposition is either true or false. Then, the philosophical controversy is often framed in terms of the question whether every proposition is either (...) true or false. The main purpose of the paper is to show that there is something wrong in this way of putting things. The point is that the common way of understanding the controversial assumption is misconceived, as it rests on a wrong picture of propositions. In the first part of the paper I outline this picture and I argue against it. In the second part I sketch a different picture of propositions and I suggest how this leads to conceive the issue of classical logic in different terms. (shrink)

We present a system of relational syllogistic, based on classical propositional logic, having primitives of the following form: $$\begin{array}{ll}\mathbf{Some}\, a \,{\rm are} \,R-{\rm related}\, {\rm to}\, \mathbf{some} \,b;\\ \mathbf{Some}\, a \,{\rm are}\,R-{\rm related}\, {\rm to}\, \mathbf{all}\, b;\\ \mathbf{All}\, a\, {\rm are}\,R-{\rm related}\, {\rm to}\, \mathbf{some}\, b;\\ \mathbf{All}\, a\, {\rm are}\,R-{\rm related}\, {\rm to}\, \mathbf{all} \,b.\end{array}$$ Such primitives formalize sentences from natural language like ‘ All students read some textbooks’. Here a, b denote arbitrary sets (of objects), and R denotes an (...) arbitrary binary relation between objects. The language of the logic contains only variables denoting sets, determining the class of set terms, and variables denoting binary relations between objects, determining the class of relational terms. Both classes of terms are closed under the standard Boolean operations. The set of relational terms is also closed under taking the converse of a relation. The results of the paper are the completeness theorem with respect to the intended semantics and the computational complexity of the satisfiability problem. (shrink)

A defense of material implication as implication.

Three chapters contain the results independent of each other. In the first chapter I present a set of axioms for the propositional calculus which are shorter than the ones known so far, in the second one I give a method of defining all ternary connectives, in the third one, I prove that the probability of propositional functions is preserved under reversible substitutions.

This is a comprehensive study of the English word 'or', and the logical operators variously proposed to present its meaning. Although there are indisputably disjunctive uses of or in English, it is a mistake to suppose that logical disjunction represents its core meaning. 'Or' is descended from the Anglo-Saxon word meaning second, a form which survives in such expressions as "every other day." Its disjunctive uses arise through metalinguistic applications of an intermediate adverbial meaning which is conjunctive rather than disjunctive (...) in character. These conjunctive uses have puzzled philosophers and logicians, and have been discussed extensively under such headings as "free choice permission." This study examines the textbook myths that have clouded our understanding of how or and other "logical" vocabulary comes to have something approaching its logical meaning in natural languages. It considers the various historical conceptions of disjunction and its place in logic from the Stoics to the present day. (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)

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.