Boolean formulas

A Boolean function ofn variables can always be specified by an explicit table giving values for all2ⁿ possible inputs. (Any cellular automaton rule with ann-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 pages616 and618 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 asOr andAnd 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 applyingExpand to a polynomial. Conjunctive normal form (CNF)Or[…]∧ Or[…]∧ … is the rough analog of applyingFactor. 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 fromCollect. (Unbalanced depths in different parts of a formula lead to latencies in a circuit, reducing practical utility.)