= Disjunctive normal form
{title2=$\bigvee_i\bigwedge_j\ell_{ij}$}
{wiki}
= DNF
{c}
{synonym}
A <Boolean formula> is in disjunctive normal form when it is a disjunction of conjunctions of <Boolean literals>. Width bounds the number of literals in each conjunction, not the number of conjunctions. A depth-$s$ <decision tree> gives such a formula of width at most $s$ by taking the disjunction of its accepting leaf conditions; rejecting leaves give the dual <conjunctive normal form>.
Back to article page
