main-content

## Über dieses Buch

The calculus of relations has been an important component of the development of logic and algebra since the middle of the nineteenth century, when Augustus De Morgan observed that since a horse is an animal we should be able to infer that the head of a horse is the head of an animal. For this, Aristotelian syllogistic does not suffice: We require relational reasoning. George Boole, in his Mathematical Analysis of Logic of 1847, initiated the treatment of logic as part of mathematics, specifically as part of algebra. Quite the opposite conviction was put forward early this century by Bertrand Russell and Alfred North Whitehead in their Principia Mathematica (1910 - 1913): that mathematics was essentially grounded in logic. Logic thus developed in two streams. On the one hand algebraic logic, in which the calculus of relations played a particularly prominent part, was taken up from Boole by Charles Sanders Peirce, who wished to do for the "calculus of relatives" what Boole had done for the calculus of sets. Peirce's work was in turn taken up by Schroder in his Algebra und Logik der Relative of 1895 (the third part of a massive work on the algebra of logic). Schroder's work, however, lay dormant for more than 40 years, until revived by Alfred Tarski in his seminal paper "On the calculus of binary relations" of 1941 (actually his presidential address to the Association for Symbolic Logic).

## Inhaltsverzeichnis

### Chapter 1. Background Material

Abstract
This chapter serves the rest of the book: all later chapters presuppose it. It introduces the calculus of binary relations, and relates it to basic concepts and results from lattice theory, universal algebra, category theory and logic. It also fixes the notation and terminology to be used in the rest of the book. Our aim here is to write in a way accessible to readers who desire a gentle introduction to the subject of relational methods. Other readers may prefer to go on to further chapters, only referring back to Chapt. 1 as needed.
Peter Jipsen, Chris Brink, Gunther Schmidt

### Chapter 2. Relation Algebras

Abstract
The contemporary theory of relation algebras is a direct outgrowth of the nineteenth century calculus of relations. After a few examples illustrating the calculus of relations (the most widely applied part of the subject), this chapter touches upon some topics in the algebraic theory of relation algebras: basic definitions, examples, constructions, elementary arithmetical theory, general algebraic results, representation theorems with applications, and connections with logic, including Tarski’s formalization of set theory without variables.

### Chapter 3. Heterogeneous Relation Algebra

Abstract
So far, relational algebra has been presented in its classical form. Relations are often conceived as something that might be called quadratic or homogeneous; a relation over a set. It is interpreted as a subset RU × U of a Cartesian product of the universe U with itself. If relations between two or more sets are considered, this may easily be subsumed under this view, uniting all the sets in question into one huge set and calling this set the universe U. On the other hand, a variant of the theory has evolved that treats relations from the very beginning as heterogeneous or rectangular, i.e. as relations where the normal case is that they are relations between two different sets. The present chapter is devoted to this variant form.
Gunther Schmidt, Claudia Hattensperger, Michael Winter

### Chapter 4. Fork Algebras

Abstract
In this chapter we present the class of fork algebras, an extension of relation algebras with an extra operator called fork. We will present results relating fork algebras both to logic and to computer science. The interpretability of first-order theories as equational theories in fork algebras will provide a tool for expressing program specifications as fork algebra equations. Furthermore, the finite axiomatizability of this class of algebras will be shown to have deep influence in the process of program development within a relational calculus based on fork algebras.
Armando Haeberer, Marcelo Frias, Gabriel Baum, Paulo Veloso

### Chapter 5. Relation Algebra and Modal Logics

Abstract
This chapter gives an introduction to modal logics as seen from the context of relation algebra. We illustrate this viewpoint with an example application: verification of reactive systems. In the design of safety-critical software systems formal semantics and proofs are mandatory. Whereas for functional systems (computing a certain function) usually denotational semantics and Hoare-style reasoning is employed, reactive systems (reacting to an environment) mostly are modelled in an automata-theoretic framework, with a modal or temporal logic proof system. Much of the success of these logics in the specification of reactive systems is due to their ability to express properties without explicit use of first-order variables. For example, consider a program defined by the following transition system:
Holger Schlingloff, Wolfgang Heinle

### Chapter 6. Relational Formalisation of Nonclassical Logics

Abstract
The purpose of this chapter is to present and motivate the application of algebras of relations to the formalisation of nonclassical logics. It is shown that a suitably defined relational logic can serve as a general framework for developing nonclassical means of reasoning that are needed in many application areas.
Ewa Orlowska

### Chapter 7. Linear Logic

Abstract
Linear logic, introduced by Jean-Yves Girard [Girard 1987], has aroused considerable interest among logicians and theoretical computer scientists. Among other things, linear logic is said to be a resource-conscious logic and a logic of actions. According to Girard [Girard 1995], it should be viewed as an extension of classical logic, rather than as an alternative logic.
Jules Desharnais, Bernard Hodgson, John Mullins

### Chapter 8. Relational Semantics of Functional Programs

Abstract
The natural meaning of a program written in a functional language like Lisp or ML is a (possibly partial) function. Functions are relations, and this chapter is a gentle introduction to the idea of regarding functional programs as elements of a relational algebra. Using relations rather than functions we avoid the complexity introduced by artificial bottom elements denoting undefinedness. Relations are also natural candidates for modelling non-determinate or set-valued functions. However, the main reason for using relations is that they can be calculated with so well. Using equational reasoning for functional programs, we can construct proofs that are intuitive, memorable and machine-checkable. One basic ingredient of functional programs — composition of functions — is a built-in operator of the relational calculus. Other control constructs as well as concrete data must be translated into the language of relations. We shall attempt to do this in a modular fashion, treating one construct at a time.
Rudolf Berghammer, Burghard von Karger

### Chapter 9. Algorithms from Relational Specifications

Abstract
The purpose of a specification is to state a problem as clearly as possible. In many cases, the most direct and intuitive way to specify a problem is by writing down a logical predicate that describes its possible solutions. Here, we employ the calculus of relations for developing efficient algorithms from problem specifications.
Rudolf Berghammer, Burghard von Karger

### Chapter 10. Programs and Datatypes

Abstract
We are programmers, in the sense that it is our concern to improve the process of program construction. Therefore we want to answer questions like: What is programming, why is it so difficult and error-prone, and how can we learn what is needed to make the process more manageable? In the following we shall address these issues in a relational framework. Section 10.1 gives an introductory overview explaining the background to our approach. Section 10.2 shows how we deal with (recursive and non-recursive) datatypes in the relational framework. Section 10.3 discusses programs in this context, concentrating on a class of programs characterized by relational equations of a specific but quite general shape. Program termination is the subject of Section 10.4. Finally, Section 10.5 briefly touches on the design and execution of (terminating) programs. For a more extensive treatment see [Doornbos 1996].
Henk Doornbos, Netty van Gasteren, Roland Backhouse

### Chapter 11. Refinement and Demonic Semantics

Abstract
In Chapter 8, it was shown how functional programs can be regarded as elements of a relation algebra. In this chapter, we consider imperative programs, which we view as computing an input-output relation on a set of states. We are interested here in programs that are meant to terminate, not in reactive programs. Our programming language is Dijkstra’s language of guarded commands [Dijkstra 1976], which allows the expression of nondeterminism, thus making a relational approach very natural.
Jules Desharnais, Ali Mili, Thanh Tung Nguyen

### Chapter 12. Tabular Representations in Relational Documents

Abstract
In this chapter the use of relations, represented as tables, for documenting the requirements and behaviour of software is motivated and explained. A formal model of tabular expressions, defining the meaning of a large class of tabular forms, is presented. Finally, we discuss the transformation of tabular expressions from one form to another, and illustrate some useful transformations.
Ryszard Janicki, David Lorge Parnas, Jeffery Zucker

### Chapter 13. Databases

Abstract
Since Codd introduced the relational database model and functional dependencies [Codd 1970], the semantics of relationships between the attributes of a database has been extensively studied by many computer scientists. In this chapter we introduce an application of the calculus of binary relations to the (n-ary) relational database model. This consists of using the notion of difunctional relations to define difunctional dependencies in the relational database model. Difunctional dependencies are weaker than functional dependencies, but more regular than the other well-known dependencies.
Ali Jaoua, Nadir Belkhiter, Habib Ounalli, Théodore Moukam

### Chapter 14. Logic, Language, and Information

Abstract
The rapidly evolving interdisciplinary field of Logic, Language and Information (LLI) treats a variety of topics, ranging from knowledge representation to the syntax, semantics and pragmatics of natural language. Moreover, it does so from a variety of perspectives. However, one word more than any other gives the flavour of much contemporary work in LLI: dynamics. The purpose of this chapter is twofold. First, we give an impression of what LLI is and why dynamics plays such a fundamental role there. Second, we relate the study of dynamics to relation algebra. The essential point that will emerge is that many LLI approaches to dynamics can be naturally viewed as explorations of fragments of relation algebra via their set-theoretic representations.
Patrick Blackburn, Maarten de Rijke, Yde Venema

### Chapter 15. Natural Language

Abstract
The purpose of this chapter is to show how relational algebra can be applied to the semantics of natural language. The use of relational algebra for natural language semantics was first proposed in [Suppes 1976] under the heading of relational grammar in the context of model theory. It was extended to various areas of English such as modification of nouns by adjectives [Suppes, Macken 1978], intonation [Suppes 1979b], rules of natural language inference [Suppes 1979a], anaphoric pronouns [Böttner 1992b] and [Böttner 1996], and coordination [Böttner 1994]. An extension to a procedural semantics was proposed in [Böttner 1992a]. Most of Suppes’ articles have now become easily accessible in [Suppes 1991].
Michael Böttner

### Backmatter

Weitere Informationen