In his article ''Learning Decision Lists,'' Rivest proves that (k-DNF
or k-CNF) is a proper subset of k-DL. The proof is based on the follow
ing incorrect claim: ... if a function f has a prime implicant of size
t, then f has no k-DNF representation if k < t. In this note, we show
a counterexample to the claim and then prove a stronger theorem, from
which Rivest's theorem follows as a corollary.