On the structure and the number of prime implicants of 2-CNFs

摘要

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 <= m(n, 2) <= (1 + o(1))3 n/3. (C) 2015 Elsevier B.V. All rights reserved.