This chapter aims to give an introduction into the formal theory of conceptual graphs (abbreviated by CGs), with an emphasis on how CGs can be understood as a diagrammatic approach to formal logic. Of course, as it can already easily be seen from the huge variety of topics covered in this book, formal logic is only one of many aspects of CGs. Anyhow, maybe not the majority, but at least a vast amount of CG research has focused on this specific facet, and even Sowa emphasizes the logic aspect of CGs. CGs are based on diagrammatic representation of logic, namely Peirce’s

(1839-1914) existential graphs (for introductions into existential graphs, see [Zeman, 1964, Roberts, 1973, Shin, 2002]). In [Sowa, 1997a] Sowa writes that ‘conceptual graphs (CGs) are an extension of existential graphs with features adopted from linguistics and AI. The purpose of the system is to express meaning in a form that is logically precise, humanly readable, and computationally tractable.’ The system of existential graphs is divided into three parts named Alpha,

Beta, and Gamma. Alpha corresponds to propositional logic, and Beta corresponds to first-order predicate logic. Gamma is more complicated: It covers features of higher order and modal logic, the possibility to express selfreference, and other features. Due to its complexity, it was not completed by Peirce. Peirce’s existential graphs and Sowa’s CGs cannot be directly compared. Sowa adopted many ideas of existential graphs, even from Gamma,

but CGs have a different and richer syntax, and they are tailored to better suit the needs of contemporary knowledge representation systems. Anyhow, Sowa’s goal CGs to be “logically precise” and his reference to existential graphs clearly hints to the logical alignment of CGs. This is more explicitely expressed in [Sowa, 2000b], where Sowa states that ‘CGs have been developed as a graphic representation for logic with the full expressive power of first-order logic and with extensions to support metalanguage, modules, and namespaces.’ In the following, we scrutinize CGs in terms of formal logic. First, in Sec-

tion 2.2, we give a short introduction into CGs, as they have been introduced by Sowa. In this section, some core notations of CGs are defined. Next, in Section 2.3, we briefly investigate whether Sowa’s CGs are indeed “logically precise,” and we will see that they do not suit the needs of contemporary formal logic. For this reason, much research on the formal theory of CGs aims to fix the formal gaps and flaws of CGs. In Section 2.4, an overview over different approaches to turn CGs into a mathematically precise system of logic is given, and a core notation for a formal theory is provided. In different works, different fragments of CGs are elaborated in a precise manner. An overview of these fragments is given in Section 2.5. A final remark to the definitions in the following sections has to be made.

Different authors have used different notations, and the following definitions aim to select the most convenient ones among these. A term that is defined as it is used in this chapter is set in small caps, like vocabulary. If we refer to a notation that is not used in this volume, it is set in italics, like support.