Reduced normal form

of a Boolean function

A disjunctive normal form which is the disjunction of all the simple implicants of a given function. A conjunction $\mathfrak A$ is called an implicant of a Boolean function $f$ if the relation $\mathfrak A\to f\equiv1$ holds. An implicant is called prime if after the deletion of any letter it ceases to be an implicant. The construction of a reduced normal form is the first step in the minimization of Boolean functions (cf. Boolean functions, minimization of), since a minimal disjunctive normal form is obtained from a reduced one by eliminating certain implicants. The number of conjunctions in a reduced normal form is a measure of the difficulty of carrying out this step. Estimates of this number (see Boolean functions, normal forms of) show that the reduced normal form is usually more complex than the original representation of the function. Passing to a reduced normal form from a perfect one (cf. Perfect normal form) only reduces the lengths of the conjunctions, while their number may increase significantly. Furthermore, "almost-all" Boolean functions in reduced normal form contain no conjunctions consisting of less than $n-\log_2n$ letters, and the vast majority of conjunctions consists of $n-\log_2\log_2n$ letters.