The method of axiomatic rejection for the intuitionistic propositional logic

We prove that the intuitionistic sentential calculus is -decidable (decidable in the sense of ukasiewicz), i.e. the sets of theses of Int and of rejected formulas are disjoint and their union is equal to all formulas. A formula is rejected iff it is a sentential variable or is obtained from other formulas by means of three rejection rules. One of the rules is original, the remaining two are ukasiewicz's rejection rules: by detachement and by substitution. We extensively use the method of Beth's semantic tableaux.To the memory of Jerzy SupeckiTranslated from the Polish by Jan Zygmunt. Preparation of this paper was supported in part by C.P.B.P. 08-15.     

Double-Negation Elimination in Some Propositional Logics

This article answers two questions (posed in the literature), each concerning the guaranteed existence of proofs free of double negation. A proof is free of double negation if none of its deduced steps contains a term of the formn(n(t)) for some term t, where n denotes negation. The first question asks for conditions on the hypotheses that, if satisfied, guarantee the existence of a double-negation-free proof when the conclusion is free of double negation. The second question asks about the existence of an axiom system for classical propositional calculus whose use, for theorems with a conclusion free of double negation, guarantees the existence of a double-negation-free proof. After giving conditions that answer the first question, we answer the second question by focusing on the Lukasiewicz three-axiom system. We then extend our studies to infinite-valued sentential calculus and to intuitionistic logic and generalize the notion of being double-negation free. The double-negation proofs of interest rely exclusively on the inference rule condensed detachment, a rule that combines modus ponens with an appropriately general rule of substitution. The automated reasoning program Otter played an indispensable role in this study.     

The shortest possible length of the longest implicational axiom

A four-valued matrix is presented which validates all theorems of the implicational fragment, IF, of the classical sentential calculus in which at most two distinct sentence letters occur. The Wajsberg/Diamond-McKinsley Theorem for IF follows as a corollary: every complete set of axioms (with substitution and detachment as rules) must include at least one containing occurrences of three or more distinct sentence letters.Additionally, the matrix validates all IF theses built from nine or fewer occurrences of connectives and letters. So the classic result of Jaskovski for the full sentential calculus —that every complete axiom set must contain either two axioms of length at least nine or else one of length at least eleven—can be improved in the implicational case: every complete axiom set for IF must contain at least one axiom eleven or more characters long.Both results are best possible, and both apply as well to most subsystems of IF, e.g., the implicational fragments of the standard relevance logics, modal logics, the relatives of implicational intutionism, and logics in the ukasiewicz family.Earlier proofs of these results, utilizing a five-valued matrix built from the product matrix of C2 with itself via the method of [8], were obtained in 1988 while the author was a Visiting Research Fellow at the Automated Reasoning Project, Research School of Social Sciences, Australian National University, and were presented in [9]. The author owes thanks to the RSSS for creating the Project, and to the members of the Project generally for the stimulating atmosphere they created in turn, but especially to Robert K. Meyer for making the visit possible, and for many discussions over the years.     

A game-based formal system for Ł∞

A formal system for , based on a game-theoretic analysis of the ukasiewicz prepositional connectives, is defined and proved to be complete. An Herbrand theorem for the predicate calculus (a variant of some work of Mostowski) and some corollaries relating to its axiomatizability are proved. The predicate calculus with equality is also considered.     

On Łukasiewicz's Four-Valued Modal Logic

ukasiewicz's four-valued modal logic is surveyed and analyzed, together with ukasiewicz's motivations to develop it. A faithful interpretation of it in classical (non-modal) two-valued logic is presented, and some consequences are drawn concerning its classification and its algebraic behaviour. Some counter-intuitive aspects of this logic are discussed in the light of the presented results, ukasiewicz's own texts, and related literature.     

Proper n-valued Łukasiewicz algebras as S-algebras of Łukasiewicz n-valued prepositional calculi

Proper n-valued ukasiewicz algebras are obtained by adding some binary operators, fulfilling some simple equations, to the fundamental operations of n-valued ukasiewicz algebras. They are the s-algebras corresponding to an axiomatization of ukasiewicz n-valued propositional calculus that is an extention of the intuitionistic calculus.Dedicated to the memory of Gregorius C. Moisil     

Automated theorem proving for Łukasiewicz logics

This paper is concerned with decision proceedures for the ₀-valued ukasiewicz logics,. It is shown how linear algebra can be used to construct an automated theorem checker. Two decision proceedures are described which depend on a linear programming package. An algorithm is given for the verification of consequence relations in, and a connection is made between theorem checking in two-valued logic and theorem checking in which implies that determing of a -free formula whether it takes the value one is NP-complete problem.     

The completeness of the factor semantics for Łukasiewicz's infinite-valued logics

In [12] it was shown that the factor semantics based on the notion ofT-F-sequences is a correct model of the ukasiewicz's infinite-valued logics. But we could not consider some important aspects of the structure of this model because of the short size of paper. In this paper we give a more complete study of this problem: A new proof of the completeness of the factor semantic for ukasiewicz's logic using Wajsberg algebras [3] (and not MV-algebras in [1]) and Symmetrical Heyting monoids [7] is proposed. Some consequences of such an approach are investigated.     

Averaging the truth-value in Łukasiewicz logic

Chang's MV algebras are the algebras of the infinite-valued sentential calculus of ukasiewicz. We introduce finitely additive measures (called states) on MV algebras with the intent of capturing the notion of average degree of truth of a proposition. Since Boolean algebras coincide with idempotent MV algebras, states yield a generalization of finitely additive measures. Since MV algebras stand to Boolean algebras as AFC*-algebras stand to commutative AFC*-algebras, states are naturally related to noncommutativeC*-algebraic measures.     

Complete and atomic algebras of the infinite valued Łukasiewicz logic

The infinite-valued logic of ukasiewicz was originally defined by means of an infinite-valued matrix. ukasiewicz took special forms of negation and implication as basic connectives and proposed an axiom system that he conjectured would be sufficient to derive the valid formulas of the logic; this was eventually verified by M. Wajsberg. The algebraic counterparts of this logic have become know as Wajsberg algebras. In this paper we show that a Wajsberg algebra is complete and atomic (as a lattice) if and only if it is a direct product of finite Wajsberg chains. The classical characterization of complete and atomic Boolean algebras as fields of sets is a particular case of this result.This research was partially supported by the Consejo Nacional Investigaciones Científicas y Técnicas de la República Argentina (CONICET).     

Construction of monadic three-valued Łukasiewicz algebras

The notion of monadic three-valued ukasiewicz algebras was introduced by L. Monteiro ([12], [14]) as a generalization of monadic Boolean algebras. A. Monteiro ([9], [10]) and later L. Monteiro and L. Gonzalez Coppola [17] obtained a method for the construction of a three-valued ukasiewicz algebra from a monadic Boolea algebra. In this note we give the construction of a monadic three-valued ukasiewicz algebra from a Boolean algebra B where we have defined two quantification operations and ^* such that ^*x=^*x (where ^*x=-^*-x). In this case we shall say that and ^* commutes. If B is finite and is an existential quantifier over B, we shall show how to obtain all the existential quantifiers ^* which commute with .Taking into account R. Mayet [3] we also construct a monadic three-valued ukasiewicz algebra from a monadic Boolean algebra B and a monadic ideal I of B. The most essential results of the present paper will be submitted to the XXXIX Annual Meeting of the Unión Matemática Argentina (October 1989, Rosario, Argentina).     

Three-valued Logic,Indeterminacy and Quantum Mechanics

The paper consists of two parts. The first part begins with the problem of whether the original three-valued calculus, invented by J. ukasiewicz, really conforms to his philosophical and semantic intuitions. I claim that one of the basic semantic assumptions underlying ukasiewicz's three-valued logic should be that if under any possible circumstances a sentence of the form X will be the case at time t is true (resp. false) at time t, then this sentence must be already true (resp. false) at present. However, it is easy to see that this principle is violated in ukasiewicz's original calculus (as the cases of the law of excluded middle and the law of contradiction show). Nevertheless it is possible to construct (either with the help of the notion of supervaluation, or purely algebraically) a different three-valued, semi-classical sentential calculus, which would properly incorporate ukasiewicz's initial intuitions. Algebraically, this calculus has the ordinary Boolean structure, and therefore it retains all classically valid formulas. Yet because possible valuations are no longer represented by ultrafilters, but by filters (not necessarily maximal), the new calculus displays certain non-classical metalogical features (like, for example, non-extensionality and the lack of the metalogical rule enabling one to derive p is true or q is true from pqq is true).The second part analyses whether the proposed calculus could be useful in formalizing inferences in situations, when for some reason (epistemological or ontological) our knowledge of certain facts is subject to limitation. Special attention should be paid to the possibility of employing this calculus to the case of quantum mechanics. I am going to compare it with standard non-Boolean quantum logic (in the Jauch–Piron approach), and to show that certain shortcomings of the latter can be avoided in the former. For example, I will argue that in order to properly account for quantum features of microphysics, we do not need to drop the law of distributivity. Also the idea of reading off the logical structure of propositions from the structure of Hilbert space leads to some conceptual troubles, which I am going to point out. The thesis of the paper is that all we need to speak about quantum reality can be acquired by dropping the principle of bivalence and extensionality, while accepting all classically valid formulas.     

Inferential Intensionality

The paper is a study of properties of quasi-consequence operation which is a key notion of the so-called inferential approach in the theory of sentential calculi established in [5]. The principal motivation behind the quasi-consequence, q-consequence for short, stems from the mathematical practice which treats some auxiliary assumptions as mere hypotheses rather than axioms and their further occurrence in place of conclusions may be justified or not. The main semantic feature of the q-consequence reflecting the idea is that its rules lead from the non-rejected assumptions to the accepted conclusions.First, we focus on the syntactic features of the framework and present the q-consequence as related to the notion of proof. Such a presentation uncovers the reasons for which the adjective inferential is used to characterize the approach and, possibly, the term inference operation replaces q-consequence. It also shows that the inferential approach is a generalisation of the Tarski setting and, therefore, it may potentially absorb several concepts from the theory of sentential calculi, cf. [10]. However, as some concrete applications show, see e.g.[4], the new approach opens perspectives for further exploration.The main part of the paper is devoted to some notions absent, in Tarski approach. We show that for a given q-consequence operation W instead of one W-equivalence established by the properties of W we may consider two congruence relations. For one of them the current name is kept preserved and for the other the term W-equality is adopted. While the two relations coincide for any W which is a consequence operation, for an arbitrary W the inferential equality and the inferential equivalence may differ. Further to this we introduce the concepts of inferential extensionality and intensionality for q-consequence operations and connectives. Some general results obtained in Section 2 sufficiently confirm the importance of these notions. To complete a view, in Section 4 we apply the new intensionality-extensionality distinction to inferential extensions of a version of the ukasiewicz four valued modal logic.     

TPS: A hybrid automatic-interactive system for developing proofs

The theorem proving system Tps provides support for constructing proofs using a mix of automation and user interaction, and for manipulating and inspecting proofs. Its library facilities allow the user to store and organize work. Mathematical theorems can be expressed very naturally in Tps using higher-order logic. A number of proof representations are available in Tps, so proofs can be inspected from various perspectives.     

Paraconsistent logic and model theory

The object of this paper is to show how one is able to construct a paraconsistent theory of models that reflects much of the classical one. In other words the aim is to demonstrate that there is a very smooth and natural transition from the model theory of classical logic to that of certain categories of paraconsistent logic. To this end we take an extension of da Costa'sC ₁ ⁼ (obtained by adding the axiom A A) and prove for it results which correspond to many major classical model theories, taken from Shoenfield [5]. In particular we prove counterparts of the theorems of o-Tarski and Chang-o-Suszko, Craig-Robinson and the Beth definability theorem.     

Characterization of prime numbers in Łukasiewicz's logical matrix

In this paper we define n+1-valued matrix logic K_n+1 whose class of tautologies is non-empty iff n is a prime number. This result amounts to a new definition of a prime number. We prove that if n is prime, then the functional properties of K_n+1 are the same as those of ukasiewicz's n +1-valued matrix logic _n+1. In an indirect way, the proof we provide reflects the complexity of the distribution of prime numbers in the natural series. Further, we introduce a generalization K _n+1 ^* of K_n+1 such that the set of tautologies of K_n+1 is not empty iff n is of the form p , where p is prime and is natural. Also in this case we prove the equivalence of functional properties of the introduced logic and those of _n+1. In the concluding part, we discuss briefly a partition of the natural series into equivalence classes such that each class contains exactly one prime number. We conjecture that for each prime number the corresponding equivalence class is finite.To the memory of Jerzy Supecki     

Condensed detachment as a rule of inference

Condensed detachment is usually regarded as a notation, and defined by example. In this paper it is regarded as a rule of inference, and rigorously defined with the help of the Unification Theorem of J. A. Robinson. Historically, however, the invention of condensed detachment by C. A. Meredith preceded Robinson's studies of unification. It is argued that Meredith's ideas deserve recognition in the history of unification, and the possibility that Meredith was influenced, through ukasiewicz, by ideas of Tarski going back at least to 1939, and possibly to 1930 or earlier, is discussed. It is proved that a term is derivable by substitution and ordinary detachment from given axioms if and only if it is a substitution instance of a term which is derivable from these axioms by condensed detachment, and it is shown how this theorem enables the ideas of ukasiewicz and Tarski mentioned above to be formalized and extended. Finally, it is shown how condensed detachment may be subsumed within the resolution principle of J. A. Robinson, and several computer studies of particular Hilbert-type propositional calculi using programs based on condensed detachment or on resolution are briefly discussed.     

An extension of the Łukasiewicz logic to the modal logic of quantum mechanics

An attempt is made to include the axioms of Mackey for probabilities of experiments in quantum mechanics into the calculus _x0 of ukasiewicz. The obtained calculusQ contains an additional modal signQ and four modal rules of inference. The propositionQx is read x is confirmed. The most specific rule of inference may be read: for comparable observations implication is equivalent to confirmation of material implication.The semantic truth ofQ is established by the interpretation with the help of physical objects obeying to the rules of quantum mechanics. The embedding of the usual quantum propositional logic inQ is accomplished.Allatum est die 9 Junii 1976