Boolean Functions

Boolean functions are very simple. If B = {FALSE, TRUE } then a Boolean function of n variables has domain Bn and range B; that is f: Bn → B. This limits the number of possible functions. For example, there are only 2 Boolean functions of 1 variable: f(x) = x and f(x) = ¬ x.

The case of two variables is only slightly more complex. Let’s adopt the usual convention that 0 is FALSE and 1 is TRUE. The two variables can each take on two values so there are four possible inputs: (x, y) = (0, 0), (0, 1), (1, 0), and (1, 1). A given function f: B2B can take on either of two values for each of the 4 inputs so there are 24 = 16 Boolean functions of two variables. It’s easy to list them. Let’s agree to represent a function by the sequence of four numbers f (0, 0), f (0, 1), f (1, 0), f (1, 1). Then the 16 functions of two variables are: 0000, 0001, 0010, …, 1111. If we think of the sequence of four numbers as a single binary number, we can name and completely describe a function just by its number. For example function 10 (1010) is ¬ y—it is TRUE exactly when y is FALSE. A slightly more complex example is function 1. It is x AND y. Similarly, function 13 is ¬ x OR y. Knuth shows in section 7.1.1 of AOCP v. 4A that every Boolean function can be written in terms of the operators AND, OR, and NOT.

All this serves as an introduction to a splendid post by Russ Cox. He wonders what the minimal number of AND and OR operations it takes to express the Boolean functions of n variables. Back in 2001 he calculated the answer for n = 4 using a method similar to the one shown below. That’s harder than you might think because there are 216 Boolean functions of 4 variables and since you build them up by combining pairs of functions with AND and OR there are 216 × 216 = 232 pairs of functions. It turns out that 15 is the minimum number for 4-variable functions.

Until recently, the answer wasn’t known for n = 5. The reason for that is that when n = 5, the number of pairs of functions is 264 and the total amount of work is on the order of 30 × 264—too much to do using the brute force method that works for n ≤ 4. Russ’s post is mostly about how he and Alex Healy were able to reduce the amount of work enough to calculate the n = 5 case. The answer is 28. The n = 6 case is too large for any sort of brute force method to work.

In order to help me understand his post, I recreated the brute force method he described for n ≤ 4. The Scheme code below calculates the number of AND/OR operations that each function takes as well as the implementation of the function in terms of AND and OR. To understand the code, notice that given two functions f and g you can calculate f AND g and f OR g simply by performing the operation on their numbers. For example, if f is function 4 and g is function 2 then f AND g = 0100 AND 0010 = 0000 = function 0, and f OR g = 0100 OR 0010 = 0110 = function 6.

The strategy is to set the number of operations for each function other than the single variable functions (x, y, ¬ x, ¬ y) to ∞ and the single variable functions to 0 (since they don’t require any AND/OR ops. Then the AND and OR operations are performed on each pair of functions and if opsf + opsg + 1 < opsf ⊗ g (where ⊗ is either AND or OR) then set opsf ⊗ g to opsf + opsg + 1. This is done repeatedly until there are no further changes.

This code calculates to n = 2 case but it is easily extended to n = 3 and, in principle, to n = 4 although the interpreted guile may run too slowly in that case.

(define x 3)
(define notx 12)
(define y 5)
(define noty 10)
(define infinity +inf.0)
(define d (make-vector 16 infinity))  ; number of and/or ops
(define defs (make-vector 16))        ; function definitions

;; Initialize single variable functions (x, y, not x, not y)
(define funcs (list x notx y noty))
(define predefined (list "x" "(NOT x)" "y" "(NOT y)"))
(for-each (lambda (f) (vector-set! d f 0)) funcs)
(for-each (lambda (f p) (vector-set! defs f p)) funcs predefined)

;; Closure to track whether any functions changed
(define changed (let ((c #t)) (lambda x (if (null? x) c (set! c (car x))))))

;; Calculate function definitions and number of and/or ops
(let ((newfuncs '()))                 ; newly created functions this round
  (while  (changed)
    (changed #f)
    (set! funcs (append funcs newfuncs))
    (set! newfuncs '())
    (let outer ((f-funcs funcs))
      (unless (null? f-funcs)
        (let inner ((f (car f-funcs)) (g-funcs funcs))
          (unless (null? g-funcs)
            (let* ((g (car g-funcs))
                   (forg (logior f g)) (fandg (logand f g))
                   (d-g (vector-ref d g)) (d-f (vector-ref d f))
                   (cd (+ d-f d-g 1)))
              (when (< cd (vector-ref d forg))
                (changed #t)
                (push forg newfuncs)
                (vector-set! d forg cd)
                (vector-set! defs forg (format #f "(~a OR ~a)"
                                               (vector-ref defs f)
                                               (vector-ref defs g))))
              (when (< cd (vector-ref d fandg))
                (changed #t)
                (push fandg newfuncs)
                (vector-set! d fandg cd)
                (vector-set! defs fandg (format #f "(~a AND ~a)"
                                                (vector-ref defs f)
                                                (vector-ref defs g))))
              (inner f (cdr g-funcs)))))
        (outer (cdr f-funcs))))))

Here’s the results of running the above.

n Function Definition Ops
0 0000 (x AND (NOT x)) 1
1 0001 (x AND y) 1
2 0010 (x AND (NOT y)) 1
3 0011 x 0
4 0100 ((NOT x) AND y) 1
5 0101 y 0
6 0110 (((NOT x) OR (NOT y)) AND (x OR y)) 3
7 0111 (x OR y) 1
8 1000 ((NOT x) AND (NOT y)) 1
9 1001 (((NOT x) AND (NOT y)) OR (x AND y)) 3
10 1010 (NOT y) 0
11 1011 (x OR (NOT y)) 1
12 1100 (NOT x) 0
13 1101 ((NOT x) OR y) 1
14 1110 ((NOT x) OR (NOT y)) 1
15 1111 (x OR (NOT x)) 1

All of that is the easy part. Read Russ’s post to see how they solved the n = 5 case. It’s a great read and, as usual with Russ, an example of first-rate engineering.

I started this post by saying that Boolean functions are simple. They may be simple in their basic structure but that doesn’t mean they’re trivial. Indeed, Knuth devotes over 200 pages to them in volume 4A of AOCP. There are lots of open, hard problems involving them. For example the satisfiability problem, which Knuth describes as the most famous unsolved problem in Computer Science, asks for an efficient method of deciding whether or not a Boolean function is identically zero. That seems easy enough but has resisted efforts for even some simple cases. Nevertheless, it’s a problem of tremendous practical importance.

Update: Fixed potential bug in code.

This entry was posted in Programming and tagged . Bookmark the permalink.