This article is about Eulerian circles of set theory and logic. For the geometric Euler circle, see Nine-point circle.
An Euler diagram is a diagrammatic means of representing sets and their relationships. The first use of "Eulerian circles" is commonly attributed to Swiss mathematician Leonhard Euler (1707–1783). They are closely related to Venn diagrams.Venn and Euler diagrams were incorporated as part of instruction in set theory as part of the new math movement in the 1960s. Since then, they have also been adopted by other curriculum fields such as reading.[1]
Contents |
Overview
Euler diagrams consist of simple closed curves (usually circles) in the plane that depict sets. The sizes or shapes of the curves are not important: the significance of the diagram is in how they overlap. The spatial relationships between the regions bounded by each curve (overlap, containment or neither) corresponds to set-theoretic relationships (intersection, subset and disjointness).Each Euler curve divides the plane into two regions or "zones": the interior, which symbolically represents the elements of the set, and the exterior, which represents all elements that are not members of the set. Curves whose interior zones do not intersect represent disjoint sets. Two curves whose interior zones intersect represent sets that have common elements; the zone inside both curves represents the set of elements common to both sets (the intersection of the sets). A curve that is contained completely within the interior zone of another represents a subset of it.
Venn diagrams are a more restrictive form of Euler diagrams. A Venn diagram must contain all the possible zones of overlap between its curves, representing all combinations of inclusion/exclusion of its constituent sets, but in an Euler diagram some zones might be missing. When the number of sets grows beyond 3, or even with three sets, but under the allowance of more than two curves passing at the same point, we start seeing the appearance of multiple mathematically unique Venn diagrams. Venn diagrams represent the relationships between n sets, with 2n zones, Euler diagrams may not have all zones. (An example is given below in the History section; in the top-right illustration the O and I diagrams are merely rotated; Venn stated that this difficulty in part led him to develop his diagrams).
In a logical setting, one can use model theoretic semantics to interpret Euler diagrams, within a universe of discourse. In the examples above, the Euler diagram depicts that the sets Animal and Mineral are disjoint since the corresponding curves are disjoint, and also that the set Four Legs is a subset of the set of Animals. The Venn diagram, which uses the same categories of Animal, Mineral, and Four Legs, does not encapsulate these relationships. Traditionally the emptiness of a set in Venn diagrams is depicted by shading in the region. Euler diagrams represent emptiness either by shading or by the use of a missing region.
Often a set of well-formedness conditions are imposed; these are topological or geometric constraints imposed on the structure of the diagram. For example, connectedness of zones might be enforced, or concurrency of curves or multiple points might be banned, as might tangential intersection of curves. In the diagram to the right, examples of small Venn diagrams are transformed into Euler diagrams by sequences of transformations; some of the intermediate diagrams have concurrency of curves. However, this sort of transformation of a Venn diagram with shading into an Euler diagram without shading is not always possible. There are examples of Euler diagrams with 9 sets that are not drawable using simple closed curves without the creation of unwanted zones since they would have to have non-planar dual graphs.
History
As shown in the illustration to the right, Sir William Hamilton in his posthumously published Lectures on Metaphysics and Logic (1858–60) asserts that the original use of circles to "sensualize ... the abstractions of Logic" (p. 180) was not Leonhard Paul Euler (1707–1783) but rather Christian Weise (?–1708) in his Nucleus Logicoe Weisianoe that appeared in 1712 posthumously. He references Euler's Letters to a German Princess on different Matters of Physics and Philosophy1" [1Partie ii., Lettre XXXV., ed. Cournot. – ED.][2]
In Hamilton's illustration the four forms of the syllogism as symbolized by the drawings A, E, I and O are:[3]
- A: The Universal Affirmative, Example: "All metals are elements".
- E: The Universal Negative, Example: "No metals are compound substances".
- I: The Particular Affirmative, Example: "Some metals are brittle".
- O: The Particular Negative, Example: "Some metals are not brittle".
- "...of the first sixty logical treatises, published during the last century or so, which were consulted for this purpose:-somewhat at random, as they happened to be most accessible :-it appeared that thirty four appealed to the aid of diagrams, nearly all of these making use of the Eulerian Scheme." (Footnote 1 page 100)
- “In fact ... those diagrams not only do not fit in with the ordinary scheme of propositions which they are employed to illustrate, but do not seem to have any recognized scheme of propositions to which they could be consistently affiliated.” (pp. 124–125)
- "We now come to Euler's well-known circles which were first described in his Lettres a une Princesse d'Allemagne (Letters 102–105). The weak point about these consists in the fact that they only illustrate in strictness the actual relations of classes to one another, rather than the imperfect knowledge of these relations which we may possess, or wish to convey, by means of the proposition. Accordingly they will not fit in with the propositions of common logic, but demand the constitution of a new group of appropriate elementary propositions.... This defect must have been noticed from the first in the case of the particular affirmative and negative, for the same diagram is commonly employed to stand for them both, which it does indifferently well". (italics added: page 424)
By 1914 Louis Couturat (1868–1914) had labeled the terms as shown on the drawing on the right. Moreover, he had labeled the exterior region (shown as a'b'c') as well. He succinctly explains how to use the diagram – one must strike out the regions that are to vanish:
- "VENN'S method is translated in geometrical diagrams which represent all the constituents, so that, in order to obtain the result, we need only strike out (by shading) those which are made to vanish by the data of the problem." (italics added p. 73)
- "No Y is Z and ALL X is Y: therefore No X is Z" has the equation x'yz' + xyz' + x'y'z for the unshaded area inside the circles (but note that this is not entirely correct; see the next paragraph).
- "No Y is Z and ALL X is Y: therefore No X is Z" has the equation x'yz' + xyz' + x'y'z + x'y'z' .
Couturat now observes that, in a direct algorithmic (formal, systematic) manner, one cannot derive reduced Boolean equations, nor does it show how to arrive at the conclusion "No X is Z". Couturat concluded that the process "has ... serious inconveniences as a method for solving logical problems":
- "It does not show how the data are exhibited by canceling certain constituents, nor does it show how to combine the remaining constituents so as to obtain the consequences sought. In short, it serves only to exhibit one single step in the argument, namely the equation of the problem; it dispenses neither with the previous steps, i. e., "throwing of the problem into an equation" and the transformation of the premises, nor with the subsequent steps, i. e., the combinations that lead to the various consequences. Hence it is of very little use, inasmuch as the constituents can be represented by algebraic symbols quite as well as by plane regions, and are much easier to deal with in this form."(p. 75)
-
- "For more than three variables, the basic illustrative form of the Venn diagram is inadequate. Extensions are possible, however, the most convenient of which is the Karnaugh map, to be discussed in Chapter 6." (p. 64)
-
- "The Karnaugh map1 [1Karnaugh 1953] is one of the most powerful tools in the repertory of the logic designer. ... A Karnaugh map may be regarded either as a pictorial form of a truth table or as an extension of the Venn diagram." (pp. 103–104)
Example: Euler- to Venn-diagram and Karnaugh map
This example shows the Euler and Venn diagrams and Karnaugh map deriving and verifying the deduction "No X's are Z's". In the illustration and table the following logical symbols are used:- 1 can be read as "true", 0 as "false"
- ~ for NOT and abbreviated to ' when illustrating the minterms e.g. x' =defined NOT x,
- + for Boolean OR (from Boolean algebra: 0+0=0, 0+1 = 1+0 = 1, 1+1=1)
- & (logical AND) between propositions; in the mintems AND is omitted in a manner similar to arithmetic multiplication: e.g. x'y'z =defined ~x & ~y & z (From Boolean algebra: 0*0=0, 0*1 = 1*0=0, 1*1 = 1, where * is shown for clarity)
- → (logical IMPLICATION): read as IF ... THEN ..., or " IMPLIES ", P → Q =defined NOT P OR Q
Given the example above, the formula for the Euler and Venn diagrams is:
- "No Y's are Z's" and "All X's are Y's": ( ~(y & z) & (x → y) ) =defined P
- "No X's are Z's": ( ~ (x & z) ) =defined Q
- ( ~(y & z) & (x → y) ) → ( ~ (x & z) ): P → Q
- IF ( "No Y's are Z's" and "All X's are Y's" ) THEN ( "No X's are Z's" )
Square # | Venn, Karnaugh region | x | y | z | (~ | (y | & | z) | & | (x | → | y)) | → | (~ | (x | & | z)) | ||
0 | x'y'z' | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | ||
1 | x'y'z | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | ||
2 | x'yz' | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | ||
3 | x'yz | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | ||
4 | xy'z' | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | ||
5 | xy'z | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | ||
6 | xyz' | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | ||
7 | xyz | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 |
Modus ponens (or "the fundamental rule of inference"[6]) is often written as follows: The two terms on the left, "P → Q" and "P", are called premises (by convention linked by a comma), the symbol ⊢ means "yields" (in the sense of logical deduction), and the term on the right is called the conclusion:
- P → Q, P ⊢ Q
- P → Q , P ⊢ Q
- i.e.: ( ~(y & z) & (x → y) ) → ( ~ (x & z) ) , ( ~(y & z) & (x → y) ) ⊢ ( ~ (x & z) )
- i.e.: IF "No Y's are Z's" and "All X's are Y's" THEN "No X's are Z's", "No Y's are Z's" and "All X's are Y's" ⊢ "No X's are Z's"
The use of tautological implication means that other possible deductions exist besides "No X's are Z's"; the criterion for a successful deduction is that the 1's under the sub-major connective on the right include all the 1's under the sub-major connective on the left (the major connective being the implication that results in the tautology). For example, in the truth table, on the right side of the implication (→, the major connective symbol) the bold-face column under the sub-major connective symbol " ~ " has the all the same 1s that appear in the bold-faced column under the left-side sub-major connective & (rows 0, 1, 2 and 6), plus two more (rows 3 and 4).
Gallery
-
A Venn diagram shows all possible intersections.
-
Euler diagram visualizing a real situation, the relationships between various supranational European organisations.
-
Euler diagram visualizing a real situation, the relationships between various supranational African organisations.
-
Humorous diagram comparing Euler and Venn diagrams.
-
Euler diagram of types of triangles, assuming isosceles triangles have at least 2 equal sides.
-
Euler diagram of terminology of the British Isles.
Footnotes
- ^ Strategies for Reading Comprehension Venn Diagrams
- ^ By the time these lectures of Hamilton were published, Hamilton too had died. His editors (symbolized by ED.), responsible for most of the footnoting, were the logicians Henry Longueville Mansel and John Veitch.
- ^ Hamilton 1860:179. The examples are from Jevons 1881:71ff.
- ^ See footnote at George Stibitz.
- ^ This is a sophisticated concept. Russell and Whitehead (2nd edition 1927) in their Principia Mathematica describe it this way: "The trust in inference is the belief that if the two former assertions [the premises P, P→Q ] are not in error, the final assertion is not in error . . . An inference is the dropping of a true premiss [sic]; it is the dissolution of an implication" (p. 9). Further discussion of this appears in "Primitive Ideas and Propositions" as the first of their "primitive propositions" (axioms): *1.1 Anything implied by a true elementary proposition is true" (p. 94). In a footnote the authors refer the reader back to Russell's 1903 Principles of Mathematics §38.
- ^ cf Reichenbach 1947:64
- ^ Reichenbach discusses the fact that the implication P → Q need not be a tautology (a so-called "tautological implication"). Even "simple" implication (connective or adjunctive) will work, but only for those rows of the truth table that evaluate as true, cf Reichenbach 1947:64–66.
References
By date of publishing:- Sir William Hamilton 1860 Lectures on Metaphysics and Logic edited by Henry Longueville Mansel and John Veitch, William Blackwood and Sons, Edinburgh and London.
- W. Stanley Jevons 1880 Elemetnary Lessons in Logic: Deductive and Inductive. With Copious Questions and Examples, and a Vocabulary of Logical Terms, M. A. MacMillan and Co., London and New York.
- John Venn 1881 Symbolic Logic, MacMillan and Co., London.
- Alfred North Whitehead and Bertrand Russell 1913 1st edition, 1927 2nd edition Principia Mathematica to *56 Cambridge At The University Press (1962 edition), UK, no ISBN.
- Louis Couturat 1914 The Algebra of Logic: Authorized English Translation by Lydia Gillingham Robinson with a Preface by Philip E. B. Jourdain, The Open Court Publishing Company, Chicago and London.
- Emil Post 1921 "Introduction to a general theory of elementary propositions" reprinted with commentary by Jean van Heijenoort in Jean van Heijenoort, editor 1967 From Frege to Gödel: A Sourcebook of Mathematical Logic, 1879–1931, Harvard University Press, Cambridge, MA, ISBN 0-674-42449-8 (pbk.)
- Claude E. Shannon 1938 "A Symbolic Analysis of Relay and Switching Circuits", Transactions American Institute of Electrical Engineers vol 57, pp. 471–495. Derived from Claude Elwood Shannon: Collected Papers edited by N.J.A. Solane and Aaron D. Wyner, IEEE Press, New York.
- Hans Reichenbach 1947 Elements of Symbolic Logic republished 1980 by Dover Publications, Inc., NY, ISBN 0-486-24004-5.
- Edward W. Veitch 1952 "A Chart Method for Simplifying Truth Functions", Transactions of the 1952 ACM Annual Meeting, ACM Annual Conference/Annual Meeting "Pittsburgh", ACM, NY, pp. 127–133.
- Maurice Karnaugh November 1953 The Map Method for Synthesis of Combinational Logic Circuits, AIEE Committee on Technical Operations for presentation at the AIEE summer General Meeting, Atlantic City, N. J., June 15–19, 1953, pp. 593–599.
- Frederich J. Hill and Gerald R. Peterson 1968, 1974 Introduction to Switching Theory and Logical Design, John Wiley & Sons NY, ISBN 0-71-39882-9.
- Ed Sandifer 2003 How Euler Did It, http://www.maa.org/editorial/euler/How%20Euler%20Did%20It%2003%20Venn%20Diagrams.pdf
External links
Wikimedia Commons has media related to: Euler diagrams |
- Euler Diagrams. Brighton, UK (2004).What are Euler Diagrams?
- Visualisation with Euler diagrams project