View source for Reduced normal form

{{TEX|done}}
''of a Boolean function''

A [[Disjunctive normal form|disjunctive normal form]] which is the disjunction of all the simple implicants of a given function. A [[Conjunction|conjunction]] $\mathfrak A$ is called an implicant of a [[Boolean function|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|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|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|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.