Euler diagram

An Euler diagram does not need to show all possible intersections.

An Euler diagram is a diagrammatic means of representing sets and their relationships. It is the modern manifestation of an Euler circle, which was invented by Leonhard Euler in the 18th century.

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]

Overview

Euler diagrams usually consist of simple closed curves in the plane which are used to depict sets. The spatial relationships between the curves (overlap, containment or neither) corresponds to set-theoretic relationships (intersection, subset and disjointness).

Euler diagrams discriminate the well-known Venn diagrams which represent all possible set intersections available with the given sets.

The intersection of the interior of a collection of curves and the exterior of the rest of the curves in the diagrams is called a zone. Thus, in Venn diagrams all zones must be present (given the set of curves), but in an Euler diagram some zones might be missing.

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 zone.

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 below, 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 which are not drawable using simple closed curves without the creation of unwanted zones since they would have to have non-planar dual graphs.

History

Photo of page from Hamilton's 1860 "Lectures" page 180. (Click on it, up to two times, to enlarge). The symbolism A, E, I, and O refer to the four forms of the syllogism. The small text to the left says: "The first employment of circular diagrams in logic improperly ascribed to Euler. To be found in Christian Weise."

On the right is a photo of page 74 from Couturat 1914 wherein he labels the 8 regions of the Venn diagram. The modern name for these "regions" is minterms. These are shown on the left with the variables x, y and z per Venn's drawing. The symbolism is as follows: logical AND ( & ) is represented by arithmetic multiplication, and the logical NOT ( ~ )is represented by " ' " after the variable, e.g. the region x'y'z is read as "NOT x AND NOT y AND NOT z" i.e. ~x & ~y & z.

Both the Veitch and Karnaugh diagrams show all the minterms, but the Veitch is not particularly useful for reduction of formulas. Observe the strong resemblance between the Venn and Karnaugh diagrams; the colors and the variables x, y, and z are per Venn's example.

William Hamilton (1805-1865) in his 1860 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 Philosophy¹" [¹Partie ii., Lettre XXXV., ed. Cournot. --ED.]^[2]

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".

In his 1881 Symbolic Logic Chapter V "Diagrammatic Representation", John Venn (1834-1923) comments on the remarkable prevalence of the Euler diagram:

"...of the first sixty logical treatises, published during the last century or so, which were consuIted 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)

Composite of two pages 115-116 from Venn 1881 showing his example of how to convert a syllogism of three parts into his type of diagram. Venn calls the circles "Eulerian circles" (cf Sandifer 2003, Venn 1881:114 etc) in the "Eulerian scheme" (Venn 1881:100) of "old-fashioned Eulerian diagrams" (Venn 1881:113).

But nevertheless, he contended "the inapplicability of this scheme for the purposes of a really general Logic" (page 100) and in a footnote observed that "it fits in but badly even with the four propositions of the common Logic [the four forms of the syllogism] to which it is normally applied" (page 101). Venn ends his chapter with the observation that will be made in the examples below -- that their use is based on practice and intuition, not on a strict algorithmic practice:

“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.” (p.124-125)

Finally, in his Chapter XX HISTORIC NOTES Venn gets to a crucial criticism (italicized in the quote below); observe in Hamilton's illustration that the O (Particular Negative) and I (Particular Affirmative) are simply rotated:

"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)

(Sandifer 2003 reports that Euler makes such observations too; Euler reports that his figure 45 (a simple intersection of two circles) has 4 different interpretations). Whatever the case, armed with these observations and criticisms, Venn then demonstrates (pp. 100-125) how he derived what has become known as his Venn diagrams from the "old-fashioned Euler diagrams". In particular he gives an example, shown on the left.

By 1914 Louis Couturat (1968-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)

Given the Venn's assignments, then, the unshaded areas can be summed to yield the following equation for Venn's example:

"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.

In Venn nowhere does is the 0^th term x'y'z' appear i.e. the background surrounding the circles, discussed or labeled. But Couturat corrects this in his drawing.

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)

Thus the matter would rest until 1952 when Maurice Karnaugh (1924- ) would adapt and expand a method proposed by Edward W. Veitch; this work would rely on the truth table method precisely defined in Emil Post's 1921 PhD thesis "Introduction to a general theory of elementary propositions" and the application of propositional logic to switching logic by Claude Shannon, George Stibitz, and Alan Turing^[4]. In chapter "Boolean Algebra" Hill and Peterson (1968, 1964) present sections 4.5ff "Set Theory as an Example of Boolean Algebra" and in it they present the Venn diagram with shading and all. They give examples of Venn diagrams to solve example switching-circuit problems, but end up with this statement:

"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)

In Chapter 6, section 6.4 "Karnaugh Map Representation of Boolean Functions" they begin with:

"The Karnaugh map¹ [¹Karnaugh 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

The history of Karnaugh's development of his "chart" or "map" method is obscure. Karnaugh in his 1953 referenced Veitch 1951, Veitch referenced Claude E. Shannon 1938 (essentially Shannon's Master's thesis at M.I.T.), and Shannon in turn referenced, among other authors of logic texts, Couturat 1914. In Veitch's method the variables are arranged in a rectangle or square; as described in Karnaugh map, Karnaugh in his method changed the order of the variables to correspond to what has become known as (the vertices of) a hypercube.

Example: Euler- to Venn-diagram and Karnaugh map

--work in progress-- In the illustration and table the following logical symbols are used:

1 is "true", 0 is "false"

~ for NOT and abbeviated 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

Before it can presented in a Venn diagram or Karnaugh Map the Euler diagram's syllogism "No Y is Z, All X is Y" first must be reworded into the more formal language of the propositional calculus: " 'It is not the case that: Y AND Z' AND 'If an X then a Y' ". Once the propositions are reduced to symbols and a propositional formula ( ~(y & z) & (x --> y) ), one can construct the formula's truth table; from this table the Venn and/or the Karnaugh map are readily produced. By use of the adjacency of "1"s in the Karnaugh map (the grey ovals around terms 0 and 1 and around terms 2 and 6) one can "reduce" the example's Boolean equation i.e. (x'y'z' + x'y'z) + (x'yz' + xyz') to just two terms: x'y' + yz'. But how to deduce the notion that "No X is Z", and just how the reduction relates to this deduction, is not forthcoming from this example.

Given a proposed conclusion such as "No X is a Z", one can demonstrate using a truth table that given the two propositions "No Y is a Z" and "If an X then a Y", a reduction to "No X is a Z" yields a tautology -- a formula yielding "true" (shown as 1's in these examples) for all evaluations of its propositional variables (e.g. x, y, z valued at {0, 1} in all combinations):

( ~(y & z) & (x → y) ) → ( ~ (x & z) )

One can abbreviate this as follows:

( ~(y & z) & (x → y) ) =_defined P

( ~ (x & z) ) =_defined Q

So now the formula can be abbreviated to:

P → Q

Given the tautology, the stage is now set to use modus ponens to deduce that indeed "No x is a Z". The modus ponens "detaches" the conclusion from the premises, both of which must be true: The tautology is true as demonstrated, and only the evaluation from row of P that corresponds to row 7 of the truth table where x, y and z are true is allowed -- this row evaluates to "true" as well^[5].

P → Q, P ⊢ Q, where the symbol ⊢ means "yields" in the sense of logical deduction

( ~(y & z) & (x → y) ) → ( ~ (x & z) ), ( ~(y & z) & (x → y) ) ⊢ ( ~ (x & z) )

16 possible deductions exist, one of which is that "No X is a Z". Observe that on the right of the following truth table, the column under NOT (signified by the symbol " ~ ") has the same 1's that appear in the bold-faced column under the left &.

-- Explanation of example needs work. Other deductions are possible (16 total). End with some examples. --

Gallery

A Venn diagram shows all possible intersections.

Examples of small Venn diagrams with shaded regions representing empty sets that are easily transformed into Euler diagrams.

Example of an Euler diagram visualizing a real situation, the relationships between various supranational European organisations.

Footnotes

References

By date of publishing:

• William Rowan Hamilton edited by Henry L. Mansel and John Veitch, 1860, Lectures on Logic, Gould and Lincoln, Boston MA.

• 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.

• 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 Jean van Heijenoort, editor 1967 From Frege to Gödel: A Sourcebook of Mathematical Logic[rest of reference TBD

• 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.

• 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