s
(on left) showing how they can be easily transformed into equivalent Euler diagrams
(right). In these, black shaded regions represent
empty sets (to diagram universal quantification), red shaded regions with an x represent nonempty sets (to diagram existential quantification), and the other regions have not been specified as empty or non-empty.
Venn diagrams are a more restrictive form of Euler diagrams. A Venn diagram must contain all 2
n 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: • A = \{1,\, 2,\, 5\} • B = \{1,\, 6\} • C = \{4,\, 7\} The Euler and the Venn diagrams of those sets are: File:3-set Euler diagram.svg|Euler diagram File:3-set Venn diagram.svg|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 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 (from
Boolean algebra: 0 + 0 = 0, 0 + 1 = 1 + 0 = 1, 1 + 1 = 1) • & (logical AND) between propositions; in the minterms 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 : " 'It is not the case that: AND AND 'If an then a ". 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 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" ) At this point the above implication
P →
Q (i.e. ~(y & z) & (x → y) ) → ~(x & z) ) 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 (or "the fundamental rule of inference") 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" is only the case for
P in those circumstances when
P evaluates as "true" (e.g. rows OR OR OR : x′y′z′ + x′y′z + x′yz′ + xyz′ = x′y′ + yz′). :
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 all the same 1s that appear in the bold-faced column under the left-side sub-major connective
& (rows , , and ), plus two more (rows and ). == Gallery ==