On the degree of complexity of sentential logics.II. An example of the logic with semi-negation

In this paper being a sequel to our [1] the logic with semi-negation is chosen as an example to elucidate some basic notions of the semantics for sentential calculi. E.g., there are shown some links between the Post number and the degree of complexity of a sentential logic, and it is proved that the degree of complexity of the sentential logic with semi-negation is 20. This is the first known example of a logic with such a degree of complexity. The results of the final part of the paper cast a new light on the scope of the Kripke-style semantics in comparison to the matrix semantics.In memory of Roman Suszko     

On S

The sentential logic S extends classical logic by an implication-like connective. The logic was first presented by Chellas as the smallest system modelled by contraining the Stalnaker-Lewis semantics for counterfactual conditionals such that the conditional is effectively evaluated as in the ternary relations semantics for relevant logics. The resulting logic occupies a key position among modal and substructural logics. We prove completeness results and study conditions for proceeding from one family of logics to another.We are grateful to Peter Apostoli, Kosta Doen, and anonymous referees for their comments on an earlier version of this paper. A.F.'s work has been supported by a grant from the Volkswagen-Stiftung.Presented byJan Zygmunt     

Constructing a continuum of predicate extensions of each intermediate propositional logic

Wajsberg and Jankov provided us with methods of constructing a continuum of logics. However, their methods are not suitable for super-intuitionistic and modal predicate logics. The aim of this paper is to present simple ways of modification of their methods appropriate for such logics. We give some concrete applications as generic examples. Among others, we show that there is a continuum of logics (1) between the intuitionistic predicate logic and the logic of constant domains, (2) between a predicate extension ofS4 andS4 with the Barcan formula. Furthermore, we prove that (3) there is a continuum of predicate logics with equality whose equality-free fragment is just the intuitionistic predicate logic.Dedicated to the memory of the late Professor S. MaeharaThis research was supported in part by Grant-in Aid for Encouragement of Young Scientists No. 06740140, Ministry of Education, Science and Culture, Japan.Presented byHiroakira Ono     

On two problems of Harvey Friedman

The paper considers certain properties of intermediate and moda propositional logics.The first part contains a proof of the theorem stating that each intermediate logic is closed under the Kreisel-Putnam rule xyz/(xy)(xz).The second part includes a proof of the theorem ensuring existence of a greatest structurally complete intermediate logic having the disjunction property. This theorem confirms H. Friedman's conjecture 41 (cf. [2], problem 41).In the third part the reader will find a criterion which allows us to obtain sets satisfying the conditions of Friedman's problem 42, on the basis of intermediate logics satisfying the conditions of problem 41.Finally, the fourth part contains a proof of a criterion which allows us to obtain modal logics endowed with Hallden's property on the basis of structurally complete intermediate logics having the disjunction property.Dedicated to Professor Roman SuszkoThe author would like to thank professors J. Perzanowski and A. Wroski for valuable suggestions.     

An axiomatization of the modal theory of the veiled recession frame

The veiled recession frame has served several times in the literature to provide examples of modal logics failing to have certain desirable properties. Makinson [4] was the first to use it in his presentation of a modal logic without the finite model property. Thomason [5] constructed a (rather complicated) logic whose Kripke frames have an accessibility relation which is reflexive and transitive, but which is satisfied by the (non-transitive) veiled recession frame, and hence incomplete. In Van Benthem [2] the frame was an essential tool to find simple examples of incomplete logics, axiomatized by a formula in two proposition letters of degree 2, or by a formula in one proposition letter of degree 4 (the degree of a modal formula is the maximal number of nested occurrences of the necessity operator in ). In [3] we showed that the modal logic determined by the veiled recession frame is incomplete, and besides that, is an immediate predecessor of classical logic (or, more precisely, the modal logic axiomatized by the formula pp), and hence is a logic, maximal among the incomplete ones. Considering the importance of the modal logic determined by the veiled recession frame, it seems worthwhile to ask for an axiomatization, and in particular, to answer the question if it is finitely axiomatizable. In the present paper we find a finite axiomatization of the logic, and in fact, a rather simple one consisting of formulas in at most two proposition letters and of degree at most three.The paper was written with support of the Netherlands organization for the Advancement of Pure Research (Z.W.O.).     

Syntactic features and synonymy relations: a unified treatment of some proofs of the compactness and interpolation theorems

This paper introduces the notion of syntactic feature to provide a unified treatment of earlier model theoretic proofs of both the compactness and interpolation theorems for a variety of two valued logics including sentential logic, first order logic, and a family of modal sentential logic includingM,B,S ₄ andS ₅. The compactness papers focused on providing a proof of the consequence formulation which exhibited the appropriate finite subset. A unified presentation of these proofs is given by isolating their essential feature and presenting it as an abstract principle about syntactic features. The interpolation papers focused on exhibiting the interpolant. A unified presentation of these proofs is given by isolating their essential feature and presenting it as a second abstract principle about syntactic features. This second principle reduces the problem of exhibiting the interpolant to that of establishing the existence of a family of syntactic features satisfying certain conditions. The existence of such features is established for a variety of logics (including those mentioned above) by purely combinatorial arguments.Presented byMelvin Fitting     

ExpTime Tableau Decision Procedures for Regular Grammar Logics with Converse

Grammar logics were introduced by Fariñas del Cerro and Penttonen in 1988 and have been widely studied. In this paper we consider regular grammar logics with converse (REG ^c logics) and present sound and complete tableau calculi for the general satisfiability problem of REG ^c logics and the problem of checking consistency of an ABox w.r.t. a TBox in a REG ^c logic. Using our calculi we develop ExpTime (optimal) tableau decision procedures for the mentioned problems, to which various optimization techniques can be applied. We also prove a new result that the data complexity of the instance checking problem in REG ^c logics is coNP-complete.     

Extension Properties and Subdirect Representation in Abstract Algebraic Logic

This paper continues the investigation, started in Lávi?ka and Noguera (Stud Log 105(3): 521–551, 2017), of infinitary propositional logics from the perspective of their algebraic completeness and filter extension properties in abstract algebraic logic. If follows from the Lindenbaum Lemma used in standard proofs of algebraic completeness that, in every finitary logic, (completely) intersection-prime theories form a basis of the closure system of all theories. In this article we consider the open problem of whether these properties can be transferred to lattices of filters over arbitrary algebras of the logic. We show that in general the answer is negative, obtaining a richer hierarchy of pairwise different classes of infinitary logics that we separate with natural examples. As by-products we obtain a characterization of subdirect representation for arbitrary logics, develop a fruitful new notion of natural expansion, and contribute to the understanding of semilinear logics.     

Algebraic aspects of deduction theorems

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.A part of this paper was presented in abstracted form in Bulletin of the Section of Logic, Vol. 12, No. 3 (1983), pp. 111–116, and in The Journal of Symbolic Logic.     

The Classification of Propositional Calculi

We discuss Smirnovs problem of finding a common background for classifying implicational logics. We formulate and solve the problem of extending, in an appropriate way, an implicational fragment H of the intuitionistic propositional logic to an implicational fragment TV of the classical propositional logic. As a result we obtain logical constructions having the form of Boolean lattices whose elements are implicational logics. In this way, whole classes of new logics can be obtained. We also consider the transition from implicational logics to full logics. On the base of the lattices constructed, we formulate the main classification principles for propositional logics.     

On Gentzen Relations Associated with Finite-valued Logics Preserving Degrees of Truth

When considering m-sequents, it is always possible to obtain an m-sequent calculus VL for every m-valued logic (defined from an arbitrary finite algebra L of cardinality m) following for instance the works of the Vienna Group for Multiple-valued Logics. The Gentzen relations associated with the calculi VL are always finitely equivalential but might not be algebraizable. In this paper we associate an algebraizable 2-Gentzen relation with every sequent calculus VL in a uniform way, provided the original algebra L has a reduct that is a distributive lattice or a pseudocomplemented distributive lattice. We also show that the sentential logic naturally associated with the provable sequents of this algebraizable Gentzen relation is the logic that preserves degrees of truth with respect to the original algebra (in contrast with the more common logic that merely preserves truth). Finally, for some particular logics we obtain 2-sequent calculi that axiomatize the algebraizable Gentzen relations obtained so far.     

Expressive power and semantic completeness: Boolean connectives in modal logic

We illustrate, with three examples, the interaction between boolean and modal connectives by looking at the role of truth-functional reasoning in the provision of completeness proofs for normal modal logics. The first example (§ 1) is of a logic (more accurately: range of logics) which is incomplete in the sense of being determined by no class of Kripke frames, where the incompleteness is entirely due to the lack of boolean negation amongst the underlying non-modal connectives. The second example (§ 2) focusses on the breakdown, in the absence of boolean disjunction, of the usual canonical model argument for the logic of dense Kripke frames, though a proof of incompleteness with respect to the Kripke semantics is not offered. An alternative semantic account is developed, in terms of which a completeness proof can be given, and this is used (§ 3) in the discussion of the third example, a bimodal logic which is, as with the first example, provably incomplete in terms of the Kripke semantics, the incompleteness being due to the lack of disjunction (as a primitive or defined boolean connective).     

The Decision Problem of Modal Product Logics with a Diagonal,and Faulty Counter Machines

In the propositional modal (and algebraic) treatment of two-variable first-order logic equality is modelled by a ‘diagonal’ constant, interpreted in square products of universal frames as the identity (also known as the ‘diagonal’) relation. Here we study the decision problem of products of two arbitrary modal logics equipped with such a diagonal. As the presence or absence of equality in two-variable first-order logic does not influence the complexity of its satisfiability problem, one might expect that adding a diagonal to product logics in general is similarly harmless. We show that this is far from being the case, and there can be quite a big jump in complexity, even from decidable to the highly undecidable. Our undecidable logics can also be viewed as new fragments of first-order logic where adding equality changes a decidable fragment to undecidable. We prove our results by a novel application of counter machine problems. While our formalism apparently cannot force reliable counter machine computations directly, the presence of a unique diagonal in the models makes it possible to encode both lossy and insertion-error computations, for the same sequence of instructions. We show that, given such a pair of faulty computations, it is then possible to reconstruct a reliable run from them.     

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.     

Public announcement logic with distributed knowledge: expressivity,completeness and complexity

While dynamic epistemic logics with common knowledge have been extensively studied, dynamic epistemic logics with distributed knowledge have so far received far less attention. In this paper we study extensions of public announcement logic (\(\mathcal{PAL }\)) with distributed knowledge, in particular their expressivity, axiomatisations and complexity. \(\mathcal{PAL }\) extended only with distributed knowledge is not more expressive than standard epistemic logic with distributed knowledge. Our focus is therefore on \(\mathcal{PACD }\), the result of adding both common and distributed knowledge to \(\mathcal{PAL }\), which is more expressive than each of its component logics. We introduce an axiomatisation of \(\mathcal{PACD }\), which is not surprising: it is the combination of well-known axioms. The completeness proof, however, is not trivial, and requires novel combinations and extensions of techniques for dealing with \(S5\) knowledge, distributed knowledge, common knowledge and public announcements at the same time. We furthermore show that \(\mathcal{PACD }\) is decidable, more precisely that it is \(\textsc {exptime}\)-complete. This result also carries over to \(\mathcal{S 5\mathcal CD }\) with common and distributed knowledge operators for all coalitions (and not only the grand coalition). Finally, we propose a notion of a trans-bisimulation to generalise certain results and give deeper insight into the proofs.     

Finding Missing Proofs with Automated Reasoning

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.     

Equivalential and algebraizable logics

The notion of an algebraizable logic in the sense of Blok and Pigozzi [3] is generalized to that of a possibly infinitely algebraizable, for short, p.i.-algebraizable logic by admitting infinite sets of equivalence formulas and defining equations. An example of the new class is given. Many ideas of this paper have been present in [3] and [4]. By a consequent matrix semantics approach the theory of algebraizable and p.i.-algebraizable logics is developed in a different way. It is related to the theory of equivalential logics in the sense of Prucnal and Wroski [18], and it is extended to nonfinitary logics. The main result states that a logic is algebraizable (p.i.-algebraizable) iff it is finitely equivalential (equivalential) and the truth predicate in the reduced matrix models is equationally definable.Most of the results of the present and a forthcoming paper originally appeared in [13].Presented by Wolfgang Rautenberg     

On Proof Terms and Embeddings of Classical Substructural Logics

There is an intimate connection between proofs of the natural deduction systems and typed lambda calculus. It is well-known that in simply typed lambda calculus, the notion of formulae-as-types makes it possible to find fine structure of the implicational fragment of intuitionistic logic, i.e., relevant logic, BCK-logic and linear logic. In this paper, we investigate three classical substructural logics (GL, GLc, GLw) of Gentzen's sequent calculus consisting of implication and negation, which contain some of the right structural rules. In terms of Parigot's -calculus with proper restrictions, we introduce a proof term assignment to these classical substructural logics. According to these notions, we can classify the -terms into four categories. It is proved that well-typed GLx--terms correspond to GLx proofs, and that a GLx--term has a principal type if stratified where x is nil, c, w or cw. Moreover, we investigate embeddings of classical substructural logics into the corresponding intuitionistic substructural logics. It is proved that the Gödel-style translations of GLx--terms are embeddings preserving substructural logics. As by-products, it is obtained that an inhabitation problem is decidable and well-typed GLx--terms are strongly normalizable.