Beeler, M., Gosper, R.W., and Schroeppel, R. HAKMEM. MIT AI Memo 239, Feb. 29, 1972. Retyped and converted to html ('Web browser format) by Henry Baker, April, 1995.

BOOLEAN ALGEBRA

Previous Up Next

ITEM 17 (Schroeppel):

Problem: synthesize a given logic function or set of functions using the minimum number of two-input AND gates. NOT gates are assumed free. Feedback is not allowed. The given functions are allowed to have X (don't care) entries for some values of the variables. P XOR Q requires three AND gates. MAJORITY(P,Q,R) requires 4 AND gates. "PQRS is a prime number" seems to need seven gates. The hope is that the best Boolean networks for functions might lead to the best algorithms.

ITEM 18 (Speciner):

        Number of monotonic increasing Boolean
N       functions of N variables
-       --------------------------------------
0       2       (T, F)
1       3       (T, F, P)
2       6       (T, F, P, Q, P AND Q, P OR Q)
3       20
4       168 = 8 * 3 * 7
5       7581 = 3 * 7 * 19^2
6       7,828,354 = 2 * 359 * 10903  (Ouch!)
N from 0 to 4 suggest that a formula should exist, but 5 and 6 are discouraging. A difficult generalization: Given two partial orderings, find the number of maps from one to the other that are compatible with the ordering. A related puzzle: A partition of N is a finite string of non-increasing integers that add up to N. Thus 7 3 3 2 1 1 1 is a partition of 18. Sometimes an infinite string of zeros is extended to the right, filling a half-line. The number of partitions of N, P(N), is a fairly well understood function.

The generating function is

     infinity
      ======
      \              n           1
       >       P(n) X  = ------------------
      /                  infinity
      ======              /===\
      n = 0                ! !           k
                           ! !     (1 - X )
                           ! !
                          k = 1
A planar partition is like a partition, but the entries are in a two-dimensional array (the first quadrant) instead of a string. Entries must be non-increasing in both the x and y directions. A planar partition of 34 would be:
1
3 1
3 2 2 1
7 6 4 3 1
Zeros fill out the unused portion of the quadrant. The number of planar partitions of n, PL(n), is not a very well understood function.

The generating function is

    infinity
     ======
     \               n           1
      >       PL(n) X  = -------------------
     /                   infinity
     ======               /===\
     n = 0                 ! !           k k
                           ! !     (1 - X )
                           ! !
                          k = 1
No simple proof of the generating function is known. Similarly, one can define cubic partitions with entries in the first octant, but no one has been able to discover the generating function. Some counts for cubic partitions and a discussion appear in Knuth, Math. Comp. 1970 or so.

ITEM 19 (Schroeppel):

The 2-NOTs problem: Synthesize a black box which computes NOT-A, NOT-B, and NOT-C from A, B, and C, using an arbitrary number of ANDs and ORs, but only 2 NOTs.

Clue: (Stop! Perhaps you would like to work on this awhile.)

Lemma: Functions synthesizable with one NOT are those where the image of any upward path (through variable space) has at most one decrease (that is, from T to F).

ITEM 20 (Roger Banks):

A Venn diagram for N variables where the shape representing each variable is convex can be made by superimposing successive M-gons (M = 2, 4, 8, ...), every other side of which has been pushed out to the circumscribing circle. If you object to superimposed boundaries, you may shrink the nested M-gons a very slight amount which depends on N.

ITEM 21 (Schroeppel & Waltz):

PROBLEM: Cover the Execuport character raster completely with the minimum number of characters. The three characters I, H and # works. Using capital letters only, the five characters B, I, M, V and X is a minimal solution. Find a general method of solving such problems.

ITEM 22 (Gosper):

PROBLEM: Given several binary numbers, how can one find a mask with a minimal number of 1 bits, which when AND-ed with each of the original numbers preserves their distinctness from each other? What about permuting bit positions for minimum numerical spread, then taking the low several bits?

ITEM 23 (Schroeppel):

(A AND B) + (A OR B) = A + B = (A XOR B) + 2 (A AND B).

ITEM 24 (Minsky):

There exists a convex figure n congruent copies of which, for any n, form a Venn diagram of 2^n regions.

Previous Up Next