=Paper=
{{Paper
|id=Vol-1132/paper5
|storemode=property
|title=Continuity, Connectivity and Regularity in Spatial Diagrams for N Terms
|pdfUrl=https://ceur-ws.org/Vol-1132/paper5.pdf
|volume=Vol-1132
}}
==Continuity, Connectivity and Regularity in Spatial Diagrams for N Terms==
https://ceur-ws.org/Vol-1132/paper5.pdf
Continuity, Connectivity and Regularity
in Spatial Diagrams for N Terms
Amirouche Moktefi Ahti-Veikko Pietarinen
Francesco Bellucci Department of Philosophy, History, Culture and Art Studies
Ragnar Nurkse School of Innovation and Governance University of Helsinki &
Tallinn University of Technology Ragnar Nurkse School of Innovation and Governance
Tallinn, Estonia Tallinn University of Technology
amirouche.moktefi@ttu.ee Tallinn, Estonia & Helsinki, Finland
bellucci.francesco@gmail.com ahti-veikko.pietarinen@helsinki.fi
Abstract—This paper discusses the role of continuity, Charles S. Peirce considered that spatial diagrams are
connectivity and regularity in the design of spatial logic diagrams “veridically iconic, naturally analogous to the thing
for N terms. Three specific diagrammatic schemes are discussed: represented, and not a creation of conventions” [2, p. 316].
Venn diagrams, Marquand tables and Karnaugh maps. Umberto Eco disputes this view and argues that the
representation of classes with spaces is rather purely
Keywords— diagrams; Euler; Venn; Marquand; Karnaugh; conventional because belonging to a class is not a spatial fact
continuity ; connectivity; regularity. “except the fact that I might be defined to belong to the class
of all those who are located in a certain place” [3, pp. 228-
229]. Now, the interesting point is that it is with this very
I. INTRODUCTION: CONTUINITY AND CONNECTIVITY understanding that Euler introduced his spatial diagrams as we
The aim of this paper is to discuss the role of the indicated above. As such, the individuals that form a class are
topological properties of continuity and connectivity in the to be imagined as if they were all assembled within that single
design of spatial diagrams for N terms. Spatial diagrams have space. Hence, what Eco considers to be an exception would
been and are still widely used in logic. They have been rather be the general rule. The fact that these individuals
popularized by Leonhard Euler who used them thoroughly in cannot be really assembled does not matter. Classification
his Letters to a German Princess (1768). There are no itself is a purely mental operation and there is no need for
conditions as to the shape of the spaces as long as they are classes or spaces to really exist. All that is required is to have
formed by continuous surfaces within closed curves. Early an accurate diagram that provides a visual aid.
logicians used mostly circles but squares have been also Having a continuous space simplifies the expression of
regularly used, especially when the number of terms increases. what is represented and provides a representation that could be
The very idea of spatial diagrams is simple: to represent a visually better grasped. However, saving continuity becomes
class of individuals with a space where those individuals are difficult when the number of terms represented increases.
gathered. That’s how Euler introduced his diagrams: “As a There, it often happens that a class A is represented with a
general notion contains an infinite number of individual discontinuous space. For instance A could be represented with
objects, we may consider it as a space in which they are all several sub-spaces representing each a subdivision of A. In
contained. Thus, for the notion of man we form a space […] in such situations, diagrams are better drawn in such a way as to
which we conceive all men to be comprehended” [1, p. 339]. make those subdivisions connected. As such, they can be
For instance, if we consider the circle A in [Fig. 1] to represent grouped into one continuous space standing for the entire class
the class of men, then it is understood that every man is A as shown in [Fig. 2]. Hence, the connectivity of the
comprehended within that circle. This mode of representation subdivisions is what makes the whole space continuous.
deserves further exploration as to what cognitive and
semeiotic processes are at work when it comes to representing ABC ABC’
a class with a space. ABC ABC’
A
AB’C AB’C’
AB’C AB’C’
Fig. 1
Fig. 2
Research supported by Estonian Research Council Project PUT267,
“Diagrammatic Mind: Logical and Communicative Aspects of Iconicity,”
Principal Investigator Prof. Ahti-Veikko Pietarinen.
31
Keeping the subdivisions connected might prove to be
difficult in diagrams with more than 3 or 4 classes. In the
following, we will discuss how three designers of spatial
diagrams (Venn, Marquand and Karnaugh) handled the issues
of continuity and connectivity in diagrams for N terms.
Drawing such diagrams for more than 3 terms was not
required within syllogistic where arguments were reduced to
series of syllogisms. Such problems were easily solved with Fig. 5
traditional Euler diagrams. One represents classes with circles,
then the logical relations of the classes are represented by the
topological relations of the circles. However, the development
of Boolean algebra changed the picture. Logicians had to face
problems where they were offered an indeterminate number of
premises with an indeterminate number of terms and were
asked to extract the conclusion that follows by eliminating
undesired or superfluous terms. Fig. 6
II. VENN DIAGRAMS FOR N TERMS
In 1880, the logician John Venn, who was a great admirer
of Boole, invented a new type of diagrams where relations
between classes are not directly exhibited by the circles [4].
One first draws a framework diagram where all combinations Fig. 7
of terms are represented. For instance, for 2 terms x and y, one
uses two circles to divide the universe into 4 compartments xy,
xy’, x’y, x’y’ (where x’ stands for not-x, and y’ for not-y).
In order to represent propositions, one has to add marks to
indicate the occupation or emptiness of the compartments. For
instance, to represent the proposition “All x are y”, one has to
shade xy’ to indicate its emptiness, as shown in [Fig. 3]. In
order to handle more complex logic problems, Venn designed Fig. 8
diagrams where n continuous curves divide the universe into
In this 5-term diagram, the fifth term (z) is represented by
2n compartments. For n = 3, one simply uses the famous three-
an annulus. It follows that class not-z is discontinuous and is
circle diagram [Fig. 4]. For n = 4, Venn knew how to add a
formed by two disconnected spaces. It must be noted that
curve to his 3-term diagram in order to obtain a 4-term
Venn knew, using an inductive method, how to represent 5-
diagram [Fig. 5]. However, he preferred to use a new figure
term continuous diagrams [Fig. 8]. However, Venn preferred
with four ellipses, as shown in [Fig. 6], because of its
to use the other diagram because of its symmetry, in spite of
simplicity and symmetry [5, p. 116]. For n = 5, Venn failed in
his dissatisfaction with its discontinuity. For more than 5
making ellipses intersect in the desired way. So, he suggested
terms, Venn believed his diagrams would not offer the visual
using the diagram shown in [Fig. 7].
aid one would expect, even if they continue to be accurate:
“Up to four or five terms inclusive, our plan works very
successfully in practice; where it begins to fail is in the
accidental circumstance that its further development soon
becomes intricate and awkward, though never ceasing to be
feasible” [5, p. 113]. When Venn faced such complex
Fig. 3 problems, he preferred to use tabular diagrams that were
invented by the logician Allan Marquand [5, pp. 139-140,
373-376].
III. MARQUAND TABLES FOR N TERMS
Allan Marquand was one of Peirce’s students at John
Hopkins University. He introduced new diagrams that were
Fig. 4 designed to supersede Venn diagrams, Marquand says: “It is
the object of this paper to suggest a mode of constructing
logical diagrams, by which they may be indefinitely extended
to any number of terms, without losing so rapidly their special
32
function, viz. that of affording visual aid in the solution of
problems” [6, p. 266].
Marquand used squares rather than circles. He first
represents the logical universe with a square. The limitation of
the universe, absent in Venn diagrams, makes it possible to
represent with a closed surface the class where all terms are
negated. Marquand tables should not be understood however
as Venn diagrams to which we have added a square around to
limit the universe. Indeed, the cognitive constructions of the
diagrams differ. Venn puts together the individuals that form a
given class x and leaves outside the individuals that are not x. Fig. 10
Marquand rather divides the universe into 2-subclasses x and
not-x, equally considered. Thus, Venn proceeds by Contrary to Venn who abandoned unhappily the continuity
classification while Marquand appeals to division. of his diagrams, Marquand did not seem to be bothered with
this constraint, as long as the diagrams are easy to extend for
After one has represented the universe with a square, it further terms. All one has to do is to divide again the square
suffices to divide it into subdivisions corresponding to the dichotomically to introduce an additional term. After
different combinations of the terms involved in the argument. Marquand, several tabular schemes have been introduced and
For two terms A and B, one gets [Fig. 9] (where a stands for continued to be used in subsequent years [7; 8]. Much later,
the negation of A, etc.). This diagram shows how important it interest in such diagrams has been renewed in the 1950s when
was to choose a rectilinear shape in order to get a symmetrical computer scientists had to simplify logical forms in order to
division of the universe. Making subdivisions of equal size is get better and cheaper electronic circuits. Such methods have
purely conventional for Marquand and Venn. However, it is been notably introduced by Edward W. Veitch in 1952 [9] and
obvious that for convenience and practicality, it is better to Maurice Karnaugh in 1953 [10].
make the compartment of equal size. It must be remembered
that Euler and Venn always favored symmetrical diagrams
where classes were represented with congruent spaces (same IV. KARNAUGH MAPS FOR N TERMS
shape and same size). For 4 terms, Marquand divides the
square in the way represented in [Fig. 10]. In order to simplify a logical form F, one first divides each
term of F into its simplest components, then one collects
It is important for our purpose to understand how the order together the components to get a simpler expression of F. Let
of the combinations is obtained on each side. For instance, us consider the logical form: F = A’B’C + AD + A’BD + A’
horizontally, Marquand divides first the square into two B’C’ (where A’ stands for the negation of A, etc.). There are
subclasses: A and not-A. Then each sub-class is itself divided four variables A, B, C, D. Karnaugh uses a square divided into
into sub-divisions C and not-C. Hence, this dichotomy 16 subdivisions; each subdivision corresponds to one
division produces the horizontal sequence AC, Ac, aC, ac that combination of the variables [Fig. 11]. For each combination
can be observed on the top of the diagram. The vertical where F is true, one puts 1 in the appropriate subdivision.
sequence is produced similarly. One immediately observes Each red curve in [Fig. 11, left] highlights the subdivisions
that several classes are not represented with continuous that correspond to one term of F. For instance, the eastern
spaces: C, c, D and d. circle encloses the cases where term AD is true.
Any equivalent form of F would still have the same truth
value for any given combination of the variables. Hence,
looking for a simpler (equivalent) form of F does not involve
changing the content of the subdivisions. It rather requires
looking for a different assemblage of the subdivisions, with
fewer and larger curves yielding to fewer and more general
terms. In present case, [Fig. 11, right] shows how we get a
simpler expression of F. For instance, the vertical blue curve
encloses all affirmed subdivisions where A’B’ is fixed.
Similarly, the horizontal curve encloses eight affirmed
Fig. 9
subdivisions with one fixed variable D. Hence, we obtain
simple form: F = A’B’ + D.
33
A
B
A
B
construction (cylinder) even when the diagrams were drawn
C C
on a two-dimensional surface.
D D
It is obvious that when N is superior to 5 or 6 terms, using
continuous figures becomes tedious as it makes it difficult to
get regular diagrams. Regularity here is meant as the
possession of some features (symmetry, congruence,
familiarity, recurrence) that simplify the identification of the
terms involved in each sub-division of the diagram.
Mathematicians tackled this problem for more than a century
in order to construct ‘nice’ Venn diagrams for N terms. From a
Fig. 11 mathematical viewpoint, the continuity of the diagrams is
essential as is rightly explained by Anthony W. F. Edwards:
“Both Venn and Carroll gave up at four sets and offered five-
set diagrams whose fifth set did not consist of a closed curve,
so that some regions became disjoint. In our terminology, they
were not really Venn diagrams at all: once one admits the
possibility of sets being bounded by more than one closed
curve, one might as well just list all the binary numbers
between 0 and 2n-1 and put a little ring round each!” [12, p.
32]. From a logical viewpoint, the matter is different however.
Making diagrams continuous and spaces connected is not a
challenge in itself. The logician rather expects such diagrams
Fig. 12 to provide a visual aid for solving logic problems. As such,
continuity and connectivity are pursued as long as they
Karnaugh considered that finding such assemblages of contribute to making the diagrams helpful. When the number
connected squares could be done by “direct inspection” [10, p. of terms increases, discontinuous diagrams loose the
594]. This is made possible by the fact that the variables are advantages of having every class within a single space but
ordered is such a way as to always have one variable provide regular schemes where it is easier to locate every
unchanged between adjacent squares. Indeed, the appeal to subdivision.
Gray’s sequence: 00, 01, 11, 10 (see the horizontal sequence at
the top of the map) makes simplification easier. It is For instance, Venn abandoned his diagrams in favour of
noteworthy that Veitch first used the same sequence as Marquand’s tables for more than 6 terms. Venn, referring to
Marquand’s: 00, 01, 10, 11 [Fig. 12, left]. Thus, several the 8x8 Marquand diagram for 6 terms argued that: “The
variables were represented with discontinuous spaces. For scheme is very compendious: thus one adapted for 10 terms,
instance the two green curves represent together a single and involving 1024 combinations, can be conveniently printed
variable. In Karnaugh’s map [Fig. 12, right], that variable is on one of these pages. Of course there is not the help to the
represented with one continuous space, as shown by the green eye here, afforded by keeping all the subdivisions of a single
curve. Here we see how Karnaugh changed the sequence in class within one boundary […] But this is almost inevitable
order to restore the continuity of classes that were abandoned where we deal with many class terms” [5, p.140]. In a way,
by Marquand and Veitch. Interestingly, Veitch himself Karnaugh maps might be perceived as a response to Venn by
adopted later Karnaugh’s sequence [11]. suggesting that methods exist to deal with the simplification
on subdivisions of areas into contiguous parts observable by
It might be objected that some variables in Karnaugh maps ‘direct inspection’. In all the cases of the above, only 0 and 1
are also discontinuous (see the red and blue curves in [Fig. 12, are the values in the diagrams and maps, but generalisations to
right]). However, Karnaugh considered those opposite ends of other than binary Boolean algebras should pose no problems.
columns and rows to be adjacent, as if the map was inscribed These generalisations retain the desired contiguity of maps
on a torus or a cylinder. As such, their connectivity was saved. and the directly observable properties of simplification.
This paper shows how continuity, connectivity and
V. CONCLUSION: TOWARD REGULARITY regularity acted as major constraints for diagram designers
(Venn, Marquand and Karnaugh). Their opposed solutions
The discussion of Venn, Marquand and Karnaugh show the difficulties they faced and the choices they made. It
diagrams shows the crucial role of continuity and connectivity provides a nice illustration of the uneasy balance between
in the making of those diagrams for more than 3 terms. These visual aid and logical efficiency that was constantly pursued
topological properties have been differently handled by these by logicians [13].
authors. Venn knew how to draw continuous classes but
sacrificed that continuity in favour of regularity in his 5-term
diagrams. On the contrary, Marquand was not bothered as to REFERENCES
whether the classes were continuous or the subdivisions
connected. Finally, Karnaugh made his best to save the [1] L. Euler, Letters of Euler on Different Subjects in Natural Philosophy
Addressed to a German Princess, vol. 1. New York: J. & J. Harper,
connectivity of spaces by imagining a three-dimensional 1833.
34
[2] C. S. Peirce, Collected Papers, vol. 4. Cambridge, MA: Harvard [9] E. W. Veitch, “A chart method for simplifying truth functions,”
University Press, 1933. Proceedings of the Association for Computing Machinery, pp. 127-133,
[3] U. Eco, Le Signe. Bruxelles : Labor, 1988. 2-3 May 1952.
[4] J. Venn, “On the diagrammatic and mechanical representation of [10] M. Karnaugh, “The map method for synthesis of combinational logic
propositions and reasonings,” Philosophical Magazine, vol. 10, pp. 1-18, circuits,” Transactions of the American Institute of Electrical Engineers
1880. - Part 1, vol. 72, pp. 593-599, 1953.
[5] J. Venn, Symbolic Logic, 2nd ed. London: Macmillan, 1894. [11] E. W. Veitch, “Logical equation minimization involving higher order
solutions,” in Proceedings of the International Conference on
[6] A. Marquand, “On logical diagrams for n terms,” Philosophical Information Processing. Paris: Unesco, 1959, pp. 423-424.
Magazine, vol. 12, pp. 266-270, 1881.
[12] A. W. F. Edwards, Cogwheels of the Mind: the Story of Venn Diagrams.
[7] A. Macfarlane, “The logical spectrum,” Philosophical Magazine, vol. Maryland: Johns Hopkins University Press, 2004.
19, pp. 286-290, 1885.
[13] A. Moktefi, and S.-J. Shin, “History of logic diagrams”, in Logic: A
[8] L. Carroll, The Game of Logic. London: Macmillan, 1886.
History of its Central Concepts, D. M. Gabbay, F. J. Pelletier and J.
Woods, Eds. Amsterdam: North-Holland, 2012, pp. 611-682.
35