Fundamenta Informaticae - Volume 156, issue 3-4

Authors: Niwiński, Damian | Orłowska, Ewa

Article Type: Other

DOI: 10.3233/FI-2017-1607

Citation: Fundamenta Informaticae, vol. 156, no. 3-4, pp. i-ii, 2017

Authors: Czelakowski, Janusz

Article Type: Research Article

Abstract: The paper is concerned with the problem of building models for first-order languages from the perspective of the classic paper of Rasiowa and Sikorski [9]. The central idea, developed in this paper, consists in constructing first-order models from individual variables. The key notion of a Rasiowa–Sikorski set of formulas for an arbitrary countable language L is examined. Each Rasiowa–Sikorski set defines a countable model for L . Conversely, every countable model for L is determined by a Rasiowa–Sikorski set. The focus is on constructing Rasiowa–Sikorski sets by applying forcing techniques restricted to Boolean algebras arising from the subsets …of the set of atomic formulas of L . Show more

Keywords: first-order logic, substitutional semantics, Lindenbaum set, Rasiowa–Sikorski set, Boolean algebra, ultrafilter, forcing

DOI: 10.3233/FI-2017-1608

Citation: Fundamenta Informaticae, vol. 156, no. 3-4, pp. 255-280, 2017

Authors: Düntsch, Ivo | Kwuida, Léonard | Orłowska, Ewa

Article Type: Research Article

Abstract: Dicomplemented lattices were introduced as an abstraction of Wille’s concept algebras which provided negations to a concept lattice. We prove a discrete representation theorem for the class of dicomplemented lattices. The theorem is based on a topology free version of Urquhart’s representation of general lattices.

DOI: 10.3233/FI-2017-1609

Citation: Fundamenta Informaticae, vol. 156, no. 3-4, pp. 281-295, 2017

Authors: Fitting, Melvin

Article Type: Research Article

Abstract: In 1951 in his book An Essay in Modal Logic , Georg Henrik von Wright strongly called attention to the analogies between quantifiers and modal operators. In 1984 I published a paper in Synthese examining the analogy formally. Confession: the presentation in that paper was badly done, and there is a significant (though correctable) error. Its time to repair the damage, present the ideas in a better way, and continue the investigation further. There are natural sublogics of classical first-order logic that are direct analogs of standard, basic modal logics. The behavior of quantifiers can be given a …possible world semantics, some analogous to normal models, some to regular models, and some to neighborhood models. The first-order logics have axiom systems and generally also tableau systems, paralleling those of modal logics. Many have the interpolation property. This gives concrete substance to von Wright’s observations. But then, what is the crucial difference between modal operators and quantifiers? This turns out to be surprising in its simplicity, and leads to an interesting way of looking at the familiar Henkin style completeness proof for first-order logic. Show more

DOI: 10.3233/FI-2017-1610

Citation: Fundamenta Informaticae, vol. 156, no. 3-4, pp. 297-330, 2017

Authors: Romanowska, Anna B. | Smith, Jonathan D.H.

Article Type: Research Article

Abstract: The primary goal of the paper is to establish a duality for quasilattices. The main ingredients are duality for semilattices and their representations, the structural analysis of quasilattices as Płonka sums of lattices, and the duality for lattices developed by Hartonas and Dunn. Lattice duality treats the identity function on a lattice as a Galois connection between its meet and join semilattice reducts, and then invokes a duality between Galois connections and polarities. A second goal of the paper is a further examination of this latter duality, using the concept of a pairing to provide an algebraic equivalent to the …relational structure of a polarity. Show more

Keywords: duality, Plonka sum, quasilattice, semilattice sum, Galois connection

DOI: 10.3233/FI-2017-1611

Citation: Fundamenta Informaticae, vol. 156, no. 3-4, pp. 331-359, 2017

Authors: Sofronie-Stokkermans, Viorica

Article Type: Research Article

Abstract: In this paper we show that subsumption problems in lightweight description logics (such as ɛℒ and ɛℒ+ ) can be expressed as uniform word problems in classes of semilattices with monotone operators. We use possibilities of efficient local reasoning in such classes of algebras, to obtain uniform PTIME decision procedures for CBox subsumption in ɛℒ, ɛℒ+ and extensions thereof. These locality considerations allow us to present a new family of (possibly many-sorted) logics which extend ɛℒ and ɛℒ+ with n -ary roles and/or numerical domains. As a by-product, this allows us to show that the algebraic models of …ɛℒ and ɛℒ+ have ground interpolation and thus that ɛℒ, ɛℒ+ , and their extensions studied in this paper have interpolation. Show more

DOI: 10.3233/FI-2017-1612

Citation: Fundamenta Informaticae, vol. 156, no. 3-4, pp. 361-411, 2017

Authors: Vakarelov, Dimiter

Article Type: Research Article

Abstract: We discuss in this work the importance of some predicates of ontological existence in mereology and in mereotopology especially for systems incorporating time. Tarski showed that mereology can be identified in some sense with complete Boolean algebras with zero 0 deleted. If one prefers to use only first-order language, the first-order theory for Boolean algebras can be used with zero included for simplicity. We extend the language of Boolean algebra with a one-place predicate AE (x ), called “actual existence” and satisfying some natural axioms. We present natural models for Boolean algebras with predicate AE (x ) motivating the axioms …and prove corresponding representation theorems. Mereotopology is considered as an extension of mereology with some relations of topological nature, like contact. One of the standard mereotopological systems is contact algebra, which is an extension of Boolean algebra with a contact relation C , satisfying some simple and obvious axioms. We consider in this paper a natural generalization of contact algebra as an extension of Boolean algebra with the predicate AE (x ) and a contact relation Ca called “actual contact”, assuming for them natural axioms combining Ca and AE . Relational and topological models are proposed for the resulting system and corresponding representation theorems are proved. I dedicate this paper to my teacher in logic Professor Helena Rasiowa for her 100-th birth anniversary. Professor Rasiowa showed me the importance of algebraic and topological methods in logic and this was her main influence on me. Show more

Keywords: Mereotopology, Contact algebra, Actual existence, Actual contact, Topological representation

DOI: 10.3233/FI-2017-1613

Citation: Fundamenta Informaticae, vol. 156, no. 3-4, pp. 413-432, 2017

Article Type: Other

Citation: Fundamenta Informaticae, vol. 156, no. 3-4, pp. 433-434, 2017