An
Contents 1 Overview 2 In mathematics 2.1 History 2.2 Example: Euler- to Venn-diagram and Karnaugh map 3 Gallery 4 See also 5 Notes 6 References 7 Further reading 8 External links Overview[edit] An
Euler diagrams consist of simple closed shapes in a two dimensional plane that each depict a set or category. How or if these shapes overlap demonstrates the relationships between the sets. There are only 3 possible relationships between any 2 sets; completely inclusive, partially inclusive, and exclusive. This is also referred to as containment, overlap or neither or, especially in mathematics, it may be referred to as subset, intersection and disjointed. 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
A = 1 , 2 , 5 displaystyle A= 1,,2,,5 B = 1 , 6 displaystyle B= 1,,6 C = 4 , 7 displaystyle C= 4,,7 The Euler and the
Euler diagram Venn diagram In a logical setting, one can use model theoretic semantics to
interpret Euler diagrams, within a universe of discourse. In the
examples below, the
Photo of page from Hamilton's Lectures on Logic. The symbolism A, E, I, and O refer to the categorical statements that can occur in a syllogism. The small text to the left erroneously states: "The first employment of circular diagrams in logic improperly ascribed to Euler. To be found in Christian Weise", a book actually written by Johann Christian Lange.[2][3] 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)
erroneously asserts that the original use of circles to "sensualize
... the abstractions of Logic" (p. 180) was not Leonhard Paul
Euler (1707–1783) but rather
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",
"...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 on page 101 observed that, "It fits in but badly even with the four propositions of the common Logic to which it is normally applied." Venn ends his chapter with the observation illustrated 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,
"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
"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.[nb 2] 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
"For more than three variables, the basic illustrative form of the
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
The history of Karnaugh's development of his "chart" or "map" method
is obscure. Karnaugh in his 1953 referenced Veitch 1951, Veitch
referenced
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
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 1s 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 Ys are Zs" and "All Xs are Ys": ( ~(y & z) & (x → y) ) =defined P And the proposed deduction is: "No Xs are Zs": ( ~ (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 Ys are Zs" and "All Xs are Ys" ) THEN ( "No Xs are Zs" ) The Truth Table demonstrates that the formula ( ~(y & z) & (x → y) ) → ( ~ (x & z) ) is a tautology as shown by all 1s 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 Xs
are Zs" and dispense with the terms on the left.[nb 3]
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').[nb 4] P → Q , P ⊢ Q i.e.: ( ~(y & z) & (x → y) ) → ( ~ (x & z) ) , ( ~(y & z) & (x → y) ) ⊢ ( ~ (x & z) ) i.e.: IF "No Ys are Zs" and "All Xs are Ys" THEN "No Xs are Zs", "No Ys are Zs" and "All Xs are Ys" ⊢ "No Xs are Zs" One is now free to "detach" the conclusion "No Xs are Zs", 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 Xs are Zs"; the criterion for a successful deduction is that the 1s under the sub-major connective on the right include all the 1s 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[edit] A
An
Humorous diagram comparing Euler and Venn diagrams.
The 22 (of 256) essentially different
See also[edit]
Notes[edit] ^ 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
References[edit] ^ Strategies for Reading Comprehension Venn Diagrams
^ a b Venn, John (1881). Symbolic Logic. London: MacMillan and Co.
p. 509.
^ a b Mac Queen, Gailand (October 1967). The Logic
Further reading[edit] By date of publishing: Sir William Hamilton 1860 Lectures on Metaphysics and Logic edited by
External links[edit] Wikimedia Commons has media related to Euler diagrams. Free software for generating Venn and Euler diagrams using circles eulerAPE: Drawing area-proportional Euler diagrams using ellipses eulerGlyphs: Drawing area-proportional Euler diagrams with glyphs eulerForce: Laying out Euler diagrams using a force-directed approach Euler Diagrams. Brighton, UK (2004).What are Euler Diagrams? Venn Diagrams vs Euler Diagrams Visualisation with Eule |