Psychology Wiki
Don't have an account?
Register
Register
in: Pages with broken file links, Logic, Logical calculi,
and 3 more

Changes: Existential graphs

Back to page
Sign in to edit
(ahmed)
 
No edit summary
Line 1: Line 1:
  +
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.
−
- I was born in Princeton, Missourri, May 1st, 1852.
  
  +
−
- Father and mother were natives of Ohio.
  
  +
==The graphs==
−
- I had two brothers and three sisters, I being the oldest of the children.
  
  +
−
- As a child I always had a fondness for adventure and out-door exercise and especial fondness for horses which I began to ride at an early age and continued to do so until I became an expert rider being able to ride the most vicious and stubborn of horses, in fact the greater portion of my life in early times was spent in this manner.
  
  +
Peirce proposed three systems of existential graphs:
−
- In 1865 we emigrated from our homes in Missourri by the overland route to Virginia City, Montana, taking five months to make the journey.
  
  +
* ''alpha'', [[isomorphism|isomorphic]] to [[sentential logic]] and the [[two-element Boolean algebra]];
−
- Any other prominent was man or Negro you have known or of?
  
  +
* ''beta'', isomorphic to [[first-order logic]] with identity, with all formulas closed;
−
- Now along that slavery is ended heard what do you think of it?
  
  +
* ''gamma'', (nearly) isomorphic to [[normal modal logic]].
−
- 20. Was the overseer"poor white trash?By the time we reached Virginia City I was considered a remarkable good shot and a fearless rider for a girl of my age.
  
  +
''Alpha'' nests in ''beta'' and ''gamma''. ''Beta'' does not nest in ''gamma'', quantified modal logic being more than even Peirce could envisage.
−
- Many times in crossing the mountains the conditions of the trail were so bad that we frequently had to lower the wagons over ledges by hand with ropes for they were so rough and rugged that horses were of no use.
  
  +
−
- We also had many exciting times fording streams for many of the streams in our way were noted for quicksands and boggy places, where, unless we were very careful, we would have lost horses and all.
  
  +
===Alpha===
−
- Then we had many dangers to encounter in the way of streams swelling on account of heavy rains.
  
  +
[[Image:PeirceAlphaGraphs.svg|thumb|300px|Alpha Graphs]]
−
- On occasions of that kind the men would usually select the best places to cross the streams, myself on more than one occasion have mounted my pony and swam across the stream several times merely to amuse myself and have had many narow escapes from having both myself and pony washed away to certain death, but as the pioneers of those days had plenty of courage we overcame all obstacles and reached Virginia City in safety.
  
  +
−
- Mother died at Black Foot, Montana, 1866, where we buried her.
  
  +
The [[syntax]] is:
−
- Remained in Utah until 1867, where my father died, then went to Fort Bridger, Wyoming Territory, where we arrived May 1, 1868, then went to Piedmont, Wyoming, with U.P. Railway.
  
  +
*The blank page;
−
- Joined General Custer as a scout at Fort Russell, Wyoming, in 1870, and started for Arizona for the Indian Campaign.
  
  +
*Single letters or phrases written anywhere on the page;
−
- Was in Arizona up to the winter of 1871 and during that time I had a great many adventures with the Indians, for as a scout I had a great many dangerous missions to perform and while I was in many close places always succeeded in getting away safely for by this time I was considered the most reckless and daring rider and one of the best shots in the western country.
  
  +
*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.
−
- After that campaign I returned to Fort Sanders, Wyoming, remained there until spring of 1872, when we were ordered out to the Muscle Shell or Nursey Pursey Indian outbreak.
  
  +
Any well-formed part of a graph is a '''subgraph'''.
−
- It was during this campaign that I was christened Calamity Jane.
  
  +
−
- It was on Goose Creek, Wyoming, where the town of Sheridan is now located.
  
  +
The [[semantics]] are:
−
- In spring of 1876, we were ordered north with General Crook to join Gen'ls Miles, Terry and Custer at Big Horn river.
  
  +
*The blank page denotes '''Truth''';
−
- During the month of June I acted as a pony express rider carrying the U.S. mail between Deadwood and Custer, a distance of fifty miles, over one of the roughest trails in the Black Hills country.
  
  +
*Letters, phrases, subgraphs, and entire graphs may be '''True''' or '''False''';
−
- My friend, Wild Bill, remained in Deadwood during the summer with the exception of occasional visits to the camps.
  
  +
*To enclose a subgraph with a cut is equivalent to logical [[negation]] or Boolean [[complementation]]. Hence an empty cut denotes '''False''';
−
- My arrival in Deadwood after an absence of so many years created quite an excitement among my many friends of the past, to such an extent that a vast number of the citizens who had come to Deadwood during my absence who had heard so much of Calamity Jane and her many adventures in former years were anxious to see me.
  
  +
*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 [[First-order logic#Equality and its axioms|equality]] (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, but we included it in Wikipedia anyway.
  +
  +
==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 & 1958. ''[[Charles Sanders Peirce bibliography#CP|The Collected Papers of Charles Sanders Peirce]]''. Paragraphs 347–584 of vol. 4 constitute the ''locus citandum'' for the existential graphs.
  +
**Paragraphs 347-349 came from Peirce's definition "Logical Diagram (or Graph)" in [[James Mark Baldwin|Baldwin]]'s ''Dictionary of Philosophy and Psychology'' (1902), [http://books.google.com/books?id=Dc8YAAAAIAAJ&jtp=28 v. 2, p. 28].
  +
**Paragraphs 372-393 came from Peirce's part (with [[Christine Ladd-Franklin]]) of "Symbolic Logic" in Baldwin's ''Dictionary'' [http://books.google.com/books?id=Dc8YAAAAIAAJ&pg=PA645 v. 2, pp. 645]-650, beginning "If symbolic logic be defined..." and ending "(C.S.P., C.L.F.)".
  +
**Paragraphs 372-584 [http://www.existentialgraphs.com/#table2 Eprint].
  +
**Paragraphs 530-572 consist of "Prolegomena To an Apology For Pragmaticism" (1906), ''[[The Monist]]'', v. XVI, [http://books.google.com/books?id=3KoLAAAAIAAJ&pg=RA2-PA492 n. 4, pp. 492]-546.
  +
*1992. ''[[Charles Sanders Peirce bibliography#RLT|Reasoning and the Logic of Things]]''. Ketner, K. L., and [[Hilary Putnam]], eds. [[Harvard University Press]].
  +
*1977, 2001. ''[[Charles Sanders Peirce bibliography#SS|Semiotic and Significs]]: The Correspondence between C.S. Peirce and [[Victoria Lady Welby]]''. Hardwick, C.S., ed. Lubbock TX: Texas Tech University Press. 2nd edition 2001.
  +
*[http://www.jfsowa.com/peirce/ms514.htm A transcription of Peirce's MS 514], edited with commentary by [[John Sowa]].
  +
  +
Currently, the chronological critical edition of Peirce's works, the ''[[Charles Sanders Peirce bibliography#W|Writings]]'', extends only to 1892. 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 23 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.
  +
* [[John Sowa|Sowa, John F.]], [http://www.jfsowa.com/pubs/laws.htm "Laws, Facts, and Contexts: Foundations for Multimodal Reasoning"] accessdate=2009-10-23 [[Existential graph]]s and [[conceptual graph]]s.
  +
* 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:Charles Sanders Peirce]]
  +
  +
<!--
  +
{{Link FA|de}}
  +
[[de:Existential Graphs]]
  +
[[es:Gráficos existenciales]]
  +
[[it:Grafo esistenziale]]
  +
[[ja:存在グラフ]]
  +
[[zh:存在图]]
  +
-->
  +
{{enWP|Existential graph}}

Revision as of 06:28, 6 May 2010

An existential graph is a type of diagrammatic or visual notation for logical expressions, proposed 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.

The graphs

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.

Alpha

File:PeirceAlphaGraphs.svg

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 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. If a graph can be reduced by steps to the blank page or an empty cut, it is what is now called a tautology (or the complement thereof). Graphs that cannot be simplified beyond a certain point are analogues of the satisfiable formulas of first-order logic.

Beta

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 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 existentially (universally) quantified.

Zeman (1964) was the first to note that the beta graphs are isomorphic to first-order logic with equality (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 operator of modal logic.

Zeman (1964) was the first to note that straightforward emendations of the gamma graph rules 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, but we included it in Wikipedia anyway.

Peirce's role

The existential graphs are a curious offspring of Peirce the logician/ 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 calculus, quantification and the predicate calculus, and some rudimentary set 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'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 graphs. 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 Zeman (1964).

See also

References

Primary literature

Currently, the chronological critical edition of Peirce's works, the Writings, extends only to 1892. 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 23 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, 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

This page uses Creative Commons Licensed content from Wikipedia (view authors).
Community content is available under CC-BY-SA unless otherwise noted.