# «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 ...»

With quantifiers, two additional procedures must also be checked for reversibility: skolemization in step 2 and unification in step 3. In clause form, all variables are governed by universal quantifiers: ∀x1,...,∀xn.

Skolemization replaces each existential quantifier with a term t, which is a constant or a function applied to one or more of the universally quantified variables. Unification, which is discussed in Section A.3, involves universal instantiations followed by joining the pegs of functions or relations that are being unified. After the pegs are joined, rule 2e allows redundant copies of relation or function symbols to be erased.

To show that skolemization and unification are reversible with EG rules, note that the universal quantifiers of an algebraic formula correspond to lines of identity or defining nodes [*x1],...,[*xn] just inside the shaded area of the corresponding EG. To show that skolemization is reversible inside a negation, consider the following

**example, in which the skolem function s(x) replaces the variable y:**

∀x∃yR(x,y) ⇒ ∃f ∀xR(x,f(x)) ⇒ ∀xR(x,s(x)) If the left formula is true, the middle one must be true for at least one function f, and the right formula names such a function s. When negated, these implications are reversible: if the right formula is false, no function f exists for the middle one, and the left one is also false. This argument can be generalized to any number of universal quantifiers, including zero for a skolem constant.

Unification is an application of ∀-elimination followed by merging identical functions or relations applied to identical values. In EGs, it is performed by joining a subgraph that represents a constant or functional term to a line of identity followed by joining pegs according to the rule of inference discussed in Section A.3. Its inverse inside a negation corresponds to Gentzen’s ∃-introduction. In EGs, it is performed by cutting the line and erasing the subgraph. The operation of joining lines whose values are known to be identical is an equivalence that can be reversed in any area.

On broader questions about graph representations, many theoretical and computational issues remain to be explored. Stewart (1996) showed that a theorem prover based on EGs with Peirce’s rules of inference was comparable in performance to a resolution theorem prover. But the world’s fastest theorem provers depend on efficient methods for storing intermediate results and recognizing which are the most relevant at each step.

Transforming graphs to clause form can be counterproductive because it may obscure features that are important for pattern recognition. Peirce’s original inspiration for graph logic came from the graphical notations in organic chemistry, and chemists are still in the forefront of research on finding patterns in large graphs and large collections of graphs. The innovations in processing chemical graphs have led to powerful new techniques for logical graphs (Majumdar and Sowa 2009). Interdisciplinary research that combines techniques from chemistry, logic, and mathematics may lead to further breakthroughs.

As these discussions indicate, the structure of EGs and Peirce’s rules of inference can help generalize and clarify the foundations of logic and proof theory. Since each rule inserts or erases a semantic unit, those rules can be applied to any notation just by defining negative areas, positive areas, and semantic units in terms of the syntax. The rules can also be adapted to modal, intuitionistic, relevance, and nonmonotonic logics by varying the constraints on insertions and erasures. Higher-order logic uses Cantor’s hierarchy of infinities to represent a hierarchy of domains for quantifiers. Although Peirce had studied and commented on Cantor’s theories, he put his relations in the same “universe of discourse” as the individuals. In that regard, Peirce’s semantics is closer to some systems currently used in computer science, such as the model theory for Common Logic, which supports EGIF. Peirce’s voluminous manuscripts about logic are a gold mine of insights and innovations. Their relative neglect during the 20th century makes them a largely unexplored treasure for the 21st.

Appendix: EGIF Grammar The Existential Graph Interchange Format (EGIF) is a linear notation that serves as a bridge between EGs and other notations for logic. Over the years, Peirce had written manuscripts with many variants of notation, terminology, and explanations of existential graphs. Those variations have raised some still unresolved questions about possible differences in their semantics. With its formally defined semantics, EGIF provides one precise interpretation of each graph translated to it. Whether that interpretation is the one Peirce had intended is not always clear. But the EGIF interpretation serves as a fixed reference point against which other interpretations can be compared and analyzed.

EGIF is a proper subset of the Conceptual Graph Interchange Format (CGIF), which is one of the dialects of the ISO/IEC standard 24707 for Common Logic. Any statement in EGIF can be automatically processed by computer systems designed for CGIF. In this appendix, Section A.1 presents the lexical rules for the names and identifiers used in EGIF. Section A.2 presents the phrase-structure rules. Section A.3 states contextsensitive constraints and gives some examples. Section A.4 discusses the IKL extensions beyond Common Logic and their use in representing Peirce’s Gamma graphs.

A.1 Lexical Rules All EGIF syntax rules are stated as Extended Backus-Naur Form (EBNF) rules, as defined by the ISO/IEC standard 14977. The lexical rules specify names and identifiers, which exclude white space except as noted.

The phrase-structure rules specify larger combinations that may have zero or more characters of white space between constituents. Each EBNF rule is preceded by an English sentence that serves as an informative description of the syntactic category. In case of ambiguity, the EBNF rule is normative.

The following four lexical categories are defined formally in Section A.2 of ISO/IEC 24707, which is the normative specification. The brief definitions here are informative summaries. White space, which is any sequence of one or more white characters, is permitted only in quoted strings and enclosed names.

• A digit is any of the ten decimal digits from ‘0’ to ‘9’.

• An enclosedname is any sequence of Unicode characters, except control characters, preceded and followed by a double quote ‘"’. Any double quote internal to an enclosedname must be represented by the string ‘\"’. Any backslash internal to an enclosedname must be represented by the string ‘\\’.

• A letter is any of the 26 upper case letters from ‘A’ to ‘Z’ or the 26 lower case letters from ‘a’ to ‘z’.

• A white character is a space, a tab, a new line, a page feed, or a carriage return.

In addition to the above lexical categories, EGIF uses the following lexical category specified in Section B.2

**of ISO/IEC 24707:**

• An identifier consists of a letter followed by zero or more letters, digits, or underscores ‘_’.

identifier = letter, {letter | digit | '_'};

Identifiers and enclosed names are case sensitive: the identifier Apple is distinct from apple. But an identifier is considered identical to the enclosedname with the same case and spelling: Apple names the same relation type as "Apple", and apple names the same type as "apple".

A.2 Phrase-Structure Rules The EGIF phrase structure rules define a proper subset of CGIF. Unlike the lexical rules, the phrase-structure rules permit an arbitrary amount of white space between constituents. Following are two ways of writing the

**EGIF for Peirce’s Figure 4:**

~[[*x](thunder?x)~[(lightning?x)]] ~ [ [ * x ] ( thunder ? x ) ~ [ ( lightning ? x ) ] ] Every EGIF statement is also a syntactically correct CGIF statement with the same semantics. But the EGIF category names reflect the EG structure, their definitions have fewer options than the rules for CGIF, and their names begin with an upper case letter to distinguish them from the category names for CGIF. Following are the EBNF rules. The start symbol is EG.

• A bound label consists of a question mark ‘?’ and an identifier.

BoundLabel = '?', identifier;

• A coreference node consists of a left bracket ‘[’, one or more bound labels, and a right bracket ‘]’.

CoreferenceNode = '[', BoundLabel, {BoundLabel}, ']';

• A defining label consists of an asterisk ‘*’ and an identifier.

DefiningLabel = '*', identifier;

• A defining node consists of a left bracket ‘[’, a defining label, and a right bracket ‘]’.

DefiningNode = '[', DefiningLabel, ']';

• A double negation is a negation that encloses a negation and no other node. This rule is not necessary to define the syntax of EGIF, but the term is used in the inference rules 3e and 3i.

DoubleNegation = '~', '[', Negation, ']';

• An existential graph (EG) consists of zero or more nodes.

EG = {Node};

• A function consists of a left parenthesis ‘(’, a type, zero or more bound labels, a vertical bar ‘|’, a bound label, and a right parenthesis ‘)’.

Function = '(', Type, {BoundLabel}, '|', BoundLabel, ')';

• A negation consists of a symbol ‘~’, a left bracket ‘[’, an existential graph, and a right bracket ‘]’.

Negation = '~', '[', EG, ']';

• A node is one of a defining node, a coreference node, a relation, a function, or a negation.

Node = DefiningNode | CoreferenceNode | Relation | Function | Negation;

• A relation consists of a left parenthesis ‘(’, a type, zero or more bound labels, and a right parenthesis ‘)’.

Relation = '(', Type, {BoundLabel}, ')';

• A type is one of an identifier, an enclosed name, or a hash mark ‘#’ followed by a bound label.

Type = identifier | enclosedname | '#', BoundLabel;

A.3 Constraints and Examples As the grammar rule for EG shows, an existential graph is represented by zero or more nodes in EGIF. The only constraints on the nodes or their ordering are determined by the scope of defining nodes and their bound

**nodes:**

1. No defining node may be in the scope of another defining node with the same identifier.

2. Every bound label must be in the scope of its defining node.

3. Every defining node must precede (occur to the left of) any node that directly or indirectly contains one of its bound labels.

In any area, all permutations of the nodes that preserve these three constraints are equivalent.

A name enclosed in double quotes, such as "John Q. Public", can contain spaces and punctuation. In the EGIF for Peirce’s Figure 5, the identifier will_die used an underscore to represent the space, but Peirce’s choice of name could also be represented as "will die". Either option is permissible in EGIF, but they’re not interchangeable, since an underscore is not identical to a space.

Peirce treated functions as special special cases of relations. He didn’t have a notation that distinguished them from ordinary relations. In EGIF, a function can be considered a kind of relation for which the value represented by the last argument (or peg in Peirce’s terms) is uniquely determined by the values of the pegs that precede the vertical bar. The pegs to the left of the vertical bar may be called the input pegs, and the one to the right of the bar may be called the output peg. That constraint implies the following rule of inference for

**functions:**

• If f is a function with n inputs and if for every i from 1 to n, the i-th input of one instance of f is coreferent with the i-th input of another instance of f, then the output pegs of both instances may be joined.

This rule of inference is the basis for the method of unification for reasoning about combinations of functions. The EGIF grammar also allows functions with zero inputs. Every instance of such a function would have exactly the same output value, and this rule of inference would imply that the output pegs of all instances of that function may be joined.

Peirce did not introduce an EG notation for proper names or constants. Instead, he used monadic relations, such as —Alexander, which would be true of anyone named Alexander. Following is a subgraph from one of his examples (CP 4.445, Figure 80).

In EGIF, a name that is true of exactly one individual could be used as the name of a function with zero inputs. In the function ("Philippus Aureolus Theophrastus Bombastus von Hohenheim" | ?p), the bound label ?p would represent a line of identity for the unique person with that name. A name such as Alexander, which may be unique in a specific context, could be written as a function with an input peg for the context and an output peg for the person of that name: (Alexander ?c | ?p). Although Peirce did not define a notation for

**functions in EGs, the output peg of a function could be distinguished by an arrowhead in the graphic form:**

—Alexander→.

The grammar rule for Type includes an option with a hash symbol # followed by a bound label. That option supports the feature of Common Logic that allows quantified variables to range over functions and relations.

As an example, consider the sentence “There is family relation between any two members of the same

**family.” Following are two interpretations of that sentence and their representations in EGIF:**

1. “R is a relation, and if x and y are members of a family F, then x and y are related by R.” [*R] (relation ?R) ~[[*F] [*x] [*y] (family ?F) (memberOf ?x ?F) (memberOf ?y ?F) ~[ (#?R ?x ?y] ] 2. “If F is a family, then R is a relation, and if x and y are members of F, then x and y are related by R.” ~[ [*F] (family ?F) ~[ [*R] (relation ?R) ~[[*x] [*y] (memberOf ?x ?F) (memberOf ?y ?F) ~[ (#?R ?x ?y] ] ] ] The first line of the second EGIF could also be read “For any family F, there is a relation R...” Note that EGIF allows bound labels that refer to relations to occur in the argument position (peg) of another relation or with the prefix # in the type position. For Gamma graphs, which are discussed in the next section, Peirce experimented with graphical ways of representing such options.