Terminological Logics and Conceptual Graphs: An Historical Perspective^{⋆}

Renate A. Schmidt

Max-Planck-Institut für Informatik, Im Stadtwald, 66123 Saarbrücken, Germany

Work on conceptual graphs and terminological representation systems started roughly at the same time. The first version of the conceptual graph formalism was developed in the late sixties by J. Sowa. And, terminological logics originate with the work of R. Brachman in the mid-seventies on a system called klone. However, in this Note I argue that, when studying conceptual graphs and terminological systems we should look further back than the sixties and seventies. The mathematical history of both formalisms can be traced, as far back, as the nineteenth century, to the beginnings of algebraic logic and quantification theory. The history goes back to the work of the famous American philosopher Charles Sanders Peirce. It is well-known from the writings of Sowa that his conceptual graphs are based on the existential graphs of Peirce. It is less well-known that, in essence, Peirce also developed the algebraic framework for terminological logics. In this Note I concentrate on Peirce’s algebraic treatment of sets and binary relations and the modern developments initiated and pursued by Tarski and his students and colleagues.

Terminological representation languages are first-order languages in which predicates have at most two arguments. They may be regarded as algebraic languages describing sets and relations interacting with each other. For concepts (monadic predicates) are interpreted as sets and roles (dyadic predicates) are interpreted as binary relations. Sets give rise to Boolean algebra and relations also give rise to algebras, namely relation algebras (due to Tarski [5]). Sets can be combined with relations, and these interactions have an algebraic formalisation, as well, for example, in Boolean modules [1] and Peirce algebras [2]. In [3] and [2] we show that the algebraic framework of Boolean modules and Peirce algebras accommodates most terminological representation formalisms (without number restrictions), even the most expressive ones, like KL of [6].

The history of these algebras can be traced back to the work of Boole, De Morgan, Peirce and Schröder. It was A. De Morgan (1847–1864) who started formalising the logic of binary relations as a generalisation of Aristotle’s syllogistic logic. De Morgan invented relational composition and relational converse (the terminological versions being comp and inv). Peirce (1866–1883) gave the first algebraic treatment of the algebra of relations interacting with sets. He invented the composition of a relation with a set. Whereas De Morgan was primarily interested in a paradigm of binary relations including expressions like ‘x is a lover of a servant of y’ and ‘x is master of y’ (as the converse of ‘y is a servant of x’), Peirce considered the paradigm with expressions such as ‘servant of a lover’ obtained as a product of a relation (being servant of) and a set (the set of

⋆ In Kunze, J., and Stoyan, H. (eds) (Sept. 1994), KI-94 Workshops: Extended Abstracts. Gesellschaft für Informatik, Bonn.

lovers). Brink [1] named this operation Peirce product. It is axiomatised in his Boolean modules. The terminological counterpart of the Peirce product is the existential quantifier some (the modal counterpart being the diamond modality). In fact, Peirce had at his disposal a set of operations from which we can obtain all the operations available in relation algebra, Boolean modules and Peirce algebra, in modal logics and in terminological logics. These include the universal quantification operator all (i.e. the modal box operator) which Peirce referred to as backward involution and yields expressions of the form ‘servant of none but a lover’. There is another kind of universal quantification, namely the variant used in some knowledge representation systems and modal systems for capturing the semantics of expressions like ‘servant of every lover’. This operation was called involution by Peirce. Their relational versions used already by De Morgan are known as residuals in modern algebraic terminology and can be associated with the so-called role value maps in terminological languages. In his later work Peirce even considered the numerical operations ‘at least’ and ‘at most’ (which surfaced in modal logic as operators called graded modalities).

In the history of relational algebra Peirce was followed by E. Schröder (1890– 1895) who gave an extensive treatment of the arithmetic of relation algebras. In its modern form relation algebras were introduced in A. Tarski’s seminal paper [5] of 1941. Today the study of algebras of relations (and, not only algebras of binary relations but also algebras of relations of arbitrary arity like cylindric algebras) is an established field in algebraic logic. The results have important applications in modal logic and also terminological logic and other fields of application (concerning completeness, axiomatisability, definability, duality and decidability). And, increasingly the importance to Computer Science and Artificial Intelligence of relation algebras and, in general, Boolean algebras with operators [4] is being realised and exploited. For references see [2].

The work on the algebra of classes and relative terms around 1870 led Peirce to develop quantification theory. In 1885 he gives a complete system for quantification theory with identity. Although the term ‘first-order logic’ was first used by Peirce, he did not invent and study first-order logic on its own. He was chiefly concerned with second-order logic of which first-order logic is a sub-system. Only in 1896 he introduced the graphical notation in the form of existential graphs.

References

1. C. Brink. Boolean modules. Journal of Algebra, 71(2):291–313, 1981.

2. C. Brink, K. Britz, and R. A. Schmidt. Peirce algebras. Formal Aspects of Computing, 6:1–20, 1994.

3. C. Brink and R. A. Schmidt. Subsumption computed algebraically. Computers and Mathematics with Applications, 23(2–5):329–342, 1992.

4. B. Jónsson and A. Tarski. Boolean algebras with operators, Part I & II. American Journal of Mathematics, 73 & 74:891–939 & 127–162, 1951 & 1952.

5. A. Tarski. On the calculus of relations. Journal of Symbolic Logic, 6(3):73–89, 1941.

6. W. A. Woods and J. G. Schmolze. The kl-one family. Computers and Mathematics with Applications, 23(2–5):133–177, 1992.