## Valuesolid For Sheffer Stroke

SIERPINSKI'S GASKET (above left) can be approximated using mathematical logic. Plugging four-digit binary numbers into the truth table for the Sheffer stroke yields a color diagram in which the green squares form a gasketlike shape (left). The figure can also be seen in the value solid for the Sheffer stroke (above).

 4 1 1 ,„y.ii„i. XII! * ° »"IX WEX EjVLE ___
 w
 X 35SO orb X X o ^xc o liixx 3XC o Oxk okÈ X X o X o
 X jÉO mAmWS, ix X !IXX "™o oHo ilXX "OO X O X xlxp 3XX axe O o X X o X o

It is also possible to change 0 to 1 and 1 to 0 by applying the operator NOT: that is, NOT P is true if P is false, and vice versa. There are 16 possible truth tables for

ALL POSSIBLE GAMES of tic-tac-toe can be depicted in a quasi-fractal diagram. The squares in the 3-by-3 grid are divided into smaller grids that show all the opening moves (right). Subsequent moves are illustrated in still smaller grids created by subdividing the unoccupied squares. A sample game can be viewed by repeatedly magnifying sections of the diagram ( far right).

possible moves for O. If we just put O's in each of those subsquares, though, we would have nowhere to put X's second move. Instead we repeat the trick already used for the opening move: We divide each of the eight unmarked subsquares into a 3-by-3 grid of sub-subsquares, getting eight small tic-tac-toe boards. We put an X in the top left corner of each, to represent X's opening move. Then we put one of O's eight possible moves into each of the small tic-tac-toe boards.

We can continue in this fashion, recording all the possible moves in subgrids of ever smaller size. At every stage, all the unoccupied squares are subdivided into 3-by-3 grids, and all moves previous to that stage are copied into the cells of those grids. The final figure has a quasi-fractal structure because the rules of the game are recursive: the possible moves at each stage are determined by the moves made before. The geometry of fractals is also recursive: similar shapes repeat on ever smaller scales. The tic-tac-toe figure is a quasi-frac-tal rather than a true fractal because the game ends after a finite number of moves.

Now we turn to logic. The simplest area of conventional mathematical logic, prop-ositional calculus, is concerned with statements whose "truth-value" is either 1, representing true, or 0, representing false. For example, the statement P = "pigs can fly" has a truth-value of 0, whereas Q = "Africa is a continent" has a truth-value of 1. Statements can be combined using various logical operators, such as AND and OR. If P and Q are as above, the statement P AND Q is "pigs can fly, and Africa is a continent." This statement is false, so the truth-value of P AND Q is 0. The results of applying AND to statements can be summed up in a truth table:

It is also possible to change 0 to 1 and 1 to 0 by applying the operator NOT: that is, NOT P is true if P is false, and vice versa. There are 16 possible truth tables for c o

two statements, representing all the possible ways to put 0's and 1's in the table's final column. We can denote them with successive four-digit binary numbers: 0000, 0001, 0010, 0011 and so on, up to 1111. (In decimal notation, these numbers are 0, 1, 2, 3, ... , 15.) This list leads to another quasi-fractal. To draw it, sketch a 16-by-16 array of squares and add a border above the top row that identifies each column with one of the binary numbers [see illustration on page 86]. Then add a similar border down the left side of the array to enumerate the rows. Choose 16 different colors to correspond to the 16 binary numbers and color the border squares accordingly. Next, choose a logical operator: for example, the Sheffer stroke, which is represented by the symbol I. In computer engineering, the Sheffer stroke is known as NAND, because P I Q = NOT (P AND Q). Its truth table is:

 P Q P I Q 0 0 1 (0 1 1 1 0 1 1 1 0

P I Q truth table and put the square's column number in the table's second column. Then perform the NAND operations and put the resulting truth-values in the table's final column. This yields another four-digit binary number. Find the color that corresponds to this number and use it to mark the square in the 16-by-16 array. For instance, consider the square in row 5, column 11. In binary notation, these numbers are 0101 and 1011. Plugging them into the truth table for P I Q yields:

 P Q P I Q 0 1 1 1 0 1 0 1 1 1 1 0

The number in the final column is 1110, or 14 in decimal notation. So the square in row 5, column 11 is given the color corresponding to 14.

The final product of this laborious process is shown in the illustration on page 86. Notice that the green squares, corresponding to the binary number 1111, form a shape very similar to Sierpinski's gasket! Instead of color-coding the picture, one can also graph the value of each square in a third dimension, as a height given by its decimal number divided by 16. For example, the height of the square in row 5, column 11 would be 14/16 = 0.875. These graphs are called value solids. In the value solid for the Sheffer stroke, a gasketlike shape can clearly be seen. The explanation is simple: any formal logical system that involves recursion—whether a game or a truth table—can provide a recipe for drawing quasi-fractals. E3

Now, for each of the squares in the 16-by-16 array, put the square's four-digit row number in the first column of the