Home > Articles > Programming

This chapter is from the book

This chapter is from the book

2–22 A Boolean Decomposition Formula

In this section, we have a look at the minimum number of binary Boolean operations, or instructions, that suffice to implement any Boolean function of three, four, or five variables. By a “Boolean function” we mean a Boolean-valued function of Boolean arguments.

Our notation for Boolean algebra uses “+” for or, juxtaposition for and, 056_01.jpg for exclusive or, and either an overbar or a prefix ¬ for not. These operators can be applied to single-bit operands or “bitwise” to computer words. Our main result is the following theorem:

  • THEOREM. If f(x, y, z) is a Boolean function of three variables, then it can be decomposed into the form g(x, y) 056_01.jpg zh(x, y), where g and h are Boolean functions of two variables.6

Proof [Ditlow]. f(x, y, z) can be expressed as a sum of minterms, and then z-bar.jpg and z can be factored out of their terms, giving

051equ01.jpg

Because the operands to “+” cannot both be 1, the or can be replaced with exclusive or, giving

051equ02.jpg

where we have twice used the identity (a 056_01.jpg b) c = ac 056_01.jpg bc.

This is in the required form with g(x, y) = f0(x, y) and h (x, y) = f0(x, y) 056_01.jpg f1(x, y). f0(x, y), incidentally, is f(x, y, z) with z = 0, and f1(x, y) is f(x, y, z) with z = 1.

  • COROLLARY. If a computer’s instruction set includes an instruction for each of the 16 Boolean functions of two variables, then any Boolean function of three variables can be implemented with four (or fewer) instructions.

One instruction implements g(x, y), another implements h(x, y), and these are combined with and and exclusive or.

As an example, consider the Boolean function that is 1 if exactly two of x, y, and z are 1:

052equ01.jpg

Before proceeding, the interested reader might like to try to implement f with four instructions, without using the theorem.

From the proof of the theorem,

052equ02.jpg

which is four instructions.

Clearly, the theorem can be extended to functions of four or more variables. That is, any Boolean function f(x1, x2, …, xn) can be decomposed into the form g(x1, x2, …, xn–1) 056_01.jpg xnh (x1, x2, …, xn–1). Thus, a function of four variables can be decomposed as follows:

This shows that a computer that has an instruction for each of the 16 binary Boolean functions can implement any function of four variables with ten instructions. Similarly, any function of five variables can be implemented with 22 instructions.

However, it is possible to do much better. For functions of four or more variables there is probably no simple plug-in equation like the theorem gives, but exhaustive computer searches have been done. The results are that any Boolean function of four variables can be implemented with seven binary Boolean instructions, and any such function of five variables can be implemented with 12 such instructions [Knu4, 7.1.2].

In the case of five variables, only 1920 of the 225 = 4,294,967,296 functions require 12 instructions, and these 1920 functions are all essentially the same function. The variations are obtained by permuting the arguments, replacing some arguments with their complements, or complementing the value of the function.

  • + Share This
  • 🔖 Save To Your Account