Euler diagram
An Euler diagram is a diagrammatic means of representing sets and their relationships. They are particularly useful for explaining complex hierarchies and overlapping definitions. They are similar to another set diagramming technique, Venn diagrams. Unlike Venn diagrams, which show all possible relations between different sets, the Euler diagram shows only relevant relationships.
The Swiss mathematician Leonhard Euler is one of the most important authors in the history of this type of diagram, but he is only the namesake, not the inventor. Euler diagrams were first developed for logic, especially syllogistics, and only later transferred to set theory. In the United States, both Venn and Euler diagrams were incorporated as part of instruction in set theory as part of the new math movement of the 1960s. Since then, they have also been adopted by other curriculum fields such as reading as well as organizations and businesses.
Euler diagrams consist of simple closed shapes in a two-dimensional plane that each depict a set or category. How or whether these shapes overlap demonstrates the relationships between the sets. Each 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 which do not overlap represent disjoint sets, which have no elements in common. Two curves that overlap represent sets that intersect, that have common elements; the zone inside both curves represents the set of elements common to both sets. A curve completely within the interior of another is a subset of it.
Venn diagrams are a more restrictive form of Euler diagrams. A Venn diagram must contain all 2n logically possible zones of overlap between its n curves, representing all combinations of inclusion/exclusion of its constituent sets. Regions not part of the set are indicated by coloring them black, in contrast to Euler diagrams, where membership in the set is indicated by overlap as well as color.
History
Diagrams reminiscent of Euler diagrams and with similar functions seem to have existed for a long time. However, exact dates for these diagrams can only be determined historically after the invention of printing press.Before Euler
The first authors to print an Euler-esque diagram and briefly discuss it in their texts were Juan Luis Vives, Nicolaus Reimers, Bartholomäus Keckermann and Johann Heinrich Alsted. The first detailed elaboration of these diagrams can be traced back to Erhard Weigel, who called this type of diagram a 'logometrum'. Weigel was the first to prove all valid syllogisms with the aid of shapes in a two-dimensional plane. In the case of generally affirmative judgements, the geometric shape for the subject should lie completely within the shape for the predicate. In the case of negative judgements, it should lie completely outside. In the case of particular judgements, the geometric shapes should partially overlap and not overlap. To prove a syllogism, one must first draw all possible figures for the premises and then see whether one can also read the conclusion from them. If this is the case, the syllogism is valid; otherwise, it is invalid.Erhard Weigel used initial letters to represent the diagrams, whereas his students, such as Johann Christoph Sturm and Gottfried Wilhelm Leibniz, used circles or lines. Another tradition can be traced back to Christian Weise, who is said to have used these diagrams in his teaching. This is reported by his students Samuel Großer and Johann Christian Lange. Lange in particular went beyond syllogistics with these diagrams and worked with quantified predicates, for example.
Euler and the time after
In his Letters to a German Princess, Euler focused solely on traditional syllogistics. He further developed Weigel's approach and not only tested the validity of syllogisms, but also developed a method for drawing conclusions from premises. At the same time as Euler, Gottfried Ploucquet and Johann Heinrich Lambert also used similar diagrams. However, the diagrams only became widely known in the 1790s through Immanuel Kant, who used them in his lectures on logic and his students then spread knowledge of the diagrams throughout Europe. In the 19th century, Euler diagrams became the most widely used form of representation in logic, esp. by 'Kantians' such as Arthur Schopenhauer, Karl [Christian Friedrich Krause] or Sir [William Hamilton, 9th Baronet|Sir William Hamilton].File:Hamilton Lectures on Logic 1874 Euler Diagrams.png|thumb|344x344px|A page from Hamilton's Lectures on Logic; the symbols ', ', ', and ' refer to four types of categorical statement which can occur in a syllogism The small text to the left erroneously says: "The first employment of circular diagrams in logic improperly ascribed to Euler. To be found in Christian Weise", a book which was actually written by Johann Christian Lange.Since the history of the diagrams was only partially researched in the 19th century, most logicians attributed the diagrams to Euler, leading to numerous misunderstandings, some of which persist to this day. As shown in the illustration to the right, Sir William Hamilton erroneously asserted that the original use of the circles to "sensualize... the abstractions of logic" was not Euler but rather Weise; however the latter book was actually written by Johann Christian Lange, rather than Weise. He references Euler's Letters to a German Princess.
In Hamilton's illustration of the four categorical propositions which can occur in a syllogism as symbolized by the drawings ', ', ', and ' are:
Euler diagrams in the era of Venn
comments on the remarkable prevalence of the Euler diagram:But nevertheless, he contended, "the inapplicability of this scheme for the purposes of a really general logic" and then noted that,
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:
Finally, in his Venn gets to a crucial criticism ; observe in Hamilton's illustration that the ' and ' are simply rotated:
Whatever the case, armed with these observations and criticisms, Venn then demonstrates how he derived what has become known as his Venn diagrams from the “... old-fashioned Euler diagrams.” In particular Venn gives an example, shown at the left.
By 1914, Couturat had labeled the terms as shown on the drawing at the right. Moreover, he had labeled the exterior region as well. He succinctly explains how to use the diagram – one must strike out the regions that are to vanish:
Given the Venn's assignments, then, the unshaded areas inside the circles can be summed to yield the following equation for Venn's example:
In Venn the background surrounding the circles, does not appear: That is, the term marked "0", Nowhere is it discussed or labeled, but Couturat corrects this in his drawing. The correct equation must include this unshaded area shown in boldface:
In modern use, the Venn diagram includes a "box" that surrounds all the circles; this is called the universe of discourse or the domain of discourse.
Couturat observed that, in a direct algorithmic manner, one cannot derive reduced Boolean equations, nor does it show how to arrive at the conclusion " is ". Couturat concluded that the process "has... serious inconveniences as a method for solving logical problems":
Thus the matter would rest until 1952 when Maurice Karnaugh would adapt and expand a method proposed by Edward W. Veitch; this work would rely on the truth table method precisely defined by Emil Post and the application of propositional logic to switching logic by Shannon, Stibitz, and Turing.
For example, Hill & Peterson 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:
In Chapter 6, section 6.4 "Karnaugh map representation of Boolean functions" they begin with:
The history of Karnaugh's development of his "chart" or "map" method is obscure. The chain of citations becomes an academic game of "credit, credit; ¿who's got the credit?": referenced, Veitch, referenced, and, in turn referenced . 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 a hypercube.
Modern use of Euler diagrams
In the 1990s, Euler diagrams were developed as a logical system. The cognitive advantages of the diagrams soon became apparent. The diagrams were therefore not only used as set diagrams, but have since been used in many different ways and functions in computer science including artificial intelligence and software engineering, information technology, bioscience, medicine, economics, statistics and many other fields, and their philosophy and history have been discussed. In 2000, the conference series began, which regularly addresses current research on Euler diagrams, among other topics.Relation between Euler and Venn diagrams
s are a more restrictive form of Euler diagrams. A Venn diagram must contain all 2n logically possible zones of overlap between its n curves, representing all combinations of inclusion/exclusion of its constituent sets. Regions not part of the set are indicated by coloring them black, in contrast to Euler diagrams, where membership in the set is indicated by overlap as well as color. When the number of sets grows beyond 3 a Venn diagram becomes visually complex, especially compared to the corresponding Euler diagram. The difference between Euler and Venn diagrams can be seen in the following example. Take the three sets:In a logical setting, one can use model-theoretic semantics to interpret Euler diagrams, within a universe of discourse. In the examples below, 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 absence of a 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 adjacent diagram, 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.
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 Xs are Zs".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
- & between propositions; in the minterms AND is omitted in a manner similar to arithmetic multiplication: e.g. x′y′z =defined ~x & ~y & z
- → : read as IF... THEN..., or " IMPLIES ", P → Q = defined NOT P OR Q
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 and put the deduction on the right 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 then P → Q is a tautology. Given this fact, one can "detach" the formula on the right in the manner described below the truth table.
Given the example above, the formula for the Euler and Venn diagrams is:
And the proposed deduction is:
So now the formula to be evaluated can be abbreviated to:
At this point the above implication P → Q & → ~ is still a formula, and the deductionthe "detachment" of Q out of P → Qhas 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.
Modus ponens is often written as follows: The two terms on the left, P → Q and P, are called premises, the symbol ⊢ means "yields", and the term on the right is called the conclusion:
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" is only the case for P in those circumstances when P evaluates as "true".
One is now free to "detach" the conclusion "No Xs are Zs", perhaps to use it in a subsequent deduction.
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. For example, in the truth table, on the right side of the implication the bold-face column under the sub-major connective symbol " ~ " has all the same 1s that appear in the bold-faced column under the left-side sub-major connective &, plus two more.