Logic Diagrams

views updated

LOGIC DIAGRAMS

"Logic diagrams" are geometrical figures that are in some respect isomorphic with the structure of statements in a formal logic and therefore can be manipulated to solve problems in that logic. They are useful teaching devices for strengthening a student's intuitive grasp of logical structure, they can be used for checking results obtained by algebraic methods, and they provide elegant demonstrations of the close relation of logic to topology and set theory.

Leonhard Euler, the Swiss mathematician, was the first to make systematic use of a logic diagram. Circles had earlier been employed, by Gottfried Wilhelm Leibniz and others, to diagram syllogisms, but it was Euler who, in 1761, first explained in detail how circles could be manipulated for such purposes. Euler's contemporary Johann Heinrich Lambert, the German mathematician, in his Neues

Organon (1764) used straight lines, in a manner similar to Euler's use of circles, for diagramming syllogisms.

Venn Diagrams

The Euler and Lambert methods, as well as later variants using squares and other types of closed curves, are no longer in use because of the great improvement on their basic conception which was introduced by the English logician John Venn. The Venn diagram is best explained by showing how it is used to validate a syllogism. The syllogism's three terms, S, M, and P, are represented by simple closed curves—most conveniently drawn as circles—that mutually intersect, as in Figure 1. The set of points inside circle S represents all members of class S, and points outside are members of class not-S —and similarly for the other two circles. Shading a compartment indicates that it has no members. An X inside a compartment shows that it contains at least one member. An X on the border of two compartments means that at least one of the two compartments has members.

Consider the following syllogism:

Some S is M.
All M is P.
Therefore, some S is P.

The first premise states that the intersection of sets S and M is not empty. This is indicated by an X on the border

dividing the two compartments within the overlap of circles S and M (Figure 2). The second premise states that the set indicated by that portion of circle M that lies outside of P is empty. When this area is shaded (Figure 3) the X must be shifted to the only remaining compartment into which it can go. Because the X is now inside both S and P, it is evident that some S is P ; therefore, the syllogism is valid.

Venn did not restrict this method to syllogisms. He generalized it to take care of any problem in the calculus of classes, then the most popular interpretation of what is now called Boolean algebra. For statements with four terms he used four intersecting ellipses, as shown in Figure 4. Since it is not possible for five ellipses to intersect in the desired manner, statements with five or more terms must be diagramed on more complicated patterns. Various methods of forming nonconvex closed curves for Venn diagrams of statements with more than four terms have been devised.

Rectangular Charts

Statements involving a large number of terms are best diagramed on a rectangle divided into smaller rectangles that are labeled in such a way that the chart can be manipulated efficiently as a Venn diagram. Many different methods of constructing such charts were worked out in the late nineteenth and early twentieth centuries, each

with merits and defects. The first to be published was that of Allan Marquand in 1881. Figure 5 shows a Marquand chart for four terms. Alexander Macfarlane preferred a narrow strip, which he called a "logical spectrum," subdivided and labeled as in Figure 6. Later, in "Adaptation of the Method of the Logical Spectrum to Boole's Problem" (in Proceedings of the American Association for the Advancement of Science 39 [1890]: 57f.), Macfarlane used his chart for solving a complicated problem in George Boole's Laws of Thought (1854).

Other types of rectangular charts were devised by William J. Newlin, William E. Hocking, and Lewis Carroll. Carroll introduced his chart in a book for children, The Game of Logic (London and New York, 1886). Instead of shading compartments, he proposed marking them with counters of two colors, one for classes known to have members, the other for null classes.

An elaborate diagrammatic method designed to cover all types of logic, including modal logics, was devised in 1897 by the American philosopher Charles Sanders Peirce and later discussed in several brief, obscurely written papers. Although Peirce considered these "existential graphs," as he called them, his greatest contribution to logic, they aroused little interest among later logicians and have yet to be fully explicated and evaluated.

Diagrams for the Propositional Calculus

In the early twentieth century the class interpretation of Boolean algebra was supplemented by a more useful interpretation in which classes are replaced by propositions that are either true or false and related to one another by logical connectives. The Venn diagrams, as well as their chart extensions, work just as efficiently for the propositional calculus as for the class calculus, but cultural lag has prevented this fact from entering most logic textbooks. For example, the class statement "All apples are red" is equivalent to the propositional statement "If x is an apple, then x is red." The same Venn diagram is therefore used for both statements (Figure 7). Similarly, the class statement "No A is B " is equivalent to the propositional statement "Not both A and B," symbolized in modern logic by the Sheffer stroke. Both statements are diagramed as in Figure 8.

A major defect of the Venn system is that it is difficult to distinguish the shading of one statement from the shading of another, so that one loses track of individual premises. This is best remedied by diagramming each statement on a separate sheet of transparent paper and superposing all sheets on the same basic diagram. Such a method using cellophane sheets shaded with different colors and superposed on a rectangular diagram was devised by Karl Döhmann, of Berlin.

A network method for solving problems in the propositional calculus, designed to keep statements separate and to bring out visually the nature of the logical connectives, is given in Martin Gardner's Logic Machines and Diagrams (1958), Chapter 3. Each term is represented by two vertical lines, one for "true," the other for "false." A connective is symbolized by "shuttles" that connect truth-value lines in the manner indicated by the "true" lines of a truth table for that connective. Figure 9 shows the diagram for implication.

A "Boole table," devised by Walter E. Stuerman, also keeps individual statements separate and can be used for graphing any type of Boolean algebra. It combines features of Macfarlane's chart with Lambert's linear method. John F. Randolph has developed a simple method of handling a Marquand diagram by sketching nested cross marks and using dots to indicate nonempty compartments.

Although the Venn circles and their various chart extensions can obviously be given three-dimensional forms, no three-dimensional techniques for diagramming Boolean algebra have been found useful because of the extreme difficulty of manipulating solid diagrams. In this connection, however, mention should be made of a curious cubical chart, devised by C. Howard Hinton in 1904, that is constructed with 64 smaller cubes and used for identifying valid syllogisms.

Boolean algebra is now known to be a special type of lattice, which in turn is a certain type of partially ordered set. A lattice diagram for a Boolean algebra of two terms is easily drawn, and although of little use in problem solving, it displays graphically many features of the propositional calculus.

In the logic of relations a large variety of useful diagrams have been widely used. The tree graph, for example, which goes back to ancient Greece, is an efficient way to indicate a familiar type of relation. Examples include the tree of Porphyry, found in medieval and Renaissance logics, the later tree diagrams of Peter Ramus, diagrams showing the evolution of organisms, family tree graphs, and graphs of stochastic processes in probability theory. The topological diagrams in Kurt Lewin's Principles of Topological Psychology (1936), as well as modern "sociograms," transport networks, and so on, may be called logic diagrams if "logic" is taken in a broad sense. However, such diagrams are now studied in the branch of mathematics called graph theory and are not generally considered logic diagrams. In a wide sense any geometrical figure is a logic diagram since it expresses logical relations between its parts.

Areas for Exploration

All diagrams for Boolean algebras work most efficiently when the statements to be diagramed are simple binary relations. Compound statements with parenthetical expressions are awkward to handle unless the statements are first translated into simpler expressions. Attempts

have been made to extend the Venn diagrams and other types of Boolean graphs to take care of parenthetical statements directly, but in all cases the diagrams become too complex to be useful. Perhaps simpler methods will be found by which traditional diagrams can be made to accommodate parenthetical expressions.

Little progress has been made in developing good diagrammatic methods for minimizing a complex logical statement—that is, for reducing it to a simpler but equivalent form. Several chart methods for minimizing have been worked out. The closest to a diagrammatic technique is the Karnaugh map, first explained by Maurice Karnaugh in 1953. The map is based on an earlier diagram called the Veitch chart, in turn based on a Marquand chart.

Work on better methods of minimizing is still in progress. The work has important practical consequences because electrical networks can be translated into Boolean algebra and the expression minimized and then translated back into network design to effect a simplification of circuitry. It is possible that a by-product of new minimizing methods may be a diagrammatic method superior to any yet found.

Another field open to exploration is the devising of efficient ways to diagram logics not of the Boolean type, notably modal logics and the various many-valued logics.

Bibliography

Venn's Symbolic Logic, rev. 2nd ed. (London: Macmillan, 1894), remains the best single source for the early history of logic diagrams. It also contains the fullest exposition of his own method, which he first presented in "On the Diagrammatic and Mechanical Representation of Propositions and Reasonings," Philosophical Magazine 10 (July 1880): 1–18. For more recent history and references, consult Martin Gardner, Logic Machines and Diagrams (New York: McGraw-Hill, 1958).

Euler's explanation of his circles can be found in his Lettres à une princesse d'Allemagne, Vol. II, letters 102–108 (St. Petersburg: Academie Impériale des Sciences, 1768). Lambert's method, in an improved form, is explained in J. N. Keynes, Studies and Exercises in Formal Logic. 4th ed. (London: Macmillan, 1906), p. 243.

For Venn diagrams of statements with more than four terms, see W. E. Hocking, "Two Extensions of the Use of Graphs in Elementary Logic," in University of California Publications in Philosophy 2 (2) (1909): 31–44; Edmund C. Berkeley, "Boolean Algebra and Applications to Insurance," in Record, American Institute of Actuaries 26 (1937): 373–414, and 27 (1938): 167–176 (reprinted, New York, 1952); Trenchard More Jr., "On the Construction of Venn Diagrams," in Journal of Symbolic Logic 24 (1959): 303–304; and Stephen Barr, Experiments in Topology (New York: Crowell, 1964), p. 206. A method of drawing five irregular but congruent convex pentagons intersecting in the required manner is explained by David W. Henderson in "Venn Diagrams for More Than Four Classes," American Mathematical Monthly 70 (1963): 424–426.

On rectangular Venn charts, see Allan Marquand, "A Logical Diagram for n Terms," in Philosophical Magazine 12 (1881): 266–270; Alexander Macfarlane, "The Logical Spectrum," in Philosophical Magazine 19 (1885): 286–289; William J. Newlin, "A New Logical Diagram," in Journal of Philosophy, Psychology, and Scientific Methods 3 (1906): 539–545; and the Hocking paper mentioned above. Carroll's method is further developed in his Symbolic Logic (London and New York, 1896; paperback ed., New York, 1958). Peirce's papers are reprinted in the Collected Papers of Charles Sanders Peirce, edited by Charles Hartshorne and Paul Weiss, Vol. IV (Cambridge, MA: Harvard University Press, 1933).

An explanation of how Venn circles can be used to handle problems in the propositional calculus appears in Gardner's Logic Machines and Diagrams (op. cit.), pp. 48–54. Döhmann explained his method in a privately printed booklet, Eine logistische Farbenquadrat-Methode (Berlin, 1962). Stuerman described his "Boole table" in "Plotting Boolean Functions," American Mathematical Monthly 67 (1960): 170–172, and in "The Boole Table Generalized," American Mathematical Monthly 68 (1961): 53–56. Randolph's method is given in "Cross-Examining Propositional Calculus and Set Operations," American Mathematical Monthly 72 (1965): 117–127. Hinton explained his cubical chart in his eccentric book The Fourth Dimension (London: Sonnenschein, 1904), pp. 100–106. John Evenden presented a two-term lattice diagram for Boolean algebra in "A Lattice-Diagram for the Propositional Calculus," Mathematical Gazette 46 (1962): 119–122.

Karnaugh first explained his map in "The Map Method for Synthesis of Combinational Logic Circuits," Transactions of the American Institute of Electrical Engineers, Part 1, 72 (1953): 593–599. E. W. Veitch explained his earlier diagram in "A Chart Method for Simplifying Truth Functions," Proceedings of the Association for Computing Machinery (May 2 and 3, 1952), 127–133.

Martin Gardner (1967)

Encyclopedia of Philosophy