View source for Reduced normal form

''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]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080360/r0803601.png" /> is called an implicant of a [[Boolean function|Boolean function]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080360/r0803602.png" /> if the relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080360/r0803603.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080360/r0803604.png" /> letters, and the vast majority of conjunctions consists of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080360/r0803605.png" /> letters.