Search

Algebraic proof systems, such as Polynomial Calculus (PC) and Polynomial Calculus with Resolution (PCR), refute contradictions using polynomials. Space complexity for such systems measures the number of distinct monomials to be kept in memory while verifying a proof. We introduce a new combinatorial framework for proving space lower bounds in algebraic proof systems. As an immediate application, we obtain the space lower bounds previously provided for PC/PCR [Alekhnovich et al. 2002; Filmus et al. 2012]. More importantly, using our approach in its full potential, we prove Ω (n) space lower bounds in PC/PCR for random &#954:-CNFs (κ ≥ 4) in n variables, thus solving an open problem posed in Alekhnovich et al. [2002] and Filmus et al. [2012]. Our method also applies to the Graph Pigeonhole Principle, which is a variant of the Pigeonhole Principle defined over a constant (left) degree expander graph. [ABSTRACT FROM AUTHOR]

It is introduced an immune dynamic n-valued Łukasiewicz logic I D Ł n on the base of n-valued Łukasiewicz logic Ł n and corresponding to it immune dynamic M V n -algebra ( I D L n -algebra), 1 < n < ω , which are algebraic counterparts of the logic, that in turn represent two-sorted algebras (M , R , ◊) that combine the varieties of M V n -algebras M = (M , ⊕ , ⊙ , ∼ , 0 , 1) and regular algebras R = (R , ∪ , ; , ∗) into a single finitely axiomatized variety resembling R-module with "scalar" multiplication ◊ . Kripke semantics is developed for immune dynamic Łukasiewicz logic I D Ł n with application in immune system. [ABSTRACT FROM AUTHOR]

Let α be an arbitrary infinite ordinal, and 2

When an algebraic logic based on a poset instead of a lattice is investigated then there is a natural problem how to introduce implication to be everywhere defined and satisfying (left) adjointness with conjunction. We have already studied this problem for the logic of quantum mechanics which is based on an orthomodular poset or the logic of quantum effects based on a so-called effect algebra which is only partial and need not be lattice-ordered. For this, we introduced the so-called operator residuation where the values of implication and conjunction need not be elements of the underlying poset, but only certain subsets of it. However, this approach can be generalized for posets satisfying more general conditions. If these posets are even finite, we can focus on maximal or minimal elements of the corresponding subsets and the formulas for the mentioned operators can be essentially simplified. This is shown in the present paper where all theorems are explained by corresponding examples. [ABSTRACT FROM AUTHOR]

Effect algebras form a formal algebraic description of the structure of the so-called effects in a Hilbert space which serve as an event-state space for effects in quantum mechanics. This is why effect algebras are considered as logics of quantum mechanics, more precisely as an algebraic semantics of these logics. Because every productive logic is equipped with implication, we introduce here such a concept and demonstrate its properties. In particular, we show that this implication is connected with conjunction via a certain "unsharp" residuation which is formulated on the basis of a strict unsharp residuated poset. Though this structure is rather complicated, it can be converted back into an effect algebra and hence it is sound. Further, we study the Modus Ponens rule for this implication by means of so-called deductive systems and finally we study the contraposition law. [ABSTRACT FROM AUTHOR]

Ehrhard et al. (2018. Proceedings of the ACM on Programming Languages, POPL 2, Article 59.) proposed a model of probabilistic functional programming in a category of normed positive cones and stable measurable cone maps, which can be seen as a coordinate-free generalization of probabilistic coherence spaces (PCSs). However, unlike the case of PCSs, it remained unclear if the model could be refined to a model of classical linear logic. In this work, we consider a somewhat similar category which gives indeed a coordinate-free model of full propositional linear logic with nondegenerate interpretation of additives and sound interpretation of exponentials. Objects are dual pairs of normed cones satisfying certain specific completeness properties, such as existence of norm-bounded monotone weak limits, and morphisms are bounded (adjointable) positive maps. Norms allow us a distinct interpretation of dual additive connectives as product and coproduct. Exponential connectives are modeled using real analytic functions and distributions that have representations as power series with positive coefficients. Unlike the familiar case of PCSs, there is no reference or need for a preferred basis; in this sense the model is invariant. PCSs form a full subcategory, whose objects, seen as posets, are lattices. Thus, we get a model fitting in the tradition of interpreting linear logic in a linear algebraic setting, which arguably is free from the drawbacks of its predecessors. [ABSTRACT FROM AUTHOR]

Since orthomodular posets serve as an algebraic axiomatization of the logic of quantum mechanics, it is a natural question how the connective of implication can be defined in this logic. It should be introduced in such a way that it is related with conjunction, i.e. with the partial operation meet, by means of some kind of adjointness. We present here such an implication for which a so-called unsharp residuated poset can be constructed. Then this implication is connected with the operation meet by the so-called unsharp adjointness. We prove that also conversely, under some additional assumptions, such an unsharp residuated poset can be converted into an orthomodular poset and that this assignment is nearly one-to-one. [ABSTRACT FROM AUTHOR]

The article focuses on publishing papers in various fields of logic, including philosophical and non-classical logics, algebraic logic, applications in computer science, linguistics, while providing detailed guidelines for manuscript submissions, formatting, references, and artwork.

Parallel reduction is a major component of parallel programming and widely used for summarisation and aggregation. It is not well understood, however, what sorts of non-trivial summarisations can be implemented as parallel reductions. This paper develops a calculus named λAS, a simply typed lambda calculus with algebraic simplification. This calculus provides a foundation for studying a parallelisation of complex reductions by equational reasoning. Its key feature is δ abstraction. A δ abstraction is observationally equivalent to the standard λ abstraction, but its body is simplified before the arrival of its arguments using algebraic properties such as associativity and commutativity. In addition, the type system of λAS guarantees that simplifications due to δ abstractions do not lead to serious overheads. The usefulness of λAS is demonstrated on examples of developing complex parallel reductions, including those containing more than one reduction operator, loops with conditional jumps, prefix sum patterns and even tree manipulations. [ABSTRACT FROM AUTHOR]

The paper aims at studying, in full generality, logics defined by imposing a variable inclusion condition on a given logic ⊢ . We prove that the description of the algebraic counterpart of the left variable inclusion companion of a given logic ⊢ is related to the construction of Płonka sums of the matrix models of ⊢ . This observation allows to obtain a Hilbert-style axiomatization of the logics of left variable inclusion, to describe the structure of their reduced models, and to locate them in the Leibniz hierarchy. [ABSTRACT FROM AUTHOR]

In the last decades much research effort has been devoted to extending the success of model checking from the traditional field of finite state machines and various versions of temporal logics to suitable subclasses of context-free languages and appropriate extensions of temporal logics. To the best of our knowledge such attempts only covered structured languages , i.e. languages whose structure is immediately "visible" in their sentences, such as tree-languages or visibly pushdown ones. In this paper we present a new temporal logic suitable to express and automatically verify properties of operator precedence languages. This "historical" language family has been recently proved to enjoy fundamental algebraic and logic properties that make it suitable for model checking applications yet breaking the barrier of visible-structure languages (in fact the original motivation of its inventor Floyd was just to support efficient parsing , i.e. building the "hidden syntax tree" of language sentences). We prove that our logic is at least as expressive as analogous logics defined for visible pushdown languages yet covering a much more powerful family; we design a procedure that, given a formula in our logic builds an automaton recognizing the sentences satisfying the formula, whose size is at most exponential in the length of the formula. Our results cover both finite and infinite string languages. [ABSTRACT FROM AUTHOR]

Let α be an ordinal and L be a unimodal logic (like S4 or S5). A modal cylindric algebra of dimension α, an LCAα, is a cylindric algebra of dimension α, expanded with α-many L modalities. For a frame (U, R) of L, each k < α, one defines a diamond box operator on. This defines the semantics of the L modalities in set algebras, with the rest of the operations defined like in cylindric set algebras of dimension α. We study interpolation properties for the corresponding predicate logic having α-many variables. Our results are valid for any reflexive L whose frames contain the universal frames (U, U × U). In particular, they hold for K5CAα, S4CAα (which is an algebraizable extension of topological predicate logic with semantics induced by Alexandrov topologies). [ABSTRACT FROM AUTHOR]

The conversion between logic and algebraic expressions of Boolean control networks plays a worthy role in the analysis and design of digital circuits. In this paper, for a single Boolean function, a direct conversion between the minterm canonical form and the structure matrix is provided. For a Boolean control network consisting of systems of Boolean functions, two algorithms are developed to achieve the mutual conversion between the logic and algebraic expressions. The presented algorithms decrease exponentially the complexity of the semi-tensor product based method. Some numerical examples are given to demonstrate the algorithms and to compare our method with the existing ones. [ABSTRACT FROM AUTHOR]

Effect algebras form an algebraic formalization of the logic of quantum mechanics. For lattice effect algebras E , we investigate a natural implication and prove that the implication reduct of E is term equivalent to E . Then, we present a simple axiom system in Gentzen style in order to axiomatize the logic induced by lattice effect algebras. For effect algebras which need not be lattice-ordered, we introduce a certain kind of implication which is everywhere defined but whose result need not be a single element. Then, we study effect implication algebras and prove the correspondence between these algebras and effect algebras satisfying the ascending chain condition. We present an axiom system in Gentzen style also for not necessarily lattice-ordered effect algebras and prove that it is an algebraic semantics for the logic induced by finite effect algebras. [ABSTRACT FROM AUTHOR]

Multialgebras (or hyperalgebras or non-deterministic algebras) have been much studied in mathematics and in computer science. In 2016 Carnielli and Coniglio introduced a class of multialgebras called swap structures, as a semantic framework for dealing with several Logics of Formal Inconsistency (or LFI s) that cannot be semantically characterized by a single finite matrix. In particular, these LFI s are not algebraizable by the standard tools of abstract algebraic logic. In this paper, the first steps towards a theory of non-deterministic algebraization of logics by swap structures are given. Specifically, a formal study of swap structures for LFI s is developed, by adapting concepts of universal algebra to multialgebras in a suitable way. A decomposition theorem similar to Birkhoff's representation theorem is obtained for each class of swap structures. Moreover, when applied to the 3-valued algebraizable logics J3 and Ciore , their classes of algebraic models are retrieved, and the swap structures semantics become twist structures semantics (as independently introduced by M. Fidel and D. Vakarelov). This fact, together with the existence of a functor from the category of Boolean algebras to the category of swap structures for each LFI (which is closely connected with Kalman's functor), suggests that swap structures can be seen as non-deterministic twist structures. This opens new avenues for dealing with non-algebraizable logics by the more general methodology of multialgebraic semantics. [ABSTRACT FROM AUTHOR]

There are two foundational, but not fully developed, ideas in paraconsistency, namely, the duality between paraconsistent and intuitionistic paradigms, and the introduction of logical operators that express metalogical notions in the object language. The aim of this paper is to show how these two ideas can be adequately accomplished by the logics of formal inconsistency (LFI s) and by the logics of formal undeterminedness (LFU s). LFI s recover the validity of the principle of explosion in a paraconsistent scenario, while LFU s recover the validity of the principle of excluded middle in a paracomplete scenario. We introduce definitions of duality between inference rules and connectives that allow comparing rules and connectives that belong to different logics. Two formal systems are studied, the logics mbC and mbD , that display the duality between paraconsistency and paracompleteness as a duality between inference rules added to a common core—in the case studied here, this common core is classical positive propositional logic. The logics mbC and mbD are equipped with recovery operators that restore classical logic for, respectively, consistent and determined propositions. These two logics are then combined obtaining a pair of LFI and undeterminedness, namely, mbCD and mbCDE. The logic mbCDE exhibits some nice duality properties. Besides, it is simultaneously paraconsistent and paracomplete, and able to recover the principles of excluded middle and explosion one at a time. The last sections offer an algebraic account for such logics by adapting the swap structures semantics framework of the LFI s the LFU s. This semantics highlights some subtle aspects of these logics, and allows us to prove decidability by means of finite nondeterministic matrices. [ABSTRACT FROM AUTHOR]

Fix 2 < n < ω and let C A n denote the class of cylindric algebras of dimension n. Roughly, C A n is the algebraic counterpart of the proof theory of first-order logic restricted to the first n variables which we denote by L n . The variety R C A n of representable C A n s reflects algebraically the semantics of L n . A variety V of Boolean algebras with operators is atom-canonical, if whenever A ∈ V is atomic, then its Dedekind–MacNeille completion is also in V. We show using a so-called blow up and blur construction that for any k ≥ 2 n , any variety of the form S N r n C A k containing (and including) R C A n (when k = ω) is not atom-canonical. We show that a restricted form of that the celebrated Henkin–Orey omitting types theorem, which we refer to below as Vaught's Theorem ( V T), fails dramatically for L n even if we allow only so-called m-square models for 2 n ≤ m ≤ ω. We deduce that many multi-modal logics, like S 5 n , the m clique guarded fragments and packed fragments of L n are not Sahlqvist. In contrast, we prove a positive O T T for L n theories with respect to usual semantics, by imposing extra conditions (such as quantifier elimination) on possibly uncountable theories considered and/or the non-principal types omitted (that are also allowed to be possibly uncountable) such as completeness.ast is a maximality condition delineating the edge of an independent statement to a provable one. is shown that the maximality condition cannot be removed even to prove the weaker V T for uncountable theories; and this construction is used to reprove a celebrated result of Hirsch and Hodkinson, namely, that the class of completely representable C A n s is not el. [ABSTRACT FROM AUTHOR]

Fix 2 < n < ω and let CAn denote the class of cyindric algebras of dimension n. Roughly CAn is the algebraic counterpart of the proof theory of first order logic restricted to the first n variables which we denote by Ln. The variety RCAn of representable CAns reflects algebraically the semantics of Ln. Members of RCAn are concrete algebras consisting of genuine n-ary relations, with set theoretic operations induced by the nature of relations, such as projections referred to as cylindrifications. Although CAn has a finite equational axiomatization, RCAn is not finitely axiomatizable, and it generally exhibits wild, often unpredictable and unruly behavior. This makes the theory of CAn substantially richer than that of Boolean algebras, just as much as Lω,ω is richer than propositional logic. We show using a so-called blow up and blur construction that several varieties (in fact infinitely many) containing and including the variety RCAn are not atom-canonical. A variety V of Boolean algebras with operators is atom canonical, if whenever 𝔄 ∈ V is atomic, then its Dedekind-MacNeille completion, sometimes referred to as its minimal completion, is also in V. From our hitherto obtained algebraic results we show, employing the powerful machinery of algebraic logic, that the celebrated Henkin-Orey omitting types theorem, which is one of the classical first (historically) cornerstones of model theory of Lω,ω, fails dramatically for Ln even if we allow certain generalized models that are only locallly clasfsical. It is also shown that any class K such that N r n C A ω ∩ CRC A n ⊆ ¯ K ⊆ ¯ S c N r n C A n + 3 , where CRCAn is the class of completely representable CAns, and Sc denotes the operation of forming dense (complete) subalgebras, is not elementary. Finally, we show that any class K such that S d RaC A ω ⊆ ¯ K ⊆ ¯ S c RaC A 5 is not elementary, where Sd denotes the operation of forming dense subalgebra. [ABSTRACT FROM AUTHOR]

Paraorthomodular lattices are quantum structures of prominent importance within the framework of the logico-algebraic approach to (unsharp) quantum theory. However, at the present time it is not clear whether the above algebras may be regarded as the algebraic semantic of a logic in its own right. In this paper, we start the investigation of material implications in paraorthomodular lattices by showing that any bounded modular lattice with antitone involution A can be converted into a left-residuated groupoid if it satisfies a strengthened form of regularity. Moreover, the above condition turns out to be also necessary whenever A is distributive. [ABSTRACT FROM AUTHOR]

We shall be concerned with the modal logic BK—which is based on the Belnap–Dunn four-valued matrix, and can be viewed as being obtained from the least normal modal logic K by adding 'strong negation'. Though all four values 'truth', 'falsity', 'neither' and 'both' are employed in its Kripke semantics, only the first two are expressible as terms. We show that expanding the original language of BK to include constants for 'neither' or/and 'both' leads to quite unexpected results. To be more precise, adding one of these constants has the effect of eliminating the respective value at the level of BK-extensions. In particular, if one adds both of these, then the corresponding lattice of extensions turns out to be isomorphic to that of ordinary normal modal logics. [ABSTRACT FROM AUTHOR]

In this paper we deal with some fuzzy logics and their equivalent algebraic semantics. After introducing new constructions for left-continuous t-norms, we define the concept of rotation logic as the assertional logic of a variety of M T L -algebras generated by t-norm algebras of a certain type; next we prove which algebraic models of those logics come from the algebraic construction of generalized rotation. In the final sections we show other examples and applications of the construction, focusing on the variety of W N M -algebras. [ABSTRACT FROM AUTHOR]

This is a companion article to the translation of 'Zasada sprzeczności a logika symboliczna', the appendix on symbolic logic of Jan Łukasiewicz's 1910 book O zasadzie sprzeczności u Arytotelesa (On the Principle of Contradiction in Aristotle). While the appendix closely follows Couturat's 1905 book L'algebra de la logique (The Algebra of Logic), footnotes show that Łukasiewicz was aware of the work of Peirce, Huntington and Russell (before Principia Mathematica). This appendix was influential in the development of the Polish school of logic, directly inspiring Stanisław Leśniewski and Leon Chwistek and more widely by serving as a text of the new symbolic logic. This appendix was an important source of the dominant algebraic logic in Poland, but also indicates that Łukasiewicz appreciated Russell's axiomatic approach to logic. [ABSTRACT FROM AUTHOR]

In this paper, we build a logic which is named N-sequent calculus. Based on this logic, we provide two kinds of logical representations of Lawson compact algebraic L-domains: one in terms of logical algebras and the other in terms of logical syntax. The first representation takes the corresponding logical algebras as research objects. The use of prime filters achieves the connection between our logic and Lawson compact algebraic L-domains. This approach is inspired by Abramsky's SFP domain logic and the disjunctive propositional logic on algebraic L-domains introduced by Yixiang Chen and Achim Jung. However, there are essential differences between them at the morphisms part. For the second representation, we directly adopt N-sequent calculi themselves as objects instead of the logical algebras. Then we establish the category of N-sequent calculi with consequence relations equivalent to that of Lawson compact algebraic L-domains with Scott continuous maps. This demonstrates the capability of the syntax of the logic in representing domains. [ABSTRACT FROM AUTHOR]

An intuitive introduction to L-algebras and their relationship to groups with a one- or two-sided lattice ordering is given, with applications in algebra, analysis, and geometry. [ABSTRACT FROM AUTHOR]

Wind generated waves are a very random phenomenon and it is one of the main environmental disturbances that affect the operation of Autonomous Underwater Vehicles (AUV) navigating in shallow waters and coastal zones. In order to attenuate the undesirable effect of the ocean waves on the control system of AUVs, the measurements from the sensors need to be filtered out, using the estimated wave encounter frequency. Developing an estimator capable of providing the encounter frequency in real time using the Algebraic Identification method, is fully reported in this paper. In the design of the proposed algebraic estimator, a linear differential equation to represent the waves spectrum is used, which simplifies the mathematical procedure. The simulations carried out with simulated data and with real data from an experiment at sea, show the excellent results of the estimator in terms of precision in the final value and estimation time. In addition, its show the use of the wave encounter frequency estimation to adjust the filtering techniques previously implemented for the vehicle in a proper way, which results in a reduction of vibrations and energy consumption of the vehicle's rudder system. [ABSTRACT FROM AUTHOR]

Suszko's problem is the problem of finding the minimal number of truth values needed to semantically characterize a syntactic consequence relation. Suszko proved that every Tarskian consequence relation can be characterized using only two truth values. Malinowski showed that this number can equal three if some of Tarski's structural constraints are relaxed. By so doing, Malinowski introduced a case of so-called mixed consequence , allowing the notion of a designated value to vary between the premises and the conclusions of an argument. In this article we give a more systematic perspective on Suszko's problem and on mixed consequence. First, we prove general representation theorems relating structural properties of a consequence relation to their semantic interpretation, uncovering the semantic counterpart of substitution-invariance, and establishing that (intersective) mixed consequence is fundamentally the semantic counterpart of the structural property of monotonicity. We use those theorems to derive maximum-rank results proved recently in a different setting by French and Ripley, as well as by Blasio, Marcos, and Wansing, for logics with various structural properties (reflexivity, transitivity, none, or both). We strengthen these results into exact rank results for nonpermeable logics (roughly, those which distinguish the role of premises and conclusions). We discuss the underlying notion of rank, and the associated reduction proposed independently by Scott and Suszko. As emphasized by Suszko, that reduction fails to preserve compositionality in general, meaning that the resulting semantics is no longer truth-functional. We propose a modification of that notion of reduction, allowing us to prove that over compact logics with what we call regular connectives , rank results are maintained even if we request the preservation of truth-functionality and additional semantic properties. [ABSTRACT FROM AUTHOR]

The logic DAI of demodalised analytic implication has been introduced by J.M. Dunn (and independently investigated by R.D. Epstein) as a variation on a time-honoured logical system by C.I. Lewis' student W.T. Parry. The main tenet underlying this logic is that no implication can be valid unless its consequent is "analytically contained" in its antecedent. DAI has been investigated both proof-theoretically and model-theoretically, but no study so far has focussed on DAI from the viewpoint of abstract algebraic logic. We provide several different algebraic semantics for DAI, showing their equivalence with the known semantics by Dunn and Epstein. We also show that DAI is algebraisable and we identify its equivalent quasivariety semantics. This class turns out to be a linguistic and axiomatic expansion of involutive bisemilattices, a subquasivariety of which forms the algebraic counterpart of Paraconsistent Weak Kleene logic (PWK). This fact sheds further light on the relationship between containment logics and logics of nonsense. [ABSTRACT FROM AUTHOR]

Shramko [(2016). Truth, falsehood, information and beyond: The American plan generalized. In K. Bimbo (Ed.), J. Michael Dunn on information based logics, outstanding contributions to logic (pp. 191–212). Dordrecht: Springer] formulated multilattice logic and the algebraic completeness theorem for it. However, the proof has not been presented. In this paper, we consider Kamide and Shramko's multilattice logic M L n [Kamide & Shramko (2017a). Embedding from multilattice logic into classical logic and vice versa. Journal of Logic and Computation, 27(5), 1549–1575] which is an extension of Shramko's original multilattice logic by several implications and coimplications. Using the technique of algebraic embedding, we show that Kamide and Shramko's sequent calculus for multilattice logic M L n is sound and complete with respect to multilattices. Moreover, we introduce yet another algebraic semantics for this logic based on the notion of a De Morgan multilattice. Using Lindenbaum-Tarski algebras, we show that M L n is sound and complete with respect to De Morgan multilattices. Besides, we modify Kamide and Shramko's notion of modal multilattice [Kamide & Shramko (2017b). Modal multilattice logic. Logica Universalis, 11(3), 317–343], i.e. we present the concept of De Morgan modal multilattice. We prove that Kamide and Shramko's modal multilattice logic (Kamide & Shramko, 2017b) is adequate with respect to De Morgan modal multilattices. [ABSTRACT FROM AUTHOR]

We extend Lawvere-Pitts prop-categories (aka. hyperdoctrines) to develop a general framework for providing fibered algebraic semantics for general first-order logics. This framework includes a natural notion of substitution, which allows first-order logics to be considered as structural closure operators just as propositional logics are in abstract algebraic logic. We then establish an extension of the homomorphism theorem from universal algebra for generalized prop-categories and characterize two natural closure operators on the prop-categorical semantics. The first closes a class of structures (which are interpreted as morphisms of prop-categories) under the satisfaction of their common first-order theory and the second closes a class of prop-categories under their associated first-order consequence. It turns out that these closure operators have characterizations that closely mirror Birkhoff's characterization of the closure of a class of algebras under the satisfaction of their common equational theory and Blok and Jónsson's characterization of closure under equational consequence, respectively. These algebraic characterizations of the first-order closure operators are unique to the prop-categorical semantics. They do not have analogues, for example, in the Tarskian semantics for classical first-order logic. The prop-categories we consider are much more general than traditional intuitionistic prop-categories or triposes (i.e., topos representing indexed partially ordered sets). Nonetheless, to the best of our knowledge, our results are new, even when restricted to these special classes of prop-categories. [ABSTRACT FROM AUTHOR]

In this paper we present a topological duality for a certain subclass of the $F_{ømega}$-structures defined by M. M. Fidel, which conform to a non-standard semantics for the paraconsistent N. C. A. da Costa logic $C_ømega$. Actually, the duality introduced here is focused on $F_ømega$-structures whose supports are chains. For our purposes, we characterize every $F_ømega$-chain by means of a new structure that we will call down-covered chain (DCC) here. This characterization will allow us to prove the dual equivalence between the category of $F_ømega$-chains and a new category, whose objects are certain special topological spaces (together with a distinguished family of open sets) and whose morphisms are particular continuous functions.