Alfred Tarski’s influence on computer science was indirect but significant in a number of directions and was in certain respects fundamental. Here surveyed is Tarski’s work on the decision procedure for algebra and geometry, the method of elimination of quantifiers, the semantics of formal languages, model-theoretic preservation theorems, and algebraic logic; various connections of each with computer science are taken up.

Much of the inspiration for structuralist approaches to mathematics can be found in the late nineteenth- and early twentieth-century program of characterizing various mathematical systems upto isomorphism. From the perspective of this program, differences between isomorphic systems are irrelevant. It is argued that a different view of the import of the differences between isomorphic systems can be obtained from the perspective of contemporary discussions of representation theorems and that from this perspective both the identification of isomorphic systems and the reduction (...) to abstract structures or patterns should be resisted. (shrink)

Being is said and interpreted in various ways. These are studied in ontology. Ontology is concerned with both particular beings of several sorts as well as with the being and Being itself — respectively beings’ collection and unification into one.

In this paper it is shown that Heyting and Co-Heyting mereological systems provide a convenient conceptual framework for spatial reasoning, in which spatial concepts such as connectedness, interior parts, (exterior) contact, and boundary can be defined in a natural and intuitively appealing way. This fact refutes the wide-spread contention that mereology cannot deal with the more advanced aspects of spatial reasoning and therefore has to be enhanced by further non-mereological concepts to overcome its congenital limitations. The allegedly unmereological concept of (...) boundary is treated in detail and shown to be essentially affected by mereological considerations. More precisely, the concept of boundary turns out to be realizable in a variety of different mereologically grounded versions. In particular, every part K of a Heyting algebra H gives rise to a well-behaved K-relative boundary operator. (shrink)

The middle years of the nineteenth century saw two crucial develop ments in the history of modern logic: George Boole's algebraic treat ment of logic and Augustus De Morgan's formulation of the logic of relations. The former episode has been studied extensively; the latter, hardly at all. This is a pity, for the most central feature of modern logic may well be its ability to handle relational inferences. De Morgan was the first person to work out an extensive logic of (...) relations, and the purpose of this book is to study this attempt in detail. Augustus De Morgan (1806-1871) was a British mathematician and logician who was Professor of Mathematics at the University of London (now, University College) from 1828 to 1866. A prolific but not highly original mathematician, De Morgan devoted much of his energies to the rather different field of logic. In his Formal Logic (1847) and a series of papers "On the Syllogism" (1846-1862), he attempted with great ingenuity to reformulate and extend the tradi tional syllogism and to systematize modes of reasoning that lie outside its boundaries. Chief among these is the logic of relations. De Mor gan's interest in relations culminated in his important memoir, "On the Syllogism: IV and on the Logic of Relations," read in 1860. (shrink)

A network of aligned ontologies is a distributed system, whose components are interacting and interoperating, the result of this interaction being, either the extension of local assertions, which are valid within each individual ontology, to global assertions holding between remote ontology syntactic entities through a network path, or to local assertions holding between local entities of an ontology, but induced by remote ontologies, through a cycle in the network. The mechanism for achieving this interaction is the composition of relations. In (...) this perspective, we introduce the notions of local composable relations, which relate ontology entities belonging to the same ontology, remotely induced composable relations, which relate ontology entities belonging to remote ontologies through a path of ontologies and alignments in the network, and network induced local composable relations, which relate ontology entities belonging to the same ontology, but through a path of ontologies and alignments forming a cycle starting and ending at the same ontology, to characterize the logical consequences extracted from a network of aligned ontologies, and we propose a category-based methodology for detecting semantic inconsistencies in networks of aligned ontologies, which is based on contravariant representable functors and on the definition of two composition operators suitable for propagating local knowledge through the network. (shrink)

We consider algebras on binary relations with two main operators: relational composition and dynamic negation. Relational composition has its standard interpretation, while dynamic negation is an operator familiar to students of Dynamic Predicate Logic (DPL) (Groenendijk and Stokhof, 1991): given a relation R its dynamic negation R is a test that contains precisely those pairs (s,s) for which s is not in the domain of R. These two operators comprise precisely the propositional part of DPL.This paper contains a finite equational (...) axiomatization for these dynamic relation algebras. The completenessresult uses techniques from modal logic. We also lookat the variety generated by the class of dynamic relation algebras and note that there exist nonrepresentable algebras in this variety, ones which cannot be construedas spaces of relations. These results are also proved for an extension to a signature containing atomic tests and union. (shrink)

For every finite n ≥ 4 there is a logically valid sentence φ n with the following properties: φ n contains only 3 variables (each of which occurs many times); φ n contains exactly one nonlogical binary relation symbol (no function symbols, no constants, and no equality symbol): φ n has a proof in first-order logic with equality that contains exactly n variables, but no proof containing only n - 1 variables. This result was first proved using the machinery of (...) algebraic logic developed in several research monographs and papers. Here we replicate the result and its proof entirely within the realm of (elementary) first-order binary predicate logic with equality. We need the usual syntax, axioms, and rules of inference to show that φ n has a proof with only n variables. To show that φ n has no proof with only n - 1 variables we use alternative semantics in place of the usual, standard, set-theoretical semantics of first-order logic. (shrink)

We investigate complex algebras of the form arising from a frame where, and exhibit their abstract algebraic and logical counterparts.

Contact relations have been studied in the context of qualitative geometry and physics since the early 1920s, and have recently received attention in qualitative spatial reasoning. In this paper, we present a sound and complete proof system in the style of Rasiowa and Sikorski (1963) for relation algebras generated by a contact relation.

The standard model for mereotopological structures are Boolean subalgebras of the complete Boolean algebra of regular closed subsets of a nonempty connected regular T 0 topological space with an additional "contact relation" C defined by xCy x ØA (possibly) more general class of models is provided by the Region Connection Calculus (RCC) of Randell et al. We show that the basic operations of the relational calculus on a "contact relation" generate at least 25 relations in any model of the RCC, (...) and hence, in any standard model of mereotopology. It follows that the expressiveness of the RCC in relational logic is much greater than the original 8 RCC base relations might suggest. We also interpret these 25 relations in the the standard model of the collection of regular open sets in the two-dimensional Euclidean plane. (shrink)

We consider fragments of the relational logic RL(1) obtained by posing various constraints on the relational terms involving the operator of composition of relations. These fragments allow to express several non classical logics including modal and description logics. We show how relational dual tableaux can be employed to provide decision procedures for each of them.

Nathan Houser, Don D. Roberts and James Van Evra (eds), Studies in the Logic of Charles Sanders Peirce, In:Bloomington and Indianapolis, Indiana University Press, 1997, xiii + 653 pp. £41.95. ISBN 0-253-33020-3.

Online collection of papers by Devitt, Dretske, Guarino, Hochberg, Jackson, Petitot, Searle, Tye, Varzi and other leading thinkers on philosophy and the foundations of cognitive Science. Topics dealt with include: Wittgenstein and Cognitive Science, Content and Object, Logic and Foundations, Language and Linguistics, and Ontology and Mereology.