Theorem 1. The problem in the post is NP-complete. Proof. MIN DNF is the following special case of the problem in the post: Given a truth table $T$ and integer $k$, is there a DNF of size at most $k$ whose truth table is $T$? MIN DNF is known to be NP-complete (see [1] and works cited by it). Since the problem in the post generalizes MIN DNF, the problem ...