An Euler diagram illustrating that the set of "animals with four legs"
is a subset of "animals", but the set of "minerals" is disjoint (has no
members in common) with "animals".
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]
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.
Examples of small
Venn diagrams (on left) with shaded regions representing
empty sets, showing how they can be easily transformed into equivalent Euler diagrams
(right).
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 2
n
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
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 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.
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".
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 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)
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.” (pp. 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 (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)
Given the Venn's assignments, then, the unshaded areas
inside the circles 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 inside the circles (but note that this is not entirely correct; see the next paragraph).
In Venn the 0th term, x'y'z', i.e. the background surrounding the
circles, does not appear. Nowhere is it discussed or labeled, but
Couturat corrects this in his drawing. The correct equation must include
this unshaded area shown in boldface:
- "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' .
In modern usage the Venn diagram includes a "box" that surrounds all the circles; this is called the
universe of discourse or the
domain of discourse.
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 (among others)
Claude Shannon,
George Stibitz, and
Alan Turing.
[4]
For example, 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 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)
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
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
Before it can be presented in a Venn diagram or Karnaugh Map, the Euler
diagram's syllogism "No Y is Z, All X is Y" must first 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 (indicated by 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 the means for deducing 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 test whether or not it is a correct
deduction by use of a
truth table.
The easiest method is put the starting formula on the left (abbreviate
it as "P") and put the (possible) deduction on the right (abbreviate it
as "Q") and connect the two with
logical implication i.e. P → Q, read as
IF P
THEN Q. If the evaluation of the truth table produces all 1's under the implication-sign (→, the so-called
major connective) then P → Q is a
tautology. Given this fact, one can "detach" the formula on the right (abbreviated as "Q") in the manner described below the truth table.
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
And the proposed deduction is:
- "No X's are Z's": ( ~ (x & z) ) =defined Q
So now the formula to be evaluated can be abbreviated to:
- ( ~(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" )
The Truth Table demonstrates that the formula ( ~(y & z)
& (x → y) ) → ( ~ (x & z) ) is a tautology as shown by all 1's
in yellow column..
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 |
At this point the above implication P → Q (i.e. ~(y & z) & (x
→ y) ) → ~(x & z) ) is still a formula, and the deduction – the
"detachment" of Q out of P → Q – has not occurred. But given the
demonstration that P → Q is tautology, the stage is now set for the use
of the procedure of
modus ponens to "detach" Q: "No X's are Z's" and dispense with the terms on the left.
[5]
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
For the modus ponens to succeed, both premises P → Q and P must be
true.
Because, as demonstrated above the premise P → Q is a tautology,
"truth" is always the case no matter how x, y and z are valued, but
"truth" will only be the case for P in those circumstances when P
evaluates as "true" (e.g. rows 0
OR 1
OR 2
OR 6: x'y'z' + x'y'z + x'yz' + xyz' = x'y' + yz').
[7]
- 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"
One is now free to "detach" the conclusion "No X's are Z's", perhaps
to use it in a subsequent deduction (or as a topic of conversation).
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
-
-
-
-
-
Euler diagram of types of
triangles, assuming isosceles triangles have at least 2 equal sides.
-
- ^ 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