Johnston diagram

From Wikipedia, the free encyclopedia

This article or section does not adequately cite its references or sources.
Please help improve this article by adding citations to reliable sources. (help, get involved!)
Any material not supported by sources may be challenged and removed at any time. This article has been tagged since November 2006.

Johnston diagrams, which look similar to Euler or Venn diagrams, illustrate formal propositional logic in a visual manner. Logically they are equivalent to truth tables; some may find them easier to understand at a glance. By overlaying one Johnston diagram on another, deductions can be made from sets of propositions.

Suppose that it is desired to compose logical statements describing the present state of current events in the world (or perhaps about imaginary situations in an imaginary world). Let the universal set contain (as elements) all the possible states which the world might find itself in. Only one of a variety (perhaps infinite) of elements represents the actual state of the world. All other elements represent alternative states of the world — "possible worlds". Thus, the universal set represents the space of all logical possibilities.

Then, the objective of a logical statement should be to say something about the state of the actual world. The way this will be done — using Johnston diagrams — is to blacken out regions of the universal set which contain elements which represent alternative states of the world which could not possibly be the state of the actual world.

So black regions on a Johnston diagram are "regions of impossibility", whereas white regions are "regions of possibility": one (and only one) of the elements in the regions of possibility describes the "world" as it actually is. The objective is to narrow down the region of possibility as much as possible, up to a single point which describes reality.

Let the universal set be represented by a rectangle. Start out by drawing a closed curve (e.g. a circle) inside the universal set. The circle separates the universal set into a pair of regions. Let the circle be called A. Points inside or on the circle are members of A; points outside the circle are not members of A, but are members of $\bar{A}$ , the complement of A.

Now let the region of the complement of A be blackened out (see Figure 1).

Figure 1. Johnston diagram representing the statement "A is true".

Then the region of possibility has become equivalent to set A, so Figure 1 is a Johnston diagram representing the propositional statement A.

But if, instead, the region inside A is blackened and the region outside it whitened, then the region of possibility will be equivalent to the complement of A (see Figure 2) and the diagram will represent the propositional statement $\neg A$ : "not A".

Figure 2. Johnston diagram representing the statement "A is not true".

Draw another circle — intersecting the first circle — and call it B. Points inside this second circle are members of B, and points outside it are members of $\bar{B}$ .

If the region inside B is whitened and the region outside it is blackened (see Figure 3), the resulting diagram is equivalent to the statement B,

Figure 3. Johnston diagram representing the statement: "B is true".

but if the region inside B is blackened and the region outside it is whitened (see Figure 4), the resulting diagram is equivalent to the statement $\neg B$ ("not B").

Figure 4. Johnston diagram representing the statement: "B is not true".

A pair of statements can be combined by means of the logical AND operator. To combine a pair of Johnston diagrams using the AND operator, superpose them so that elements (points) that end up on top of each other (in the superposition) are identically equivalent and represent the same possible state of the world.

Then blacken out the combined diagram as follows: if a point belongs to the impossibility space of at least one of the two component statements, then it belongs to the impossibility space of both statements. So, combining Figures 1 and 3 by means of the AND operator produces Figure 5, equivalent to the propositional statement $A \wedge B$ ("A and B"), and Figure 5's possibility space is the set $A \cap B$ ("A intersection B").

Figure 5. Johnston diagram representing the statement: "Both A and B are true."

A pair of statements can also be combined by means of the logical OR operator. To do so, superpose their Johnston diagrams, and blacken out the combined diagrams as follows: if a point belongs to the impossibility spaces of both component diagrams, then it belongs to the impossibility space of the combined diagram. Otherwise, if it belongs to at least one component possibility space, then it belongs to the combined possibility space.

So, combining Figures 1 and 3 by means of the OR operator produces Figure 6, equivalent to the propositional statement $A \vee B$ ("A or B"), and Figure 6's possibility space is the set $A \cup B$ ("A union B").

Figure 6. Johnston diagram representing the statement: "A or B is true." (Either A or B (or both) are true.)

It is also possible to apply the logical NOT operator to a Johnston diagram to obtain its negation. To do so, swap the possibility and impossibility spaces of the given diagram. This means to whiten black regions while simultaneously blackening white regions. The resulting diagram will represent a statement which negates the statement represented by the original diagram.

As an example, applying the NOT operator to Figure 1 yields Figure 2: statement A becomes statement $\neg A$ . Another example is to apply the NOT operator to Figure 6, obtaining Figure 7 whose impossibility space is the set $A \cup B$ and whose impossibility space is the set $\overline{A \cup B} = \bar{A} \cap \bar{B}$ , and which represents the logical statement $\neg (A \vee B)$ which is equivalent — due to De Morgan's law — to the statement $\neg A \wedge \neg B$ ("not A and not B").

Figure 7. Johnston diagram representing the statement "Neither A nor B is true".

Notice that Figure 7 can also be obtained by combining Figures 2 and 4 by means of the AND operator.

Statements A and B can also be combined to form the statement $A \rightarrow B$ ("A implies B"). To represent this with a Johnston diagram, let its possibility space be equivalent to the set $\bar{A} \cup B$ . Thus, the statement $A \rightarrow B$ can be represented by combining Figures 2 and 3 by means of the OR operator. The result is shown in Figure 8, viz.

Figure 8. Johnston diagram representing the statement "A implies B" or "if A then B" or "A is true only if B is true."

By looking at Figure 8 one can clearly see that IF the actual state of the world is described by a member of set A, THEN this member also belongs to set B (the "actual world" can only lie within the possibility space shown in white).

Similarly, statements A and B can be combined to form the statement $B \rightarrow A$ ("B implies A"). The Johnston diagram for this statement must have a possibility space equivalent to the set $\bar{B} \cup A$ . Thus, the statement $B \rightarrow A$ can be represented by combining Figures 4 and 1 by means of the OR operator. The result is shown in Figure 9, viz.

Figure 9. Johnston diagram representing the statement "B implies A" or "if B then A" or "A is true if B is true."

Alternatively, the set in Figure 9 can be expressed as $\overline{B - A}$ : the complement of the subtraction of A from B.

Finally, the pair of statements $A \rightarrow B$ and $B \rightarrow A$ can be combined into the single statement $A \leftrightarrow B$ ("A if and only if B"). The corresponding Johnston diagram can be formed by combining Figures 8 and 9 by means of the AND operator, resulting in Figure 10, viz.

Figure 10. Johnston diagram representing the statement "A is true if and only if B is true" or "A is equivalent to B".

The possibility space of this Johnston diagram is the set

$( \bar{A} \cup B ) \cap ( \bar{B} \cup A ) = ( A \cap B ) \cup ( \bar{A} \cap \bar{B} ),$

or, equivalently, the set

$\overline{A - B} \cap \overline{B - A} = \overline{A \, \Delta \, B},$

i.e. the complement of the symmetric difference between A and B.

Then there are two relatively trivial cases: the tautology and the contradiction. The tautology is the statement whose Johnston diagram has no black region of impossibility: it is all white, and its region of possibility is equivalent to the universal set. Every axiom of logic must necessarily be a tautology. A tautology does not say anything about the state of the actual world, because tautologies are true in all the possible worlds — the actual and all its alternatives. It says nothing about the contingent state of affairs in the actual world. Tautologies are either self-evident (axioms) or can be deduced (as theorems) from other tautologies. Thus, all tautologies can be deduced a priori, but the contingent state of the actual world can only be obtained a posteriori through observation.

An example of a tautology can be obtained by combining Figures 1 and 2 by means of the OR operator (see Figure 11).

Figure 11. Johnston diagram representing the statement "Either A is true or A is not true."

This corresponds to the axiom of (classical) propositional calculus $A \vee \neg A$ ("A or not A"), which is called tertium non datur ("a third [possibility] is not given").

On the other hand, the contradiction is the statement whose Johnston diagram is all black: its impossibility region is equivalent to the universal set, and its possibility region is the empty set. A contradiction says too much. In fact, a contradiction is the most one can ever say: a contradiction ANDed to any other statement produces a contradiction, but it can never be true, because the world does exist, and it has a state, which is its actual state. At least one element in the universal set must describe the actual world, so the region of possibility cannot be null.

A contradiction can be obtained by combining Figures 1 and 2 by means of the AND operator (see Figure 12).

Figure 12. Johnston diagram representing the contradictory statement "A is true but A is not true."

This corresponds to the contradictory statement $A \wedge \neg A$ ("A and not A"), which is the negation of the tautology $A \vee \neg A$ . The negation of every tautology is a contradiction. This suggests a method of proof called reductio ad absurdum: to prove a theorem, assume its negation, then show that it leads somehow to contradiction. Once the contradiction has been reached, the proof is finished: enough said.

In summary, a Johnston diagram is a way of representing logical statements (of propositional calculus) by means of sets. Thus, logical operators can be transformed into set operations, using the following table:

Assertion	Set
A	A
$\neg A$	$\bar{A}$
$A \wedge B$	$A \cap B$
$A \vee B$	$A \cup B$
$A \rightarrow B$	$\overline{A - B}$
$A \leftrightarrow B$	$\overline{A \, \Delta \, B}$
true	universal set
false	$\varnothing$

It is also possible to, in like manner, transform inferences into logical statements involving sets, viz.

Inference	Assertion
$A \vdash B$	$A \subset B$
$A, \ B \vdash C$	$A \cap B \subset C$
$A, \ B, \ C \vdash D$	$A \cap B \cap C \subset D$
$A, \ B, \ C, \ D \vdash E$	$A \cap B \cap C \cap D \subset E$
...	...
$A_1, \ ... \ , \ A_n \vdash B$	$\cap_{i=1}^n A_i \subset B$

Johnston visualization can also be applied to inference rules. An inference rule always has two premises and one conclusion, and can be represented generically as

$P_1, \ P_2 \vdash C$

where P₁ and P₂ are the premises and C is the conclusion. This inference rule transforms into the statement

$(P_1 \cap P_2) \subset C$

where P₁, P₂ and C have become sets. For any such sets, the following statements are always true:

$C \subset P_1,$

$C \subset P_2,$

$C \subset (P_1 \cup P_2),$

∴ $(P_1 \cap P_2) \subset C \subset (P_1 \cup P_2).$

To each logical statement corresponds a "possibility set", namely the set which is equivalent to the region of possibility in the Johnston diagram of the statement. One may say that the amount of information contained by a statement is — roughly speaking — inversely proportional to the size of the statement's possibility set. (Then the information contained by a contradiction would be infinite; however, such information would never be obtained, as a contradiction is unprovable)

If $A \subset B$ , then A is smaller or equal in size to B, so that A contains greater or equal information than B. Then, since $(P_1 \cap P_2) \subset C \subset (P_1 \cup P_2)$ , then $m(P_1 \cap P_2) \ge m(C) \ge m(P_1 \cup P_2)$ , where function m measures the amount of "information" contained by a set.