O'Reilly logo

Art of Computer Programming, Volume 4A, The: Combinatorial Algorithms, Part 1 by Donald E. Knuth

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

7.1.2. Boolean Evaluation

Our next goal is to study the efficient evaluation of Boolean functions, much as we studied the evaluation of polynomials in Section 4.6.4. One natural way to investigate this topic is to consider chains of basic operations, analogous to the polynomial chains discussed in that section.

A Boolean chain, for functions of n variables (x1, . . ., xn), is a sequence (xn + 1, . . ., xn + r) with the property that each step combines two of the preceding steps:

Image

where 1 ≤ j(i) < i and 1 ≤ k(i) < i, and where i is one of the sixteen binary operators of Table 7.1.11. For example, when n = 3 the two chains

both evaluate the “mux” ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required