**'Rug' Enumeration images**

We begin with an extremely simple formal system, for which we will construct several different forms of images. The system at issue is propositional logic, made even simpler by restricting it to a single sentence letter p. In order to make things simpler still, we use a single connective: either the Sheffer stroke | , which can be read as NAND, or the dagger , which can be read as NOR. As is well known, either NAND or NOR suffices as a complete base for all Boolean connectives.

Our goal, then, is to construct an image of truth-values for all formulae expressible in terms only of p and | or The values at issue are merely four, equivalent to p, ~p (p|p or p p) tautology or contradiction . In Figures 4 through 8 we use the following colors for these values: green for p, blue for ~p, red for tautologies and dark blue for contradictions.

Let us start with a simple 'rug' pattern with an enumeration of all
formulae expressible in terms of our single sentence-letter and single
connective. For a first enumeration we represent
the plan of the rug is laid out
schematically as follows (Figure 3)^{2}.

Figure 3.

Here formula 1 is p p, formed by a single stroke between the formula heading its row and the formula at the top of its column. That formula, now simply labelled '1', is then placed in the second position along each axis. Formula 2 is formed as a 'slash product' of the formula heading its row and its column -- in the form (row column) -- in the same way. Formula 2 is thus (p|1) or (p|(p|p)). Formula 2 is added as the third formula on each axis. Formula 3 is ((p|p)|p), formula 4 is (p|(p|(p|p))), formula 5 is ((p|p)|(p|p)), formula 6 is ((p|(p|p))|p), and so forth. The pattern continues to generate progressively longer formulae, constituting in the abstract an infinite partial plane extending to the bottom and right and containing all formulae of our simple single- sentence-letter form of propositional calculus.

In Figure 4 the schema is shown in shades of color. Squares correspond directly to the formulae indicated in the schematic sketch above, including formulae along the axes, and are colored in terms of their values: as noted, green = p or equivalent formulae, light blue = p|p or ~p, red represents tautologies and dark blue represents contradictions . The first graph in Figure 4 is a smaller fragment of the upper left corner of the rug, with the values of formulae indicated on axes as well. The second image in Figure 4 shows a larger section, incorporating the first.

Fig. 4

Fig. 6

Figures 7 and 8 show a rug pattern using a different enumeration of
formulae, following the alternative schematic in Figure 6.

Fig. 7 NAND using square enumeration

Fig. 8 NOR using square enumeration

Nothing, it should be noted, dictates any particular form for enumeration in such a display; nothing dictates the diagonal enumeration of Figure 3 over the square enumeration of figure 6, for example, nor either of these over any of the infinite alternatives. There is therefore an ineliminable arbitrariness to the choice of any particular rug pattern for a formal system. It is also clear, however, that certain properties of patterns--including those noted above--will appear regardless of the pattern of enumeration chosen. Pattern-properties invariant under enumeration can be expected to correspond to deep or basic properties of the system. The rug patterns sketched above are for an extremely simple form of propositional calculus, explicitly restricted to just one sentence letter. Can such an approach be extended to include systems with additional sentence letters as well? Of course. One way of extending the enumeration schemata above so as to include two sentence letters rather than one is simply to begin with the two sentence letters on each axis. In all other regards enumeration can proceed as before (Figure 9):

Fig. 9

With two sentence letters, of course, four colors will no longer suffice for values of tautologies, contradictions, and all possible shades of contingency. For a system with both p and q we will require 16 colors in all, corresponding to the sixteen possible truth tables composed of four lines, or equivalently the sixteen binaries composed of four digits. Complete color shade patterns--employing a complete palette of contingencies--are shown for propositional calculus with p and q in Figure 10. These represent NAND and NOR with our initial diagonal enumeration scheme. Corresponding illustrations in terms of our second mode of enumeration appear as Figure 11. It is interesting to note that although a number of the characteristics marked with respect to propositional calculus with a single sentence letter above still hold, one does not: here it is no longer true that contingent values match between NAND and NOR versions. That property, though provable for propositional calculus with a single sentence letter, disappears in richer systems.

NAND NOR

Fig. 10

Fig. 11

Fig. 12

Fig. 13

Fig. 14

This illustration has been limited to monadic predicates simply because the scheme becomes so complicated so quickly even in that case. A representation of the full propositional calculus would demand only the further complication that we include all n-valued Predicate letters paired with n-tuplets of our variables. These can be generated in separate grids first so as to form a single enumeration, then introduced into the main grid in the position of P1, P2, P3... (Figure 15).

Fig. 15

If we return for a moment to the simple form of propositional calculus with which we began, restricted to a single sentence letter, it should be clear that either of the enumerations offered above will generate progressively longer wffs. It is not true, of course, that the length of wffs within such an enumeration increases monotonically; formula 10 in our original enumeration is shorter than formula 9, for example. Along the diagonal of either schema, however, formulae do increase in size with each step.

Fig. 16