Euler Diagram - Example: Euler- To Venn-diagram and Karnaugh Map

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

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

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.

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

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