This paper studies a propositional logic which is obtained by interpreting implication as formal provability. It is also the logic of finite irreflexive Kripke Models.A Kripke Model completeness theorem is given and several completeness theorems for interpretations into Provability Logic and Peano Arithmetic.

Ken López-Escobar questions the timeless status of various entities—propositions, numbers, etc.—as well as my characterization of pure propositional logic as an ontological theory. In my response I argue that my characterization of propositional logic does not depend on timeless propositions, or on other abstract truth bearers, but is a characterization in terms of truth relations between any truth bearers. I also discuss his views on numbers as cultural constructs, as well as his use of quantification in (...) propositional logic.Ken López-Escobar questiona o estatuto atemporal de vários entes—pro-posições, números, etc.— assim como minha caracterização da lógica proposicional pura como teoria ontológica. Na réplica argumento que minha caracterização não depende de proposições atemporais, ou de outros portadores de verdade abstratos, mas é uma caracterização em termos de relações de verdade entre quaisquer portadores de verdade. Examino também suas considerações sobre números como construtos culturais, assim como seu uso de quantificação na lógica proposicional. (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)

Intuitionistic propositional logic with Galois negations ( \(\mathsf {IGN}\) ) is introduced. Heyting algebras with Galois negations are obtained from Heyting algebras by adding the Galois pair \((\lnot,{\sim })\) and dual Galois pair \((\dot{\lnot },\dot{\sim })\) of negations. Discrete duality between GN-frames and algebras as well as the relational semantics for \(\mathsf {IGN}\) are developed. A Hilbert-style axiomatic system \(\mathsf {HN}\) is given for \(\mathsf {IGN}\), and Galois negation logics are defined as extensions of \(\mathsf {IGN}\). We give (...) the bi-tense logic \(\mathsf {S4N}_t\) which is obtained from the minimal tense extension of the modal logic \(\mathsf {S4}\) by adding tense operators. We give a new extended Gödel translation \(\tau \) and prove that \(\mathsf {IGN}\) is embedded into \(\mathsf {S4N}_t\) by \(\tau \). Moreover, every Kripke-complete Galois negation logic _L_ is embedded into its tense companion \(\tau (L)\). (shrink)

I will show that the semantic structure of a new imperfect-information propositional logic can be described in terms of extensive forms of semantic games. I will discuss some ensuing properties of these games such as imperfect recall, informational consistency, and team playing. Finally, I will suggest a couple of applications that arise in physics, and most notably in quantum theory and quantum logics.

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)

A propositional framework of formal reasoning is proposed, which emphasises the pattern of entering and exiting context. Contexts are modelled by an algebraic structure which reflects the order and manner in which context is entered into and exited from.The equations of the algebra partitions context terms into equivalence classes. A formal semantics is defined, containing models that map equivalence classes of certain context terms to sets of interpretations of the formula language. The corresponding Hilbert system incorporates the algebraic equations (...) as axioms asserted in context.In semigroups of contexts, where combination of contexts is associative, finite ground algebraic equations correspond to contingent equivalence between certain logical formulas. Systems for sets and multisets of contexts are obtained by presenting their respective algebras as associativity plus finite ground equations. Soundness and completeness results are proved.Some contextual reasoning systems in the literature are inherently associative, and we present those as special cases. (shrink)

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 paper presents a propositional version of Kit Fine's (quantified) logic for essentialist statements, provides it with a semantics, and proves the former adequate (i.e. sound and complete) with respect to the latter.

This presentation of a system of propositional logic is a foundational paper for systems of illocutionary logic. The language contains the illocutionary force operators '' for assertion and ' ' for supposition. Sentences occurring in proofs of the deductive system must be prefixed with one of these operators, and rules of take account of the forces of the sentences. Two kinds of semantic conditions are investigated; familiar truth conditions and commitment conditions. Accepting a statement A or rejecting (...) A commits a person to accepting some statements (the symbol '' marks this value), to rejecting some statements (), and will leave the person uncommitted with respect to others (). Commitment valuations assign the values to sentences of ; such a valuation is conceived as reflecting the beliefs/knowledge of a particular person. This paper explores the relations between truth conditions and commitment conditions, and between semantic concepts defined in terms of these conditions. (shrink)

Propositional logic, with the aid of SAT solvers, has become capable of solving a range of important and complicated problems. Expanding this range, to contain additional varieties of problems, is subject to the complexity resulting from encoding counting constraints in conjunctive normal form. Due to the limitation of the expressive power of propositional logic, generally, such an encoding increases the numbers of variables and clauses excessively. This work eliminates the indicated drawback by interpolating constraint symbols and (...) the set of natural numbers \ into the alphabet of propositional logic and adjusting the underlying language accordingly. In the extended logic counting constraints are naturally formulated, while many important aspects, such as Boolean nature and the soundness and completeness theorems, are kept preserved. (shrink)

In this work, an intuitionistic propositional logic with a Galois connection is introduced. In addition to the intuitionistic logic axioms and inference rule of modus ponens, the logic contains only two rules of inference mimicking the performance of Galois connections. Both Kripke-style and algebraic semantics are presented for IntGC, and IntGC is proved to be complete with respect to both of these semantics. We show that IntGC has the finite model property and is decidable, but Glivenko's (...) Theorem does not hold. Duality between algebraic and Kripke semantics is presented, and a representation theorem for Heyting algebras with Galois connections is proved. In addition, an application to rough L-valued sets is presented. (shrink)

There is an exponential speed-up in the number of lines of the quantified propositional sequent calculus over Substitution Frege Systems, if one considers proofs as trees. Whether this is true also for the number of symbols, is still an open problem.

ABSTRACT: This paper collects the evidence in Ammonius' surviving works for elements of a propositional logic, coming to the conclusion that Ammonius had a theory of hypothetical syllogisms in the tradition of Aristotle and the Peripatetics, with Platonic elements mixed in, and using some Stoic elements, but not a propositional logic in the narrower sense as we find it in Stoic logic.

In this paper a formalized logic of propositions, PA1, is presented. It is proven consistent and its relationships to traditional logic, to PM ([15]), to subjunctive (including contrary-to-fact) implication and to the “paradoxes” of material and strict implication are developed. Apart from any intrinsic merit it possesses, its chief significance lies in demonstrating the feasibility of a general logic containing theprinciple of subjunctive contrariety, i.e., the principle that ‘Ifpwere true thenqwould be true’ and ‘Ifpwere true thenqwould be (...) false’ are incompatible. (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)

We give a procedure for counting the number of different proofs of a formula in various sorts of propositional logic. This number is either an integer (that may be 0 if the formula is not provable) or infinite.

This account of propositional logic concentrates on the algorithmic translation of important methods, especially of decision procedures for (subclasses of) propositional logic. Important classical results and a series of new results taken from the fields of normal forms, satisfiability and deduction methods are arranged in a uniform and complete theoretic framework. The algorithms presented can be applied to VLSI design, deductive databases and other areas. After introducing the subject the authors discuss satisfiability problems and satisfiability algorithms (...) with complexity considerations, the resolution calculus with different refinements, and special features and procedures for Horn formulas. Then, a selection of further calculi and some results on the complexity of proof procedures are presented. The last chapter is devoted to quantified boolean formulas. The algorithmic approach will make this book attractive to computer scientists and graduate students in areas such as automated reasoning, logic programming, complexity theory and pure and applied logic. (shrink)

The present paper contains some technical results on a many-valued logic with truth values from the interval of real numbers [0; 1]. This logic, discussed originally in [1], latter in [2] and [3], was called the logic of fuzzy concepts. Our aim is to give an algebraic axiomatics for fuzzy propositional logic. For this purpose the variety of L-algebras with signature en- riched with a unary operation { involution is stud- ied. A one-to-one correspondence between (...) congruences on an LI-algebra and lters of a special kind is used to prove the representation theorem for LI-algebras. By this theorem every LI-algebra is isomorphic to a subdirect product of chains. The full characteristic of the subdirectly irreducible LI-algebras is given . It turns out that the variety of all L-algebras, as well as any of its subvarieties, is generated by its nite algebras. (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)

In Logical Forms Part II, Chateaubriand begins the Chapter on “Propositional Logic” by considering the reading of the ‘conditional’ by ‘implies’; in fact he states that:There is a confusion, as a matter of fact, and it runs deep, but it is a confusion in propositional logic itself, and the mathematician’s reading is a rather sensible one.After a careful, erudite analysis of various philosophical viewpoints of logic, Chateaubriand comes to the conclusion that:Pure propositional logic, (...) as just characterized, belongs to ontological logic, and it does not include a theory of deduction as a human activity. This is a part of epistemological logic, and is more closely connected to the applications of pure propositional logic.An implicit assumption in Chateaubriand’s reasoning appears to be that propositions have a timeless status. I will present arguments for the opposite viewpoint which leads to an analysis of Propositional Logic not covered under Chateaubriand’s monograph and perhaps resolves some conflicts therein; much as the conflict between the Intuitionist and Classical Mathematician on whether every function on the Reals is continuous is resolved by the realization that they are talking about different “entities”.Em Logical Forms II, Chateaubriand inicia o capítulo “Lógica Proposi-cional” considerando a leitura do ‘condicional’ como ‘implica’. De fato, ele diz o seguinte:Na verdade, existe uma confusão, e ela é profunda, mas é uma confusão na lógica proposicional ela mesma, e a leitura de um matemático é bastante sensível.Depois de uma análise cuidadosa e erudita dos vários pontos de vista filosóficos da lógica , Chateaubriand chega à conclusão que:A lógica proposicional pura, tal como aqui caracterizada, pertence à lógica ontológica, e não inclui uma teoria da dedução como atividade humana. Isto é parte da lógica epistemológica, e é mais intimamente conectada às aplicações da lógica proposicional.Uma premissa implícita no raciocínio de Chateaubriand parece ser a de que proposições têm um estatuto atemporal. Eu argumentarei em favor da visão oposta, que leva a uma análise da Lógica Proposicional não abordada no texto de Chateaubriand e que talvez resolva alguns conflitos. Muito do conflito entre Intuicionistas e Matemáticos Clássicos sobre se toda função sobre os números reais é contínua é resolvido pela compreensão de que eles estão falando de “entidades” diferentes. (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)

The text of the treatise “The Propositional Logic of Boethius” was finished in 1939. Prof. Jan Lukasiewicz wished at that time to issue it in the second volume of “Collectanea Logica”; as a result of political events, he was not able to carry out his plan. In 1938, I published an article in “Erkenntnis” entitled “AUS- sagenlogik im Mittelalter”; this article included the contents of a paper which I read to the International Congress for the Unity of Science (...) in Cambridge, England, in 1938 (Cf. Erkenntnis, vol. 7, pp. 160-168). The subject matter of this paper touched upon that of the above-mentioned treatise. Recently an article of Mr. Rend van den Driessche, “Sur le ‘de syllogismo hypothetico’ de Boece”, was published in the journal “methodos” (vol. I, no. 3). Mr. van den Driessche referred in this article to the article on propositional logic in the middle ages, which had appeared in “Erkenntnis”. This reminded me of my yet-unpublished treatise on the propositional logic of Boethius. (shrink)

In this note we compare propositional logics for closed substitutions and propositional logics for open substitutions in constructive arithmetical theories. We provide a strong example where these logics diverge in an essential way. We prove that for Markov's Arithmetic, that is, Heyting's Arithmetic plus Markov's principle plus Extended Church's Thesis, the logic of closed and the logic of open substitutions are the same.

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 logic with (...) a relevant logic that has all classical theorems as theorems. (shrink)

The main purpose of this work is to provide an English translation of and commentary on a recently published Arabic text dealing with con ditional propositions and syllogisms. The text is that of A vicenna (Abu represents his views on the subject as they were held throughout his life.

A new theoretical approach to Aristotelian Logic based on three axioms has been recently introduced. This formalization of the theory allowed for the unification of its uncommunicated traditional branches, thus restoring the theoretical unity of AL. In this brief paper, the applicability of the three AL axioms to Propositional Logic is explored. First, it is shown how the AL axioms can be applied to some simple PL arguments in a straightforward manner. Second, the development of a proof (...) method for PL inspired by the AL axioms is presented. This method mimics the underlying mechanics of the proof method from AL, and offers a complementary alternative to proof methods such as truth trees. (shrink)

The paper introduces a semantics for the language of propositional additive-multiplicative linear logic. It understands formulas as tasks that are to be accomplished by an agent (machine, robot) working as a slave for its master (user, environment). This semantics can claim to be a formalization of the resource philosophy associated with linear logic when resources are understood as agents accomplishing tasks. I axiomatically define a decidable logic TSKp and prove its soundness and completeness with respect to (...) the task semantics in the following intuitive sense: iff can be accomplished by an agent who has nothing but its intelligence (that is, no physical resources or external sources of information) for accomplishing tasks. (shrink)

We study partiality in propositional logics containing formulas with either undefined or over-defined truth-values. Undefined values are created by adding a four-place connective W termed transjunction to complete models which, together with the usual Boolean connectives is shown to be functionally complete for all partial functions. Transjunction is seen to be motivated from a game-theoretic perspective, emerging from a two-stage extensive form semantic game of imperfect information between two players. This game-theoretic approach yields an interpretation where partiality is generated (...) as a property of non-determinacy of games. Over-defined values are produced by adding a weak, contradictory negation or, alternatively, by relaxing the assumption that games are strictly competitive. In general, particular forms of extensive imperfect information games give rise to a generalised propositional logic where various forms of informational dependencies and independencies of connectives can be studied. (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.

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

This paper deals with various substructural propositional logics, in particular with substructural subsystems of Nelson's constructive propositional logics N– and N. Doen's groupoid semantics is extended to these constructive systems and is provided with an informational interpretation in terms of information pieces and operations on information pieces.

Prawitz proposed certain notions of proof-theoretic validity and conjectured that intuitionistic logic is complete for them [11, 12]. Considering propositional logic, we present a general framework of five abstract conditions which any proof-theoretic semantics should obey. Then we formulate several more specific conditions under which the intuitionistic propositional calculus turns out to be semantically incomplete. Here a crucial role is played by the generalized disjunction principle. Turning to concrete semantics, we show that prominent proposals, including Prawitz’s, (...) satisfy at least one of these conditions, thus rendering IPC semantically incomplete for them. Only for Goldfarb’s [1] proof-theoretic semantics, which deviates from standard approaches, IPC turns out to be complete. Overall, these results show that basic ideas of proof-theoretic semantics for propositional logic are not captured by IPC. (shrink)

In this paper I discuss card games designed to supplement or replace exercise sets on derivability and entailment in propositional logic. I present rules for two propositional logic card games that introduce chance and competition into discussions of propositional logic. The latter sections provide brief practical and theoretical notes on this kind of game, including ways courses that use these games can be more effective than courses that do not.

We conducted a computer-based psychological experiment in which a random mix of 40 tautologies and 40 non-tautologies were presented to the participants, who were asked to determine which ones of the formulas were tautologies. The participants were eight university students in computer science who had received tuition in propositional logic. The formulas appeared one by one, a time-limit of 45 s applied to each formula and no aids were allowed. For each formula we recorded the proportion of the (...) participants who classified the formula correctly before timeout and the mean response time among those participants. We propose a new proof formalism for modeling propositional reasoning with bounded cognitive resources. It models declarative memory, visual memory, working memory, and procedural memory according to the memory model of Atkinson and Shiffrin and reasoning processes according to the model of Newell and Simon. We also define two particular proof systems, T and NT, for showing propositional formulas to be tautologies and non-tautologies, respectively. The accuracy was found to be higher for non-tautologies than for tautologies ( p T was.89 and for non-tautologies the correlation between latency and minimum proof length in NT was.87. (shrink)

We study the non-Fregean propositional logic with propositional quantifiers, denoted by $\mathsf{SCI}_{\mathsf{Q}}$. We prove that $\mathsf{SCI}_{\mathsf{Q}}$ does not have the finite model property and that it is undecidable. We also present examples of how to interpret in $\mathsf{SCI}_{\mathsf{Q}}$ various mathematical theories, such as the theory of groups, rings, and fields, and we characterize the spectra of $\mathsf{SCI}_{\mathsf{Q}}$-sentences. Finally, we present a translation of $\mathsf{SCI}_{\mathsf{Q}}$ into a classical two-sorted first-order logic, and we use the translation to prove (...) some model-theoretic properties of $\mathsf{SCI}_{\mathsf{Q}}$. (shrink)