Existential graph

An '''existential graph''' is a type of [[diagram]]matic or visual notation for logical expressions, proposed by [[Charles Sanders Peirce]], who wrote his first paper on [[logical graph|graphical logic]] in 1882, and continued to develop the method until his death in 1914. ==The graphs== Peirce proposed three systems of existential graphs: * ''alpha'', [[isomorphism|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. ===Alpha=== [[Image:PeirceAlphaGraphs.svg|thumb|300px|Alpha Graphs]] The [[syntax]] is: *The blank page; *Single letters or phrases written anywhere on the page; *Any graph may be enclosed by a [[simple closed curve]] called a ''cut'' or ''sep''. A cut can be empty. Cuts can nest and concatenate 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 may be '''True''' or '''False'''; *To enclose a subgraph with a cut is equivalent to logical [[negation]] or Boolean [[complementation]]. Hence an empty cut denotes '''False'''; *All subgraphs within a given cut are tacitly [[conjunction (logic)|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 [[connective (logic)|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 [[Node (computer science)|node]]s and [[tree structure|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. If a graph can be reduced by steps to the blank page or an empty cut, it is what is now called a [[Tautology (logic)|tautology]] (or the complement thereof). Graphs that cannot be simplified beyond a certain point are analogues of the [[satisfiable]] [[formula]]s of [[first-order logic]]. ===Beta=== Peirce notated [[Predicate (logic)|predicate]]s 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 [[Variable (mathematics)|variables]] or [[quantifier]]s 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 a system in which all formula are to be taken as closed, because all variables are implicitly quantified. If the "shallowest" part of a line of identity has even (odd) depth, the associated variable is tacitly [[existential quantifier|existentially]] ([[universal quantifier|universally]]) quantified. [http://www.clas.ufl.edu/users/jzeman/ Zeman (1964)] was the first to note that the ''beta'' graphs are [[isomorphism|isomorphic]] to [[first-order logic]] with {{dn|identity}} (also see Zeman 1967). However, the secondary literature, especially Roberts (1973) and Shin (2002), does not agree on just how this is so. Peirce's writings do not address this question, because first-order logic was first clearly articulated only some years after his death, in the 1928 first edition of [[David Hilbert]] and [[Wilhelm Ackermann]]'s ''[[Principles of Mathematical Logic]]''. ===Gamma=== Add to the syntax of ''alpha'' a second kind of [[simple closed curve]], written using a dashed rather than a solid line. Peirce proposed rules for this second style of cut, which can be read as the primitive [[unary operation|unary operator]] of [[modal logic]]. [http://www.clas.ufl.edu/users/jzeman/ Zeman (1964)] was the first to note that straightforward emendations of the ''gamma'' graph rules yield the well-known [[modal logic|modal logics S4]] and [[S5 (modal logic)|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. ==Peirce's role== The existential graphs are a curious offspring of [[Charles Sanders Peirce|Peirce]] the [[logic]]ian/ mathematician with Peirce the founder of a major strand of [[semiotics]]. Peirce's graphical logic is but one of his many accomplishments in logic and mathematics. 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 logic|propositional calculus]], [[quantification]] and the [[first-order logic|predicate calculus]], and some rudimentary [[set theory]]. [[model theory|Model theorists]] consider Peirce the first of their kind. He also extended De Morgan's [[relation algebra]]. He stopped short of metalogic (which eluded even ''[[Principia Mathematica]]''). But Peirce's evolving [[semiotic]] theory led him to doubt the value of logic formulated using conventional linear notation, and to prefer that logic and mathematics be notated in two (or even three) dimensions. His work went beyond [[Euler circle|Euler's diagrams]] and [[Venn]]'s revision thereof. [[Frege]]'s 1879 ''[[Begriffsschrift]]'' also employed a two-dimensional notation for logic, but one 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 graph]]s. He very soon abandoned this formalism in favor of the existential graphs. The graphical logic went unremarked during his lifetime, and was invariably denigrated or ignored after his death, until the Ph.D. theses by Roberts (1964) and [http://www.clas.ufl.edu/users/jzeman/ Zeman (1964)]. ==See also== * [[Ampheck]] * [[Conceptual graph]] * [[Entitative graph]] * [[Logical graph]] ==References== ===Primary literature=== *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 [http://www.existentialgraphs.com/peirceoneg/existentialgraphs4.372-417.htm 4.372-417] and [http://www.existentialgraphs.com/peirceoneg/existentialgraphs4.418-529.htm 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. *[http://www.jfsowa.com/peirce/ms514.htm 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 ''[http://www.iupui.edu/~peirce/ Writings]'', extends only to 1890. Much of Peirce's work on [[logical graph]]s 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. ===Secondary literature=== * Hammer, Eric M., 1998, "Semantics for Existential Graphs," ''Journal of Philosophical Logic 27'': 489 - 503. * Roberts, Don D., 1964, "Existential Graphs and Natural Deduction" in Moore, E. C., and Robin, R. S., eds., ''Studies in the Philosophy of C. S. Peirce, 2nd series''. Amherst MA: University of Massachusetts Press. The first publication to show any sympathy and understanding for Peirce's graphical logic. *--------, 1973. ''The Existential Graphs of C.S. Peirce.'' John Benjamins. An outgrowth of his 1963 thesis. * Shin, Sun-Joo, 2002. ''The Iconic Logic of Peirce's Graphs''. MIT Press. * Zeman, J. J., 1964, ''[http://www.clas.ufl.edu/users/jzeman/ The Graphical Logic of C.S. Peirce.]'' Unpublished Ph.D. thesis submitted to the [[University of Chicago]]. * --------, 1967, "A System of Implicit Quantification," ''Journal of Symbolic Logic 32'': 480-504. ==External links== * [[Stanford Encyclopedia of Philosophy]]: [http://setis.library.usyd.edu.au/stanford/entries/peirce-logic/#EG Peirce's Logic] by [[Eric Hammer]]. Employs parentheses notation. * Dau, Frithjof, [http://www.dr-dau.net/eg_readings.shtml Peirce's Existential Graphs --- Readings and Links.] An annotated bibliography on the existential graphs. * Gottschall, Christian, [http://logik.phl.univie.ac.at/~chris/gateway/formular-uk-peirce.html Proof Builder] — Java applet for deriving Alpha graphs. * Liu, Xin-Wen, "[http://philosophy.cass.cn/facu/liuxinwen/01.htm The literature of C.S. Peirce’s Existential Graphs]", Institute of Philosophy, Chinese Academy of Social Sciences, Beijing, PRC. * Van Heuveln, Bram, "[http://www.cogsci.rpi.edu/~heuveb/research/EG/index.html Existential Graphs.]" Dept. of Cognitive Science, [[Rensselaer Polytechnic Institute]]. Alpha only. * Zeman, Jay J., "[http://www.existentialgraphs.com/ Existential Graphs]". With [http://www.existentialgraphs.com/#table2 four online papers] by Peirce. [[Category:Logic]] [[Category:Logical calculi]] [[Category:Philosophical logic]] [[Category:History of logic]] [[Category:History of mathematics]] [[Category:Charles Sanders Peirce]] {{Link FA|de}} [[de:Existential Graphs]] [[es:Gráficos existenciales]] [[it:Grafo esistenziale]] [[ja:存在グラフ]] [[zh:存在图]]