Boolean formulas
A Boolean function of n variables can always be specified by an explicit table giving values for all 2n possible inputs. (Any cellular automaton rule with an n-cell neighborhood corresponds to such a function; digit sequences in rule numbers correspond to explicit tables of values.) Like ordinary algebraic functions, Boolean functions can also be represented by a variety of kinds of formulas. Those on pages 616 and 618 use so-called disjunctive normal form (DNF) And[…] ∨ And[…] ∨ …, which is common in practice in programmable logic arrays (PLAs). (The addition and multiplication operators in the main text should be interpreted as Or and And respectively.) In general any given function will allow many DNF representations; minimal ones can be found as described below. Writing a Boolean function in DNF is the rough analog of applying Expand to a polynomial. Conjunctive normal form (CNF) Or[…] ∧ Or[…] ∧ … is the rough analog of applying Factor. DNF and CNF both involve Boolean formulas of depth 2. As in the note on multilevel formulas below, one can also in effect introduce intermediate variables to get recursive formulas of larger depth, somewhat analogous to results from Collect. (Unbalanced depths in different parts of a formula lead to latencies in a circuit, reducing practical utility.)
