«1. Peirce’s Method for Teaching Logic Peirce’s existential graphs (EGs) are the simplest, most elegant, and easiest-to-learn system of logic ever ...»
Peirce’s Tutorial on Existential Graphs
John F. Sowa
Abstract. In his formal papers on existential graphs, Peirce tended to obscure the simplicity of EGs with
distracting digressions. In MS 514, however, he presented his simplest introduction to the EG syntax,
semantics, and rules of inference. This article reproduces Peirce’s original words and diagrams with further
commentary, explanations, and examples. Unlike the syntax-based approach of most current textbooks,
Peirce’s method addresses the semantic issues of logic in a way that can be transferred to any notation. The concluding section shows that his rules of inference can clarify the foundations of proof theory and relate diverse methods, such as resolution and natural deduction. To relate EGs to other notations for logic, this article uses the Existential Graph Interchange Format (EGIF), which is a subset of the CGIF dialect of Common Logic. EGIF is a linear notation that can be mapped to and from the Alpha, Beta, and Gamma variants of EGs. It can also be translated to or from other formalisms, algebraic or geometrical.
This is a revised preprint of an article that appeared in Semiotica, 186:1-4, 345-394.
1. Peirce’s Method for Teaching Logic Peirce’s existential graphs (EGs) are the simplest, most elegant, and easiest-to-learn system of logic ever invented. Yet most logicians have never used them or even seen them. Part of the reason for their neglect is that the algebraic notation by Peirce (1880, 1885) with a change of symbols by Peano (1889) had already become the de facto standard for logic. Another reason is the complexity of Peirce’s published explanations, which obscured the simplicity of the graphs with a mass of detail about important, but often distracting semiotic issues. In 1909, however, Peirce wrote Manuscript 514, which contains his clearest tutorial on existential graphs. In just 12 hand-written pages with 18 diagrams, he presented the syntax, rules of inference, and illustrative examples for first-order logic with equality. The full MS 514, however, wanders into digressions on subjects ranging from anomalies in the orbit of Mercury to a criticism of Laplace’s theory of probability. This article extracts just the words and diagrams of the tutorial and adds more examples and commentary.
A remarkable feature of the tutorial is that Peirce does not follow the common practice of teaching the Boolean operators before introducing quantifiers. Unlike his more formal publications on EGs, this tutorial does not distinguish the Alpha graphs for propositional logic from the Beta graphs for predicate logic.
Instead, Peirce returns to a notation he experimented with in 1882: the relational graphs, which combine the existential quantifier with an implicit conjunction. His first example, —man, represents the sentence “There is a man.” The line —, which Peirce called a lineof identity, represents an existential quantifier (∃x), and the string “man” is the name of a monadic predicate asserted of x. With the addition of ovals to represent negation, these graphs become sufficiently general to represent full first-order logic with equality. In five pages, Peirce presents the syntax with examples; in another six pages, he presents sound and complete rules of inference illustrated with sample proofs; and in less than half a page, he adds some remarks about endoporeutic, which is a version of model theory that is logically equivalent to Tarski’s.
Section 2 of this article reproduces Peirce’s presentation of EG syntax, adds more examples, and for each diagram shows the equivalent formula in Peirce-Peano notation and in the Existential Graph Interchange Format (EGIF). Section 3 reproduces Peirce’s rules of inference and illustrative proofs; the commentary adds further examples and shows that the rules are complete by using them to derive the more common rules of modus ponens and universal instantiation. Section 4 presents endoporeutic and uses it to prove that Peirce’s rules are sound. Section 5 recommends Peirce’s approach as a basis for teaching introductory courses on logic, and Section 6 presents theoretical principles that are simplified and clarified by EGs and Peirce’s rules. The appendix presents the grammar of EGIF and discusses its relationship to the ISO/IEC standard 24707 for Common Logic and the proposed IKL extensions to Common Logic.
2. Syntax for First-Order Logic with Equality In this article, Peirce’s actual words and diagrams are presented in indented paragraphs; the commentary is not indented. Peirce numbered some of his diagrams, but not others. To avoid multiple numbering systems, Peirce’s numbers are retained. Graphs that are not numbered are discussed only in the immediately preceding or following paragraphs. Peirce’s graphs are nested in the indented paragraphs; all other graphs are part of
the commentary. The tutorial begins at the bottom of page 10 of MS 514; the emphasis is by Peirce:
I invented several different systems of signs to deal with relations. One of them is called the general algebra of relations, and another the algebra of dyadic relations. I was finally led to prefer what I call a diagrammatic syntax. It is a way of setting down on paper any assertion, however intricate, and if one so sets down any premises, and then (guided by 3 simple rules) makes erasures and insertions, he will read before his eyes a necessary conclusion from premises.
This syntax is so simple that I will describe it. Every word makes an assertion. Thus, —man means “there is a man” in whatever universe the whole sheet offers it. The dash before “man” is the “line of identity.” this means “Some man eats a man.” This graph has two lines of identity: the curve on the left, and the straight line on the right. In the algebraic notation, each line of identity corresponds to an existential quantifier, which Peirce represented by the Greek letter Σ.
The graph could therefore be represented by the following formula in Peirce’s notation of 1880 to 1885:
Σx Σy (manx • many • eatsx,y).
Since Peano wanted to use logic for reasoning about mathematics, he replaced Peirce’s symbols with symbols that could be freely mixed with mathematical formulas. Peano gave full credit to Peirce for the notation and declared Frege’s notation unreadable. With Peano’s symbols, the graph for “Some man eats a man” would be expressed by the formula ∃x∃y(man(x) ∧ man(y) ∧ eats(x,y)).
EGIF has a one-to-one mapping to and from each feature of the graph. Since the EG has two lines of identity
and three relations, the corresponding EGIF has five components called nodes:
[*x] [*y] (man ?x) (man ?y) (eats ?x ?y).
The first two nodes, [*x] and [*y], represent the two lines of identity. The character strings x and y are called identifiers. An identifier prefixed with an asterisk, such as *x, is called a defining label. An identifier prefixed with a question mark, such as ?x, is called a bound label that is bound to the defining label with the same identifier. The three nodes in parentheses represent the three relations. Inside each relation node is the name of the relation type followed by a list of bound labels. The left-to-right order of the bound labels is the same as the order in which the corresponding lines of identity are attached to the relation names in the graph. A defining label and all bound labels with the same identifier are said to be coreferent because they refer to the same individual.
EGIF has no marker for conjunction, since there is an implicit conjunction of all nodes in the same area.
Since a graph drawn on a two-dimensional sheet has no linear ordering, the only constraint on the ordering of the nodes is that a defining label must precede all coreferent bound labels. All permutations that preserve this constraint are logically equivalent. See the appendix for the full syntax of EGIF.
To deny that there is any phoenix, we shade that assertion which we deny as a whole:
Thus what I have just scribed means “It is false that there is a phoenix.” But the following:
only means “There is something that is not identical with any phoenix.” To indicate negation in his original version of EGs, Peirce used an unshaded oval enclosure, which he called a cut or sometimes a sep because it separated the sheet of assertion into a positive (outer) area and a negative (inner) area. In MS 514, he added shading to highlight the distinction between positive and negative areas.
Without the shaded oval, the graph —phoenix would assert that there exists a phoenix. In Figure 1, the entire graph is negated, but in Figure 2, part of the line is outside the negation. The following table shows the EGIF
and formula for the unshaded graph, for Figure 1, and for for Figure 2:
The EGIF for Figure 1 encloses the EGIF for the unshaded graph in square brackets and places the symbol ~ in front. The formula places the symbol ~ in front, and its implicit scope extends to the end of the formula.
When a line crosses one or more negations, the defining label in EGIF or the corresponding existential quantifier in the algebraic formula is placed in the outermost area in which any part of the line occurs. Unlike Figure 1, which asserts the negation before the quantifier, Figure 2 asserts the quantifier before the negation.
When an oval is drawn inside another oval, the doubly nested area is positive (unshaded), as in Figure 3.
Any area nested inside an odd number of ovals is shaded, and any area inside an even number of ovals (possibly zero) is unshaded.
Fig. 3 denies fig. 4, which asserts that it thunders without lightning, for a denial shades the unshaded and unshades the shaded. Consequently fig. 3 means “If it thunders, it lightens.”
The following table shows the EGIF and formulas for Figures 3 and 4:
In the algebraic notation, ~∃ is equivalent to ∀~. With that conversion, the formula for Figure 3 becomes ∀x~(thunder(x) ∧ ~lightning(x)). By Peirce’s definition of the implication operator, ~(p ∧ ~q) is equivalent to p⊃q. Therefore, the formula for Figure 3 can be rewritten as ∀x(thunder(x) ⊃ lightning(x)). This corresponds to Peirce’s reading “If it thunders, it lightens.” Peirce also said that a negated area can be read disjunctively. By De Morgan’s law, the formula ∀x~(thunder(x) ∧ ~lightning(x)), is converted to ∀x(~thunder(x) ∨ lightning(x)), which may be read “For every x, either x does not thunder or x lightens.” For his algebraic notation, Peirce introduced the symbol Π for the universal quantifier and for implication, but he did not use them in existential graphs. The Conceptual Graph Interchange Format (CGIF), which is a superset of EGIF defined by the ISO standard, does have symbols for those operators. But EGIF is limited to the symbols that Peirce actually used in existential graphs. The major reason why he never added the additional symbols to EGs is that they are unnecessary: the graphic notation of nested ovals, especially with shading, is already more readable than the algebraic notation even with special symbols. Furthermore, new symbols would have made his rules of inference more complicated.
In order to make the lines of identity in their connexion with shading and its absence perfectly perspicuous, I must provide you with a bit or two of nomenclature. By an “area,” then, I mean the whole of any continuous part of the surface on which graphs are scribed that is alike in all parts of it either shaded or unshaded. By a “graph” I mean the way in which a given assertion is scribed. It is the general kind not a single instance. For example there is in English but one single “word” that serves as definite article. It is the word “the.” It will occur some twenty or more times on an average page; and when an editor asks for an article of so many thousand of “words” he means to count each of those instances as a distinct word. He speaks loosely of instances of words as words, which they are not.
The distinction between a graph as a general type and particular instances of it is important for the rules of inference, which are presented in Section 3 below.
Now in like manner a graph is one thing, and a “graph instance” is another thing. Any expression of an assertion in this particular diagrammatic syntax is an Existential Graph, of which I use the single word “graph” as a common abbreviation as long as I have nothing to do with another kind of graph. A graph then may be complex or indivisible. Thus is a graph instance composed of instances of three indivisible graphs which assert “there is a male” “there is something human” and “there is an African.” The syntactic junction or point of teridentity asserts the identity of something denoted by all three.
A teridentity is represented by a coreference node [?x ?y ?z], which shows that three lines of identity refer to the same individual. Following is a direct translation of the above graph to EGIF, an equivalent EGIF with a
single defining node for all three lines, and the corresponding algebraic formula:
[*x] (male ?x) [*y] (human ?y) [*z] (African ?z) [?x ?y ?z] [*x] (male ?x) (human ?x) (African ?x) ∃x(male(x) ∧ human(x) ∧ African(x)) Peirce used the term ligature for a connection of two or more lines of identity. Each ligature can be represented by a coreference node in EGIF, and coreference nodes can often be simplified or eliminated by renaming labels, as in this example. Dau (2010) analyzed various examples of ligatures in Peirce’s writings.
Indivisible graphs usually carry “pegs” which are places on their periphery appropriated to denote, each of them, one of the subjects of the graph. A graph like “thunders” is called a “medad” as having no peg (though one might have made it mean “some time it thunders” when it would require a peg). A graph or graph instance having 0 peg is medad, having 1 peg is monad, having 2 pegs is dyad, or having 3 pegs is triad.
In modern terminology, Peirce’s indivisible graphs are called atoms. In the algebraic notation, each atom consists of a single predicate or relation with its associated arguments, which Peirce called logical subjects.