Bulletin of the Section of Logic https://czasopisma.uni.lodz.pl/bulletin <div style="text-align: justify;"> <p>The&nbsp;<em>Bulletin of the Section of Logic</em>&nbsp;(<em>BSL</em>) is a quarterly peer-reviewed journal published with the support of the Lodz University Press. The&nbsp;<em>BSL</em>&nbsp;was founded in 1972 by Ryszard Wójcicki, Head of the Section of Logic of the Polish Academy of Sciences, then based in Wrocław, as a newsletter-journal designed for the exchange of scientific results among members of the Section with their national and international partners and colleagues. From1975 to 2018 the journal was managed and edited by Grzegorz Malinowski. In 1992 the Department of Logic at the University of Łódź took over the publication from the Polish Academy of Sciences changing its policy into regular peer-reviewed journal. The aim of the&nbsp;<em>Bulletin</em>&nbsp;is to act as a forum for the prompt wide dissemination of original, significant results in logic through rapid publication. The&nbsp;<em>BSL</em>&nbsp;welcomes especially contributions dealing directly with logical calculi, their methodology, application and algebraic interpretations.</p> </div> en-US andrzej.indrzejczak@filozof.uni.lodz.pl (Andrzej Indrzejczak) ojs@fimagis.pl (Firma Magis) Wed, 04 Nov 2020 11:21:28 +0000 OJS http://blogs.law.harvard.edu/tech/rss 60 Proof Compression and NP Versus PSPACE II https://czasopisma.uni.lodz.pl/bulletin/article/view/8169 <p>We upgrade [3] to a complete proof of the conjecture NP = PSPACE that is known as one of the fundamental open problems in the mathematical theory of computational complexity; this proof is based on [2]. Since minimal propositional logic is known to be PSPACE complete, while PSPACE to include NP, it suffices to show that every valid purely implicational formula ρ has a proof whose weight (= total number of symbols) and time complexity of the provability involved are both polynomial in the weight of ρ. As is [3], we use proof theoretic approach. Recall that in [3] we considered any valid ρ in question that had (by the definition of validity) a “short” tree-like proof π in the Hudelmaier-style cutfree sequent calculus for minimal logic. The “shortness” means that the height of π and the total weight of different formulas occurring in it are both polynomial in the weight of ρ. However, the size (= total number of nodes), and hence also the weight, of π could be exponential in that of ρ. To overcome this trouble we embedded π into Prawitz’s proof system of natural deductions containing single formulas, instead of sequents. As in π, the height and the total weight of different formulas of the resulting tree-like natural deduction ∂<sub>1</sub> were polynomial, although the size of ∂<sub>1</sub> still could be exponential, in the weight of ρ. In our next, crucial move, ∂<sub>1</sub> was deterministically compressed into a “small”, although multipremise, dag-like deduction ∂ whose horizontal levels contained only mutually different formulas, which made the whole weight polynomial in that of ρ. However, ∂ required a more complicated verification of the underlying provability of ρ. In this paper we present a nondeterministic compression of ∂ into a desired standard dag-like deduction ∂<sub>0</sub> that deterministically proves ρ in time and space polynomial in the weight of ρ.<sup>2</sup> Together with [3] this completes the proof of NP = PSPACE.<br />Natural deductions are essential for our proof. Tree-to-dag horizontal compression of π merging equal sequents, instead of formulas, is (possible but) not sufficient, since the total number of different sequents in π might be exponential in the weight of ρ – even assuming that all formulas occurring in sequents are subformulas of ρ. On the other hand, we need Hudelmaier’s cutfree sequent calculus in order to control both the height and total weight of different formulas of the initial tree-like proof π, since standard Prawitz’s normalization although providing natural deductions with the subformula property does not preserve polynomial heights. It is not clear yet if we can omit references to π even in the proof of the weaker result NP = coNP.</p> Lew Gordeev, Edward Hermann Haeusler Copyright (c) 2020 Bulletin of the Section of Logic http://creativecommons.org/licenses/by-nc-nd/4.0 https://czasopisma.uni.lodz.pl/bulletin/article/view/8169 Wed, 04 Nov 2020 00:00:00 +0000 Empirical Negation, Co-negation and Contraposition Rule I: Semantical Investigations https://czasopisma.uni.lodz.pl/bulletin/article/view/5862 <p>We investigate the relationship between M. De's empirical negation in Kripke and Beth Semantics. It turns out empirical negation, as well as co-negation, corresponds to different logics under different semantics. We then establish the relationship between logics related to these negations under unified syntax and semantics based on R. Sylvan's <strong>CC<sub>ω</sub></strong>.</p> Satoru Niki Copyright (c) 2020 Bulletin of the Section of Logic http://creativecommons.org/licenses/by-nc-nd/4.0 https://czasopisma.uni.lodz.pl/bulletin/article/view/5862 Wed, 04 Nov 2020 00:00:00 +0000 New Modification of the Subformula Property for a Modal Logic https://czasopisma.uni.lodz.pl/bulletin/article/view/6148 <p>A modified subformula property for the modal logic KD with the additional<br />axiom □ ◊(<em>A</em> <span class="htmlmath">∨</span> <em>B</em>) ⊃ □ ◊ <em>A</em> <span class="htmlmath">∨</span> □ ◊<em>B</em> is shown. A new modification of the notion of subformula is proposed for this purpose. This modification forms a natural extension of our former one on which modified subformula property for the modal logics K5, K5D and S4.2 has been shown ([2] and [4]). The finite model property as well as decidability for the logic follows from this.</p> Mitio Takano Copyright (c) 2020 Bulletin of the Section of Logic http://creativecommons.org/licenses/by-nc-nd/4.0 https://czasopisma.uni.lodz.pl/bulletin/article/view/6148 Wed, 04 Nov 2020 00:00:00 +0000 Module Structure on Effect Algebras https://czasopisma.uni.lodz.pl/bulletin/article/view/5707 <p>In this paper, by considering the notions of effect algebra and product effect algebra, we define the concept of effect module. Then we investigate some properties of effect modules, and we present some examples on them. Finally, we introduce some topologies on effect modules.</p> <p> </p> Simin Saidi Goraghani, Rajab Ali Borzooei Copyright (c) 2020 Bulletin of the Section of Logic http://creativecommons.org/licenses/by-nc-nd/4.0 https://czasopisma.uni.lodz.pl/bulletin/article/view/5707 Wed, 04 Nov 2020 00:00:00 +0000 Equality Logic https://czasopisma.uni.lodz.pl/bulletin/article/view/6033 <p>In this paper, we introduce and study a corresponding logic to equality-algebras and obtain some basic properties of this logic. We prove the soundness and completeness of this logic based on equality-algebras and local deduction theorem. We show that this logic is regularly algebraizable with respect to the variety of equality∆-algebras but it is not Fregean. Then we introduce the concept of (prelinear) equality∆-algebras and investigate some related properties. Also, we study ∆-deductive systems of equality∆-algebras. In particular, we prove that every prelinear equality ∆-algebra is a subdirect product of linearly ordered equality∆-algebras. Finally, we construct prelinear equality ∆ logic and prove the soundness and strong completeness of this logic respect to prelinear equality∆-algebras.</p> Shokoofeh Ghorbani Copyright (c) 2020 Bulletin of the Section of Logic http://creativecommons.org/licenses/by-nc-nd/4.0 https://czasopisma.uni.lodz.pl/bulletin/article/view/6033 Wed, 04 Nov 2020 00:00:00 +0000