On the Structure and the Number of Prime Implicants of 2-CNFs

Navid Talebanfard

Abstract

Let $m(n, k)$ be the maximum number of prime implicants that any $k$-CNF on $n$ variables can have. We show that $3^{n/3} \le m(n, 3) \le (1 + o(1)) 3^{n/3}$.