From Textop Wiki
←Older revision | Newer revision→
|The article below may contain errors of fact, bias, grammar, etc. The Citizendium Foundation and the participants in the Citizendium project make no representations about the reliability of this article or, generally, its suitability for any purpose. We make this disclaimer of all Citizendium article versions that have not been specifically approved.|
An existential graph is an element of a graph-theoretic formal system that affords a representation of logical expressions. This system was invented by Charles Sanders Peirce, who wrote his first paper on graphical logic in 1882 and continued to develop the method until his death in 1914.
Peirce proposed three systems of existential graphs:
- alpha, isomorphic to sentential logic and the two-element Boolean algebra;
- beta, isomorphic to first-order logic with identity, with all formulas closed;
- gamma, (nearly) isomorphic to normal modal logic.
Alpha nests in beta and gamma. Beta does not nest in gamma, quantified modal logic being more than even Peirce could envisage.
The syntax is:
- The blank page;
- Single letters or phrases written anywhere on the page;
- Objects (subgraphs) enclosed by a simple closed curve called a cut or sep. A cut can be empty. Cuts can be nested and concatenated at will but must never intersect.
Any well-formed part of a graph is a subgraph.
The semantics are:
- The blank page denotes Truth;
- Letters, phrases, subgraphs, and entire graphs can be True or False;
- To surround objects with a cut is equivalent to logical negation or Boolean complementation. Hence an empty cut denotes False;
- All objects within a given cut are tacitly conjoined.
Hence the alpha graphs are a minimalist notation for sentential logic, grounded in the expressive adequacy of And and Not. The alpha graphs constitute a radical simplification of the two-element Boolean algebra and the truth functors.
The depth of an object is the number of cuts that enclose it.
Rules of inference:
- Insertion - Any subgraph may be inserted into an odd numbered depth.
- Erasure - Any subgraph in an even numbered depth may be erased.
Rules of equivalence:
- Double cut - A pair of cuts with nothing between them may be drawn around any subgraph. Likewise two nested cuts with nothing between them may be erased. This rule is equivalent to Boolean involution.
- Iteration/Deiteration ? To understand this rule, it is best to view a graph as a tree structure having nodes and ancestors. Any subgraph P in node n may be copied into any node depending on n. Likewise, any subgraph P in node n may be erased if there exists a copy of P in some node ancestral to n (i.e., some node on which n depends). For an equivalent rule in an algebraic context, see C2 in Laws of form.
A proof manipulates a graph by a series of steps, with each step justified by one of the above rules, until the graph is reduced to an empty cut or the blank page. A graph that can be so reduced is what is now called a tautology (or the complement thereof). A tautologically true formula is one whose graph simplifies to the blank page. Graphs that cannot be simplified beyond a certain point are analogues of the satisfiable formulas of first order logic.
Peirce notated predicates using intuitive English phrases; the standard notation of contemporary logic, capital Latin letters, may also be employed. A dot asserts the existence of some individual in the domain of discourse. Multiple instances of the same object are linked by a line, called the "line of identity". There are no literal variables or quantifiers in the sense of first order logic. A line of identity connecting two or more predicates can be read as asserting that the predicates share a common variable. The presence of lines of identity requires modifying the alpha rules of Equivalence.
The beta graphs can be read as employing implicitly quantified variables, as a system in which all formula are to be taken as closed. If the "shallowest" part of a line of identity has even (odd) depth, the associated variable would be tacitly existentially (universally) quantified. The beta graphs appear to streamline first order logic with identity, but the secondary literature is not in agreement on just how this is accomplished. Peirce's writings do not address this question, because first order logic was first clearly defined only with the 1928 first edition of David Hilbert and Wilhelm Ackermann's Principles of Theoretical Logic.
Add to alpha a second kind of simple closed curve, written using a dashed rather than a solid line, to alpha. The resulting second style of cut can be read as the primitive unary operator of modal logic.
Zeman (1964) was the first to note that:
- The beta graphs are isomorphic to the predicate calculus (Roberts 1973 and Shin 2002 discuss this finding at length);
- Straightforward emendations of the gamma graphs yield the well-known modal logics S4 and S5. Hence the gamma graphs can be read as a peculiar form of normal modal logic. This finding of Zeman's has gone unremarked to this day.
The existential graphs are a curious offspring of the marriage of Peirce the logician/ mathematician with Peirce the founder of a major strand of semiotics. In a series of papers beginning in 1867, and culminating with his classic paper in the 1885 American Journal of Mathematics, Peirce developed much of the two-element Boolean algebra, propositional calculus, quantification and the predicate calculus, and some rudimentary set theory, and extended De Morgan's relation algebra, stopping short of the metalogic (something which eluded even Principia Mathematica). But his evolving semiotic theory led him to doubt the value of logic formulated using conventional linear typography, and to believe that logic and mathematics are best captured by a notation embedded in two (or even three) dimensions. Frege's 1879 Begriffschrifft independently reached the same conclusion, but employing a notation very different from Peirce's.
Peirce's first published paper on graphical logic (reprinted in vol. 3 of his Collected Papers) proposed a system dual (in effect) to the alpha existential graphs, called the entitative graphs. He immediately abandoned this formalism in favor of the existential graphs.
Peirce's graphical logic is but one of his many accomplishments in logic and mathematics (on which see Charles Peirce). Unnoticed during his lifetime, his graphical logic was invariably denigrated or ignored after his death, until the Ph.D. theses by Roberts (1963) and Zeman (1964).
- 1931-35. The Collected Papers of C.S. Peirce. Pp 320-470 of vol. 4 constitute the locus citandum for the existential graphs. Available online as 4.372-417 and 4.418-529.
- 1992. Reasoning and the Logic of Things. Ketner, K. L., and Hilary Putnam, eds.. Harvard University Press.
- 2001. Semiotic and Significs: The Correspondence between C.S. Peirce and Victoria Lady Welby. Hardwick, C.S., ed. Lubbock TX: Texas Tech University Press.
- A transcription of Peirce's MS 514, edited with commentary by John Sowa.
As of this writing, the chronological critical edition of Peirce's works, the Writings, extends only to 1890. Much of Peirce's work on logical graphs consists of manuscripts written after that date and still unpublished. Hence our understanding of Peirce's graphical logic is likely to change as the remaining 25 volumes of the chronological edition appear.
- Hammer, Eric M., 1998, "Semantics for Existential Graphs," Journal of Philosophical Logic 27: 489 - 503.
- Roberts, Don D., 1973. The Existential Graphs of C.S. Peirce. John Benjamins. The definitive version of his 1963 thesis.
- Shin, Sun-Joo, 2002. The Iconic Logic of Peirce's Graphs. MIT Press.
- Stanford Encyclopedia of Philosophy: Peirce's Logic by Eric Hammer. Employs parentheses notation.
- Van Heuveln, Bram, "Existential Graphs." Dept. of Cognitive Science, Rensselaer Polytechnic University. Alpha only.
- Gottschall, Christian, Proof Builder ? Java applet for deriving Alpha graphs.
- Portions of the above article are adapted from an earlier version of the Wikinfo article, "Existential graph", used under the GNU Free Documentation License.
- Portions of the above article are adapted from an earlier version of the Wikipedia article, "Existential graph", used under the GNU Free Documentation License.
Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation; with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A copy of the license is included in the section titled GNU FDL text.